python - 更好的模糊匹配性能？

Question

我目前正在使用方法 get_close_matches 来自difflib的方法来遍历 15,000 个字符串的列表，以获得与另一个大约 15,000 个字符串列表的最接近匹配：

a=['blah','pie','apple'...]
b=['jimbo','zomg','pie'...]

for value in a:
    difflib.get_close_matches(value,b,n=1,cutoff=.85)

每个值需要 0.58 秒，这意味着完成循环需要 8,714 秒或 145 分钟。是否有另一种可能更快的库/方法或提高此方法速度的方法？我已经尝试将两个数组都转换为小写，但这只会导致速度略有提高。

score 5 · Accepted Answer

fuzzyset通过它们的二元组和三元组索引字符串，因此它可以在O(log(N))与O(N)中找到近似匹配difflib。对于我的 1M+ 单词和单词对的模糊集，它可以在大约 20 秒内计算索引，并在不到 100 毫秒的时间内找到最接近的匹配。

score 3 · Accepted Answer

也许您可以为每个列表中出现的三元组（三个连续字母）建立一个索引。仅针对共享三元组中的a字符串检查字符串。b

您可能想查看 BLAST 生物信息学工具；它确实对序列数据库进行了近似序列比对。

score 3 · Accepted Answer

是用于模糊字符串匹配的超快速库。它具有与著名的fuzzywuzzy 相同的API，但速度更快，并且获得了MIT 许可。

score 1 · Accepted Answer

尝试这个

Levenshtein Python C 扩展模块包含用于快速计算 - Levenshtein（编辑）距离和编辑操作 - 字符串相似度 - 近似中值字符串，通常是字符串平均 - 字符串序列和集合相似度的函数它支持普通字符串和 Unicode 字符串。

score 0 · Accepted Answer

我尝试了几种模糊匹配的方法。最好的是余弦相似度，阈值根据您的需要（我保持 80% 模糊匹配）。

5 回答 5