python中有这种字符串匹配方法的实现吗？
我正在尝试使用近似字符串匹配来找出数据存储中的哪些条目接近重复。
python 中是否有以下方法的实现，或者我需要尝试自己的实现？
谢谢:)
...
暴力方法是 计算所有到 P 的编辑距离 T 的子串，然后选择 距离最小的子串。 然而，该算法将具有 运行时间 O(n3 m)
更好的解决方案[3][4]，利用 动态规划，使用 的替代表述 问题：对于每个位置j 文本 T 和中的每个位置 i 模式 P，计算最小编辑 第 i 个之间的距离 模式的字符、Pi 和任何 T 的子串 Tj',j 结束于 位置j。
将其应用于许多字符串的最有效方法是什么？
I am trying to work out which entries in my data store are near-duplicates using approximate string matching.
Is there any implementation of the following approach in python, or do i need to try and roll my own?
Thanks :)
...
A brute-force approach would be to
compute the edit distance to P for all
substrings of T, and then choose the
substring with the minimum distance.
However, this algorithm would have the
running time O(n3 m)A better solution[3][4], utilizing
dynamic programming, uses an
alternative formulation of the
problem: for each position j in the
text T and each position i in the
pattern P, compute the minimum edit
distance between the i first
characters of the pattern, Pi, and any
substring Tj',j of T that ends at
position j.
What is the most efficient way to apply this to many strings?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
是的。
Yes.
difflib.get_close_matches 应该完成这项工作。
difflib.get_close_matches should do the work.
difflib可能是答案，例如，difflibmight be the answer, eg,编辑距离的表现与 fuzzywuzzy 标准ratio() 函数非常相似。 fuzzywuzzy 使用 difflib http://seatgeek.com/blog/dev/ fuzzywuzzy-fuzzy-string-matching-in-python
fuzzywuzzy 文档中的示例：
https://github.com/seatgeek/fuzzywuzzy
Levenshtein distance performs very similarly to the fuzzywuzzy standard ratio() function. fuzzywuzzy uses difflib http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python
example from the fuzzywuzzy documentation:
https://github.com/seatgeek/fuzzywuzzy