Как выбрать алгоритм нечеткого сопоставления?

Question

Мне нужно знать критерии, которые делали нечеткий алгоритм отличным друг от друга между этими 3:

Алгоритм расстояния Левенштейна

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

Расстояние Дамерау – Левенштейна

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

Алгоритм Bitap с модификациями Wu и Manber

Алгоритм растрового изображения - это алгоритм приблизительного сопоставления строк. Алгоритм сообщает, содержит ли данный текст подстроку, которая «приблизительно равна» заданному шаблону, где приблизительное равенство определяется в терминах расстояния Левенштейна - если подстрока и шаблон находятся в пределах заданного расстояния k друг от друга, то алгоритм считает их равными.

Мой документ представляет собой таблицу с названиями компаний, некоторые компании дважды или трижды из-за опечаток. В данном конкретном случае, как группировать компании, сопоставляя их? Какой алгоритм выбрать и почему? В файле у меня 100к строк и он растет.

Answer 1

Если вы находитесь в Google Sheets, попробуйте использовать Flookup .Вы говорите, что в вашем списке более 100 тыс. Строк, что может оказаться сложной задачей в зависимости от (временных) пределов выполнения Google, но я все же призываю вас попробовать.Вас может заинтересовать одна функция:

FLOOKUP(lookupValue, tableArray, lookupCol, indexNum, [threshold], [rank])

Полное раскрытие: Я создал Flookup для листов Google

Answer 2

Если вы хотите сгруппировать компании, вы можете использовать локальное хеширование или метод кластеризации, такой как кластеризация K-medoids, например, с помощью Левенштейна в качестве метрики. Кроме того, вы можете использовать SymSpell .

Расстояние Левенштейна и Дамерау – Левенштейна - хорошие показатели для сходства строк, но убедитесь, что вы используете быструю реализацию. На Github слишком много популярных и безумно медленных реализаций. Лучшее, что я знаю, это PolyLeven или editdistance .