Как вы реализуете "вы имели в виду"? [дубликат]


Возможные Дубликаты:
как Google "вы имели в виду?- Алгоритм работает?

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

17 106
nlp

17 ответов:

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

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

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

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

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

доктор Норвиг Google изложил, как это работает; он даже дает реализацию Python 20ish line:

http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html

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

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

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

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

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

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

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

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

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

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

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

вы также можете получить доступ к собственному словарю google с помощью Гугл API для написания запроса на предложение.

вы можете посмотреть на Питера Норвига"Как написать корректор орфографии" статьи.

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

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

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

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

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

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

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

Soundex и "Porter stemming" (soundex тривиален, не уверен в том, что porter stemming).

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

для этого есть рубиновый камень, но я не знаю, как с ним разговаривать с 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-грамм описано в введение в информационный поиск (полный текст доступен онлайн).

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

использование модуля 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]

U get:

>>> 
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