Obecnie szukam DAWG i nie byłem w stanie znaleźć jednego dobrego sposobu skonstruowania automatu acyklicznego.
Więc zasadniczo chcę to zrobić:
Jest to zasadniczo drzewo, w którym liczba stanów jest zmniejszona. 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 rzeczywistym planem było skonstruowanie wykresu, jak pokazano po lewej stronie, a następnie spojrzenie na stany niskiego poziomu i kiedy są podobne, scal je.
Chociaż nie jestem pewien, czy jest to najlepszy sposób, czy ktoś ma pomysł, jak go zbudować.
Pozdrowienia.
Odpowiedzi:
3 dla odpowiedzi № 1DAWG są automatami skończonymi o minimalnym stanieokreślony zestaw, jeśli łańcuchy są przechowywane. Możesz je skonstruować traktując trie, które masz jako minimalny automat skończony i uruchamiając na nim standardowy algorytm minimalizacji DFA. Jest to prawdopodobnie najłatwiejszy sposób na zbudowanie DAWG, a także prawdopodobnie najszybszy.
Mam nadzieję że to pomoże!