Парсер StringToken, который дает стиль поиска Google "Вы имели в виду:" Предложения

Question

В поисках метода:

Возьмите разделенные пробелами токены в строке; вернуть предложенное слово

есть:
Поиск Google может занять "фонетический wrd nterpreterr" ,
и поверх страницы результатов он показывает «Вы имели в виду: фонетический интерпретатор слов»

Было бы предпочтительным решение на любом из языков C * или Java.

Существуют ли какие-либо открытые библиотеки, которые выполняют такую ​​функцию?

Или есть способ использовать Google API для запроса предложенного слова?

Answer 1

В своей статье Как написать корректор орфографии Питер Норвиг рассказывает, как можно реализовать Google-подобную проверку орфографии. Статья содержит 20-строчную реализацию в Python, а также ссылки на несколько повторных реализаций в C, C ++, C # и Java. Вот выдержка:

Полная информация о промышленно-силовой корректор как Google будет более запутанным чем поучительно, но я понял, что на самолете домой, менее чем за страницу кода, я мог бы написать игрушку корректор орфографии, который достигает 80 или Точность 90% при скорости обработки не менее 10 слов в секунду.

Используя код Норвига и этот текст в качестве обучающего набора, я получаю следующие результаты:

>>> import spellch
>>> [spellch.correct(w) for w in 'fonetic wrd nterpreterr'.split()]
['phonetic', 'word', 'interpreters']

Answer 2

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

Вот пример из вики, где 2 - это расстояние.

String[] l=spellChecker.suggestSimilar("sevanty", 2);
//l[0] = "seventy"

• http://wiki.apache.org/lucene-java/SpellChecker
• Старая ссылка http://today.java.net/pub/a/today/2005/08/09/didyoumean.html

Answer 3

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

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

Для простого начального решения, хотя словарная пара с сопоставлениями на основе Левенштейна работает на удивление хорошо.

Answer 4

Сначала:

• Java
• C ++
• C #

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

startup()
{
   set the spelling engines word suggestion limit to 1
}

option 1()
{
   int currentPosition = engine.NextWord(start the search at word 0, querystring);

   if(currentPosition == -1)
      return empty string; // Query is a-ok.

   while(currentPosition != -1)
   {
       queryString = engine.ReplaceWord(engine.CurrentWord, queryString, the suggestion with index 0);
       currentPosition = engine.NextWord(currentPosition, querystring);
   }

   return queryString;
}

Answer 5

Вы также можете использовать Google API для проверки правописания. Здесь есть реализация ASP здесь (хотя я и не считаю это обязательным).

Answer 6

Вы можете использовать веб-сервис Yahoo здесь: http://developer.yahoo.com/search/web/V1/spellingSuggestion.html

Однако это всего лишь веб-сервис ... (т. Е. Нет API для другого языка и т. Д.), Но он выводит JSON или XML, так что ... довольно легко адаптироваться к любому языку ...

Answer 7

API поиска Google SOAP делают это.

Answer 8

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

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
}

Идея в том, что сначала вы звоните с нулевым бюджетом и смотрите, распечатывает ли он что-нибудь. Затем попробуйте бюджет 1 и т. Д., Пока не будут распечатаны некоторые совпадения. Чем больше бюджет, тем больше времени. Возможно, вы захотите увеличить бюджет только до 2.

Добавлено: не так уж сложно расширить это для обработки общих префиксов и суффиксов. Например, английские префиксы, такие как «un», «anti» и «dis», могут быть в словаре, а затем могут ссылаться на верхнюю часть словаря. Для суффиксов, таких как «ism», «s» и «ed», может быть отдельный три, содержащий только суффиксы, и большинство слов могут ссылаться на этот суффикс. Тогда он может обрабатывать странные слова, такие как «антинационализация».