• May 27, 2016 News!The submission for Special Issue is officially open now!   [Click]
  • May 03, 2016 News!Vol.6, No.6 has been indexed by EI (Inspec).   [Click]
  • Mar 17, 2017 News!Vol.9, No.2 has been published with online version. 13 peer reviewed articles from 4 specific areas are published in this issue.   [Click]
General Information
Prof. Wael Badawy
Department of Computing and Information Systems Umm Al Qura University, Canada
I'm happy to take on the position of editor in chief of IJCTE. We encourage authors to submit papers concerning any branch of computer theory and engineering.
IJCTE 2016 Vol.8(1): 48-52 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2016.V8.1018

Comparisons of Efficient Implementations for DAWG

Masao Fuketa, Kazuhiro Morita, and Jun-ichi Aoe
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).


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.

Copyright © 2008-2015. International Journal of Computer Theory and Engineering. All rights reserved.
E-mail: ijcte@vip.163.com