3

我正在尝试使用近似字符串匹配来确定我的数据存储中的哪些条目几乎是重复的。

在python中是否有以下方法的实现,或者我需要尝试自己动手?

谢谢 :)

来自维基百科

...

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

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

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

4

4 回答 4

1

difflib.get_close_matches应该做的工作。

于 2011-03-04T10:35:55.543 回答
1

是的。

google("python levenshtein")
于 2011-03-04T10:27:52.630 回答
0

difflib可能是答案,例如,

from difflib import context_diff

a = 'acaacbaaca'
b = 'accabcaacc'

print ''.join(context_diff(a,b))
于 2011-03-04T10:23:18.233 回答
0

Levenshtein distance 的表现与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
于 2013-08-02T23:12:53.490 回答