|
CIAA2003 |
START ConferenceManager |
Ternary Directed Acyclic Word Graphs
Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda and Ayumi Shinohara
Presented at
Eighth International Conference on Implementation and Application of
Automata (CIAA 2003),
July 16-18, 2003
Santa Barbara, CA, USA
Abstract
Given a set $S$ of strings, a DFA accepting $S$ offers a very time-efficient solution to the pattern matching problem over $S$. The key is how
to implement such a DFA in the trade-off between time and space, especially the choice of how to implement the transitions of each state is
critical. Bentley and Sedgewick proposed an effective tree structure called {\em ternary trees}. The idea of ternary trees is to `implant' the
process of binary search for transitions into the structure of the trees themselves. This way the process of binary search becomes visible, and
the implementation of the trees becomes quite easy. The {\em directed acyclic word graph} ({\em DAWG}) of a string $w$ is the smallest
DFA that accepts all suffixes of $w$, and requires only linear space. We apply the scheme of ternary trees to DAWGs, introducing a new data
structure named {\em ternary DAWGs} ({\em TDAWGs}). We perform some experiments that show the efficiency of TDAWGs, compared to
DAWGs in which transitions are implemented by tables and linked lists.