Levenshtein距离与界限/界限

Question

bounty到期在4天内。该问题的答案有资格获得+ 50声望赏金。Penseur想要引起更多关注对此问题。

我发现了Python的一些Levenshtein distance实现。

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

因此，本质上，如果我只是想知道距离是否大于阈值，我不想让算法运行太久而无法计算最终距离。

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

1. Modifying Levenshtein Distance algorithm to not calculate all distances
2. Levenstein distance limit
3. Most efficient way to calculate Levenshtein distance
4. Levenshtein Distance Algorithm better than O(n*m)?

但是仍然，我看不到任何Python代码能完成我上面描述的内容（或多或少这些文章也描述了这些内容。

Answer 1

如Levenstein distance limit中所述，您可以在计算为较早返回的行上添加测试：

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]