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

В настоящее время я использую метод get_close_matches из difflib для перебора списка из 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 секунды, что означает, что для завершения цикла потребуется 8714 секунд или 145 минут. Есть ли другая библиотека/метод, который может быть быстрее, или способ повысить скорость этого метода? Я уже пытался преобразовать оба массива в нижний регистр, но это привело лишь к небольшому увеличению скорости.


python performance fuzzy-comparison levenshtein-distance difflib
person ChrisArmstrong    schedule 28.01.2014    source источник
comment
Вы можете попробовать удалить элемент из списка b после совпадения   -  person user1209304    schedule 28.01.2014

Ответы (5)


arrow_upward
5
arrow_downward

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

person hobs    schedule 11.07.2016
comment
привет @hobs спасибо, что указали на это! fuzzyset — отличный пакет, но документация очень скудная. Откуда вы знаете, что производительность находится в `0 (log (N))? Можете ли вы указать мне на некоторые документы, связанные с алгоритмом? - person ℕʘʘḆḽḘ; 27.07.2016
comment
@ℕʘʘḆḽḘ страница документов на pypi теперь довольно крутая. Они даже показывают, как разрывают строку, чтобы создать обратный индекс триграммы. Поиск по правильно реализованному обратному индексу никогда не бывает медленнее, чем O(log(N)), но в данном случае N — это количество триграмм, а не строк. - person hobs; 16.01.2019

arrow_upward
3
arrow_downward

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

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

person tmyklebu    schedule 28.01.2014

arrow_upward
1
arrow_downward

Попробуй это

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

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

person Igglyboo    schedule 28.01.2014

arrow_upward
1
arrow_downward

RapidFuzz

это сверхбыстрая библиотека для нечеткого сопоставления строк. Он имеет тот же API, что и знаменитый fuzzywuzzy, но в несколько раз быстрее и имеет лицензию MIT.

person Alexey Trofimov    schedule 03.04.2021

arrow_upward
0
arrow_downward

Я пробовал несколько методов для нечеткого соответствия. лучшим было косинусное сходство с порогом в соответствии с вашими потребностями (я сохранил нечеткое совпадение на 80%).

person Shalini Baranwal    schedule 24.04.2019