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

Question

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

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

Answer 1

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

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

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

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

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

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

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

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

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