Ternary Directed Acyclic Word Graphs
Satoru Miyamoto† , Shunsuke Inenaga†,‡,Masayuki Takeda†,‡, and Ayumi Shinohara†,‡†Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan‡
PRESTO, Japan Science and Technology Corporation (JST)E-mail: {s-miya, s-ine, takeda, ayumi}@i.kyushu-u.ac.jp

Abstract. Given a set S of strings, a DFA accepting S oﬀers a very
time-eﬃcient solution to the pattern matching problem over S. The key
is how to implement such a DFA in the trade-oﬀ between time andspace, and especially the choice of how to implement the transitions ofeach state is critical. Bentley and Sedgewick proposed an eﬀective tree
structure called 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, andthe implementation of the trees becomes quite easy. The directed acyclic
word graph (DAWG) of a string w is the smallest DFA that accepts
all suﬃxes of w, and requires only linear space. We apply the schemeof ternary trees to DAWGs, introducing a new data structure named
ternary DAWGs (TDAWGs). We perform some experiments that show
the eﬃciency of TDAWGs, compared to DAWGs in which transitions are
implemented by tables and linked lists.

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 are
stored and manipulated as strings. Therefore the development of eﬃcient data
structures for searching strings has for decades been a particularly active researcharea 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 the information 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 that the 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 escapefrom this waste of memory space by tables. Although this surely reduces spacerequirement, searching for pattern p takes O(|Σ| · |p|) time in both worst andaverage cases. It is easy to imagine that this should 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 setof 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 the processof binary search becomes visible, and the implementation of the trees becomesquite easy since each and every state of ternary trees has at most three 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 Sdenotes the total length of the strings in S. They also showed several nice applications of ternary trees [2].
We in this paper consider 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 is a 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
new data 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 for the average case is O(log |Σ| · |p|), which is an advantage
over DAWGs implemented with linked lists that require O(|Σ| · |p|) expected
time. Therefore, the key is how to construct TDAWGs quickly. Note that the setof 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 to construct a
TDAWG of w in O(|Σ| · |w|2 ) time. However, using a modiﬁcation of the on-line
algorithm of Blumer et al. [4], pleasingly, the TDAWG of w can be constructed inO(|Σ|·|w|) time. We also performed some computational experiments to evaluate
the eﬃciency of TDAWGs, using English texts, by the comparison with DAWGs
implemented by tables and linked lists. The most interesting result is that theconstruction time of TDAWGs is dramatically faster than those of DAWGs withtables and linked lists. Plus, it is evaluated that search time by TDAWGs is also
faster than that by DAWGs with linked lists.

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
the lengths of strings in S by S.
The following problem is the most fundamental and important in string processing.

c

c
o

o
c
o
a

o
a

c
a o
a

a

o

c
o

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.

Definition 1 (Substring Pattern Matching Problem).
Instance: a text string w ∈ Σ ∗ and pattern string p ∈ Σ ∗ .
Determine: whether p is a substring of w.
It is clear that this problem is solvable in time proportional to the length ofp, by using an automaton that accepts Substr (w). The most basic automatonof 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 substrings ofw accepted in one state of DAWG(w), arranged in the decreasing order of theirlengths. Let ya = 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, and 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).
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.
It is a trivial fact that DAWG(w) can be constructed in time proportional
to the number of transitions in STrie(w) by 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 time is therefore
signiﬁcant, in order to avoid creating redundant states and transitions that are

ε

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. The on-line construction of DAWG(w) with w = cocoao. The solid arrows are
the transitions, and the dashed arrows are the suﬃx links. Note that the state pointed
by the suﬃx link of the sink state will be the active state of the next phase. In theprocess of updating DAWG(cocoa) to DAWG(cocoao), the state accepting {co, o} isseparated into two states for {co} and {o}.

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 on-line, 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.
We here brieﬂy recall the on-line algorithm by Blumer et al. It 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 and denoted by LRS (wa). Letz  = LRS (w). Let |wa| = l and u1 , u2 , . . . , ul , ul+1 be the suﬃxes of wa orderedin their lengths, that is, u1 = wa and ul+1 = ε. We categorize these suﬃxes of
wa into the following three 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. It obviously takes
only constant time. 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 state corresponding to LRS (w) = z  = vi in DAWG(w), whichis called the active state of the current phase. A new transition labeled by a isinserted from the active state to the new sink state. The state to be the next
active state is found simply by traversing the suﬃx link of the state for vi , inconstant time, and a new transition labeled by a is created from the new active
state to the sink state. After we insert all the suﬃxes of Group 2 this way, theautomaton represents all the suﬃxes of wa.
We now pay attention to LRS (wa) = z = uj . Let x be the longest string inthe state where uj is accepted. We then have to check whether x = uj or not. If
not, the state is separated into two states, where one accepts the longer strings
than uj , and the other accepts the rest. Associating each state with the lengthof the longest string accepted in it, we can deal with this state separation inconstant time.
The on-line construction of DAWG(cocoao) is shown in Fig. 2.

3

Ternary Directed Acyclic Word Graphs

Bentley and Sedgewick [3, 2] introduced a new data structure called ternary
trees, which 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 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 most threetransitions.
The left ﬁgure in Fig. 3 is a ternary tree for Suﬃx (w) with w = cocoa. We
can see that this corresponds to STrie(w) in Fig. 1, and therefore, the tree iscalled a ternary 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. Thismeans that we can regard CharSetw (x) as a set of the states that immediately
follows string x in the TSTrie of w, where elements of CharSetw (x) are arrangedin lexicographical order, top-down. There are many variations of the arrangement of elements in CharSetw (x), but we arrange them in increasing order of
their leftmost occurrences in w, top-down. Thus the arrangement of the states

c
a

a

c

o

o

c

c

o
a

a

o
a

o

a

o

c
a

o
a

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

is uniquely determined, and the resulting structure is called the TSTrie of w, denoted by TSTrie(w). The state corresponding to the character in 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).
Given a pattern p, at any node of TSTrie(w) we examine if the character ain p we currently focus on is lexicographically larger than the character b stored
in the state. If a < b, then we take the left transition from the state and compare
a to 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 is recognized, andwe compare the next character in p to the character in the next state. We givea concrete example of searching for pattern oa using TSTrie(cocoa) in Fig. 3.
We start from the initial state of the tree and have o > c, and thus go down
to the next state via the right transition. At the next state we have o = o, andthus we take the center transition from the state and arrive at the next state,with the character o recognized. We then compare the next character a in thepattern with c in the state where we are. Now we have 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 and arrive at the next state, where ﬁnally oa
is accepted. This way, for any pattern p ∈ Σ ∗ we can solve the substring patternmatching 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ﬁgure in Fig. 3 is TDAWG(cocoa). Compare it to DAWG(cocoa) in Fig. 1 andTSTrie(cocoa) in Fig. 3. It is quite obvious that using TDAWG(w) we can
examine if p ∈ Substr (w) in O(log |Σ|·|p|) expected time, as well. Reasonably,
TDAWG(w) can be constructed by the on-line algorithm of Blumer et al. [4]that was recalled in Section 2. In TDAWG(w) only top states have suﬃx links,and can be directed by suﬃx links of other states.
The on-line construction of TDAWG(cocoa) is shown in Fig. 4.

ε

c

co
c

coc
c
o

c
o

o

o

c

coco

cocoa
c
o

cocoao
c

o

o

a

c
o

c
o

a

c
a

o
a

a

o

o

c

c

o

a

a
o

Fig. 4. The 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 are pointed
by 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.

Theorem 3. For any string w ∈ Σ ∗ , TDAWG(w) can be constructed on-line,in O(|Σ| · |w|) time using O(|w|) space.

4

Experiments

In this section we show some experimental results that reveal the advantage of
our TDAWGs, compared to DAWGs with tables (table DAWGs) and DAWGs
with linked lists (list DAWGs). The tables were implemented by arrays of length
256. The linked lists were linearly searched at any state of the list DAWGs. All
the three algorithms to construct TDAWGs, table DAWGs and list DAWGs
were implemented in the C language. All calculations were performed on a
Laptop PC with PentiumIII-650MHz CPU and 256MB main memory running
VineLinux2.6r2. We used the English text “ohsumed.91” available at http://trec.nist.gov/data.html.

[Mbyte]30[sec]

table_DAWG

20
Time

Memory space

200

TDAWG

list_DAWG
100

list_DAWG
10

TDAWG

0
0

200

400

0
0

[Kbyte]200

Text length

400[Kbyte]Text length

Space requirements of TDAWG and list_DAWG

Construction times of TDAWG, list_DAWG and table_DAWG[µsec]
0.6
list_DAWG

0.4
Time

TDAWG

0.2
table_DAWG

0
0

5

10

15

Pattern length
Search times of TDAWG, list_DAWG and table_DAWG

Fig. 5. The upper left chart is the memory requirements (in Mbytes) of TDAWGs andlist DAWGs. The upper right chart is the construction times (in seconds) of TDAWGs,
list DAWGs and table DAWGs. The lower chart is the searching time (in micro seconds) of TDAWGs, list DAWGs and table DAWGs.

The upper left chart of Fig. 5 shows memory requirements for TDAWGs
and list DAWGs, where memory spaces for both grow linearly, as expected. One
can see that TDAWGs require about 20% more memory than list DAWGs. The
memory requirement of table DAWGs is not shown since it is too much for the
scale of the chart. The table DAWG for the text of size 64KB required 98.82MB
of memory space, and that for the text of size 128KB needed 197.53MB. Thus
table DAWGs are rather unusable in reality.
The second test was the construction times for TDAWGs, table TDAWGs,
and list DAWGs, shown upper right of Fig. 5. One can see that the TDAWGs
were constructed about twice faster than the list DAWGs. This seems the eﬀectof binary search in the TDAWGs, while the linked lists were linearly searched in
the list DAWGs. As for the table DAWGs, though searching the transition canbe done in constant time, the memory allocation for the tables seemed to taketoo much time.
The third test was searching times for patterns of diﬀerent lengths. We randomly chose 100 substrings of the text for each length, and searched for every ofthem 1 million times. The result shown in the lower chart in Fig. 5 is the averagetime of searching for a pattern once. Remark that the TDAWGs are faster thanlist DAWGs, even for longer patterns.

5Conclusions and Further WorkIn this paper we introduced a new data structure called ternary directed acyclic
word graphs (TDAWGs). The process of binary search for the transitions is‘implanted’ in each state of TDAWGs. For any string w ∈ Σ ∗ , TDAWG(w) can
be constructed in O(|Σ| · |w|) time using O(|w|) space, in on-line fashion. Our
experiments showed that TDAWGs can be constructed much faster than both
DAWGs with tables and DAWGs with linked lists, for English texts. Moreover,searching time of TDAWGs is also better than that of DAWGs with linked
lists. Thinking over the fact that TDAWGs are better in speed than the twoother types of DAWGs though the alphabet size of the English text is only 256,TDAWGs should be a lot more eﬀective when applied to texts of large alphabet
such as Japanese, Korean, Chinese, and so on. We emphasize that the beneﬁtof the ternary-based implementation is not limited to DAWGs. Namely, it canbe 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 theexperimental results on TDAWGs, ternary suﬃx trees and ternary CDAWGs
are promising to perform very well in practice.
As previously mentioned, the search time for pattern p using DAWGs withlinked lists is O(|Σ| · |p|) in the worst case, but there is a way to improve it toO(log |Σ|·|p|) time with additional eﬀort for performing binary search. However,
it is not practical since the additional work consumes a considerable amountof time, and is not implementation-friendly. Further, it does not allow us to
update the input text sting since it is just an oﬀ-line algorithm. However, as for
TDAWGs, we can apply the technique of AVL trees [1] for balancing the statesof TDAWGs. In this scheme, the states for CharSetw (x) for any substring x are“AVL-balanced”, and thus the time to search for pattern p is O(log |Σ| · |p|)even in the worst case. The diﬀerence from DAWGs with linked lists is that we
can construct “AVL-balanced” TDAWGs in on-line manner, directly, and can
update the input text string easily. Moreover, the construction algorithm runsin O(log |Σ| · |w|) time unlike the case of linked lists requiring O(|Σ| · |w|) time.
Therefore, TDAWGs are more practical and ﬂexible for guaranteeing O(log |Σ| ·|p|)-time search in the worst case.
Moreover, there is a 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. 6, which is called the minimum

c
o
c
o
a

Fig. 6. The MTDAWG of string cocoa.

TDAWG (MTDAWG) of the string. To use Revuz’s algorithm we have to maintain the reversed transition for every transition, and it for sure requires toomuch space. Thus we are now interested in an on-line algorithm to construct
MTDAWGs directly, but it is still incomplete. We expect that searching for pattern strings using MTDAWGs will be faster than using TDAWGs, since memory
allocation for MTDAWGs is likely to be more quick.

References
1. G. M. Andelson-Velskii and E. M. 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. Theoretical Computer
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 LNCS, 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
A. Amir and G. M. Landau, editors, Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM’01), volume 2089 of LNCS, pages 169–180.
Springer-Verlag, 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.