Najlepszy sposób na skonstruowanie Directed Acyclic Word Graph (DAWG)

Question

Obecnie szukam DAWGs i nie byłem w stanie znaleźć jednego dobrego sposobu na zbudowanie acyklicznego automatu.

Więc w zasadzie to, co chcę zrobić to:

To jest po prostu drzewo, gdzie liczba stanów są ograniczone. Używałbym go z liczbami, ale koncepcja jest dokładnie taka sama.

Zastanawiam się, jaki byłby najszybszy sposób, aby to zrobić, moim faktycznym planem było skonstruowanie wykresu pokazanego po lewej stronie, a następnie przyjrzenie się stanom niskiego poziomu i kiedy są one podobne, połączenie ich.

Chociaż nie jestem pewien, czy to najlepszy sposób na zrobienie tego, czy ktoś ma pomysł, jak go zbudować.

Pozdrawiam.

Answer 1

DAWG to minimalne, skończone automaty dla określonego zbioru, jeśli przechowują łańcuchy. Możesz je skonstruować, traktując trie, które masz jako nieskończony automat skończony i uruchamiając na nim standardowy algorytm minimalizacji DFA. Jest to prawdopodobnie najłatwiejszy sposób skonstruowania DAWG, a także prawdopodobnie najszybszego.

Mam nadzieję, że to pomoże!