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

436

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

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

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

ОБНОВЛЕНИЕ: хорошо, как я могу подражать этому без миллионов 'неоплачиваемых пользователей'?

  • Создать опечатки для каждого «известного» или «правильного» термина и выполнить поиск?
  • Какой-то другой, более элегантный метод?
Эндрю Гарри
источник
1
Вот VB.NET-версия Norvig Spelling Corrector. Вы можете найти это полезным, если еще не слишком поздно!
Ральф Виггам
7
Возможный дубликат Как вы реализуете «Вы имели в виду»?
Курт Макки,
Я набираю на клавиатуре не QWERTY (Colemak), и эта функция не так умна. Он наверняка учится на записанных парах исправления ошибок и поэтому настроен на qwerty. Обычные средства проверки орфографии работают нормально для моей клавиатуры, как и ожидалось - расстояние редактирования строки не зависит от компоновки.
полковник Паник

Ответы:

366

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

Поиск 101!

в мин 22:03

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здесь объясняется, как работает обработка на естественном языке.

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

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

OscarRyz
источник
Как работает алгоритм? Как Google переходит от «Мы получаем миллиарды поисковых запросов с различными терминами, и это те поиски» к «этот термин, следовательно, должен быть обычной ошибочной формулировкой этого термина»? Они решили эту проблему, но мне интересно, как это сделать. Как они выясняют, что два запроса выполняются одним и тем же пользователем, и какое слово является «исправлением» другого, и как они объединяют это в миллиарды запросов?
Томасруттер
51
Если все начали писать "ночь" с орфографическими ошибками ... Я думаю, они уже сталкивались с этим, когда люди искали "Flickr".
Макс Либберт
42
проблема со всеми ошибочными написаниями уже произошла в гораздо более серьезном смысле: попробуйте ввести «fuscia» в Google. Google говорит: "Вы имели в виду фуксию?" Правильное написание, на самом деле, «фуксия», но никто не может правильно его написать по какой-то причине. Проблема еще хуже на Dictionary.com; если вы введете «fuschia» в их поиске, вы получите «Нет результатов для fuschia. Вы имели в виду« fuschia »?» (то есть, вы имели в виду то, что только что набрали?)
Дейзи София Холлман
8
Я не верю, что они используют только данные об орфографических ошибках - определенно существует некоторое расстояние Левенштейна или что-то подобное - ищите «Plack» (и одно или несколько других слов), и это всегда исправляется на «черный», что является очень маловероятным ошибочным написанием / опечатка
plusplus
4
@ Якуб Я думаю, что они исправили проблему, так как я сделал этот комментарий 4+ года назад. Действительно, Google также исправил проблему. Поиск для фуксии автоматически включает результаты для фуксии.
Дейзи София Холлман
104

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

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

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

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

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

Шаг 2. Проверка слова - поиск слов, похожих на проверенный

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

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

Давиде Гуалано
источник
6
@Davide: "" "примеры написаны на python, но они понятны и просты для понимания" "": я не понимаю, как вы используете "но" ... я бы сказал, учитывая стиль письма Python + Norvig, "ясно и просто понять "это ожидаемый результат.
Джон Мачин
20
«Но» было там, потому что Гарри сказал в своем вопросе, что он разработчик VB.NET, поэтому я предположил, что он не уверен в языке Python.
Давиде Гуалано
56

Теорию алгоритма «вы имели в виду» вы можете найти в главе 3 «Введение в поиск информации». Он доступен онлайн бесплатно. Раздел 3.3 (стр. 52) точно отвечает на ваш вопрос. И чтобы конкретно ответить на ваше обновление, вам нужен только словарь слов и ничего больше (включая миллионы пользователей).

Сере Дери
источник
10

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

Например, они имеют так много данных из всего Интернета, что могут подсчитать, сколько раз встречается последовательность из трех слов (известная как триграмма ). Так что, если они увидят фразу вроде: «розовый фруктовый концерт», они смогут увидеть, что в ней мало хитов, а затем найти наиболее вероятный «розовый * концерт» в их корпусе.

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

Клаудиу
источник
7

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

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

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

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

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

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

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

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

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

eulerfx
источник
6

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

Николя Дориер
источник
4

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

Так,

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

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

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

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

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

Geee
источник
4

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

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

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

Азиз Альто
источник
3

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

seanb
источник
3

Как предположение ... это может

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

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

Павел Капустин
источник
2

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

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

schonarth
источник
1
Никто не сомневался, что у Google есть все необходимые данные, чтобы сделать это, но вопрос был в том, чтобы узнать подробности о том, как Google разработал алгоритм, позволяющий сделать это с таким большим количеством данных в разумные сроки. У них было бы несколько миллиардов запросов в день - как они могут легко определить, является ли поисковый термин «исправлением орфографии» другого, недавнего? Какие факторы заставляют Google решить, что один термин является ошибочным написанием другого? Это детали реализации, которые могут представлять интерес.
Томасруттер
2

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

Я думаю, что в наше время это называется mashup :-)

Томас Петричек
источник
как долго, пока Google не остановит ваш бот от соскабливания? - или не будет Google даже заметить в эти дни?
Эндрю Гарри
Я не думаю, что они заметят, если количество запросов в секунду не слишком велико.
Маурисио Шеффер
2

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

Алгоритм

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

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

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

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

Джимит Патель
источник
1

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

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

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

Жозеп Вальс
источник
0

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


источник
-1

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

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

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

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

ewakened
источник