Best way to construct a Directed Acyclic Word Graph (DAWG)

Question

I am currently looking into DAWGs and I haven't been able to find one good way of constructing an acyclic automaton.

So basically, what I want to do is this :

It is basically a tree, where the number of states are reduced. I would use it with numbers but the concept is exactly the same.

I wonder what would be the fastest way to do it, my actual plan was to construct the graph as shown on the left, and then look at the states of low level and when they are similar merge them.

Although, I am not sure this is the best way of doing it, does anyone have an idea on how to construct it.

Regards.

Answer 1

DAWGs are minimal-state finite automata for the particular set if strings they store. You can construct them by treating the trie you have as a non-minimal finite automaton and running a standard DFA minimization algorithm on it. This is perhaps the easiest way to construct the DAWG, and also probably the fastest.

Hope this helps!