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

Question

我目前正在使用 difflib 中的 get_close_matches 方法迭代包含 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 分钟。是否有其他可能更快的库/方法或提高此方法速度的方法？我已经尝试将两个数组转换为小写，但这只导致速度略有提高。

Answer 1

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