Как исправить ввод пользователя (Вы имели в виду гугл?)

В этом вам может помочь алгоритм Soundex.

http://en.wikipedia.org/wiki/Soundex

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

Bitap Algorithm предназначен для поиска приблизительного совпадения в тексте. Может быть, вы могли бы использовать это для расчета вероятных совпадений. (основано на расстоянии Левенштейна)

(Обновление: после прочтения Ben S answer (можно использовать существующее решение, возможно aspell))

Как говорили другие, Google выполняет автокоррекцию, наблюдая, как пользователи исправляют себя. Если я буду искать "someting" (sic), а затем сразу же "something", очень вероятно, что первый запрос был неверным. Возможная эвристика для обнаружения этого:

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

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

Обратите внимание, что вам, вероятно, понадобится много запросов, чтобы собрать достаточно данных, чтобы эти предложения были полезными.

Я бы подумал об использовании для этого уже существующего решения.

Aspell с настраиваемый словарь имен может хорошо подойти для этого. При создании файла словаря будет предварительно вычислена вся информация, необходимая для быстрого предоставления предложений.

Это старая проблема, DWIM (делайте то, что я имею в виду) , классно реализованный на Xerox Alto Уорреном Тейтельманом. Если ваша проблема связана с произношением, вот вам обзорная статья, которая может помочь:

Дж. Зобель и П. Дарт, "Сопоставление фонетических строк: уроки информационного обновления", Proc. 19-й ежегодный Интер. ACM SIGIR Conf. по исследованиям и разработкам в области информационного поиска (SIGIR'96), август 1996 г., стр. 166-172.

Мои друзья, которые занимаются поиском информации, сказали мне, что Soundex, описанный Кнутом, теперь считается очень устаревшим.

Просто используйте Solr или аналогичный поисковый сервер, и тогда вам не придется быть экспертом в предмет. Со списком вариантов правописания запустите поиск по каждому предложенному результату, и, если результатов больше, чем текущий поисковый запрос, добавьте это как результат «вы имели в виду». (Это предотвращает ложные предложения по написанию, которые на самом деле не возвращают более релевантных результатов.) Таким образом, вам не нужно собирать много данных, чтобы сделать первоначальное предложение «вы имели в виду», хотя в Solr есть механизмы, с помощью которых вы может вручную настроить результаты определенных запросов.

Как правило, вы не будете использовать СУБД для этого типа поиска, вместо этого в зависимости от предназначенных только для чтения, слегка устаревших баз данных, предназначенных для этой цели. (Solr добавляет дружественный программный интерфейс и конфигурацию к базовому движку и базе данных Lucene.) На веб-сайте компании, в которой я работаю, ночная служба выбирает измененные записи из СУБД и отправляет их как документы в Solr. С очень небольшими усилиями у нас есть система, в которой окно поиска может очень эффективно искать продукты, отзывы клиентов, страницы веб-сайтов и записи в блогах и предлагать варианты написания в результатах поиска, а также многогранный просмотр, такой как вы видите в NewEgg, Netflix, или Home Depot, с очень небольшой дополнительной нагрузкой на сервер (особенно на СУБД). (Я считаю, что и Zappo [новый сайт], и Netflix используют Solr внутри компании, но не цитируйте меня по этому поводу.)

В вашем сценарии вы должны заполнить индекс Solr списком имен и выбрать соответствующий алгоритм сопоставления в файле конфигурации.

Как и в одном из ответов на вопрос, на который вы ссылаетесь, отличное решение Питера Норвига подойдет для это вместе с кодом Python. Google, вероятно, запрашивает предложение несколькими способами, но у них есть много данных. Конечно, они могут моделировать поведение пользователя с помощью огромных журналов запросов, но они также могут просто использовать текстовые данные, чтобы найти наиболее вероятное правильное написание слова, посмотрев, какое исправление является более распространенным. Слово someting не встречается в словаре, и, хотя это обычная ошибка в написании, правильное написание встречается гораздо чаще. Когда вы находите похожие слова, вам нужно слово, которое является как наиболее близким к орфографии с ошибкой, так и наиболее вероятным в данном контексте.

Решение Norvig состоит в том, чтобы взять корпус из нескольких книг из Project Gutenberg и подсчитать встречающиеся слова. Из этих слов он создает словарь, в котором вы также можете оценить вероятность слова (COUNT(word) / COUNT(all words)). Если вы сохраните все это как прямой хэш, доступ будет быстрым, но хранение может стать проблемой, поэтому вы также можете использовать такие вещи, как пытается суффикс. Время доступа остается прежним (если вы реализуете его на основе хэша), но требования к хранилищу могут быть намного меньше.

Затем он вносит простые изменения в слово с ошибкой (удаляя, добавляя или заменяя букву), а затем ограничивает список возможностей, используя словарь из корпуса. Это основано на идее расстояния редактирования (например, расстояние Левенштейна) с простой эвристикой, согласно которой большинство орфографических ошибок происходит при расстоянии редактирования 2 или меньше. Вы можете расширять это по мере ваших потребностей и вычислительной мощности.

Как только у него есть возможные слова, он находит наиболее вероятное слово из корпуса, и это ваше предложение. Есть много вещей, которые вы можете добавить, чтобы улучшить модель. Например, вы также можете настроить вероятность, учитывая расстояние клавиатуры от букв в орфографической орфографии. Конечно, это предполагает, что пользователь использует клавиатуру QWERTY на английском языке. Например, транспонирование e и q более вероятно, чем транспонирование e и l.

Для людей, которые рекомендуют Soundex, он очень устарел. Метафон (проще) или Двойной метафон (сложный) намного лучше. Если это действительно данные об именах, они должны работать нормально, если имена имеют европейское происхождение или, по крайней мере, фонетические.

Что касается поиска, если вы хотите использовать свой собственный, а не использовать Aspell или какую-либо другую интеллектуальную структуру данных ... предварительный расчет возможных совпадений - O (n ^ 2) в наивном случае, но мы знаем, чтобы быть совпадающими, они должны перекрываться "фонемами", а может и двумя. Этот шаг предварительной индексации (который имеет низкую частоту ложных срабатываний) может значительно снизить сложность (в практическом случае, что-то вроде O (30 ^ 2 * k ^ 2), где k - ‹* n).

У вас есть две возможные проблемы, которые вам нужно решить (или не решать, если вы того пожелаете)

1. Пользователи ошибаются при вводе слова (алгоритм расстояния редактирования)
2. Пользователи, не знающие слова и угадывающие (алгоритм фонетического сопоставления)

Вас интересует и то, и другое, или одно или другое? На самом деле это две разные вещи; например Шон и Шон звучат одинаково, но имеют расстояние редактирования 3 - слишком большое, чтобы считаться опечаткой.

Вам следует предварительно проиндексировать количество слов, чтобы убедиться, что вы предлагаете только релевантные ответы (аналогично предложению ealdent). Например, если я ввел sith, я мог бы ожидать, что меня спросят, имел ли я в виду smith, однако, если бы я набрал smith, было бы бессмысленно предлагать sith. Определите алгоритм, который измеряет относительную вероятность слова и предлагает только те слова, которые более вероятны.

Мой опыт свободного сопоставления подкрепил простой, но важный урок - выполняйте столько слоев индексации / сита, сколько вам нужно, и не бойтесь включать более 2 или 3 слоев. Вычеркивайте все, что не начинается с правильной буквы, для например, затем отбраковывайте все, что не оканчивается на правильную букву, и так далее. Вы действительно хотите выполнить расчет расстояния редактирования только для минимально возможного набора данных, поскольку это очень интенсивная операция.

Итак, если у вас есть алгоритм O (n), O (nlogn) и O (n ^ 2) - выполните все три в указанном порядке, чтобы убедиться, что вы только помещаете свои `` хорошие перспективы '' в свой тяжелый алгоритм. .