Как Google "Вы имели в виду?" Алгоритм работы?

Question

Я занимаюсь разработкой внутреннего веб-сайта для инструмента управления портфелем. Там много текстовых данных, названий компаний и т. Д. Я был очень впечатлен способностью некоторых поисковых систем очень быстро отвечать на запросы с помощью «Вы имели в виду: xxxx».

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

[Я разрабатываю в ASP.NET (В.Б. - не держите его против меня!)]

UPDATE: Хорошо, как я могу имитировать это без миллионов «неоплачиваемых пользователей»?

• Сгенерировать опечатки для каждого «известного» или «правильного» термина и выполнить поиск?
• Какой-нибудь другой, более элегантный метод?

Answer 1

относительно вашего вопроса, как имитировать поведение, не имея тонны данных - почему бы не использовать тонны данных, собранных Google? Загрузите результаты поиска Google sarch для слова с ошибкой и выполните поиск по запросу "Вы имели в виду:" в HTML.

Полагаю, в наше время это называется mashup: -)

Answer 2

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

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

Answer 3

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

Answer 4

Вы хотите сказать, что проверка орфографии? Если это проверка орфографии, а не целая фраза, тогда у меня есть ссылка на проверку орфографии, где алгоритм разрабатывается в python. Проверьте эту ссылку

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

Answer 5

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

Apache Solr - это механизм полнотекстового поиска, который помимо многих других функций также обеспечивает проверку орфографии или предложения запросов. Из документации :

По умолчанию средства проверки правописания Lucene сначала сортируют счет из расчета расстояния строки и второй по частоте (если имеется) предложения в индексе.

Answer 6

Помимо приведенных выше ответов, если вы хотите быстро что-то реализовать самостоятельно, вот предложение -

Алгоритм

Вы можете найти реализацию и подробную документацию этого алгоритма на GitHub .

• Создать приоритетную очередь с компаратором.
• Создайте дерево поиска Ternay и вставьте все английские слова (из сообщения Norvig ) вместе с их частотами.
• Начать обход TST и для каждого слова, встречающегося в TST, вычислить его расстояние Левенштейна ( LD ) из input_word
• Если LD & le; 3 затем поместите его в очередь приоритетов.
• Наконец извлеките 10 слов из очереди приоритетов и отобразите.

Answer 7

Самый простой способ понять это - динамическое программирование Google.

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

Оптимальное решение использует динамическое программирование и рекурсию.

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

Answer 8

Существует определенная структура данных - троичное дерево поиска - которая, естественно, поддерживает частичные совпадения и совпадения ближайших соседей.