在Python中有这个字符串匹配方法的实现吗？

Question

我正在尝试找出我的数据存储中哪些条目是近似重复的，使用的是一种叫做近似字符串匹配的方法。

请问在Python中有没有现成的实现，还是说我需要自己动手写一个？

谢谢 :)

来自维基百科:

...

一种简单粗暴的方法是，计算文本T中所有子字符串与模式P之间的编辑距离，然后选择距离最小的那个子字符串。不过，这种算法的运行时间是O(n³ m)，也就是非常慢。

一个更好的解决方案[3][4]，利用动态规划，采用了问题的另一种表述：对于文本T中的每个位置j和模式P中的每个位置i，计算模式前i个字符Pi与文本T中以位置j结尾的任意子字符串Tj',j之间的最小编辑距离。

那么，如何高效地将这个方法应用到多个字符串上呢？

Answer 1

difflib 可能是解决这个问题的工具，比如说：

from difflib import context_diff

a = 'acaacbaaca'
b = 'accabcaacc'

print ''.join(context_diff(a,b))

Answer 2

difflib.get_close_matches 这个功能可以帮你完成这个任务。

Answer 3

是的。

google("python levenshtein")