更好的模糊匹配性能？

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毫秒內找到最接近的匹配。