Ориентированный ациклический граф

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