| Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка.Статью следует исправить согласно стилистическим правилам Википедии. |
DAWG (от англ. directed acyclic word graph) — это компактная форма хранения списка слов оптимизированная для выяснения входит ли некое слово в данный список или нет. Ну и снова сам список получить несложно рекурсивным обходом дерева. С точки зрения программы осуществляющей обход или поиск, DAWG ничем не отличается от дерева, просто одинаковые поддеревья хранятся в единственном экземпляре.Сам способ преобразования очевиден: поиск одинаковых поддеревьев и переподключение ссылок на единственный экземпляр.На самом деле помимо буквы, в вершинах хранится флажок указывающий является ли данная буква последней. Так что для списков неповторяющихся слов преобразование в DAWG и обратно происходит без потерь (с точностью до порядка слов).
Для улучшения этой статьи желательно:
Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником. |
