Abstract—Key retrieval is very important in various applications. A trie and DAWG are data structures for key retrieval. The double array is one of methods to construct a trie and has both high speed and compactness. In this paper, a data structure of DAWG by the double array using BASE and CHECK is compared with that of DAWG by the double array using CHECK and NEXT, and the retrieval speed and the space usage are theoretically observed. When DAWG and DFA by the double array are constructed, it turns out that it is important to consider indexes for CHECK and NEXT arrays as edge numbers.
Index Terms—Automaton, DAWG, double array, triple array.
The authors are with the Department of Information Science and Intelligent Systems, University of Tokushima, Tokushima, Japan (e-mail: {fuketa, kam, aoe}@is.tokushima-u.ac.jp).
[PDF]
Cite:Masao Fuketa, Kazuhiro Morita, and Jun-ichi Aoe, "Comparisons of Efficient Implementations for DAWG," International Journal of Computer Theory and Engineering vol. 8, no. 1, pp. 48-52, 2016.
