Лучшее нечеткое сопоставление производительности?

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) 

Он принимает .58 секунды на значение, которое означает, что его займет 8,714 секунды или 145 минут, чтобы закончить цикл. Есть ли другая библиотека/метод, который может быть быстрее или способ улучшить скорость для этого метода? Я уже пробовал преобразовывать оба массива в нижний регистр, но это только приводило к небольшому увеличению скорости.

Answer 1

Попробуйте

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

Модуль расширения Левенштейн Python C содержит функции для быстрого вычисления - Левенштейн (редактирования) расстояния и операций редактирования - схожести строк - приближенными срединных строк, и вообще строка усреднения - string sequence и set Similarity. Он поддерживает как обычные, так и Unicode-строки.

Answer 2

Возможно, вы можете создать индекс триграмм (три последовательных буквы), которые появляются в каждом списке. Проверяйте строки только в a против строк в b, которые разделяют триграмму.

Возможно, вам стоит взглянуть на инструмент биоинформатики BLAST; он приближает выравнивание последовательностей к базе данных последовательности.

Answer 3

fuzzyset индексов строки по их биграмм и триграммы так, он находит приблизительные матчи в O (журнал (N)) против O (N) для difflib. Для моего fuzzyset 1M + слов и пар слов он может вычислить индекс примерно через 20 секунд и найти ближайшее совпадение менее чем за 100 мс.