有界/极限的编辑距离

Question

我发现了Levenshtein distancePython的一些实现。

我想知道如何有效地修改这些算法，以便在编辑距离大于n（例如 3）时它们会中断，而不是运行到最后？

因此，如果我只是想知道距离是否大于阈值，那么本质上我不想让算法运行太长时间来计算最终距离。

我在这里找到了一些相关的帖子：

1. 修改 Levenshtein Distance 算法以不计算所有距离
2. 莱文斯坦距离限制
3. 计算编辑距离的最有效方法
4. Levenshtein 距离算法比 O(n*m) 更好？

但是，我仍然没有看到任何 Python 代码执行我上面描述的操作（这或多或少也是这些帖子所描述的）。

PS：下面@amirouche提供的解决方案基于我通过一些基准测试测试过的最快实现（来自此处： https : //en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python，https :// stackoverflow.com/a/32558749/9024698）及其有界版本是我的测试中最快的版本（不排除可能有更快的版本）。

Answer 1

如Levenstein 距离限制中所述，您可以在计算出的行上添加测试以提前返回：

def levenshtein(s1, s2, maximum):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        if all((x >= maximum for x in distances_)):
            return False
        distances = distances_
    return distances[-1]