莱文斯坦距离限制

Question

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

也许有类似的算法可以完成。

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

Answer 1

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

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

知道了这一点，您可以忽略原始矩阵中的所有单元格 where |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) 矩阵并调整索引来节省空间。

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

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