5

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 :

DAWG

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Anoracx
  • 438
  • 7
  • 24

1 Answers1

3

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Well, yeah but there are multiple minimisation algorithms, and I'd rather prefer to build the DAWG "myself", because I'll need to store it in an array at some point. I'am actually looking for a pseudocode to get the tree -> DAWG. – Anoracx Oct 08 '13 at 18:17
  • @Anoracx- I guess I'm confused about what you're asking. The trie->DAWG step is a DFA minimization step. What do you mean by "build the DAWG yourself?" – templatetypedef Oct 08 '13 at 18:56
  • Well I thought from reading wikipedia that a DAWG (DAFSA) was a type of tree constructed from a normal tree / DFA. So I was actually thinking that there would a particular algorithm to do it. And not just minimisation algorithms. So when I said I want to do it myself, I was actually looking for a way of converting it from a DFA to a DAFSA (DAWG), and if the idea of starting from bottom was a good idea. – Anoracx Oct 08 '13 at 19:11
  • @Anoracx- Ah, I see. To the best of my knowledge, since mathematically you're minimizing the DFA, *any* algorithm you do will be a DFA minimization algorithm, and my concern is that if you try to do this on your own you'll either (a) reinvent the wheel, but less efficiently, or (b) end up with an incorrect algorithm. – templatetypedef Oct 08 '13 at 20:31
  • @templatetypedef And then one would never be able to learn how to reconstruct this data again. That is the only flaw I have with "avoiding reinvention of the wheel". – tom_mai78101 Dec 23 '17 at 18:41