Подтвердить что ты не робот

Как мне приблизиться "Вы имели в виду?" без использования Google?

Я помню дубликаты этого вопроса:

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

Почему это интересно?

Ok. Попробуйте ввести qualfy" в Google, и он сообщает вам:

Возможно, вы имели в виду: qualify

Достаточно честный. Он использует статистическое машинное обучение для данных, собранных миллиардами пользователей для этого. Но теперь попробуйте ввести это: " Trytoreconnectyou" в Google, и он сообщает вам:

Возможно, вы имели в виду: Try To Reconnect You

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Второй случай должен быть немного более простым. Вы найдете все допустимые слова, которые начинаются с строки ( "T" неверно, "Tr" неверно, "Try" - это слово, "Tryt" - это не слово и т.д.), И для каждого действительного слова вы повторяете алгоритм для оставшейся строки. Это должно быть довольно быстро, если ваш словарь индексируется. Если вы найдете результат, в котором вы можете разложить длинную строку на множество допустимых слов без оставшихся символов, это то, что вы рекомендуете. Конечно, если вы Google, вы, вероятно, модифицируете алгоритм для поиска подстрок, которые достаточно близки к опечаткам для реальных слов, и у вас есть некоторая логика для обработки случаев, когда строка может быть прочитана несколькими способами с достаточным достаточным количеством проверки орфографии (возможно, используя количество результатов, чтобы разорвать связь).

Ответ 2

Из уст лошади: Как написать корректор правописания

Интересным здесь является то, как вам не нужно связывать журналы запросов, чтобы аппроксимировать алгоритм. Вы можете использовать корпус в основном правильного текста (например, кучу книг из Project Gutenberg).

Ответ 3

Я думаю, что это можно сделать, используя spellchecker вместе с N-grams.

Для Trytoreconnectyou мы сначала проверяем все 1-граммы (все словарные слова) и находим самое близкое совпадение, которое довольно ужасно. Поэтому мы пытаемся использовать 2 грамма (которые можно построить, удалив пробелы из фраз длиной 2), а затем 3 грамма и так далее. Когда мы попробуем 4-граммов, мы обнаружим, что есть фраза, которая находится на расстоянии 0 от нашего поискового запроса. Поскольку мы не можем сделать лучше, мы вернем этот ответ в качестве предложения.

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

Ответ 4

Впечатляющая махинация, как ее работа вы можете найти здесь http://alias-i.com/lingpipe-3.9.3/demos/tutorial/querySpellChecker/read-me.html.

В нескольких словах это компромисс между изменением запроса (на уровне персонажа или слова) до увеличения охвата в поисковых документах. Например, "aple" приводит к 2 миллионам документов, но "яблоко" приводит к 60 миллионам, а модификация - только один символ, поэтому очевидно, что вы имеете в виду яблоко.

Ответ 5

Наборы данных/инструменты, которые могут быть полезны:

Вы можете использовать WordNet как простой словарь терминов, и вы можете увеличить его с помощью частых терминов, извлеченных из корпуса.

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

Вместо этого я предлагаю вам использовать что-то вроде чувствительного к местоположению хэширования (LSH). Это обычно используется для обнаружения дубликатов документов, но оно будет работать так же хорошо, как и исправление орфографии. Вам понадобится список терминов и строк терминов, извлеченных из ваших данных, которые, по вашему мнению, люди могут искать, вам нужно будет выбрать длину отсечки для строк. Альтернативно, если у вас есть данные о том, что люди на самом деле ищут, вы можете использовать это. Для каждой строки терминов вы создаете вектор (вероятно, символьные биграммы или триграммы будут делать трюк) и сохраните его в LSH.

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

Примечание: ссылки удалены, поскольку я новый пользователь - извините.

Ответ 6

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

Изменить (2011-03-16):

Я вдруг вспомнил еще один похожий на Soundex алгоритм, с которым я столкнулся пару лет назад. В статье этой статьи доктора Добба Лоуренс Филипс обсуждает усовершенствования своего алгоритма Metaphone, получившего название "Двойной метафон".

Вы можете найти реализацию этого алгоритма Python здесь и более реализаций на том же сайте .

Опять же, эти алгоритмы не будут такими же, как то, что использует Google, но для слов на английском языке они должны получить вас очень близко. Вы также можете просмотреть страницу wikipedia для Фонетических алгоритмов для списка других подобных алгоритмов.