algorithm - это - мета теги




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

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

Так,

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


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


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

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

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


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

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

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

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

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

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

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


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

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


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

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

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

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


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

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

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


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

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

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


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

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

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

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

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

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

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

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


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





text-search