Sparse Compact Directed
Acyclic Word Graphs
Shunsuke Inenaga(Japan Society for the Promotion of Science& Kyushu University)

Masayuki Takeda(Kyushu University& Japan Science and Technology Agency)

Traditional Pattern Matching Problem
Given：text T in Σ∗ and pattern P in Σ∗ Return：whether or not P appears in TΣ: alphabet (set of characters)∗ Σ : set of strings

A text indexing structure for T enables you to solve
the above problem in O(m) time (for fixed Σ).
m: the length of P

Suffix Trie

A trie representing all suffixes of T
T = aacb$aacb$
acb$
cb$
b$
$$bcaacb$cb$$b$

Introducing Word Separator ## : word separator - special symbol not in Σ D = Σ∗ # : dictionary of words

Text T : an element of D+(T is a sequence T1T2…Tk of k words in D)
e.g., T = This#is#a#pen#Σ = {A,…,z} D = {...,This#,...,a#,...is#,...pen#,...}
Word-level Pattern Matching Problem
Given: text T in D+ and pattern P in D+ Return: whether or not P appears at the beginningof any word in T

e.g.
T = The#space#runner#is#not#your#good#pace#runner#
P = pace#runner#

Word-level Pattern Matching Problem
Given: text T in D+ and pattern P in D+ Return: whether or not P appears at the beginningof any word in Te.g.
T = The#space#runner#is#not#your#good#pace#runner#
P = pace#runner#

Word Suffix Trie

A trie representing the suffixes of T which begin ata word.
T = aa#b#
aa#b#
a#b#
#b#
b#
##b#aab#Normal and Word Suffix Tries
T = aa#b##b#aa#b#

#bb

#

#

Normal Suffix Trie

#b#

aab

Word Suffix Trie#Normal and Word Suffix Trees
T = aa#b#a#b#a#b##b#b#

Normal Suffix Tree

#b#

aab

#

Word Suffix Tree

Sizes of Word Suffix Tries and Trees

For text T = T1T2…Tk of length n,the word suffix trie of T requires O(nk) space, but

the word suffix tree of T requires O(k) space!!
because the word suffix tree has only k leaves andhas only branching internal nodes.

Construction of Word Suffix Trees

Algorithm by Andersson et al.（1996）


for text T = T1T2…Tk of length n, constructs word suffix
trees in O(n) expected time with O(k) space.

Our algorithm (CPM’06)
builds word suffix trees in O(n) time in the worst case,with O(k) space.

Our Construction Algorithm

We modify Ukkonen’s on-line normal suffix tree
construction algorithm by using minimum DFA
accepting dictionary D

We replace the root node of the suffix tree with the final
state of the DFA.

Minimum DFAThe minimum DFA accepting D = Σ∗ # clearlyrequires constant space (for fixed Σ).
Σ#On-line Construction of Word Suffix Trees
T = aa#b#a,ba#

On-line Construction of Word Suffix Trees
T = aa#b#a,ba#

On-line Construction of Word Suffix Trees
T = aa#b#a,b#aa

On-line Construction of Word Suffix Trees
T = aa#b#a,b#aa

On-line Construction of Word Suffix Trees
T = aa#b#

a,b
#

#aa

On-line Construction of Word Suffix Trees
T = aa#b#a,b##aaOn-line Construction of Word Suffix Trees
T = aa#b#a,b#

b#

aab

On-line Construction of Word Suffix Trees
T = aa#b#

a,b#b#aabOn-line Construction of Word Suffix Trees
T = aa#b#

a,b
#

#

b#

aab

#

Pseudo-Code
Just change hereCompact Directed Acyclic Word Graphs
T = aa#b#
a#b

#

a#
b#

#b#

Suffix Treeba#
minimization

a #b#
#b
#

#
b#

b
#

Compact Directed Acyclic
Word Graph (CDAWG)

Sparse CDAWGs
T = aa#b#

#b#

aab#

Word Suffix Treeminimization

aa#b#b#Sparse Compact Directed Acyclic
Word Graph (SCDAWG)

Sparse CDAWGs [cont.]
T = a#b#a#bab#
a#b#
a#
bab#

a#bb#
aa#
bb#
ab#

Word Suffix Treeab#minimization

#a#
bab#

bab#

SCDAWGSCDAWG Construction

SCDAWGs can be constructed by minimizing word
suffix trees in O(k) time.
using Revuz’s DAG minimization algorithm (1992)

SCDAWG Construction [cont.]
Question : Direct construction for SCDAWGs?
Answer : YES!
Using minimal DFA accepting dictionary D,
we can directly build SCDAWGs in O(n) time andO(k) space.
We modify the CDAWG on-line construction algorithm(Inenaga et al. 05) by using the above DFA.

Pseudo-Code
Just change here

Σ,#aa ## bb ###b#b#

Different structures#

Body is the same!!

aa
#b
#a,bb
#

Some Events

Basically on-line construction of SCDAWGs issimilar to that of word suffix trees.
Except for the two following unique events:Edge merging
 Node splittingEdge Merging

a,b

T = a#b#a#bab#bc...

#
#b#
a#bab
#
a#b

Edge Merging

a,b

T = a#b#a#bab#bc...

#
#
b#
a#
baab
#
a#ba

Edge Merging

a,b

T = a#b#a#bab#bc...

#
#
b#
a#
baaba

#
a#ba

Edge Merging

a,b

T = a#b#a#bab#bc...

#a#
b#
a#
baba

Node Splittinga,b

T = a#b#a#bab#bc...

#
a#
b#
a#bab
#bab
#

Node Splittinga,b

T = a#b#a#bab#bc...

#a#b#
a#
bab#
bbab#bNode Splittinga,bT = a#b#a#bab#bc...
a#b#b##aa a#b#b#abb ba#bb#
bab#bConclusion

We introduced new text indexing structure sparsecompact directed acyclic word graphs(SCDAWGs) for word-level pattern matching.
We presented an on-line algorithm to construct
SCDAWGs directly, in O(n) time with O(k) space.
The key is the use of minimum DFA accepting
dictionary D.

Related Work“Sparse Directed Acyclic Word Graphs”
by Shunsuke Inenaga and Masayuki Takeda
Accepted to SPIRE’06