algorithm - 仅使用对角线条的 Levenshtein 矩阵

Question

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

“通过检查对角线而不是行，并使用惰性求值，我们可以在 O(m (1 + d)) 时间内找到编辑距离(其中 d 是编辑距离)，这比常规方法快得多距离较小的动态规划算法。"

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

Answer 1

第二次尝试解释:

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

我们可以将动态规划视为在有向图中寻找从 (0, 0) 到 (m, n) 的最短路径，该有向图中的顶点对应于矩阵条目，具有长度为 1 的向右弧和长度为 1 的向下弧，并且length-0 或 length-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|，因为这是达到该状态所需的非对角线移动次数的下限。 strip 是坐标 (i, j) 满足 |i - j| 的每个元素≤ d，看起来像

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

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

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

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

尽管渐近运行时间是相同的。