Updateable DAWG library or DAWG construction from non-sorted data

Question

dawgdic is a great DAWG library, but it has a significant drawback because it is static (not updateable) and has to be constructed form strings sorted in alphabetical order. If the raw data from which the DAWG is constructed is big (several gigabytes), the initial construction of DAWG involving sorting a huge array of strings can demand too much resources.

Is there a library that provides a memory-efficient structure as dawgdic which allows construction from non-sorted dictionary?

score 3 · Answer 1 · edited May 23 '17 at 11:44

3

Currently, I don't think there's any library that allows construction of DAWGs from a non-sorted dictionaries.

But, after a lot of searching, I've found this paper, "Incremental Construction of Minimal Acyclic Finite-State Automata" , which I think has exactly what you want. Maybe you could make your own library after reading this, and share it with everyone!

EDIT: Have you looked at this question?

edited May 23 '17 at 11:44

Community

1
1

answered Oct 04 '13 at 11:36

max

4,248
2
25
38

Thank you for the paper, although I probably won't have time to write my own library. – lizarisk Oct 04 '13 at 11:47

score 2 · Answer 2 · answered Oct 04 '13 at 11:53

2

I've found some great libraries that allow online construction from non-sorted data, altough they are not based on DAWG:

cedar - a very fast double-array trie
marisa-trie - а very space efficient string matching library

answered Oct 04 '13 at 11:53

lizarisk

7,562
10
46
70

score 2 · Answer 3 · answered Jul 01 '16 at 18:32

I currently know of no C++ implementations of a DAWG which support the construction from non-sorted data, but if you're open to creating your own solution which has such a feature, Incremental Construction of Minimal Acyclic Finite-State Automata (2000) is a paper which basically lays out the algorithm behind it.

Alternatively, if you're open to porting solutions from other languages, it may be worth your while to check out MDAG, a Java implementation of the data structure. It supports both on-the-fly string addition and string removal, which is exactly what you are looking for. The code is also easy to follow, and extensively commented, so porting it should be a fairly simple task.

Disclaimer: I am the author of MDAG :) .

Updateable DAWG library or DAWG construction from non-sorted data

3 Answers3