Ternary Directed Acyclic Word Graphs
Satoru Miyamoto a Shunsuke Inenaga b Masayuki Takeda a,c
Ayumi Shinohara a,ca Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japanb Department of Computer Science, P.O.Box 26 (Teollisuuskatu 23), FIN-00014

University of Helsinki, Finlandc SORST, Japan Science and Technology Agency (JST)Abstract
Given a set S of strings, a DFA accepting S oﬀers a very time-eﬃcient solution to thepattern matching problem over S. The key is how to implement such a DFA in the
trade-oﬀ between time and space, and especially the choice of how to implement thetransitions of each state is critical. Bentley and Sedgewick proposed an eﬀective tree
structure called ternary trees. The idea of ternary trees is to ‘implant’ the processof 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 directed acyclic word graph (DAWG) of a string w is thesmallest DFA that accepts all suﬃxes of w, and requires only linear space. We apply
the scheme of ternary trees to DAWGs, introducing a new data structure named
ternary DAWGs (TDAWGs). Furthermore, the scheme of AVL trees is applied to
the TDAWGs, yielding a more time-eﬃcient structure AVL TDAWGs. We also
perform some experiments that show the eﬃciency of TDAWGs and AVL TDAWGs,
compared to DAWGs in which transitions are implemented by linked lists.
Key words: deterministic ﬁnite state automata, pattern matching on strings,
directed acyclic word graphs, ternary search trees, AVL trees

1

Introduction

Due to rapid advance in information technology and global growth of computer
networks, we can utilize a large amount of data today. In most cases, data
Email addresses: s-miya@i.kyushu-u.ac.jp (Satoru Miyamoto),
inenaga@cs.helsinki.fi (Shunsuke Inenaga), takeda@i.kyushu-u.ac.jp(Masayuki Takeda), ayumi@i.kyushu-u.ac.jp (Ayumi Shinohara).

Preprint submitted to Elsevier Science

3 May 2004

are stored and manipulated as strings. Therefore the development of eﬃcient
data structures for searching strings has for decades been a particularly active
research area in computer science.
Given a set S of strings, we want some eﬃcient data structure that enables
us to search S very quickly. Obviously a DFA that accepts S is the one.
The problem arising in implementing such an automaton is how to store theinformation of the transitions in each state. The most basic idea is to use
tables, with which searching S for a given pattern p is feasible in O(|p|) time,
where |p| denotes the length of p. However, the signiﬁcant drawback is thatthe size of the tables is proportional to the size of the alphabet Σ used. In
particular, it is crucial when the size of Σ is thousands large like in Asian
languages such as Japanese, Korean, Chinese, and so on. Using linked lists
is one apparent means of escape from this waste of memory space by tables.
Although this surely reduces space requirement, searching for pattern p takes
O(|Σ|·|p|) time in both worst and average cases. It is easy to imagine that thisshould be a serious disadvantage when searching texts of a large alphabet.
Bentley and Sedgewick [3] introduced an eﬀective tree structure called ternary
search trees (to be simply called ternary trees in this paper), for storing a
set of strings. The idea of ternary trees is to ‘implant’ the process of binary
search for transitions into the structure of the trees themselves. This way theprocess of binary search becomes visible, and the implementation of the trees
becomes quite easy since each and every state of ternary trees has at mostthree transitions. Bentley and Sedgewick gave an algorithm that, for any set S
of strings, constructs its ternary tree in O(|Σ| · S) time with O(S) space,
where S denotes the total length of the strings in S. They also showed
several nice applications of ternary trees [2].
This paper considers the most fundamental pattern matching problem on
strings, the substring pattern matching problem, which is described as follows: Given a text string w and pattern string p, examine whether or not p isa substring of w. Clearly, a DFA that recognizes the set of all suﬃxes of w
permits us to solve this problem very quickly. The smallest DFA of this kind
was introduced by Blumer et al. [4], called the directed acyclic word graph(DAWG) of string w, that only requires O(|w|) space.
In this paper, we apply the scheme of ternary trees to DAWGs, yielding a newdata structure called ternary DAWGs (TDAWGs). By the use of a TDAWG
of w, searching text w for patten p takes O(|Σ| · |p|) time in the worst case,but the time complexity in the average case is O(log |Σ| · |p|), which is anadvantage over DAWGs implemented with linked lists that require O(|Σ| · |p|)expected time. Therefore, the key is how to construct TDAWGs quickly. Notethat the set of all suﬃxes of a string w is of size quadratic in |w|. Namely,
simply applying the algorithm by Bentley and Sedgewick [3] merely allows us
2

to construct a TDAWG of w in O(|Σ|·|w|2 ) time. However, using a modiﬁcationof the on-line algorithm of Blumer et al. [4], pleasingly, the TDAWG of w canbe constructed in O(|Σ| · |w|) time.
In addition, we have tackled the application of the scheme of AVL trees [1]to our TDAWGs. AVL trees are a kind of binary trees on which searching forany single character can be done in O(log |Σ|) time even in the worst case.
Our new structure is a combination of AVL trees and TDAWGs, named AVL
TDAWGs. Using the AVL TDAWG for a string w, it can be examined inO(log |Σ| · |p|) time whether p is a substring of w or not, even in the worst
case. Another nice feature of AVL TDAWGs is that the AVL TDAWG of any
string w can be built in O(log |Σ| · |w|) time.
We also performed some computational experiments to evaluate the eﬃciencyof TDAWGs and AVL DAWGs using English and Japanese texts, by the comparison with DAWGs implemented by linked lists. The most exciting result isthat the construction times of TDAWGs and AVL TDAWGs for the Japanese
text are dramatically shorter than those of DAWGs with linked lists. Thisis typically shows our TDAWGs and AVL TDAWGs work very well for texts
over a large size alphabet. Plus, search times by TDAWGs and AVL TDAWGs
are much faster than those by DAWGs with linked lists. Our experiment also
reveals that AVL TDAWGs are the fastest in searching for patterns both forEnglish text and Japanese text, and this is surely the eﬀect of AVL balancing
for speeding up binary searches.
The rest of the paper is organized as follows. In Section 2, we recall the definition and the on-line construction algorithm of DAWGs. In Section 3, we
introduce our new structure TDAWGs and show how they work. Section 4 isdevoted to the introduction of the enhanced version of our new structure, AVL
TDAWGs. We give the results of our experiments in Section 5 and conclude
in Section 6.

2

Directed Acyclic Word Graphs

Let Σ be a ﬁnite alphabet. An element of Σ∗ is called a string. Strings x, y, andz are said to be a preﬁx, substring, and suﬃx of string w = xyz, respectively.
The sets of preﬁxes, substrings, and suﬃxes of a string w are denoted by
Preﬁx (w), Substr (w), and Suﬃx (w), respectively. The length of a string w
is denoted by |w|. The empty string is denoted by ε, that is, |ε| = 0. Let
Σ+ = Σ∗ − {ε}.
Let S ⊆ Σ∗ . The number of strings in S is denoted by |S|, and the sum of thelengths of strings in S by S.
3

c

c
o

o
c
o
a

o
a

c
a o

o

c

a

o

a

a
a

a

Fig. 1. STrie(cocoa) is shown on the left, where all the states are accepting. By
minimizing this automaton we obtain DAWG(cocoa), on the right.

The following problem is the most fundamental and important in string processing.
Definition 1 (Substring Pattern Matching Problem)
Instance: a text string w ∈ Σ∗ and pattern string p ∈ Σ∗ .
Determine: whether p is a substring of w.
Obviously, an automaton that accepts Substr (w) is pretty useful to solve thisproblem. The most basic automaton of this kind is the suﬃx trie. The suﬃx
trie of a string w ∈ Σ∗ is denoted by STrie(w). What is obtained by minimizing
STrie(w) is called the directed acyclic word graph (DAWG) of w [9], denoted
by DAWG(w). In Fig. 1 we show STrie(w) and DAWG(w) with w = cocoa.
The initial state of DAWG(w) is also called the source state, and the state accepting w is called the sink state of DAWG(w). Each state of DAWG(w) otherthan the source state has a suﬃx link. Assume x1 , . . . , xk are the substringsof w accepted in one state of DAWG(w), arranged in the decreasing order of
their lengths. Let ay = xk , where y ∈ Σ∗ and a ∈ Σ. Then the suﬃx link of
the state accepting x1 , . . . , xk points to the state in which y is accepted.
DAWGs were ﬁrst introduced by Blumer et al. [4], and have widely beenused for solving the substring pattern matching problem as well as in various
applications [7,8,15].
Theorem 1 (Crochemore [6]) For any string w ∈ Σ∗ , DAWG(w) is thesmallest (partial) DFA that recognizes Suﬃx (w).
Proposition 1 Using DAWG(w) whose transitions are implemented with linked
lists, the substring pattern matching problem of Deﬁnition 1 is solvable inO(|Σ| · |p|) time in the worst and average cases.
Theorem 2 (Blumer et al. [4]) For any string w ∈ Σ∗ with |w| > 1, DAWG(w)has at most 2|w| − 1 states and 3|w| − 3 transitions.
4

ε

c

co

coc

c

c

c

o

o

o

o

c

cocoa

coco
c

cocoao
c

o

c

o

o

o

o

c

c

o

o

o a

a

a

o

a

a

c

c

a
a

o
Fig. 2. On-line construction of DAWG(w) with w = cocoao. The solid arrows are
the transitions, and the dashed arrows are the suﬃx links. In the process of updating
DAWG(cocoa) to DAWG(cocoao), the state accepting {co, o} is separated into twostates for {co} and {o}.

It is a trivial fact that DAWG(w) can be constructed in time proportional to
the number of transitions in STrie(w) using the DAG-minimization algorithm
by Revuz [13]. However, the number of transitions of STrie(w) is unfortunately quadratic in |w|. The direct construction of DAWG(w) in linear timeis therefore signiﬁcant, in order to avoid creating redundant states and transitions that are deleted in the process of minimizing STrie(w). Blumer et al. [4]indeed presented an algorithm that directly constructs DAWG(w) and runs
in linear time if Σ is ﬁxed, by means of suﬃx links. Their algorithm is online, namely, for any w ∈ Σ∗ and a ∈ Σ it allows us to update DAWG(w)to DAWG(wa) in amortized constant time, meaning that we need not construct DAWG(wa) from scratch. On-line construction of DAWG(cocoao) is
illustrated in Fig. 2.
We here brieﬂy recall the on-line algorithm by Blumer et al. A more detailed
description and pseudo-code of the algorithm can be found in [4]. The algorithm updates DAWG(w) to DAWG(wa) by inserting suﬃxes of wa into
DAWG(w) in decreasing order of their lengths. Let z be the longest string in
Substr (w) ∩ Suﬃx (wa). Then z is called the longest repeated suﬃx of wa and5denoted by LRS (wa). Let z  = LRS (w). Let |wa| = l and u1 , u2 , . . . , ul , ul+1
be the suﬃxes of wa ordered by their lengths, that is, u1 = wa and ul+1 = ε.
We categorize these suﬃxes of wa into the three following groups.
(Group 1) u1 , . . . , ui−1
(Group 2) ui , . . . , uj−1 where ui = z  a(Group 3) uj , . . . , ul+1 where uj = z
Note all suﬃxes in Group 3 are already represented in DAWG(w). We caninsert all the suﬃxes of Group 1 into DAWG(w) by creating a new transition
labeled by a from the current sink state to the new sink state. Therefore,
we have only to care about those in Group 2. Let vi , . . . , vj−1 be the suﬃxes
of w such that, for any i ≤ k ≤ j − 1, vk a = uk . We start from the statecorresponding to LRS (w) = z  = vi in DAWG(w), which is called the active
state of the current phase. A new transition labeled by a is inserted from theactive state to the new sink state. The state to be the next active state isfound simply by traversing the suﬃx link of the state for vi , in constant time,and a new transition labeled by a is created from the new active state to thesink state. After we insert all the suﬃxes of Group 2 this way, the automaton
represents all the suﬃxes of wa. We now pay attention to LRS (wa) = z = uj .
The suﬃx link of the new sink state is set to point to the state that acceptsuj .
Let us see a concrete example from Fig. 2. See the conversion of DAWG(coco)
to DAWG(cocoa). Regarding the suﬃxes of cocoa, we have Group 1: cocoa,
ocoa; Group 2: coa, oa, a; Group 3: ε. By creating a new transition labeled
by a from the old sink state to the new sink state, the suﬃxes cocoa andocoa in Group 1 get to be accepted by the automaton. Notice the current
active state is the state corresponding to {co, o}. From this state we create
a new transition labeled by a to the new sink state. Then two suﬃxes coa
and oa in Group 2 are now accepted. After that, we go up to the source state
by traversing the suﬃx link of the state accepting {co, o}. We create a newtransition labeled with a from the source state to the new sink state, andnow all the suﬃxes of cocoa are accepted by the automaton. Finally, we set
the suﬃx link of the new sink state so that it points to the source state that
accepts ε.
We note that an event so called node separation can happen at the last stage of
updating DAWG(w) to DAWG(wa). Let s be the state which accepts uj , andlet x be the longest string accepted by state s. We then check whether x = uj
or not. If so, we are ﬁnished. Otherwise, state s is separated into two states,s and its duplication s , where s becomes to accept the strings longer thanuj and s accepts the rest. A concrete example can be seen in the conversion
of DAWG(cocoa) into DAWG(cocoao) shown in Fig. 2. Here, uj = o andx = co, thus we have uj = x. Then state s which in this case accepts {co, o}
is separated into two states accepting {co} and {o}, respectively. All the
6

c
a

a

c

o

o

c

c

o
a

a

o

a

o

c

o

a

a

o
a

Fig. 3. TSTrie(w) is on the left, and TDAWG(w) on the right, with w = cocoa.

(outgoing) transitions of s are also duplicated for s , namely, the target stateof the transitions of s is the same as the target state of the transitions of s(see Fig. 2). The suﬃx links of s and s also have to be adjusted. Let t be
the state to which the suﬃx link of s is directed. Then the suﬃx link of s isredirected to s , and the suﬃx link of s is directed to t. Associating each statewith the length of the longest string accepted in it, we can deal with this state
separation in amortized constant time.
Theorem 3 (Blumer et al. [4]) For any string w ∈ Σ∗ , DAWG(w) can beconstructed on-line and in O(|Σ| · |w|) time using O(|w|) space, if the transitions are implemented by linked lists.
The |Σ| factor in the time complexity of the above theorem comes from thefact that searching transitions in each state takes O(|Σ|) time if we implement
the transitions by linked lists, as stated in Proposition 1. Therefore, eﬃcient
implementation of the transitions is crucial in order to achieve faster searchand construction of DAWGs. In the following sections, we will show our new
automata which enable us faster search and construction.

3

Ternary Directed Acyclic Word Graphs

In this section, we present a new kind of automata called ternary directed
acyclic word graphs (TDAWGs). The idea is to implement the transitions of
DAWGs by using ternary search trees [3,2] (in short, ternary trees). Ternary
trees are quite useful for storing a set of strings from both viewpoints ofspace eﬃciency and search speed. The idea of ternary trees is to ‘implant’ theprocess of binary search for linked lists into the trees themselves. This way
the process of binary search becomes visible, and the implementation of thetrees becomes quite easy since each and every state of ternary trees has at
most three transitions.
7

The left of Fig. 3 is a ternary tree for Suﬃx (w) with w = cocoa. We can seethat this corresponds to STrie(w) in Fig. 1, and therefore, the tree is called aternary suﬃx trie (TSTrie) of string cocoa.
For a substring x of a string w ∈ Σ∗ , we consider set CharSetw (x) = {a ∈ Σ |xa ∈ Substr (w)} of characters. In STrie(w), each character of CharSetw (x) is
associated with a transition from state x (see STrie(cocoa) in Fig. 1). However, in a TSTrie of w, each character in CharSetw (x) corresponds to a state.
This means that we can regard CharSetw (x) as a set of the states that immediately follow string x in the TSTrie of w, where elements of CharSetw (x) arearranged in lexicographical order, top-down. There are many variations of thearrangement of elements in CharSetw (x), but we arrange them in increasingorder of their leftmost occurrences in w, top-down. Thus the arrangement of
the states is uniquely determined, and the resulting structure is called the
TSTrie of w, denoted by TSTrie(w). The state corresponding to the characterin CharSetw (x) with the earliest occurrence, is called the top state with respect
to CharSetw (x), since it is arranged on the top of the states for characters in
CharSetw (x).
We now describe how searching for a pattern takes place in TSTrie(w). Givena pattern p, at any node of TSTrie(w) we examine if the character a in p wecurrently focus on is lexicographically larger than the character b stored in thestate. If a < b, then we take the left transition from the state and compare ato the character in the next state. If a > b, then we take the right transition
from the state and compare a to the character in the next state. If a = b,then we take the center transition from the state, now the character a has
been recognized, and we compare the next character in p to the character in
the next state. We give a concrete example of searching for pattern oa using
TSTrie(cocoa) in Fig. 3. We start from the initial state of the tree and haveo > c, and thus go down to the next state via the right transition. At the next
state we have o = o, and thus we take the center transition from the state andarrive at the next state, with the character o recognized. We then compare
the next character a in the pattern with c in the state where we are. Now wehave a < c, we go down along the left transition of the state and arrive at
the next state, where we have a = a. Then we take the center transition andarrive at the next state, where ﬁnally oa is accepted. This way, for any patternp ∈ Σ∗ we can solve the substring pattern matching problem of Deﬁnition 1
in O(log |Σ|·|p|) expected time.
We now consider to apply the above scheme to DAWG(w). What is obtained
here is the ternary DAWG (TDAWG) of w, denoted by TDAWG(w). The
right of Fig. 3 is TDAWG(cocoa). Compare it to DAWG(cocoa) in Fig. 1
and TSTrie(cocoa) in Fig. 3.
Proposition 2 Using TDAWG(w), the substring pattern matching problem
8

ε

c

co
c

coc
c
o

c
o

o

o

c

coco

cocoa
c
o

c
o

o

a

c
o

cocoao
c
o

a

c
a

o
a

a

o

o

c

c

o

a

a
o

Fig. 4. On-line construction of TDAWG(w) with w = cocoao. The dashed arrows
are the suﬃx links. Notice only top states have suﬃx links, and only top states
can be the target of suﬃx links of other top states. In the process of updating
TDAWG(cocoa) to TDAWG(cocoao), the state accepting {co, o} is separated into
two states for {co} and {o}, as well as the case of DAWGs shown in Fig 2.

of Deﬁnition 1 is solvable in O(|Σ|·|p|) time in the worst case, and in O(log |Σ|·|p|) time in the average case.
Notice the advantage in the average case of TDAWGs against DAWGs on
searching for patterns (See Proposition 1).
On-line construction of TDAWGs can be done based on the on-line DAWG
construction algorithm by Blumer et al. [4], which was recalled in Section 2.
On-line construction of TDAWG(cocoao) is illustrated in Fig. 4.
Here are two small remarks about on-line construction of TDAWGs: The ﬁrst
is about suﬃx links. In TDAWGs only top states have suﬃx links, and only top
states can be the target of suﬃx links of other top states. The second is aboutstate separation. When a top state is separated, then the other states belonging
to the same CharSet as the top state have to be duplicated. A concrete example
can be seen in the conversion of TDAWG(cocoa) to TDAWG(cocoao) in
Fig. 4, where top state accepting {co, o} is separated into two top states
accepting {co} and {o}.
9

c

e
c
a

f

a

d

e
b

d

f

b
Fig. 5. Examples of a non-AVL tree on the left and an AVL tree on the right.

Now we have the following theorem:
Theorem 4 For any string w ∈ Σ∗ , TDAWG(w) can be constructed on-line,in O(|Σ| · |w|) time using O(|w|) space.

4

AVL Ternary Directed Acyclic Word Graphs

AVL trees [1] are a well-known fast tree structure in binary searches. The idea
is to balance each subtree so that the worst case time complexity for binary
search becomes O(log |Σ|).
Definition 2 (AVL Tree) Deﬁne the height of a tree as the maximum lengthof any path from its root to a leaf. An AVL tree is a binary search tree suchthat the height of the left and right subtrees of any node diﬀers by at most one.
See Fig. 5 for examples of a non-AVL tree and AVL tree.
Now our idea is to apply this scheme to our TDAWGs so that, for any top stateof TDAWG(w) corresponding to a substring x of w, the tree for CharSetw (x)consisting of the left and right transitions is an AVL tree. We call it the AVL
TDAWG of w, and denote by avl TDAWG(w). avl TDAWG(w) is superior
to TDAWG(w) on searching for a pattern p, as stated in the following proposition.
Proposition 3 Using avl TDAWG(w), the substring pattern matching problem of Deﬁnition 1 is solvable in O(log |Σ| · |p|) time in the worst and averagecases.
Moreover, we can construct avl TDAWG(w) in on-line manner, by examining
the AVL condition each time a new state (character) is inserted into the tree
for CharSetw (x) consisting of the left and right transitions. The addition ofa new state to the tree can sometimes violate the AVL condition, and thenwe rotate those states so that the tree can still remain an AVL tree. It is awell-known fact that:10Lemma 1 (G. Adelson-Velskii and E. Landis [1]) Inserting a new node
into an AVL tree takes O(log N ) time, where N is the number of nodes of the
AVL tree.
Due to the above lemma, we obtain the following theorem.
Theorem 5 For any string w ∈ Σ∗ , avl TDAWG(w) can be constructed online, in O(log |Σ| · |w|) time using O(|w|) space.
On-line construction of avl TDAWG(w) is illustrated in Fig. 6. One mightsuspect that it is sometimes necessary to redirect suﬃx links after rotating
nodes, as seen in the node rotation of avl TDAWG(bef) in Fig. 6. The numberof the suﬃx links for each CharSetw (x) is O(|Σ|), and thus, if such redirection
can happen every time a new character is added, we no longer can construct
avl TDAWG(w) in O(log |Σ| · |w|) time. However, if we use an auxiliary stateconnected to the current top state for each CharSetw (x) and associate thesuﬃx links with this auxiliary state, we can redirect all the suﬃx links inO(1) time by reconnecting the auxiliary state to the new top state after therotation. Hence we can achieve the improved time complexity mentioned in
Theorem 5.

5Experiments

In this section we show some experimental results that reveal the advantage
of our TDAWGs and AVL TDAWGs, compared to DAWGs whose transitions are implemented with linked lists (denoted list DAWGs). The linked
lists were linearly searched at any state of the list DAWGs. All the threealgorithms to construct TDAWGs, AVL TDAWGs, and list DAWGs were implemented in the C language. All calculations were performed on a Desktop
PC with Pentium4-1.7GHz CPU and 768MB main memory running Windows XP Professional. We used the English text “ohsumed.91” available at
http://trec.nist.gov/data.html, and the Japanese texts from novels ofSoseki Natsume available at http://www.aozora.gr.jp/.
The ﬁrst test was to compare memory space requirements of TDAWGs, AVL
TDAWGs, and list DAWGs. The left chart of Fig. 7 shows memory requirements of TDAWGs, AVL TDAWGs, and list DAWGs for the English texts,
where the memory requirements grow linearly, as expected. TDAWGs require
about 19% more memory than list DAWGs. Also, AVL TDAWGs require
about 24% and 4% more memory than list DAWGs and TDAWGs, respectively. The right chart of Fig. 7 shows memory requirements of TDAWGs, AVL
TDAWGs, and list DAWGs for the Japanese texts. Here again, the memory
requirements grow linearly as expected. TDAWGs require about 28% more
11

ε

b

be
b

b
e

e

bef
b

e

e

node rotarion

e

b

f

f

f

e
f

befa

befac
e

e

b

f

b

e

a

a

e

f

f

a

a

f
c

c

befacd
e
b
a

e
f

c
f

c

b
node rotarion

d

a

e

e
d

f

f

a

a

c

c

d

d

Fig. 6. On-line construction of avl TDAWG(w) with w = befacd. The dashedarrows are the suﬃx links. After a new character f is inserted into the source stateof avl TDAWG(be), the tree for the source state becomes a non-AVL tree. Therefore
we rotate the nodes for characters b, e, and f so that the tree remains an AVL tree
(second upper right). Another type of node rotation happens in inserting a new
character d into the source state of avl TDAWG(befac). The resulting structure(lower right) is avl TDAWG(befacd) in which the trees for all CharSetw (x) are
AVL balanced.

12

memory requirements for English text

memory requirements for Japanese text

[Mbyte][Mbyte]
AVL_TDAWG

AVL_TDAWG

memory space

memory space

20

TDAWG

20

list_DAWG
10

0
0

200

400

list_DAWG
1000[Kbyte]

TDAWG

200

text size

400

600

[Kbyte]text size

Fig. 7. The left and right charts show the space requirements of the TDAWG, AVL
TDAWG, and list DAWG for the English and Japanese texts, respectively.
construction times for English text
3
[sec]

[sec]

construction times for Japanese text

2
AVL_TDAWG

2
list_DAWG
time

time

list_DAWG
1

1
TDAWG
AVL_TDAWG
0
0

200

400

0
0

[Kbyte]

200

400

TDAWG
600 [Kbyte]

text size

text size

Fig. 8. The left and right charts show the construction times of the TDAWG, AVL
TDAWG, and list DAWG for the English and Japanese texts, respectively.

memory than list DAWGs, and AVL TDAWGs require about 35% and 5%
more memory than list DAWGs and TDAWGs, respectively.
The second test was to compare construction times of TDAWGs, AVL TDAWGs,
and list DAWGs. The left chart of Fig. 8 shows construction times of the
TDAWGs, AVL TDAWGs, and list DAWGs for the English texts. One cansee that the constructions of TDAWGs were done about 1.2 times fasterthan that of list DAWGs. This should be the eﬀect of binary search in the
TDAWGs, while the linked lists were linearly searched in the list DAWGs.
AVL TDAWGs were constructed about twice slower than TDAWGs. It seems
that this comes from the cost of node rotations for balancing each AVL tree
in the AVL TDAWGs. The right chart of Fig. 8 shows construction times of
TDAWGs, AVL TDAWGs, and list DAWGs for the Japanese texts, which is13

searching times for Japanese text

searching times for English text[µsec][µsec]

0.004

list_DAWG

0.002

time

time

list_DAWG

TDAWG

0.002

0.001
AVL_TDAWG

TDAWG

AVL_TDAWG0005pattern size

10
[byte]

10

20[byte]

pattern size

Fig. 9. The left and right charts show the search times of the TDAWG, AVL
TDAWG, and list DAWG for the English and Japanese texts, respectively.

one of the most dramatic results from our experiments. TDAWGs were constructed thirteen times faster than list DAWGs, and even AVL DAWGs wereconstructed eight times faster than list DAWGs! This is obviously because thelinked lists of the list DAWGs were linearly searched, while binary searches
were operated in the others. This result typically shows one eﬀectiveness of
TDAWGs and AVL DAWGs for texts over a large alphabet.
The third test was searching times for patterns of diﬀerent lengths. We used 9
texts of diﬀerent lengths, in the range from 32 to 512 Kbytes. For each text, we
randomly chose 100 of their substrings of each length, and searched for eachof these substrings 1 million times. The result shown in the left chart of Fig. 9
is the average time of searching for a pattern, using the English texts. One
can see both TDAWGs and AVL TDAWGs are more than twice faster thanlist DAWGs. Moreover, search on AVL TDAWGs is slightly faster than on
TDAWGs, due to the eﬀect of balancing trees. In the right chart of Fig. 9 thatshows the average time of searching for a pattern in the Japanese texts, theeﬀect of TDAWGs and AVL TDAWGs is visualized better; TDAWGs are morethan three times faster than list DAWGs, and AVL TDAWGs are about ﬁvetimes faster than list DAWGs. Moreover, searching on AVL TDAWGs is about
1.5 times faster than TDAWGs, where balancing trees on AVL TDAWGs took
eﬀect.

6

Conclusions and Further Work

Table 1 summarizes the space requirements, construction times, worst-casesearch times, and average search times of DAWGs whose transitions are im14

Table 1
Comparison of DAWG implemented with tables (denoted table DAWG), DAWG
implemented with linked lists (denoted list DAWG), TDAWGs, and AVL TDAWGs,
where Σ is the alphabet, and n and m are the length of the text and pattern,
respectively.
type of DAWG

space
requirement

construction
time

worst-casesearch time

averagesearch time

table DAWG

O(|Σ|n)O(|Σ|n)

O(m)

O(m)

list DAWG

O(n)O(|Σ|n)O(|Σ|m)O(|Σ|m)

TDAWG

O(n)

O(|Σ|n)O(|Σ|m)O(log|Σ|m)

AVL TDAWG

O(n)O(log|Σ|n)O(log|Σ|m)O(log|Σ|m)plemented with tables (table DAWG), DAWGs whose transitions are implemented with linked lists (list DAWG), TDAWGs and AVL TDAWGs. Although table DAWGs are surely very fast in search, they actually consume
too much space, O(|Σ|n). Especially for texts over a large sized alphabet such
as Japanese, Korean, Chinese etc., table DAWGs are absolutely unrealistic.
TDAWGs are better in average search time than list DAWGs, where the linked
lists in list DAWGs are linearly searched but binary searches take place in
TDAWGs. AVL DAWGs have good complexities for all of space requirement,
construction time, worst-case search time, and average search time. The resultsof our experiments in Section 5 have shown that our new structures TDAWGs
and AVL TDAWGs are useful in practice as well, especially for texts over alarge alphabet.
We emphasize that the beneﬁt of the ternary-based implementation is not
limited to DAWGs. Namely, it can be applied to any automata-oriented index
structure such as suﬃx trees [16,12,14,10] and compact directed acyclic word
graphs (CDAWGs) [5,9,11]. Therefore, we can also consider ternary suﬃx trees
and ternary CDAWGs. Concerning the experimental results on TDAWGs,
ternary suﬃx trees and ternary CDAWGs promise to perform very well inpractice.
Moreover, there is another variation of TDAWGs that is more space-economical.
Note that Fig. 3 of Section 3 can be minimized by the algorithm of Revuz [13],and the resulting structure is shown in Fig. 10, which is called the minimum
TDAWG (MTDAWG) of the string. To use Revuz’s algorithm we have to maintain the reversed transition for every transition, and it certainly requires toomuch space. Thus we are now interested in an on-line algorithm to construct
MTDAWGs directly, and it is our future work. We expect that search timeon MTDAWGs will be in practice faster than using TDAWGs, since memory
allocation for MTDAWGs is likely to be quicker.
15

c
o
c
o
a

Fig. 10. The MTDAWG of string cocoa.

References[1] G. Andelson-Velskii and E. Landis. An algorithm for the organisation of
information. Soviet. Math., 3:1259–1262, 1962.
[2] J. Bentley and B. Sedgewick. Ternary search trees. Dr. Dobb’s Journal, 1998.
http://www.ddj.com/.
[3] J. Bentley and R. Sedgewick. Fast algorithms for sorting and searching
strings. In Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA’97), pages 360–369. ACM/SIAM, 1997.
[4] A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, and J. Seiferas.
The smallest automaton recognizing the subwords of a text. TheoreticalComputer Science, 40:31–55, 1985.
[5] A. Blumer, J. Blumer, D. Haussler, R. McConnell, and A. Ehrenfeucht.
Complete inverted ﬁles for eﬃcient text retrieval and analysis. J. ACM,
34(3):578–595, 1987.
[6] M. Crochemore. Transducers and repetitions. Theoretical Computer Science,
45:63–86, 1986.
[7] M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New
York, 1994.
[8] M. Crochemore and W. Rytter. Jewels of Stringology. World Scientiﬁc, 2002.
[9] M. Crochemore and R. Vérin. On compact directed acyclic word graphs. In
Structures in Logic and Computer Science, volume 1261 of Lecture Notes in
Computer Science, pages 192–211. Springer-Verlag, 1997.
[10] D. Gusﬁeld. Algorithms on Strings, Trees, and Sequences. Cambridge University
Press, New York, 1997.
[11] S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, G. Mauri, and
G. Pavesi. On-line construction of compact directed acyclic word graphs. In
Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM’01),

16

volume 2089 of Lecture Notes in Computer Science, pages 169–180. SpringerVerlag, 2001.
[12] E. M. McCreight. A space-economical suﬃx tree construction algorithm.
J. ACM, 23(2):262–272, 1976.
[13] D. Revuz. Minimization of acyclic deterministic automata in linear time.
Theoretical Computer Science, 92(1):181–189, 1992.
[14] E. Ukkonen. On-line construction of suﬃx trees. Algorithmica, 14(3):249–260,
1995.
[15] E. Ukkonen and D. Wood. Approximate string matching with suﬃx automata.
Algorithmica, 10(5):353–364, 1993.
[16] P. Weiner. Linear pattern matching algorithms. In Proc. 14th Annual
Symposium on Switching and Automata Theory, pages 1–11, 1973.

17