Fuzzy String Matching

Question

У меня есть требование в моем приложении, чтобы нечеткое совпадение со строковым значением, введенным пользователем, против хранилища данных.

Я в основном пытаюсь найти возможные дубликаты в процессе добавления данных в систему.

Я посмотрел на Метафон, Двойной Метафон и Звук, и вывод, к которому я пришел, - это все хорошо и хорошо, когда речь идет о единственной строке ввода слова; однако я пытаюсь сопоставлять неопределенное количество слов (они на самом деле являются географическими именами).

Я действительно рассматривал разложение каждого слова из строки (исключая любые слова, которые я определяю как шумовые слова), а затем реализую некоторую логику, которая определяла бы, какие имена мест в моем хранилище данных лучше всего соответствуют (на основе ключей от алгоритм, который я выбираю); преимущество, которое я вижу в этом, было бы выборочно подтянуть или ослабить критерии соответствия в соответствии с приложением: однако это кажется мне немного грязным.

Так что мой вопрос (ы):

1: Могут ли я приближаюсь эта проблемой в правильном направлении, да я понимаю, что это будет довольно дорого; однако (не углубляясь в реализацию) эта информация будет поступать из базы данных memcache.

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

Answer 1

Возможно, вы захотите изучить Locality-sensitive Hash, например Nilsimsa Hash. Я использовал Nilsimsa для «хеш» крейгслистов в разных городах для поиска дубликатов (ПРИМЕЧАНИЕ: я не сотрудник CL, а только персональный проект, над которым я работал).

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