Я пытаюсь понять, как библиотека fuzzywuzzy вычисляет расстояние Левенштейна между двумя строками, поскольку в документах четко упоминается, что она использует это.
Алгоритм расчета расстояния Левенштейна ищет минимальное количество правок между двумя строками. Этого можно добиться с помощью добавления, удаления и замены символа в строке. Все эти операции учитываются как одна операция при подсчете баллов.
Вот несколько примеров:
Пример 1 s1 = 'привет' s2 = 'ад'
Оценка Левенштейна = 1 (требуется 1 правка, добавление «о»)
Пример 2 s1 = 'привет' s2 = 'привет'
Оценка Левенштейна = 1 (требуется 1 правка, замена «а» на «о»)
Подставляя эти оценки в формулу Fuzzywuzzy (len(s1)+len(s2) - LevenshteinScore)/((len(s1)+len(s2)):
Пример 1: (5+4-1)/9 = 89%
Пример 2: (5+5-1)/10 = 90%
Теперь fuzzywuzzy возвращает ту же оценку для примера 1, но не для примера 2. Оценка для примера 2 составляет 80%. Изучив, как он вычисляет расстояния под капотом, я обнаружил, что он считает операцию «подстановки» за 2 операции, а не за 1 (как определено для Левенштейна). Я понимаю, что он использует библиотеку difflib, но я просто хочу знать, почему он называется расстоянием Левенштейна, хотя на самом деле это не так?
Я просто пытаюсь понять, почему здесь есть различие? Что это значит или объясняет? В основном причина использования 2 операций для замены, а не одной, как определено в расстоянии Левенштейна, и по-прежнему называемого расстоянием Левенштейна. Это как-то связано с пробелами в предложениях? Является ли это стандартным способом преобразования LD в нормализованную оценку сходства?
Я был бы рад, если бы кто-нибудь мог дать мне некоторое представление. Также есть ли лучший способ преобразовать LD в показатель сходства? Или вообще измерить сходство между двумя строками? Я пытаюсь измерить сходство между некоторыми транскрипциями аудиофайлов, сделанными службой транскрипции человека, и системой автоматического распознавания речи.
Благодарю вас!