python - 在 python 中实现 Levenshtein 距离

Question

我已经实现了算法，但现在我想找到与其他字符串的编辑距离最短的字符串的编辑距离。

算法如下:

def lev(s1, s2):
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1)

Answer 1

您的“实现”有几个缺陷:

(1) 它应该以def lev(a, b):开头，而不是def lev(s1, s2):。请养成以下良好习惯:(a) 在提出问题之前运行您的代码 (b) 引用您实际运行的代码(通过复制/粘贴，而不是通过(容易出错的)重新键入)。

(2) 无终止条件；对于任何参数，它最终都会尝试评估 lev("", "") 如果不是 Python 实现限制，它将永远循环:RuntimeError: maximum recursion depth exceeded.

你需要插入两行:

if not a: return len(b)
if not b: return len(a)

让它发挥作用。

(3) Levenshtein 距离是定义递归的。没有“唯一”(唯一)算法这样的东西。递归代码很少出现在类之外，而且只能以“稻草人”的身份出现。

(4) 朴素的实现所花费的时间和内存与 len(a) * len(b) 成正比……这些字符串通常不是比 4 到 8 长一点吗？

(5) 你极其天真的实现更糟糕，因为它复制了输入的切片。

您可以在网络上找到工作 不是很天真的实现 ... google("levenshtein python") ...寻找那些使用 O(max(len( a), len(b))) 额外内存。

你问的是什么(“与其他字符串的编辑距离最短的字符串的编辑距离。”)没有意义......“THE string”？？？ “探戈需要两个人”:-)

您可能想要的(找到集合中具有最小距离的所有字符串对)，或者可能只是那个最小距离，是一个简单的编程练习。你试过什么？

顺便说一句，通过简单的算法找到这些对将需要执行 O(N ** 2) 次 lev()，其中 N 是集合中字符串的数量...如果这个是真实世界的应用程序，您应该使用经过验证的代码而不是尝试自己编写。如果这是家庭作业，你应该这么说。