更好的模糊匹配性能？

Question

我目前使用从difflib方法get_close_matches方法通过1​​5000个字符串列表进行迭代，以获得最匹配的对大约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秒将花费8,714秒或145分钟来完成循环。是否有另一种库/方法可能会更快或者提高此方法的速度？我已经尝试将两个阵列转换为小写字母，但它只会导致略微提高速度。

Answer 1

试试这个

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

的莱文斯坦的Python C扩展模块包含的快速计算功能 - 莱文斯坦（编辑）的距离，和编辑操作 - 字符串相似性 - 近似中值的字符串，一般字符串平均 - 字符串序列和集合相似性它支持普通字符串和Unicode字符串。

Answer 2

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

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

Answer 3

fuzzyset索引可以通过双字母组字符串和卦所以它找到近似匹配在O（日志（N）） VS O（N）为difflib。对于1M +单词和单词对的模糊集，它可以在约20秒内计算索引，并在不到100毫秒内找到最接近的匹配。