Implementation of directed acyclic word graph

Balík, Miroslav. "Implementation of directed acyclic word graph." Kybernetika 38.1 (2002): [91]-103. <http://eudml.org/doc/33569>.

@article{Balík2002,
abstract = {An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DAWG for a text $T$ is a minimal automaton that accepts all substrings of a text $T$, so it represents a complete index of the text. While all usual implementations of DAWG needed about 30 times larger storage space than was the size of the text, here we show an implementation that decreases this requirement down to four times the size of the text. The method uses a compression of DAWG elements, i. e. vertices, edges and labels. The construction time of this implementation is linear with respect to the size of the text, a search for a specific pattern is done in a linear time with respect to the size of the pattern. This implementation preserves both good properties of the DAWG automaton.},
author = {Balík, Miroslav},
journal = {Kybernetika},
keywords = {directed acyclic word graph automaton; string matching; data structures; directed acyclic word graph automaton; string matching; data structures},
language = {eng},
number = {1},
pages = {[91]-103},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Implementation of directed acyclic word graph},
url = {http://eudml.org/doc/33569},
volume = {38},
year = {2002},
}

TY - JOUR
AU - Balík, Miroslav
TI - Implementation of directed acyclic word graph
JO - Kybernetika
PY - 2002
PB - Institute of Information Theory and Automation AS CR
VL - 38
IS - 1
SP - [91]
EP - 103
AB - An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DAWG for a text $T$ is a minimal automaton that accepts all substrings of a text $T$, so it represents a complete index of the text. While all usual implementations of DAWG needed about 30 times larger storage space than was the size of the text, here we show an implementation that decreases this requirement down to four times the size of the text. The method uses a compression of DAWG elements, i. e. vertices, edges and labels. The construction time of this implementation is linear with respect to the size of the text, a search for a specific pattern is done in a linear time with respect to the size of the pattern. This implementation preserves both good properties of the DAWG automaton.
LA - eng
KW - directed acyclic word graph automaton; string matching; data structures; directed acyclic word graph automaton; string matching; data structures
UR - http://eudml.org/doc/33569
ER -