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

Question

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

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

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

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

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

Answer 1

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

Поиск 101!

при мин 22: 03

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

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

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

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

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

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

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

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

Также это означает, что если в одночасье все начнут произносить ночь, так как "nigth" Google предложит это слово.

EDIT

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

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

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

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

Answer 8

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

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

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

Answer 9

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

Итак,

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

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

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

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

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

Answer 10

Как догадаться ... это может

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

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