Fuzzy autocomplete

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

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

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

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

• Саундэкс основан на первой букве, то SOUNDEX(Cressy) не то же самое, как SOUNDEX(De cressy), даже если они очень похожи.
• Метафон является базовым положением букв (начинающий «kn» походит на «n», но только в первом положении)
• levenstein не заботится о длине строки: De 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 если вы собираетесь выводить Левенштейна (query, full_name) как часть выбора.

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

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

Создать phonetic_token таблицы с внешним ключом столбцом назад к вашей основной таблице имени (это имя отношения один-ко-многим -в-маркеры).

Добавить столбцы soundex и metaphone в эту таблицу.

При вставке записей в таблицу первичных имен дополнительно анализируйте их по пробелам и вставляйте метафонические звуковые сигналы soundex & каждого имени в phonetic_token.

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

Теперь при запросе soundalike именин доработок для отображения, на самом деле вы собираетесь присоединиться вашей основной таблица имен с phonetic_token WHERE Саундэкс IN (списка SOUNDEX кодов из лексем запросов) ИЛИ метафон IN (список кодов метафонов из токенов запроса).

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

---

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