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

Question

Учитывая очень большую базу данных названий продуктов, как бы вы обнаружили возможные опечатки в поиске пользователей и предложили возможные исправления (вроде как, как их представляет Google)?

Например

Пользователь вводит "форк ханделы" и нажимает "поиск".

Они возвращаются

"Никаких результатов. Вы имели в виду" ручки вилки "?"

Answer 1

Есть несколько подходов к этой проблеме:

1. Ведение таблицы самых популярных орфографических ошибок в вашей базе данных. Если вам нужны некоторые орфографические ошибки: здесь)
2. Использование алгоритма, основанного на расстоянии редактирования: В теории информации и информатике расстояние редактирования между двумя строками символов - это количество операций, необходимых для преобразования одной из них в другую. Существует несколько различных алгоритмов для определения или вычисления этой метрики. Прочитайте статью Wikipedia для алгоритма Левенштейна, например.
3. Если вы используете Lucene для полнотекстового поиска, вот хорошая статья, в которой показано, как реализовать функцию "Вы имели в виду".
4. Если вы видите эту функцию как простую коррекцию орфографии, вот несколько хороших, очень коротких реализаций на нескольких языках: Как написать корректор орфографии

Answer 2

Вы можете использовать фонетический алгоритм, такой как Soundex, чтобы найти совпадения, которые звучат похоже.

В PostgreSQL есть модуль fuzzystrmatch, в документах которого приведены примеры использования Soundex, Levenshtein, Metaphone и Double Metaphone.

Answer 3

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