Алгоритмы и структуры данных лучше всего подходят для проверки орфографии, словаря и тезауруса

Question

Лучший способ реализовать

• словарь (есть ли DS лучше, чем Trie для словаря)
• тезаурус (понятия не имею, как сопоставляются значения слов, сходные значения)
• проверка орфографии (что-то лучше, чем хэш-карта), если возможно, с правильными рекомендациями по написанию.

Когда нас спросят в одном часовом интервью, должны ли мы написать код на языке c / c ++ для алгоритма?

Answer 1

См. это для 21-строчного корректора орфографии Python 2.5 и немного фона.

Answer 2

Для словаря действительно существует структура данных, превосходящая три. Попробуйте DAWG или CDAWG: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph. Просто, чтобы усложнить ситуацию, моя любимая статья о структуре, Ciura и Deorowicz, «Как сжать лексикон», называет их «минимальными ADFA». Google вокруг, и вы найдете много конкурирующих алгоритмов для создания этих зверей. Удачи!

Answer 3

Во всех трех случаях вы можете построить BK-дерево из вашего набора слов. BK-Trees позволяют найти все слова на заданном расстоянии редактирования от введенного слова. См. M y сообщение в блоге на BK-Trees для объяснения того, как они работают.

Словарь и средство проверки правописания более или менее идентичны - словарь просто должен содержать определения вместе со словами. Для тезауруса слова объединяются в «наборы синонимов» - наборы синонимов - со всеми элементами, вставленными в BK-дерево. Когда кто-то ищет одно слово в наборе, вы отображаете все остальные как альтернативы. Слово может появляться в нескольких наборах, поэтому вам нужно убедиться, что ваши узлы BK-Tree могут обрабатывать несколько значений для данного ключа.

Answer 4

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

Корректор правописания немного сложнее - поскольку нужно сопоставить входные данные с каким-то правильным вводом. Вы можете взять эту ссылку в качестве начала: http://en.wikipedia.org/wiki/Spell_checker. В конце вы найдете ссылки на статьи о различных алгоритмах. Согласно статье в Википедии, этот документ описывает наиболее успешный алгоритм: Эндрю Голдинг и Дэн Рот "Алгоритм исправления орфографии на основе Winnow"

Answer 5

Для словаря я бы использовал коллекцию std::map (вызывающую Dictionary в .Net framework) со словом в качестве ключа и пользовательский объект (со всей информацией о слове + определение) в качестве значения.

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

Answer 6

Также проверьте фильтр Блума .