LATIN 2020

Suffix Trees, DAWGs and CDAWGs
for Forward and Backward Tries
Shunsuke Inenaga
Kyushu University, JapanLabeled TreesA string is a sequence of characters, which is equivalent
to a single path where each edge is labeled.
A labeled tree is a generalization of a string which has
branches, and it can also be seen as a compact
representation of a set of strings.
stringequivalentc

cabbc
set of strings

cababcabbc
cabbb

single pathcompacted

alabeled treecabbcbab b cb

generalized

Labeled Tree Indexing ProblemWe deal with the indexing version of the patternmatching problem on labeled trees (a.k.a. tries).
Problem
Preprocess input: A trie T.
Query input: A pattern string P.
Query output: Every sub-path of T that matches P.

We consider two version of tries:
Forward Tries: paths are read from root to leaves.
Backward Tries: paths are read from leaves to root.

Indexing Forward/Backward Tries
Backward Trie T R

Forward Trie Tcaab brootPattern P = a bbcleavesb

Partial DFA that accepts
all substrings of T .

DAWG(T )babbaac ab b cbabcbbcbac b bleavesabcroot

Pattern P R = b a
Partial DFA that accepts
all substrings of T R .

RDAWG(T )bcababacbacbacbac

Indexing Forward TriesThree kinds of indexing structures
for Forward Trie T.
Partial DFA that accepts
all substrings of T .

DAWG(T )babbaac ab b cbabcbbc

SuffixTree(T )b bacbbbac a b abbb ab bccabbab
Compact DAG representingababc
all substrings of T .
bbabcbCDAWG(T ) c b

Compact trie representing
all substrings of T .

cbbc

Indexing Backward Tries
Three kinds of indexing structures
Rfor Backward Trie T .
DAWG(T R )bcababCompact trie representing
all substrings of T R .

Partial DFA that accepts
all substrings of T R .

acbca

SuffixTree(T R )cbacbacbcb

Compact DAG representing
all substrings of T R .
RCDAWG(T )acbaabbacbaccb ba cabaabcbacbaccbbacbacDAWGs (Directed Acyclic Word Graphs)
A substring (i.e. sub-path) X of a forward trie T is said tobe left-maximal if (1) there are two distinct characters a, b
such that both aX and bX are substrings of T, or (2) X has
an occurrence begging at the root of T .

Forward Trie Tcaab b

DAWG(T )bcbbababbaac ab b cbabcbbccabaababaThis generalizes Blumer et al.’s DAWGs for strings to trees.
R DAWGs for backward tries T are defined similarly.
Suffix TreesA substring (i.e. sub-path) X of a forward trie T is said tobe right-maximal if (1) there are two distinct charactersa, b such that both Xa and Xb are substrings of T, or(2) X has an occurrence ending at a leaf of T .

Forward Trie Tcaab bbcb

SuffixTree(T )b bacbbba
ac a bbbb ab bccbc

abbccabca

This generalizes Weiner’s suffix trees for strings to trees.
R Suffix trees for backward tries T are defined similarly.
CDAWGs (Compact DAWGs)
A substring (i.e. sub-path) X of a forward trie T is said tobe bi-maximal if X is both left-maximal and right-maximalin T .

Forward Trie Tcaab b

CDAWG(T )bcbabbabbc ab abbabcbbcb

cabab
cabab
cabab
caba
cabab
cabab

Intuitively, CDAWGs are mixture of DAWGs and Suffix Trees.
 This generalizes Blumer et al.’s CDAWGs for strings to trees.
R CDAWGs for backward tries T are defined similarly.
Sizes of Indexing Structures for Tries
Size Bounds of Indexing Structures for Tries (Existing Work)
Forward Trie T

upperboundsBackward Trie T

RIndex. structures# nodes# edges# nodes# edges

DAWG

Ο(n)

−−−

CDAWG

−−−−

Suffix Tree−

−

Ο(n)

Ο(n)

Suffix Array−n−1
n is # of nodes in the input trie.

Sizes of Indexing Structures for Tries
Size Bounds of Indexing Structures for Tries (This Work)
Forward Trie T

upperboundsBackward Trie TR

Index. structures# nodes# edges# nodes# edges

DAWG2n−3

Ο(n2)

Ο(n2)

Ο(n2)

CDAWG

2n−3

Ο(n2)

2n−32n−4

Suffix Tree

Ο(n2)

Ο(n2)

2n−32n−4

Suffix Array

Ο(n2)

n−1
n is # of nodes in the input trie.

Note: For a string (i.e. path tree) with n characters,
the sizes of these indexing structures are all O(n).

Matching Upper/Lower Bounds
Size Bounds of Indexing Structures for Tries (This Work)
Forward Trie Tupperbounds

RIndex. structures# nodes# edges# nodes# edges

DAWG

2n−3

Ο(n2)

Ο(n2)

Ο(n2)

CDAWG

2n−3

Ο(n2)

2n−32n−4

Suffix TreeΟ(n2)

Ο(n2)

2n−3

2n−4

Suffix Arraylowerbounds

Backward Trie T

Ο(n2)

n−1

Forward Trie T

Backward Trie TR

Index. structures# nodes# edges# nodes# edges

DAWG

2n−3

Ω(n2)

Ω(n2)

Ω(n2)

CDAWG

2n−3

Ω(n2)

2n−32n−4

Suffix Tree

Ω(n2)

Ω(n2)

2n−32n−4

Suffix Array

Ω(n2)

n−1

Linear-size Indexing for Forward Tries
Size Bounds of Indexing Structures for Tries (This Work)
Forward Trie Tupperbounds

Backward Trie TR

Index. structures# nodes# edges# nodes# edges

DAWG2n−3

Θ(n2)

Θ(n2)

Θ(n2)

CDAWG

2n−3

Θ(n2)

2n−32n−4

Suffix Tree

Θ(n2)

Θ(n2)

2n−32n−4

Suffix Array

Θ(n2)

n−1

Theorem [This Work]
There exists an Ο(n)-size compact representation of theDAWG for forward trie T which can be built in O(n) time.
Also, this compact representation supports bidirectional
pattern matching queries on the trie in O(m log σ + occ) time.
n: # nodes in T ，m: pattern length，σ: alphabet size，occ：# pattern occurrences

RConnections of DAWG(T ) and SuffixTree(T )DAWG(T )babbaac ab b cbabcbbc

SuffixTree(T R )cabaabababcabaabcbacbaccbbac

bac

There is a one-to-one correspondence between the nodes
Rof DAWG(T ) and the nodes of SuffixTree(T ), but there
is no such correspondence between their edges.

abacabaabRSimulating DAWG(T ) edges with SuffixTree(T )We can simulate all the O(n2) edges of DAWG(T )Rwith SuffixTree(T ) using only O(n) space.
Decompose SuffixTree(T R ) intoO(n/σ) clusters, O(σ)-size each,where σ is the alphabet size.

Store carefully-selected DAWG
edges in each cluster,so that the other DAWG edges
can be retrieved upon query.

Conclusions and Open Question

We have shown a complete perspective on the size
bounds of classical indexing structures for forward tries
and backward tries.
We can simulate the DAWG for a forward trie with thesuffix tree for a backward trie, using O(n) space.
Can we simulate the CDAWG for a forward trie with theCDAWG for a backward trie, using O(n) space?
Forward Trie T

Backward Trie T

RIndex. structures# nodes# edges# nodes# edges

DAWG

2n−3

Θ(n2)

Θ(n2)

Θ(n2)

CDAWG

2n−3

Θ(n2)

2n−3

2n−4

Suffix Tree

Θ(n2)

Θ(n2)

2n−32n−4

Suffix ArrayΘ(n2)n−1