algorithm что - Как работает Google «Вы имели в виду?» Алгоритм работы?




мета теги (16)

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

Так,

  1. Вам нужен словарь (английский или на основе ваших данных)

  2. Создайте слово trellis и вычислите вероятности для переходов, используя ваш словарь.

  3. Добавьте декодер, чтобы рассчитать минимальное расстояние ошибки, используя ваши решетки. Конечно, вы должны позаботиться о вставках и удалениях при расчете расстояний. Забавно, что клавиатура QWERTY максимизирует расстояние, если вы нажимаете клавиши близко друг к другу (cae превратит автомобиль, cay превратит кошку)

  4. Верните слово с минимальным расстоянием.

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

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

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

[Я развиваюсь в ASP.NET (VB - не держите его против меня!)]

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

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

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

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

По умолчанию контрольные очки Lucene Spell сортируют предложения сначала по счету из расчета расстояния по строкам, а во-вторых, по частоте (если доступно) предложения в индексе.


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


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

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

Идея этого алгоритма основана на статистическом обучении машин.


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

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


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

Наверное, это называется mashup в наши дни :-)


Используйте расстояние Левенштейна , затем создайте метрическое дерево (или тонкое дерево) для индексации слов. Затем запустите запрос 1-ближайшего соседа, и вы получили результат.


Как догадка ... это могло бы

  1. поиск слов
  2. если он не найден, используйте некоторый алгоритм, чтобы попытаться «угадать» слово.

Может быть что-то от ИИ, например, от сети Хопфилда или обратно, или что-то еще «идентифицирует отпечатки пальцев», восстанавливает сломанные данные или исправления орфографии, как уже упоминал Давиде ...


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


Вот объяснение непосредственно из источника (почти)

Поиск 101!

при мин. 22:03

Стоит смотреть!

В основном и в соответствии с Дугласом Меррилом, бывшим техническим директором Google, он выглядит так:

1) Вы пишете слово с ошибкой в ​​Google

2) Вы не можете найти то, что хотите (не нажимайте на какие-либо результаты)

3) Вы понимаете, что вы ошибочно написали слово, чтобы переписать слово в окне поиска.

4) Вы находите то, что хотите (вы щелкаете по первым ссылкам)

Этот шаблон умножается миллионы раз, показывает, какие наиболее распространенные орфографические ошибки и какие наиболее «общие» исправления.

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

Кроме того, это означает, что если в одночасье все начинают писать ночь как «нигде», Google предложит это слово вместо этого.

РЕДАКТИРОВАТЬ

@ThomasRutter: Дуглас описывает это как «статистическое обучение машин».

Они знают, кто исправляет запрос, потому что они знают, какой запрос исходит от того, какой пользователь (используя файлы cookie)

Если пользователи выполняют запрос, и только 10% пользователей нажимают на результат, а 90% возвращаются и набирают другой запрос (с исправленным словом), и на этот раз 90% нажимают на результат, тогда они знают, что они нашли коррекция.

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

Кроме того, теперь они включают контекст в проверку орфографии, поэтому они могут даже предлагать разные слова в зависимости от контекста.

См. Эту демонстрацию google wave (@ 44m 06s), которая показывает, как контекст учитывается для автоматического исправления орфографии.

Here объясняется, как работает обработка естественного языка.

И, наконец, это потрясающая демонстрация того, что можно сделать, добавив автоматический перевод (@ 1h 12m 47s) в микс.

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


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

Алгоритм

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

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

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

  • Решите, как определить, требуется ли исправление орфографии. Они могут включать в себя недостаточные результаты, результаты, которые не являются конкретными или точными (в некоторой степени) и т. Д. Затем:

  • Используйте большой текст или словарь, где все или большинство из них, как известно, правильно написаны. Их легко найти в Интернете, в таких местах, как LingPipe . Затем, чтобы определить лучшее предложение, вы ищете слово, которое является самым близким, основанным на нескольких мерах. Наиболее интуитивно понятными являются похожие персонажи. То, что было продемонстрировано в результате исследований и экспериментов, состоит в том, что два или три символа соответствия последовательности работают лучше. (битрамы и триграммы). Для дальнейшего улучшения результатов взвешивайте более высокий балл в матче в начале или в конце слова. По соображениям производительности индексируйте все эти слова в виде триграмм или биграмм, так что, когда вы выполняете поиск, вы конвертируете в n-грамм и просматриваете через хэш-таблицу или trie.

  • Используйте эвристику, связанную с потенциальными ошибками клавиатуры на основе расположения символов. Так что «hwllo» должно быть «привет», потому что «w» близко к «e».

  • Используйте фонетический ключ (Soundex, Metaphone) для индексации слов и поиска возможных исправлений. На практике это обычно возвращает худшие результаты, чем использование индексации n-граммов, как описано выше.

  • В каждом случае вы должны выбрать лучшую коррекцию из списка. Это может быть метрика расстояния, такая как levenshtein, метрика клавиатуры и т. Д.

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


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

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


Я нашел эту статью некоторое время назад: как написать корректор правописания , написанный Питером Норвигом (директор по исследованиям в Google Inc.).

Это интересно прочитать о теме «исправления правописания». Примеры находятся в Python, но это понятно и просто для понимания, и я думаю, что алгоритм может быть легко переведен на другие языки.

Ниже следует краткое описание алгоритма. Алгоритм состоит из двух этапов: подготовка и проверка слов.

Шаг 1: Подготовка - настройка базы данных слов

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

Шаг 2. Проверка слов - поиск слов, которые аналогичны проверке

Аналогичное означает, что расстояние редактирования невелико (обычно 0-1 или 0-2). Расстояние редактирования - это минимальное количество вставок / удалений / изменений / свопов, необходимых для преобразования одного слова в другое.

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


Хм ... Я думал, что Google использовал свой обширный корпус данных (интернет), чтобы сделать серьезную НЛП (Natural Language Processing).

Например, у них так много данных из всего Интернета, что они могут подсчитывать количество раз, когда происходит последовательность из трех слов (называемая триграммой ). Поэтому, если они видят предложение типа: «pink frugr concert», они могут видеть, что у него мало хитов, а затем найдите наиболее вероятный «розовый концерт» в их корпусе.

Они, по-видимому, просто делают вариацию того, что говорил Давиде Гуалано, но так определенно прочитали эту ссылку. Разумеется, Google использует все веб-страницы, которые он знает как корпус, что делает его алгоритм особенно эффективным.


Д-р Norvig из Google рассказал, как это работает; он даже дает реализацию Python на 20-ми языках:

http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html

http://www.norvig.com/spell-correct.html

Д-р Norvig также обсуждает «вы имели в виду» в этом прекрасном разговоре . Д-р Norvig является руководителем исследования в Google - когда его спрашивают, как «вы имели в виду», он отвечает, его ответ является авторитарным .

Таким образом, проверка орфографии, по-видимому, с помощью динамического словаря построена из других поисковых запросов или даже фактических интернет-фраз и т. Д. Но это все еще проверка орфографии .

SOUNDEX и другие догадки не заглядывают, люди!





algorithm machine-learning nlp spell-checking text-search