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

Question

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

* 1003 Е.Г. *

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

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

«Результатов нет. Вы имели в виду« ручки вилки »?»

Answer 1

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

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

Answer 2

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

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

Answer 3

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