Альтернатива расстоянию Левенштейна для префиксов/суффиксов

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

Например:

Бульвиль против Бошервилля

Это почти наверняка разные города. Однако, поскольку они оба заканчиваются на «ville» (и оба начинаются на «Bo»), они имеют довольно небольшое расстояние Левенштейна.

*Я ищу алгоритм расстояния между строками, который учитывает положение символа, чтобы свести к минимуму влияние префиксов и суффиксов, взвешивая буквы в середине слова выше, чем буквы в конце слова. *

Я, наверное, мог бы написать что-нибудь сам, но мне было бы трудно поверить, что никто еще не опубликовал подходящий алгоритм.


algorithm levenshtein-distance string-algorithm
person scottmrogowski    schedule 18.12.2013    source источник
comment
Я бы почти закрыл его как дубликат stackoverflow.com/questions/10425238/, но у него есть сложный ответ, чтобы начать работать....   -  person Wrikken    schedule 18.12.2013

Ответы (2)


arrow_upward
2
arrow_downward

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

Также имейте в виду, что в целом даже серьезные орфографические ошибки дают правильную первую букву. Тогда весьма вероятно, что Cowville и Bowville — разные города, даже если их L. расстояние равно всего 1.

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

person Jim Mischel    schedule 18.12.2013
comment
Очень хорошее замечание по поводу первой буквы. В итоге я удалил общие символы в конце слов до половины длины более короткого слова. Для городов, состоящих из нескольких слов (например, Лос-Анджелес и Лос-Гатос), я сначала удалил идентичные строки перед сравнением (поэтому я сравниваю Анджелес с Гатосом). - person scottmrogowski; 07.01.2014

arrow_upward
3
arrow_downward

Это похоже на выборку в программировании на естественном языке.

В этом поле основа слова находится перед выполнением дальнейшего анализа, например.

run => run
running => run
runs => run

(Конечно, такие вещи, как ran, не связаны с run. Для этого можно использовать лемматизатор. Но я отвлекся...). Несмотря на то, что стемминг далек от совершенства в НЛП, он работает на удивление хорошо.

В вашем случае может оказаться полезным остановить город, используя правила, специфичные для названий городов, прежде чем применять Левенштейн. Я не знаю о реализации стеммера для городов, но на первый взгляд правила кажутся довольно простыми.

Вы можете начать со списка префиксов и списка суффиксов (включая любые распространенные варианты/опечатки) и просто удалить такой префикс/суффикс перед проверкой расстояния Левенштейна.

Кстати, если у вас есть дополнительная информация об адресе (например, почтовый адрес или почтовый индекс), для многих стран существует программное обеспечение для нормализации адресов, которое найдет наилучшее совпадение на основе алгоритмов, специфичных для адреса.

person Eric J.    schedule 18.12.2013