On-line Linear-timeConstruction ofWord Suffix Trees
Shunsuke Inenaga(Japan Society for the Promotion of Science& Kyushu University)

Masayuki Takeda(Kyushu University & JST)Pattern Searching Problem
Given：text T in Σ∗ and pattern P in Σ∗ Find：an occurrence of P in TΣ: alphabet∗ Σ : set of strings

Using an indexing structure for T, we can solve theabove problem in O(|P|) time.

Suffix Trie

A trie representing all suffixes of TT = 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 Searching Problem
Given: text T in D+ and pattern P in D+ Find: an occurrence of P in T which immediately
follows #

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

Word-level Pattern Searching Problem
Given: text T in D+ and pattern P in D+ Find: an occurrence of P in T which immediately
follows #e.g.
The#space#runner#is#not#your#good#pace#runner#

Word Suffix Trie

A trie representing the suffixes of T which
immediately follows # (and T itself).
T = aa#b#
aa#b#
a#b#
#b#
b#
#

#b

#

aab

#

Comparison
T = aa#b#

#b#

aa#
b#

#bb

#

#Suffix Trie#b#aabWord Suffix Trie#

ConstructionSuffix Trie ： Ukkonen’s on-line algorithm （1995）

Word Suffix Trie ： We modify Ukkonen’s algorithm by:
Using minimum DFA accepting dictionary D

Redefining suffix links

Minimum DFA

The minimum DFA accepting D = Σ∗ # clearlyrequires constant space (for fixed Σ).
Σ#

We replace the root node of the suffix trie with thefinal state of the DFA.

Suffix Links
T = aa#b#

a,b

#
#

aa

#

bb

Word Suffix Trie#Suffix Links [cont.]
T = aa#b#

#b#aa
#b#

#bb

#

#

#

Suffix Triea,b#aa#bb

Word Suffix Trie#

On-line Construction
T = aa#b#

a,b
Σ, #

#aa

Suffix Trie

Word Suffix Trie

On-line Construction
T = aa#b#a,b
Σ, #aaSuffix Trieaa#

Word Suffix Trie

On-line Construction
T = aa#b#

a,b
Σ, #

#

aa
#

#

Suffix Trie#aa#

Word Suffix Trie

On-line Construction
T = aa#b#

a,b
Σ, #

b

#

aa
#
b

#bb

Suffix Trie#aa#bbWord Suffix Trie

On-line Construction
T = aa#b#

a,b
Σ, ##b#aa#b##bb###Suffix Trie#aa#bbWord Suffix Trie#

Pseudo CodeΣ,#

Just change here!!

##bb#aa#b#

#aa

#

#bb

#

#

#a,bb

#

Drawback of Word Suffix Trie

Word suffix tries require O(k|T|) space.
Andersson et al. introduced word suffix trees which
can be implemented in O(k) space.

Construction of Word Suffix Trees

Algorithm by Andersson et al.（1996）


for text T = T1T2…Tk, constructs word suffix trees inO(|T|) expected time with O(k) space.

Our algorithmsimulates the on-line word suffix trie algorithm on wordsuffix trees.
runs in O(|T|) time in the worst cases, with O(k) space.

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

b

#

a

#
b
#

#
b
#

#b

Suffix Tree

##b

#

aab

#

Word Suffix Tree

Construction Algorithm
Just change here!!

Conclusions
We first proposed an on-line word suffix trie
construction algorithm.
The keys to the algorithm are the minimal DFA
accepting D and the re-defined suffix links.

Further, we introduced an on-line algorithm to build
word suffix trees that works with O(k) space and inO(|T|) time in the worst cases.

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