根据维基百科，Wagner-Fischer-algorithm 有一个可能的修改，它可以计算两个单词的 Levenshtein 距离是否低于某个阈值，如果你只想知道的话，这比原来的要快得多。
“通过检查对角线而不是行，并使用惰性求值，我们可以在 O(m (1 + d)) 时间内找到 Levenshtein 距离（其中 d 是 Levenshtein 距离），这比常规动态规划算法快得多如果距离很小。”
这个解决方案是如何工作的？我很难将其可视化，因为感觉任何矩阵单元格的值都取决于上方、左侧和对角线左侧的单元格的值，所以我不知道如何遍历仅使用对角线的矩阵。
第二次尝试解释：
假设我们正在寻找长度为 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 处的字符是否匹配。简而言之，这个想法是使用具有长度差异启发式 H(i, j) = |(m - i) - (n - j)| 的A* 。然后，我们不展开 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 * * *
尽管渐近运行时间是相同的。