python中有没有这种字符串匹配方法的实现？

Question

我正在尝试计算出我的数据存储中的哪些条目是使用近似字符串匹配的近似重复项。

在python中是否有下列方法的实现，或者我需要尝试和自己滚动？

谢谢:)

from wikipedia：

...

蛮力的方法是 计算对于P的编辑距离对于T的所有 子，然后选择具有最小距离的 子串。 然而，该算法将具有 运行时间为O（N 3米）

更好的解决方案[3] [4]，利用 动态规划，使用 问题的 替代制剂：在每个位置j所述 文本T和在 图案P中的每个位置i，计算，在 位置j结束图案，Pi和任何 子TJ”，T的j的第i第一 字符之间的最小编辑 距离。

将这种方法应用于多个字符串的最有效方法是什么？

Answer 1

difflib可能是答案，例如，

from difflib import context_diff 

a = 'acaacbaaca' 
b = 'accabcaacc' 

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

Answer 2

是。

google("python levenshtein") 

Answer 3

difflib.get_close_matches应该做的工作。

Answer 4

Levenshtein距离执行与fuzzywuzzy标准比率（）函数非常类似。 fuzzywuzzy使用difflib http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

例如从fuzzywuzzy文档： https://github.com/seatgeek/fuzzywuzzy

fuzz.ratio("this is a test", "this is a test!") 
    96