В расширении для мониторинга букмекеров нужно было узнавать одних и тех же игроков в разных источниках.

У одного — Novak Djokovic, у другого — Djokovic Novak. Добавляем имена из трёх слов, дефисы, разную транслитерацию и перестановки участников в парных матчах. Задача на пять минут уверенно покинула чат.

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

Попробовал другую эвристику: игнорировать порядок и оценивать расхождение по составу символов.

Считал в первой строке вхождения символов, которых во второй вообще нет. Затем повторял в обратную сторону. Из двух чисел брал максимум для более строгой оценки или минимум для мягкой. По настраиваемым порогам решали, считать ли имена совпавшими.

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

Упрощение имело цену: анаграммы могли получить нулевое расхождение. Лишние повторы общих букв тоже игнорировались. А мягкая оценка могла дать ноль, если все символы короткой версии встречались в длинной.

Поэтому здесь важны и выбранный признак, и допустимые ошибки: похожий буквенный состав ещё не доказывает, что перед нами один человек.

Такие дела!