Android DAWG implementation

Question

In my application I need to work with dictionary, what have a lot of words(110 000), so I decided to use trie, but loading of trie cost 9 seconds every time. And this is much a lot even for my emulator. Recently I have read about DAWG(Direct Acyclinc Word Graph) or Minimal Acyclinc Finite State Automaton DAWG wiki what will affect load performance but I can't find a good explanation of algorithm of creating DAWG or Trie to DAWG algorithm. Also I can't find any example, written on java, so I ask you for help. Thanks in advance

score 1 · Accepted Answer · answered Jul 01 '16 at 18:15

1

This may be a little too late for your needs, but for the sake of others who may find themselves here, have a look at MDAG, created and maintained by yours truly :) .

answered Jul 01 '16 at 18:15

Kevin

2,617
29
35

and here is my repo, which contains double-chained trie and that trie can be easily converted to respective DAWG https://github.com/MikeHerasimov/Trie – Mike Herasimov Jul 07 '16 at 08:20
also I provided serialization/deserialization algorithms – Mike Herasimov Jul 07 '16 at 08:32
and finally my trie/dawg are both internationalized – Mike Herasimov Jul 07 '16 at 08:33

score 0 · Answer 2 · answered Mar 14 '15 at 08:43

Currently I'm reading Hopcroft's book named "Introduction to automata theory" it has explanation of many automaton algorithms including automaton minimization(at 4.4.3 chapter)

link to this book John Hopcoft "Introduction to automata theory"

Also there are JFLAP, which can minimize finize state machine.

Android DAWG implementation

2 Answers2