Как исправить ввод данных пользователем (Вид Google, “Вы имели в виду?”)

the Bitap Algorithm is designed to find an approximate match in a body of text. Maybe you could use that to calculate probable matches. (it's based on the Levenshtein Distance)

(Update: after having read Ben S answer (use an existing solution, possibly aspell) is the way to go)

---

As others said, Google does auto correction by watching users correct themselves. If I search for "someting" (sic) and then immediately for "something" it is very likely that the first query was incorrect. A possible heuristic to detect this would be:

• If a user has done two searches in a short time window, and
• the first query did not yield any results (or the user did not click on anything)
• the second query did yield useful results
• the two queries are similar (have a small Levenshtein distance)

then the second query is a possible refinement of the first query which you can store and present to other users.

Note that you probably need a lot of queries to gather enough data for these suggestions to be useful.

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

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

This is an old problem, DWIM (Do What I Mean), famously implemented on the Xerox Alto by Warren Teitelman. If your problem is based on pronunciation, here is a survey paper that might help:

J. Zobel and P. Dart, "Phonetic String Matching: Lessons from Information Retieval," Proc. 19th Annual Inter. ACM SIGIR Conf. on Research and Development in Information Retrieval (SIGIR'96), Aug. 1996, pp. 166-172.

I'm told by my friends who work in information retrieval that Soundex as described by Knuth is now considered very outdated.

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

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

В вашем сценарии вы должны заполнить индекс Solr списком имен,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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