Levenshtein距离与界限/界限

debugcn 发表于 Dev

流浪者

我发现Python了Levenshtein距离的一些实现。

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

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

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

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

PS：通过以下@amirouche提供的解决方案是基于最快的实现了我与一些基准测试（从这里进行测试：https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python，https：//开头stackoverflow.com/a/32558749/9024698）及其受限制的版本是我测试中同类产品中最快的一种（不排除可能有更快的测试）。

amirouche

如Levenstein距离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]

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。