仅使用对角线条的 Levenshtein 矩阵

Question

根据 wikipedia 可以对 Wagner-Fischer 算法进行修改，该算法可以计算两个单词的 Levenshtein 距离是否低于某个阈值，如果是，则比原始算法快得多所有你想知道的。

"By examining diagonals instead of rows, and by using lazy evaluation, we can find the Levenshtein distance in O(m (1 + d)) time (where d is the Levenshtein distance), which is much faster than the regular dynamic programming algorithm if the distance is small."

这个解决方案是如何工作的？我真的很难想象它，因为感觉任何矩阵单元格的值都取决于上面、左边和对角线左边的单元格的值，所以我不确定如何遍历仅使用对角线条的矩阵。

Answer 1

第二次尝试解释：

假设我们正在查找 length-m 单词和 length-n 单词之间的距离。让矩阵条目由 [0, m] × [0, n] 索引，其中 (i, j) 条目表示 length-m 词的 length-i 前缀与 length-j length-n 词的前缀。

我们可以将动态规划看作是在有向图中寻找从(0, 0) 到(m, n) 的最短路径，该有向图中的顶点对应于矩阵项，向右的弧长为1，向下的弧长为1弧和长度为 0 或长度为 1 的对角线弧，具体取决于 i 和 j 处的字符是否匹配。简而言之，这个想法是使用 A* 和长度差异启发式 H(i, j) = |(m - i) - (n - j)|。然后，我们不扩展 A* 值大于 d 的节点。结果是只需要打开部分对角线：

   o t h e r w o r d
 t * * *
 h   * * *
 e     * * *
 w       * * *
 o         * * *
 r           * * *
 d             * * *

第一次尝试解释：

每个矩阵条目 (i, j) 的下限为 |i - j|，因为这是达到该状态所需的 non-diagonal 移动次数的下限。条带是坐标 (i, j) 满足 |i - j| 的每个元素≤ d，看起来像

   o t h e r w o r d
 t * * *
 h * * * *
 e * * * * *
 w   * * * * *
 o     * * * * *
 r       * * * * *
 d         * * * * *

对于 d = 2。当需要条带外空白元素的值时，只需使用 d。最后，任何 ≤ d 的条带条目都是有效的，因为空白元素只能贡献 d + 1，因为条带元素的左上邻居也在条带上。

对于不同长度的词，我们其实可以把参数应用到转置和限制到strip like

   o t h e r w o r d
 t * * *
 h   * * *
 e     * * *
 w       * * *
 o         * * *
 r           * * *
 d             * * *

虽然渐近运行时间是一样的

仅使用对角线条的 Levenshtein 矩阵

Levenshtein Matrix using only a diagonal strip

algorithm

matrix

string-metric

levenshtein-distance