bound/limit 的编辑距离

Question

我找到了 Levenshtein distance 的一些 Python 实现。

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

所以基本上我不想让算法运行计算最终距离太久，如果我只是想知道距离是否大于阈值。

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

Modifying Levenshtein Distance algorithm to not calculate all distances
Most efficient way to calculate Levenshtein distance
Levenshtein Distance Algorithm better than O(n*m)?

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

P.S.: 下面@amirouche 提供的解决方案是基于我用一些基准测试测试过的最快的实现（来自这里：https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python, ），它的有界版本是最快的在我的测试中属于此类（不排除可能有更快的测试）。

Answer 1

如中所述，您可以在计算到 return 的行上添加一个测试：

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]

bound/limit 的编辑距离

Levenshtein distance with bound/limit

python

break

levenshtein-distance