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

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

Когда я начал изучать оба, я не мог понять, в чем точная разница между ними. Кажется, Левенштейн дает количество правок между двумя строками, а Яро-Винклер дает нормализованную оценку от 0,0 до 1,0. Я не понял алгоритм.

Поскольку мне нужно использовать любой алгоритм, мне нужно знать, каковы фундаментальные различия между этими двумя алгоритмами.

Во-вторых, хотелось бы узнать о разнице в производительности этих двух алгоритмов.

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

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

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

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

В Интернете есть множество подробной информации об этих алгоритмах и других алгоритмах сопоставления нечетких строк. Это даст вам начало:

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

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

• Jaro
• Яро-Винклер
• Левенштейн
• Дамерау-Левенштейн

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