更好的模糊匹配性能？

Question

我目前正在使用get_close_matches方法从difflib迭代15000个字符串的列表，以获得与另一个约15000个字符串列表最接近的匹配：

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

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

每个值需要0.58秒，这意味着完成循环需要8714秒或145分钟。是否有其他库/方法可能更快，或者可以提高此方法的速度？我已经尝试过将两个数组都转换为小写，但结果只是稍微提高了速度。在

Answer 1

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

您可能想看看BLAST生物信息学工具；它根据序列数据库进行近似的序列比对。在

Answer 2

试试这个

https://code.google.com/p/pylevenshtein/

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

Answer 3

^{}根据字符串的双元组和三元组索引字符串，以便在difflib的O（log（N））vsO（N）中找到近似匹配。对于我的fuzzyset，它可以在20秒内计算出索引，并在不到100毫秒的时间内找到最接近的匹配