Как построить DAWG из дерева?

Question

Как построить DAWG из дерева?

Я просто создаю trie для словаря, и затем я обнаружил, что есть много веток с одинаковой структурой. Я хочу объединить их вместе, чтобы стать РАГ.

Какой алгоритм я бы использовал для преобразования дерева в DAWG?

3

algorithm data-structures trie dawg

Источник

user1540043 05 апр '13 в 03:43

1 ответ

Другие вопросы по тегам algorithm data-structures trie dawg

user501557 05 апр '13 в 05:00 2013-04-05 05:00 · Answer 1 · 2013-04-05 05:00

Стандартный алгоритм преобразования дерева в DAWG работает, обрабатывая дерево как детерминированный конечный автомат, а затем преобразовывая дерево в DFA с минимальным состоянием.

Есть много алгоритмов для выполнения этого преобразования. Алгоритм, с которым я наиболее знаком, - это алгоритм Хопкрофта, который работает путем нахождения пар различимых состояний и комбинирования неразличимых состояний вместе.

Надеюсь это поможет!