Как реализовать «Возможно, вы имели в виду»?

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

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

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

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

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

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

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

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

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

Soundex - по моему опыту - хрень.

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

http://en.wikipedia.org/wiki/N-gram#Google_use_of_N-gram

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

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

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

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

• «Подобные сообщения», как функциональность с использованием MS SQL Server?

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

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

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

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

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

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

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

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

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

Для него есть рубиновый драгоценный камень, но я не знаю, как с ним разговаривать с питона http://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

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

Usage

Aspell lets you check words and suggest corrections. For example:

  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: сердце Возможная поправка на wil: Будем

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

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

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

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

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

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

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

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]

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

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