Алгоритмы и Структуры данных, подходящие лучше всего для программы проверки правописания, словаря и тезауруса
Поскольку Class<?> более конкретно, чем всего Class.
, Например, foo(Class<List>) не может переопределить foo(Class<Collection>). Я забываю термин, но типы с дженериками будут всегда отличаться от тех, которые не имеют.
6 ответов
См. this для 21-строчного корректора орфографии Python 2.5 и небольшой справочной информации.
Для словаря я бы использовал ] std :: map (вызов Dictionary в платформе .Net) со словом в качестве ключа и настраиваемым объектом (со всей информацией о слове + определение) в качестве значения.
Я не вижу лучшей структуры данных, чем дерево для словаря и тезауруса. При необходимости оба могут быть объединены в одну структуру с одной ссылкой в узле, указывающей на значение слова (словарь), и одной ссылкой на синонимы (тезаурус). Он может даже предлагать некоторую форму автозаполнения (когда в узле только одна ссылка).
Корректор орфографии немного сложнее - так как нужно сопоставить ложный ввод с каким-то правильным вводом. Для начала можно использовать эту ссылку: http://en.wikipedia.org/wiki/Spell_checker . В конце концов, вы найду ссылки на статьи о различных алгоритмах. Согласно статье в Википедии, в этой статье описывается наиболее успешный алгоритм: «Алгоритм коррекции орфографии на основе Винноу» Эндрю Голдинга и Дэна Рота
Во всех трех случаях вы можете построить BK-дерево из вашего набора слов. BK-деревья позволяют найти все слова на заданном расстоянии редактирования от введенного слова. См. Сообщение в блоге m y о BK-Trees для объяснения того, как они работают.
Словарь и средство проверки орфографии более или менее идентичны - словарь просто должен содержать определения вместе со словами. Для тезауруса слова группируются в «синсеты» - наборы синонимов - со всеми элементами, вставленными в BK-дерево. Когда кто-то ищет в синсете одно слово, вы показываете все остальные как альтернативы. Слово может появляться в нескольких наборах синхросигналов, поэтому необходимо убедиться, что узлы BK-Tree могут обрабатывать несколько значений для данного ключа.
Для словаря действительно существует структура данных, превосходящая дерево. Попробуйте DAWG или CDAWG: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph . Чтобы усложнить ситуацию, в моей любимой статье о структуре, Ciura и Deorowicz «Как сжать лексикон», они называются «минимальными ADFA». Погуглите, и вы найдете множество конкурирующих алгоритмов для создания этих зверей. Удачи!