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

Question

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

python 中是否有以下方法的实现，或者我需要尝试自己的实现？

谢谢:)

来自维基百科：

...

暴力方法是 计算所有到 P 的编辑距离 T 的子串，然后选择 距离最小的子串。 然而，该算法将具有 运行时间 O(n3 m)

更好的解决方案[3][4]，利用 动态规划，使用 的替代表述 问题：对于每个位置j 文本 T 和中的每个位置 i 模式 P，计算最小编辑 第 i 个之间的距离 模式的字符、Pi 和任何 T 的子串 Tj',j 结束于 位置j。

将其应用于许多字符串的最有效方法是什么？

Answer 1

是的。

google("python levenshtein")

Answer 2

difflib.get_close_matches 应该完成这项工作。

Answer 3

difflib 可能是答案，例如，

from difflib import context_diff

a = 'acaacbaaca'
b = 'accabcaacc'

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

Answer 4

编辑距离的表现与 fuzzywuzzy 标准ratio() 函数非常相似。 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