Разница между расстоянием между Яро-Винклером и Левенштейном?

У меня есть вариант использования, когда мне нужно выполнить нечеткое сопоставление миллионов записей из нескольких файлов. Для этого я выделил два алгоритма: расстояние Яро-Винклер и Левенштейн.

Когда я начал изучать оба, я не мог понять, что такое точная разница между ними. Кажется, что Левенштейн дает количество исправлений между двумя строками, а Jaro-Winkler дает совпадение между 0.0 и 1.0. Я не понял алгоритм. Поскольку мне нужно использовать любой алгоритм, мне нужно знать точные различия в производительности алгоритма.

Ответ 1

Levenshtein подсчитывает количество исправлений (вставки, удаления или замены), необходимые для преобразования одной строки в другую. Damerau-Levenshtein - это модифицированная версия, которая также рассматривает транспозиции как отдельные изменения. Хотя вывод представляет собой целое число редактирований, это можно нормализовать, чтобы получить значение подобия по формуле

1 - (edit distance / length of the larger of the two strings)

Алгоритм Джаро является мерой общих символов, составляя не более половины длины более длинной строки на расстоянии, с учетом перестановок. Винклер модифицировал этот алгоритм, чтобы поддержать идею о том, что различия вблизи начала строки более значительны, чем различия в конце строки. Jaro и Jaro-Winkler подходят для сравнения меньших строк, таких как слова и имена.

Решение о том, что использовать, - это не просто вопрос производительности. Важно выбрать метод, который соответствует характеру строк, которые вы сравниваете. В общем, оба упомянутых алгоритма могут быть дорогими, потому что каждая строка должна быть сравнима с любой другой строкой и с миллионами строк в вашем наборе данных, это огромное количество сравнений. Это намного дороже, чем что-то вроде вычисления фонетического кодирования для каждой строки, а затем просто группировка строк, имеющих одинаковые кодировки.

Существует обширная подробная информация об этих алгоритмах и других алгоритмах нечеткого строкового соответствия в Интернете. Это даст вам начало:

Сравнение личного имени Соответствие: методы и практические Вопросы

Согласно этой статье, скорость четырех алгоритмов Яро и Левенштейна, о которых я упоминал, от самого быстрого до самого медленного:

Яро
Яро-Винклер
Левенштейн
Damerau-Левенштейна

причем самый медленный результат в 2 - 3 раза длиннее. Конечно, эти времена зависят от длин строк и реализаций, и есть способы оптимизировать эти алгоритмы, которые, возможно, не были использованы.