幂次系数

幂次系数 是一种字符串上的统计量，用于判断一个字符串是否是另一个字符串的“缩写”。函数不是对称的，因此它不是一个度量。

• 设 T（文本）为非空字符串。
• 设 P（模式）为 T 的非空子序列。
• 设 p 为 P 的一个划分，且 p_i 为其元素，其中
  • 每个 p_i 都等于 T 的某个子字符串 t_i。
  • 子字符串 t_i 不重叠。
  • t_i 的顺序与 p_i 相同。

幂次系数是长度最短划分 p 的元素数量减一。或者，它是子字符串 t_i 之间的间隙数量。

使用术语

• 子字符串是由连续元素组成的子序列。子序列不一定是子字符串。例如，xz 是 xyz 的子序列，但它不是其子字符串。
• 序列的划分是多个两两不相交的子序列序列，当连接时等于整个原始序列。

直观解释

将模式中的所有字符取出来，同时保持原始顺序，与文本中的相同字符对齐，使字符组尽可能少。系数是这些组之间的间隙数量。

示例

更多示例请见 测试。

用例

权重系数在kn和nushell中用于确定哪些目录名与缩写的匹配度更高。许多其他字符串系数和指标都被认为不合适，包括莱文斯坦距离（Levenshtein distance）。莱文斯坦距离倾向于短字符串。例如，从gra到programming的莱文斯坦距离大于到gorgia的距离，尽管它并不“相似”于缩写。Powierża coefficient对于这些字符串对是0和2，因此会选择（正确地）programming。

Powierża算法

该算法受到了Wagner–Fischer算法的启发。它也与最长公共子序列问题的解决方案非常相似。所有这些算法都是基于矩阵的。在Wagner-Fischer算法（WF）中存在三种类型的移动（水平、对角线和垂直），而我的算法中只有两种——水平和对角线。主要思想是，不管多长，间隙的成本总是1（在WF中，间隙的成本是其长度）。

这意味着算法必须区分由水平移动和由对角线移动填充的单元格。第一种类型的单元格包含Gap(score)；第二种类型是Continuation(score)。如果原始单元格包含Gap(score)，则水平移动会产生Gap(score)；如果原始单元格包含Continuation(score)，则会产生Gap(score + 1)。算法倾向于产生较低分数的移动，如果对角线移动和水平移动产生相同的分数，则偏好对角线移动。