在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)你非常幼稚的实现更糟糕,因为它复制了输入的切片.

你可以在网上找到工作不太天真的实现...谷歌("levenshtein python")...寻找使用O(max(len(a), len(b)))额外内存的实现.

你问的是什么("与其他字符串编辑距离最短的字符串的编辑距离.")没有意义......"字符串"??? "一个巴掌拍不响" :-)

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

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