编辑距离限制

Question

如果我有一些我不想超过的距离。示例 = 2。知道最小允许距离后，我是否可以在算法完全完成之前中断算法？

也许有类似的算法可以做到。

我有必要减少工作计划的时间。

Answer 1

如果你做 top-down 动态 programming/recursion + memoization，你可以将当前大小作为额外参数传递，如果超过 2，则提前 return。但我认为这将是效率低下，因为您将重新访问状态。

如果你做bottom-up dp，你将逐行填充（你只需要保留最后一行和当前行）。如果最后一行只有大于 2 的条目，则可以提前终止。

根据我的意见修改你的源码：

for (var i = 1; i <= source1Length; i++)
{
                for (var j = 1; j <= source2Length; j++)
                {
                    var cost = (source2[j - 1] == source1[i - 1]) ? 0 : 1;

                    matrix[i, j] = Math.Min(
                        Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1),
                        matrix[i - 1, j - 1] + cost);
                }
                // modify here:
                // check here if matrix[i,...] is completely > 2, if yes, break

}

Answer 2

是的，你可以，它确实降低了复杂性。

主要要注意的是levenstein_distance(a,b) >= |len(a) - len(b)|也就是距离不能小于字符串的长度差。至少您需要添加字符以使其长度相同。

了解这一点后，您可以忽略原始矩阵中 |i-j| > max_distance 的所有单元格。所以你可以从

修改你的循环

for (i in 0 -> len(a))
   for (j in 0 -> len(b))

至

for (i in 0-> len(a))
   for (j in max(0,i-max_distance) -> min(len(b), i+max_distance))

如果对您来说更容易，您可以保留原始矩阵，但您也可以通过 (len(a), 2*max_distance) 的矩阵并调整索引来保存 space .

一旦最后一行中的每个成本都> max_distance，您就可以停止算法。

这会给您带来 O(N*max_distance) 的复杂性。由于您的 max_distance 是 2，因此复杂度几乎是线性的。你也可以保释在开头是|len(a)-len(b)| > max_distance.

编辑距离限制

Levenstein distance limit

algorithm

levenshtein-distance