Levenshtein矩阵仅使用斜条

Question

根据维基百科,可以对Wagner-Fischer算法进行修改,该算法可以计算出两个单词的Levenshtein距离是否低于某个阈值,如果你想知道的话,这比原来的快得多.

"通过检查对角线而不是行,并通过使用延迟评估,我们可以在O(m(1 + d))时间内找到Levenshtein距离(其中d是Levenshtein距离),这比常规动态编程算法快得多如果距离很小."

这个解决方案如何运作？我真的很难看到它,因为感觉任何矩阵单元格的值都取决于上面的单元格的值,左边和左边的对角线,所以我不知道如何遍历矩阵仅使用斜条.

Answer 1

第二次尝试解释：

假设我们正在寻找长度为 m 的单词和长度为 n 的单词之间的距离。设矩阵条目以[0, m] × [0, n]为索引，其中(i, j)条目表示length-m单词的length-i前缀与length-j前缀的编辑距离长度为 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|，因为这是达到该状态所需的非对角移动次数的下限。条带是坐标 (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，因为条带元素的左上邻居也在条带上。

对于不同长度的单词，我们实际上可以将参数应用于转置并限制为像

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

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