Directed Acyclic Word Graphs andTheir Efficient Implementations

Shunsuke Inenaga
Department of Computer Science
University of Helsinki

Short CV
Shunsuke Inenaga
March 2003

PhD Kyushu University, Japan“String Processing Algorithms”

April – Sept. 2003 Posdoc of Japan Science Technology
Agency (JST)Sept. 2003 -Posdoc of Dep. of Computer Science,
University of Helsinki

http://www.i.kyushu-u.ac.jp/~s-ine/Pattern Matching Problem

Input: text string T and pattern string P.
Output: all occurrences of P in T.

When T is fixed

Text Indexing Structures

Text Indexing Structures
Text: cocoa

Suffix TriecocSuffix Tree

Compaction oaco occo a oaaaoca oa

Directed Acyclic
Word Graphac

Minimizationaococo

Minimizationacoaaaoaoa

Compaction
Compact Directed Acyclic
Word GraphaDirected Acyclic Word Graphs

cocoaoaa

The Directed Acyclic Word Graph(DAWG) of string w is the smallest
DFA that accepts all suffixes of w.

DAWG = Suffix Automaton

Conversion of Suffix Trie to DAWGbabcbbacbbcababcbcabcb

Merge isomorphic
subtreesbaccepting node for suffixes

Conversion to DAWGbabcbbacbbcbababcb

cabcb

Conversion to DAWG [Cont.]

babcbbacbbcbababcb

cabcb

Conversion to DAWG [Cont.]

babcbbacbbcbababcb

cabcb

Conversion to DAWG [Cont.]

baccabbacbcbcababcb

Conversion to DAWG [Cont.]

baccabbacbcbcababcb

Conversion to DAWG [Cont.]

babccababcbcababcb

Conversion to DAWG [Cont.]

babccababcbcababcb

Conversion to DAWG [Cont.]

bcacababcbcababcb

Conversion to DAWG [Cont.]

b?

caca?

babcbcababcb

DAWG Completedbcacababcbcababcb

Equivalence Class on DAWG

substrings x,y of w are recognizedby the same node of DAWG(w)iff
EndPosw(x) = EndPosw(y)EndPosw(x): the set of all positions of w where x ends

Equivalence Class on DAWG [Cont.]

bcaababcbca1 2 3 4 5 6babcb

EndPosw(aba) = {3}EndPosw(ba) = {3}cababaEquivalence Class on DAWG [Cont.]

bca1 2 3 4 5 6babababcbcabcbcab

EndPosw(ab) = {2,4}EndPosw(b) = {2,4,6}

Equivalence Class on Suffix Tree

babcbcbabcbababcbcbabcb

1 2 3 4 5 6aab

BegPosw(a) = {1,2}
BegPosw(ab) = {1,2}Size of DAWG
Theorem. (Blumer et al. 1985)
Let n = |w|.
If n > 1, DAWG(w) has at most 2n-1 nodes
and 3n-3 edges.
If n = 1, DAWG(w) has exactly 2 nodes
and 1 edge.

Construction of DAWG

Theorem. (Blumer et al. 1985)
Assume Σ is fixed.
For any string w of length n,DAWG(w) can be constructed on-line
and in O(n) time and space.

Suffix Links

bcaababcb

cababcbcababaSuffix Links

bcaababcb

ababcbcac

Suffix Links

bcacababcbcababcb

On-line Construction of DAWG
Σababcb

On-line Construction of DAWGΣaababcb

On-line Construction of DAWG
Σbabababcb

On-line Construction of DAWG
Σbabaababcb

On-line Construction of DAWG
Σbababababcb

On-line Construction of DAWG
Σbacbabccababcb

On-line Construction of DAWG
Σbacbabcbcababcb

On-line Construction of DAWG
Σbacbabcbcababcb

On-line Construction of DAWG
Σbacbabcbcababcb

On-line Construction of DAWG
Σbacbabcbcababcb

On-line Construction of DAWG
Σbacbabcbcababcb

Marking Accepting Nodes
Σbacbabcbcababcb

Marking Accepting Nodes
Σbacbabcbcababcb

Marking Accepting Nodes
Σbacbababcbabcbc

Completed!!

Search Tree of a Set of Strings?

Lnunctotw

yiemteh{Lunch, time, not, yet, now, ?}Table Implementation... ? ... L ...
?

t ... n ... y ... ...

Lnunchtotw

yiemteTable Implementation... ? ... L ...

t ... n ... y ... ...

Very fast search
Too much spaceunchotw

iemteLinked List Implementation?

Lnt

Slow search
Small spaceuontchw

yiemteTernary Search TreenL?

ot

Fast search
Small spaceunchtw

iymeetTernary Directed Acyclic Word Graphabbaabccb

ababcbc

Construction of TDAWG

Theorem. (Miyamoto et al. 2003)
For any string w of length n,TDAWG(w) can be constructed on-lineand in O(n|Σ|) time and O(n) space.

Ternary Directed Acyclic Word Graphabbaabccbababcb
cUnbalanced!

Using AVL Tree

AVL Balanced

Not AVL Balanced

Node Rotation

5531423615246

AVL DAWG
baababcbccababcb

Construction of AVL TDAWG

Theorem. (Miyamoto et al. 2003)
For any string w of length n,
AVL_TDAWG(w) can be constructed on-line
and in O(nlog|Σ|) time and O(n) space.

Complexities

spacetableO(| w | ⋅ | Σ |)search timeaverage caseworst caseO (| p |)O (| p |)linked list

O(| w |)

O (| p | ⋅ | Σ |)O (| p | ⋅ | Σ |)TDAWG

O(| w |)

O (| p | ⋅ log | Σ |)O (| p | ⋅ | Σ |)AVL-TDAWG

O(| w |)

O (| p | ⋅ log | Σ |)O (| p | ⋅ log | Σ |)

Experiment – Construction Times

EnglishJapaneseExperiment – Memory Space

EnglishJapaneseExperiment – Search Times

EnglishJapaneseCitations
A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht,
B. M. Chen, and J. Seiferas.
The smallest automaton recognizing the subwords of a text.
Theoretical Computer Science, 40:31-55, 1985.
M. Crochemore,Transducers and repetitions.
Theoretical Computer Science, 45(1): 63-86, 1986
S. Miyamoto, S. Inenaga, M. Takeda, and A. Shinohara
Ternary Directed Acyclic Word Graphs.
8th Int. Conference on Implementation and Application of Automata(CIAA 2003), Springer-Verlag LNCS 2759, pp. 121-130.
Also Accepted to Theoretical Computer Science