Ответ 1
Levenshtein подсчитывает количество исправлений (вставки, удаления или замены), необходимые для преобразования одной строки в другую. Damerau-Levenshtein - это модифицированная версия, которая также рассматривает транспозиции как отдельные изменения. Хотя вывод представляет собой целое число редактирований, это можно нормализовать, чтобы получить значение подобия по формуле
1 - (edit distance / length of the larger of the two strings)
Алгоритм Джаро является мерой общих символов, составляя не более половины длины более длинной строки на расстоянии, с учетом перестановок. Винклер модифицировал этот алгоритм, чтобы поддержать идею о том, что различия вблизи начала строки более значительны, чем различия в конце строки. Jaro и Jaro-Winkler подходят для сравнения меньших строк, таких как слова и имена.
Решение о том, что использовать, - это не просто вопрос производительности. Важно выбрать метод, который соответствует характеру строк, которые вы сравниваете. В общем, оба упомянутых алгоритма могут быть дорогими, потому что каждая строка должна быть сравнима с любой другой строкой и с миллионами строк в вашем наборе данных, это огромное количество сравнений. Это намного дороже, чем что-то вроде вычисления фонетического кодирования для каждой строки, а затем просто группировка строк, имеющих одинаковые кодировки.
Существует обширная подробная информация об этих алгоритмах и других алгоритмах нечеткого строкового соответствия в Интернете. Это даст вам начало:
Сравнение личного имени Соответствие: методы и практические Вопросы
Согласно этой статье, скорость четырех алгоритмов Яро и Левенштейна, о которых я упоминал, от самого быстрого до самого медленного:
- Яро
- Яро-Винклер
- Левенштейн
- Damerau-Левенштейна
причем самый медленный результат в 2 - 3 раза длиннее. Конечно, эти времена зависят от длин строк и реализаций, и есть способы оптимизировать эти алгоритмы, которые, возможно, не были использованы.