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

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

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

ниже следует Краткое описание алгоритма. Этот алгоритм состоит из двух этапов, подготовки и проверки слов.

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

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

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

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

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

для теории алгоритма" вы имели в виду " вы можете обратиться к главе 3 введения в информационный поиск. Он доступен онлайн бесплатно. 3.3 (стр. 52) точно отвечает на ваш вопрос. А чтобы конкретно ответить на ваше обновление вам нужен только словарь слов и ничего больше (включая миллионы пользователей).

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

4. возвращает слово, которое имеет минимальное расстояние.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

алгоритм

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

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

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

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

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

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

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

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

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

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