algorithm - 编辑距离限制

Question

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

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

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

Answer 1

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

主要要观察的是 levenstein_distance(a,b) >= |len(a) - len(b)| 即距离不能小于字符串的长度。您至少需要添加字符以使它们的长度相同。

了解这一点后，您可以忽略原始矩阵中的所有单元格，其中 |i-j| > 最大距离。所以你可以修改你的循环

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) 的矩阵并调整索引来节省空间。

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

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