Sparse Directed Acyclic
Word Graphs
Shunsuke Inenaga(Kyushu University)

Masayuki Takeda(Kyushu University & Japan Science Technology Agency)

Contents
 Basic Pattern Matching Problem
 Text Indexing Structures

 Natural Language Text Search Phrase-level Pattern Matching Problem

 Sparse Text Indexing Structures

 Sparse Directed Acyclic Word Graphs
 Size Construction

 Summary and Future WorkBasic Pattern Matching Problem

Input: text T from S* and pattern P from S*
Output: whether or not P occurs in T
S : alphabet (set of characters)
S* : set of strings

 Text indexing structures for T enable us to solve thisproblem in O(m) time (for fixed alphabet S).

m : the length of pattern PText Indexing Structures
T = aacbc

aacc
compaction

accbaccbcbbbc

suffix nodebbc
minimization

caccccacsuffix triebcc
minimizationcompactiona(compact DAWG)

bbcc

suffix treea cbccb
CDAWG cbbcbc

DAWG(directed acyclicword graph)Sizes of Indexing Structures

max num of nodes

max num of edges

suffix triesn(n+1)/2 + 1n(n+1)/2suffix trees

2n-1

2n-2

DAWGs

2n-13n-4

CDAWGsn+12n-2n : text length

Contents
 Basic Pattern Matching Problem
 Text Indexing Structures

 Natural Language Text Search Phrase-level Pattern Matching Problem

 Sparse Text Indexing Structures

 Sparse Directed Acyclic Word Graphs
 Size Construction

 Summary and Future Work

Considering Natural Language Texts
 T = “string processing and information retrieval”

 We seldom want to search from the inside of words,

we only want to search from the head of words.
 Indexing all the suffixes of text T is a waste of space Unwanted matching (see below) should be avoidede.g. P = ring processing

Introducing Word Separator # # : word separator - special symbol not in S
 D = S* # : dictionary of words Let text T be an element of D+(T is a sequence T1T2…Tk of k words from D) e.g., T = This#is#a#pen# S = {A, …, z} D = {..., This#, ..., a#, ..., is#, ..., pen#, ...}

Sizes of Sparse Indexing Structures

max num of nodes

max num of edgesword suffix triesk(n+2)/2 + 1

k(n+2)/2word suffix trees

2k-1

2k-2

SDAWGs?

?

SCDAWGs

k+1

2k-2
n : text lengthk : number of words in text
Note that k ≦ nPhrase-level Pattern Matching Problem
Input: text T from D+ and pattern P from D+
Output: whether or not P occurs
at the head of a word in T

 To solve the above problem, we want a “sparse”

text indexing structure that represents only thesuffixes of T beginning at the head of a word in T.

Word Suffix Trie
 A trie which represents only the suffixes of T

beginning at the head of a word in T
T = aa#b#
aa#b#
a#b#
#b#
b#
#aa#b

#b

#

Sparse Text Indexing Structures
T = aa#b#

aasuffix nodeb##
compaction

b

#

ba
#

a

minimizationb##word suffix trie
(Inenaga & Takeda ‘06)

minimization

word suffix tree
(Andersson et al. ‘99)

Sparse CDAWG(Inenaga & Takeda ‘06)

compaction

aa
#b
#b#?
Sparse DAWG(This work)

Contents
 Basic Pattern Matching Problem
 Text Indexing Structures

 Natural Language Text Search Phrase-level Pattern Matching Problem

 Sparse Text Indexing Structures

 Sparse Directed Acyclic Word Graphs
 Size Construction

 Summary and Future Work

Sparse Directed Acyclic Word Graph
T = aa#b#
aabaa#b#minimization

b#b#

#

Word Suffix Trie

Sparse DAWG(SDAWG)

Comparing Normal and Sparse DAWGs

T = aa#b#

suffixes of T
aa#b#
a#b#
#b#
b#
#

aa
#

ab

#b

#

ab
#
bb
##

DAWG

Sparse DAWG(SDAWG)

Size of SDAWGs – Lower Bound
Theorem:
The SDAWG of any text T of length n
has at least n+1 nodes.
aT = aa#b#

ab#b#

Size of SDAWGs – Upper Bound

Theorem:
The SDAWG of any text T of length n has
O(n) nodes and edges.

Shown by similar ideas to Blumer et al.
for the size of DAWGs (1985)

Sizes of Sparse Indexing Structures
max num of nodes

max num of edges

total spacecomplexity

word suffix triesk(n+2)/2 + 1

k(n+2)/2O(kn)word suffix trees

2k-1

2k-2

O(n)

SDAWGs

O(n)

O(n)

O(n)

SCDAWGsk+12k-2O(n)Word suffix trees and SCDAWGs
need the original text to be kept

n : text lengthk : number of words in text
Note that k ≦ n

SDAWG Construction
 SDAWGs can be constructed by minimizing word

suffix tries in O(kn) time.
 using Revuz’s DAG minimization algorithm (1992)

 Question : Is direct construction of SDAWGs

possible?
 Answer : YES!

Using minimum DFA accepting dictionary D = S*# ,we can directly build SDAWGs in O(n) time.

Minimum DFA Accepting Dictionary D The minimum DFA accepting D = S* # clearlyrequires constant space (for fixed S).
S#Modification of DAWG Construction Algorithm
 Bluer et al. proposed an on-line O(n)-time algorithm

to construct normal DAWGs (1985).
 We modify their algorithm by: replacing the source node of the DAWG with the final

state of the DFA; setting the suffix link of the source node of the DAWG
to the initial state of the DFA.
 Then the resulting algorithm constructs SDAWGs in

on-line manner and in O(n) time!

Modification of DAWG Construction Algorithm

Just change here!!

On-line Construction of SDAWG
S

T = aa#b#b...
#aOn-line Construction of SDAWG
S

T = aa#b#b...
#aa

On-line Construction of SDAWG
S

T = aa#b#b...
#aa#

On-line Construction of SDAWG
S

T = aa#b#b...
#aa#bbOn-line Construction of SDAWG
S

T = aa#b#b...
#aa
#b
#b

On-line Construction of SDAWG
S

T = aa#b#b...
#aa#b
#bb

On-line Construction of SDAWG
S

T = aa#b#b...
#aab

#b#b#

Contents
 Basic Pattern Matching Problem
 Text Indexing Structures

 Natural Language Text Search Phrase-level Pattern Matching Problem

 Sparse Text Indexing Structures

 Sparse Directed Acyclic Word Graphs
 Size Construction

 Summary and Future WorkSummary We introduced new sparse text indexing structure,

Sparse Directed Acyclic Word Graphs (SDAWGs),
that are useful for word- and phrase-level search on
natural language texts.
 We showed that SDAWGs require O(n) space.

 We developed an on-line SDAWG construction

algorithm running in O(n) time and space (for fixedS).

Future Work
 Exact max numbers of nodes and edges of SDAWGs.

max num of nodes

max num of edges

word suffix triesk(n+2)/2 + 1k(n+2)/2

word suffix trees

2k-1

2k-2

SDAWGsO(n)O(n)

SCDAWGs

k+1

2k-2

 Experiments to evaluate practical space economy ofSDAWGs in comparison to normal DAWGs and othersparse indexing structures.

Future Work [cont.]
 Constructing SDAWGs for an arbitrary subset ofsuffixes.
 Given: text T and subset S of the positions in T
 Construct: SDAWG representing only the suffixes

starting from the positions in S