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

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

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

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

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

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

Алгоритм Bitap с модификациями Ву и Манбера

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

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


python algorithm fuzzy-comparison
person T Tea Tie    schedule 16.05.2019    source источник
comment
Привет, что пробовали? Возможно, было бы лучше начать с самого сложного из алгоритмов и перейти на более раннюю версию, если он не работает так, как вам нравится. Может быть, у кого-то в сети был такой же вопрос, вы проверяли?   -  person    schedule 16.05.2019
comment
@reportgunner Я бы сделал иначе, начну с менее сложного и обновлю, если это не сработает. Кроме того, PHP предлагает методы levenshtein: php.net/manual/de/function. levenshtein.php   -  person Doğan Uçar    schedule 16.05.2019
comment
Спасибо, зачем использовать PHP? Я думал, что Python - лучший способ (для огромного количества данных, машинного обучения и других библиотек ....)   -  person T Tea Tie    schedule 16.05.2019
comment
На самом деле это не имеет значения. Автоматический поиск с нечетким расстоянием между строками всегда будет иметь не обнаружение и ложные срабатывания. Потому что человек будет знать, что «SNCF» и «Société nationale des chemins de fer», конечно, одна и та же компания, но алгоритму, основанному на расстоянии, будет трудно сказать то же самое. С другой стороны, «General Mechanics of London» и «General Mechanics of Londoderry», вероятно, будут разными компаниями (здесь только сфабрикованный пример).   -  person Serge Ballesta    schedule 16.05.2019
comment
@TTeaTie: поиск в Google для python levenshtein дает достаточно результатов, поэтому вы можете использовать Python, если знаете его лучше, чем PHP.   -  person Serge Ballesta    schedule 16.05.2019
comment
DL расширяет L заменой соседних букв. Bitap - это приблизительное L. Я предпочитаю приближение Q-граммовой фильтрации L, так как это просто и быстро.   -  person Dan D.    schedule 16.05.2019
comment
Серж, ладно, мерси. @DanD. так я могу использовать Bitap, чтобы мой алгоритм находил больше похожих компаний? Мне нужна 80% точность сопоставления.   -  person T Tea Tie    schedule 16.05.2019

Ответы (2)


arrow_upward
1
arrow_downward

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

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

Полное раскрытие информации: я создал Flookup для таблиц Google

person Community    schedule 30.05.2019

arrow_upward
0
arrow_downward

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

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

person James Smith    schedule 19.05.2019