Сопоставление строк с использованием fuzzywuzzy - используется ли расстояние Левенштейна или алгоритм сопоставления с образцом Ратклиффа / Обершелпа?

Question

fuzzywuzzy - очень популярная библиотека для сопоставления строк.Что касается документации библиотеки, то упоминается, что она использует расстояние Левенштейна для вычисления различий между последовательностями.Но после тщательного осмотра 1006 * я обнаружил, что он на самом деле использует функцию SequenceMatcher из библиотеки difflib.И эта функция согласно документации использует алгоритм сопоставления с образцом Ratcliff / Obershelp.

Согласно определениям, Расстояние Левенштейна - это минимальное количество правок, необходимых для преобразования одной строки в другую, а Алгоритм сопоставления с образцом Ratcliff / Obershelp вычисляетудвоенное количество совпадающих символов, деленное на общее количество символов в двух строках. пост , связанный с близким знаком, сравнивающий оба.

И когда я запускаю пример, я получаю тот же результат для SequenceMatcher и функции отношений в нечетком тексте.

from difflib import SequenceMatcher
from fuzzywuzzy import fuzz
s = SequenceMatcher(None, "abcd", "bcde")
s.ratio()
# 0.75
fuzz.ratio("abcd", "bcde")
# 75

Если явычислить расстояние Левенштейна вручную между двумя строками, я полагаю, это будет всего 2. В таком случае, как получилось, что он использует расстояние Левенштейна, как пишут авторы в документации?

Answer 1

FuzzyWuzzy.ratio с использованием python-Левенштейна возвращает не балл Левенштейна, а соотношение Левенштейна, которое составляет (a + b - LevenshteinScore) / (a ​​+ b), где a и bявляются длинами двух сравниваемых строк.

Если у вас не установлен python-Levenshtein, то fuzzywuzzy вообще не использует Levenshtein.В связи с этим домашняя страница Fuzzywuzzy вводит в заблуждение, хотя и рекомендует установить python-Levenshtein.

python-Levenshtein имеет некоторые проблемы с установкой;Я использовал второй ответ на этот вопрос stackoverflow , чтобы решить его.

Если у вас не установлен Python-Levenshtein, вместо этого FuzzyWuzzy использует difflib , что тоже самоедля многих входных значений, но не для всех.Разработчики рекомендуют использовать python-Levenshtein.См. эту проблему в git от fuzzywuzzy, который включает в себя пример случая, когда результаты с пакетом отличаются по сравнению с пакетом без него.Это, вероятно, не должно происходить, или, по крайней мере, документация должна прояснить это, но разработчики FuzzyWuzzy кажутся довольными, по крайней мере, функциональностью.