Нечеткое автозаполнение

Question

В моем приложении у меня есть таблица пользователей, с first_name а также last_name, У меня сейчас третий столбец full_name (автоматически генерируется), например: first_name + last_name + first_name (без специальных символов).

"Etienne", "De Crécy", "Etienne De Crecy Etienne"

В настоящее время у меня есть простой алгоритм для автозаполнения пользовательского ввода (специальные символы удалены):

SELECT * FROM users WHERE full_name LIKE "%input%"

Этот запрос возвращает Этьена со входами Crécy Etienne, Etienne De, Cré, Cre, Etienne

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

• Etiene (похоже на имя)
• Etienne Crecy (аналог полного имени, без указания части)
• Crecy Etienne (аналогично ФИО, без указания направления, другое направление)
• De Cressi (звучит как фамилия)
• Cressi (звучит как фамилия, без частичек)

Я делаю много поисков, самая актуальная идея заключается в использовании SOUNDEX метод (или Metaphone процедуры), или levenstein процедуры. Я не могу использовать это как это, потому что:

• Soundex основан на первой букве, затем SOUNDEX(Cressy) это не то же самое, что SOUNDEX(De cressy)даже если они очень похожи.
• Метафон базируется на позиции букв (начало с 'kn' похоже на запрос с 'n', но только в первой позиции)
• levenstein не заботится о длине строки: De Cressy не похож на Cressy.

Есть ли у вас какие-либо идеи по поводу "смешивания" этих методов, или у вас есть какие-то другие идеи для меня?

Answer 1

Я настоятельно рекомендую попробовать Solr или Elasticsearch для того, что вы просите (наряду с большей гибкостью и лучшей производительностью).

Однако, если вы хотите реплицировать базовый фонетический поисковый движок внутри MySQL, вам потребуется возможность извлекать несколько токенов (слов или кодировок слов) в full_name при вставке (и за запрос при автозаполнении).

1). Во-первых, убедитесь, что ваш full_name тип столбца FULLTEXT, Затем переключитесь на MATCH...AGAINST синтаксис запроса вместо LIKE %foo%,

Это даст вам точное соответствие внутреннего токена, например, "cressy" для "de cressy".

Ваша идея использовать расстояние Левенштейна в качестве критерия упорядоченности неплохая, но пробежать ее дорого, поэтому убедитесь, что вы LIMIT ред твой MATCH...AGAINST запрос и ORDER BY MATCH... DESC если вы собираетесь вывести levenshtein(query, full_name) как часть выбора.

Цель состоит в том, чтобы избежать запуска Левенштейна во всех рядах

2). Если вы все еще заинтересованы в расширении ваших результатов, чтобы включить звукоподобные:

Создайте таблицу phonetic_token со столбцом внешнего ключа обратно к таблице первичных имен (это отношение "один ко многим" между именами и токенами).

Добавить столбцы soundex, а также metaphone к этому столу.

При вставке записей в первичную таблицу имен, дополнительно анализируйте их в пробелах и вставляйте кодировки soundex и metaphone каждого имени-слова в phonetic_token,

Возможно, вы захотите добавить некоторую логику синтаксического анализа, чтобы гарантировать, что все имя, утроенное и утроенное фамилия, будут записаны (например, перед фонетическим кодированием, убедитесь, что "de cressy" токены на "de", "cressy" и "decressy", чтобы соответствовать ожидаемому вводу.)

Теперь, когда вы запрашиваете отображение похожих звуковых дополнений, вы фактически присоединитесь к своей основной таблице имен с phonetic_token ГДЕ soundex IN (список кодов soundex из токенов запроса) ИЛИ метафон IN (список кодов метафонов из токенов запроса).

Я бы предложил запустить это фонетическое совпадение в качестве второго запроса в тех случаях, когда MATCH(full_name)...AGAINST(query_text) дает слишком мало результатов.

---

Опять же, Solr или Elasticsearch сделают все эти текстовые споры за вас с помощью конфигурации, обеспечивая при этом более высокую производительность. В зависимости от области применения вашего приложения извлечение сопоставления текста из MySQL может сэкономить вам много времени и хлопот.