Как работают проверки орфографии?

18

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

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

    
задан dicroce 06.12.2008 в 21:50
источник
  • Проделайте некоторую работу перед тем, как перебросить ее в Stack Overflow. Нарисуйте дизайн, определите ключевые блоки, препятствующие достижению прогресса, расскажите нам об этом контексте, который будет использован в некоторых усилиях. –  The Archetypal Paul 06.12.2008 в 21:54
  • Если вы ищете ответы, например, «прочитайте это: ссылка», скажите так. вы можете получить лучшие ответы. –  BCS 06.12.2008 в 21:57
  • Итак, Пол, этот вопрос не является хорошим вопросом «stackoverflow»? Как именно? Знаете, страница в Интернете называется «Как работают проверки орфографии?» с задумчивыми ответами было бы полезным для всех, кто только начал изучать, как это работает. –  dicroce 06.12.2008 в 22:08
  • Как говорится, я не думаю, что это хороший вопрос, нет. Я думаю, что для этого нужно было больше контекста, почему вам нужно было написать одно, и то, что вы разработали заранее. Это происходит, когда попросите Stackoverflow выполнить вашу работу за вас. Может быть, это только я. –  The Archetypal Paul 07.12.2008 в 10:46

7 ответов

25

Прочитайте Траверс дерева . Основная концепция такова:

  1. Прочитайте файл словаря в память (этот файл содержит весь список правильно записанных слов, которые являются возможными / общедоступными для данного языка). Вы можете скачать бесплатные словарные файлы онлайн. Один пример - java.sun.com
  2. Разберите этот файл словаря в дереве поиска, чтобы сделать фактический текстовый поиск максимально эффективным. Я не буду описывать все грязные детали этого типа древовидной структуры, но дерево будет состоять из узлов, которые имеют (до) 26 ссылок на дочерние узлы (по одному для каждой буквы), плюс флаг для указания или нет, текущий узел - это конец действительного слова.
  3. Прокрутите все слова в вашем документе и проверьте каждый из них в дереве поиска. Если вы достигнете узла в дереве, где следующая буква в слове не является допустимым дочерним элементом текущего узла, слово не находится в словаре. Кроме того, если вы дойдете до конца своего слова, а флаг «действительный конец слова» не установлен на этом узле, слово не находится в словаре.
  4. Если слово не найдено в словаре, сообщите об этом пользователю. На этом этапе вы также можете предлагать альтернативные варианты написания, но это немного сложнее. Вам придется прокручивать каждый символ в слове, заменяя альтернативные символы и проверять каждый из них на дереве поиска. Вероятно, есть более эффективные алгоритмы поиска рекомендуемых слов, но я не знаю, что они собой представляют.

Действительно короткий пример:

Словарь:

Назначение apex apple назначено

Дерево: ( * обозначает допустимый конец слова) update: Спасибо Curt Sampson за то, что эта структура данных называется Деревом Патриции

A -> P -> E -> X*
      \-> P -> L -> E*
           \-> O -> I -> N -> T* -> E -> D*

Документ

apple appint ape

Результаты:

  • «яблоко» будет найдено в дереве, поэтому оно считается правильным.
  • «appint» будет помечен как неверный. При перемещении дерева вы будете следовать A -> P -> P , но второй P не имеет дочернего узла I , поэтому поиск не выполняется.
  • «ape» также завершится неудачей, так как узел E в A -> P -> E не имеет установленного флага «действительный конец слова».

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

    
ответ дан e.James 06.12.2008 в 22:35
источник
  • Это было бы замечательно и быстро для проверки правильности написания, но мне действительно нужны предложения ... –  dicroce 06.12.2008 в 23:08
  • Я добавил ссылку на статью Википедии о расстоянии Левенштейна. Это лучший алгоритм измерения, который я мог бы найти для ранжирования слов в соответствии с тем, насколько они далеко от целевого слова (в этом случае неправильно написано слово) –  e.James 06.12.2008 в 23:30
  • Тип дерева, которое вы описываете, - дерево Патрисии или дерево оснований; Википедия дает хорошее описание на: en.wikipedia.org/wiki/Patricia_tree –  Curt J. Sampson 20.06.2009 в 05:16
  • @ Курт Сэмпсон: Спасибо. Я добавил эту ссылку к моему ответу. –  e.James 20.06.2009 в 06:55
  • тройное дерево описано в 2. Оно имеет довольно большой объем компромиссов. –  HeretoLearn 03.07.2009 в 20:29
Показать остальные комментарии
3

Учитывая, что вы не знаете, с чего начать, я бы предложил использовать существующее решение. См. Например, aspell . (Лицензия GLPL). Если вам действительно нужно реализовать его самостоятельно, пожалуйста, сообщите нам, почему.

    
ответ дан The Archetypal Paul 06.12.2008 в 21:58
источник
  • Мне любопытно. Я могу использовать существующий пакет, но сначала хочу понять эту проблему. После небольшого разворота я рассматриваю использование алгоритма расстояния levenstein относительно словаря, но я не уверен, что это будет достаточно быстро (скорость и размер кода важны). –  dicroce 06.12.2008 в 22:04
  • Еще одна проверка орфографии с открытым исходным кодом - hunspell, она используется OOo и Mozilla. –  quinmars 07.12.2008 в 14:29
1

Нужно смотреть на префиксы и суффиксы.

внезапно = внезапно + ly.

, удалив ly's, вы можете избавиться от хранения только корневого слова.

Аналогично preallocate = pre + allocate.

И любовно = любовь + ing + ly становится немного сложнее, так как вызывается английские правила для ing .

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

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

Я бы посоветовал прототипирование небольшим набором слов. Проведите много испытаний, затем увеличьте масштаб. Это замечательная образовательная проблема.

    
ответ дан EvilTeach 07.12.2008 в 03:22
источник
  • Я не могу согласиться с этим. Алгоритмически вытекающие английские слова, как известно, неточно. Возможно, стоило времени и времени спасать в темные века, но не больше. –  Daniel Cassidy 07.12.2008 в 03:36
  • «Английский не берет с других языков, он следует за ними в темные переулки, сбивает их с ног и проходит через их карманы для свободной грамматики». –  Ben Blank 09.09.2009 в 20:23
0

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

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

Если вы говорите, что написано: Страна как Contry. Схожесть строки levenshtein будет 1, так как вам нужно добавить только 1 письмо, чтобы преобразовать игру в страну.

Затем вы могли бы перебирать все возможные правильные формулировки слов (только 171 000 английских слов и 3000 из них составляют 95% текста). Определите те с наименьшим значением сходства строки levenshtein, а затем верните верхние X-слова, которые наиболее похожи на слово с ошибкой.

Существует большой пакет python под названием Fuzzy Wuzzy , который эффективно реализует это и генерирует% сходства между двумя словами или предложениями на основе эта формула.

    
ответ дан TheSaint321 25.04.2018 в 00:04
источник
0

Разделение слова на корень и суффикс является knonw как «Портерский алгоритм вытеснения», это хороший способ подгонки английского языка в удивительно маленькую память.
Это также полезно для поиска, поэтому «проверка орфографии» также найдет «проверку орфографии» и «проверку орфографии»

    
ответ дан Martin Beckett 07.12.2008 в 03:51
источник
0

Я сделал это в классе

Вы должны рассмотреть python NLTK Natural Language Toolkit NLTK , который специально разработан для этого.

Он также позволяет создавать текстовые интерпретаторы, такие как chatbots

    
ответ дан Eric 20.06.2009 в 07:01
источник
0

Проверка орфографии Open Office Hunspell может быть хорошей отправной точкой. Вот домашняя страница: Hunspell в Sourceforge

    
ответ дан Thomas Maierhofer 09.09.2009 в 20:14
источник