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

  • Разделы:

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