Как вы реализуете фразу “Ты имел в виду”?[дубликат]

https://stackoverflow.com/questions/41424

09-06-2019
|

Вопрос

Возможный Дубликат:
Как работает алгоритм Google “Вы что имели в виду?” ?

Предположим, у вас уже есть поисковая система на вашем сайте.Как вы можете реализовать вопрос "Вы имели в виду:<spell_checked_word>" как это делает Google в некоторых поисковые запросы?

Решение

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

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

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

Soundex - по моему опыту - это дерьмо.

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

Другие советы

Доктор Норвиг из Google обрисовал в общих чертах, как это работает; он даже дает 20-строчную реализацию Python:

http://googlesystem.blogspot.com/ 2007/04 / упрощенный-версия-оф-Googles-spell.html

http://www.norvig.com/spell-correct.html

Доктор Норвиг также обсуждает «Вы имели в виду»? в этом прекрасном выступлении . Доктор Норвиг является руководителем исследования в Google - когда его спросили, как " вы имели в виду " реализован, его ответ авторитетный .

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

SOUNDEX и другие догадки не привлекают внимания, люди!

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

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

Как упоминалось в предыдущем посте, Google (и Microsoft, и Yahoo!) не используют какой-либо предопределенный словарь и не используют орды лингвистов, которые размышляют над возможными ошибочными написаниями запросов. Это было бы невозможно из-за масштаба проблемы, а также из-за того, что неясно, действительно ли люди могли бы правильно определить, когда и если запрос написан с ошибкой.

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

Этот простой алгоритм отлично подойдет для многих типов запросов. Если вы хотите перейти на следующий уровень, я предлагаю вам прочитать статью Microsoft Research на эту тему. Вы можете найти его здесь

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

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

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

Возможно, вы захотите ознакомиться с Питером Норвигом . & Quot; статья.

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

http://en.wikipedia.org/wiki/N-gram # Google_use_of_N-граммовая

Я думаю, это зависит от того, насколько велик ваш сайт.В нашей локальной интрасети, которой пользуются около 500 сотрудников, я просто просматриваю поисковые фразы, которые дали нулевые результаты, и ввожу эту поисковую фразу вместе с новой предложенной поисковой фразой в таблицу SQL.

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

Возможно, вы также захотите ознакомиться с моим ответом на аналогичный вопрос:

"Похожие сообщения" похожи на функциональность с использованием MS SQL Server?

Если у вас есть отраслевые переводы, вам, вероятно, понадобится тезаурус. Например, я работал в ювелирной промышленности, и в наших описаниях были такие аббревиатуры, как kt-karat, rd-round, cwt-carat weight ... Endeca (поисковая система на этой работе) имеет тезаурус, который будет переводиться с обычного опечатки, но это требует ручного вмешательства.

Я делаю это с Lucene Проверка орфографии .

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

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

Soundex и " Портер stemming " (soundex тривиален, не уверен насчет портера).

Есть нечто под названием aspell, что может помочь:http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

Для этого есть ruby gem, но я не знаю, как связаться с ним из python http://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

Вот цитата из реализации ruby

Использование

Aspell позволяет вам проверять слова и предлагать исправления.Например:
  string = "my haert wil go on"

  string.gsub(/[\w\']+/) do |word|
    if !speller.check(word)
      # word is wrong
      puts "Possible correction for #{word}:"
      puts speller.suggest(word).first
    end
  end

Это выводит:

Возможная коррекция для haert:сердце Возможная коррекция вил:Будет

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

Вы можете использовать ngram для сравнения: http://en.wikipedia.org/wiki/ N-грамм

Использование модуля Python Ngram: http://packages.python.org/ngram/index.html.

import ngram

G2 = ngram.NGram([  "iis7 configure ftp 7.5",
                    "ubunto configre 8.5",
                    "mac configure ftp"])

print "String", "\t", "Similarity"
for i in G2.search("iis7 configurftp 7.5", threshold=0.1):
    print i[1], "\t", i[0]

Вы получаете:

>>> 
String  Similarity
0.76    "iis7 configure ftp 7.5"    
0.24    "mac configure ftp"
0.19    "ubunto configre 8.5"

Почему бы не использовать Google, который вы имели в виду в своем коде? http://narenonit.blogspot.com /2012/08/trick-for-using-googles-did-you-mean.html

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow