TCS -TR-A-11-51

TCS Technical Report

Sparse and Truncated Suﬃx Trees on Variable-Length
Codes

by

Takashi Uemura and Hiroki Arimura

Division of Computer Science
Report Series A
March 28, 2011

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

arim@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7680+81-011-706-7680

Sparse and Truncated Suﬃx Trees on
Variable-Length Codes
Takashi Uemura1 and Hiroki Arimura1
Graduate School of Infomration Science and Technology, Hokkaido University
Kita 14, Nishi 9, Kita-ku, Sapporo, 060-0814 Japan{tue,arim}@ist.hokudai.ac.jp

Abstract. The sparse suﬃx trees (SST), introduced by (Kärkkäinen
and Ukkonen, COCOON 1996), is the suﬃx tree for a subset of all sufﬁxes of an input text T of length n. In this paper, we study a special
case that an input string is a sequence of codewords drawn from a regular preﬁx code ∆ ⊆ Σ + recognized by a ﬁnite automaton, and index
points locate on the code boundaries. In this case, we present an online
algorithm that constructs the sparse suﬃx tree for an input string t on
any variable-length regular preﬁx code, called the code suﬃx tree (CST),in O(n + m) time and O(k) additional space for a ﬁxed base alphabet Σ,
where m is the size of an automaton for ∆. Furthermore, we present a
modiﬁed algorithm for k-truncated version of code suﬃx trees that runsin the same time and space complexities. Hence, these results generalize
the previous results (Inenaga and Takeda, CPM 2006) for word suﬃx
trees and (Na, Apostolico, Iliopoulos, and Park, Theor. Comp. Sci., 304,
2003) for truncated suﬃx trees on arbitrary variable-length regular preﬁx
codes.

1

Introduction

Backgrounds The sparse suﬃx trees (SST), introduced by Kärkkäinen andUkkonen [11] in 1996, is the suﬃx tree (ST) [6, 13, 17] for storing a subset consisting of k suﬃxes in an input text T of length n on a base alphabet Σ, wherek ≤ n. In its most general form, the set I = {i1 , . . . , ik } ⊆ {1, . . . , n} of index
points which is given as an arbitrary subset of all n text positions. We denoteby SSTI (T ) the sparse suﬃx tree for T with respect to the set I of index points.
[11] showed that a sparse suﬃx tree on a k-evenly indexed string in O(n) worstcase time and O(k) space. Although a sparse suﬃx tree for a string with anarbitrary index set is well-deﬁned in any sense, interestingly enough, it is still
open since its introduction whether a sparse suﬃx tree for arbitrary set I of kindex positions can be constructed in O(n) time and O(k) additional space.
For the problem, recently, a collection of word-based suﬃx indexes have been
introduced [3, 5, 8–10]. To formalize this notion, we introduce the set ∆I (T ) ⊆Σ + of words, called the induced code, obtained by partitioning an input text T
by the index positions in I. Then, a suﬃx index is called word-based if the set∆I (T ) is restricted to a set of words in Σ + W , where W is a ﬁnite set of symbols,
1called word delimiters, such that W ∩ Σ = ∅. In 1999, Andersson, Larsson, andSwanson [3] introduced a word-suﬃx tree as a SSTI (T ) on a word alphabet,and presented a construction algorithm in O(n) average time and O(k) space.
In 2006, Inenaga and Takeda [8] presented the ﬁrst construction algorithm thatruns in O(n) worst-case time and O(k) space by modifying Ukkonen’s linear time
online construction algorithm for full suﬃx trees [17]. Their work is most closely
related to this work. Ferragina and Fischer [5] introduced word-suﬃx arrays andpresented a construction algorithm with O(n) worst-case time and O(k) space.
Our contribution. In this paper, we study the sparse suﬃx tree construction in more general setting than that of the word-based suﬃx trees [3, 8]. In
particular, we consider the sparse suﬃx tree for a string on an arbitrary regularpreﬁx code ∆ ⊆ Σ + which is recognized by a ﬁnite deterministic automaton.
The sparse suﬃx tree of this type is called the code suﬃx tree (CST), and anatural generalization of word suﬃx trees [3, 8]. As a main result of this paper,
we show that the code suﬃx tree for an input string T of length n on a preﬁx
code ∆ can be constructed in O(n + m) worst-case time and O(k) space for aﬁxed base alphabet Σ, where k is the number of words in T and m is the size ofthe automaton for ∆ (Theorem 2).
Key techniques. To show this, we propose a modiﬁed version of Ukkonen’s
online suﬃx tree construction algorithm [17] augmented with a DFA, called acode automaton, for recognizing ∆, which is similar to the construction in [8].
However, the proofs for correctness and time complexity are not straightforward
due to the complex behavior of the algorithm when it traverses inside of a code
automaton. To overcome this diﬃculty, we introduce an extended domain ofstrings augmented with the erasing element ⊥, which is the inverse of any codeword in ∆ and acting from left. Using ⊥, we give a general deﬁnition of suﬃx
links, and show that most properties of full suﬃx trees [17], including the existence lemma for suﬃx links, still remains valid when ∆ is a preﬁx code. Hence,
Theorem 2 above gives a partial answer to a natural question: what is the largest
class of codes for which the approach of Ukkonen’s linear-time construction algorithm [17] is suﬃcient for constructing sparse suﬃx trees on a code?
An extension. For every ℓ ≥ 1, an ℓ-truncated suﬃx tree (ℓ-TST) for T isa variation of suﬃx trees that stores all factors of T with length ℓ. Na et al. [14]introduced ℓ-TST and presented an online construction algorithm in O(n) timeand space. Based on the algorithm for CST, we present a modiﬁed version of
the algorithm for ℓ-truncated code suﬃx trees (ℓ-TCST) that constructs ℓ-TCST
for a text on ∆ in O(n) worst-case time and O(k) space, where k is the numberof words in T (Theorem 3). Finally, we ran experiments on real datasets toevaluate the usefulness of the proposed methods. For example, CSTs are 3 to 5
times smaller than STs on English and UTF-8 texts.
Organization of this paper. In Sec. 2, we give basic deﬁnitions. In Sec. 3,
we present our linear-time construction algorithm ConstructCST for code suﬃx
trees. In Sec. 4, we extend the algorithm for ℓ-truncated code suﬃx trees. In
Sec. 5, we show experimental results, and in Sec. 6, we conclude this paper.
2

⊥

⊥

Σ

0x00-0x7f

⊥
Σ

#

＼{#}

0

⊥

10xxxxxx 0x00-0x7f

1
1
0

ε

ε

ε

ε

∆1

∆2

∆3

∆4

⊥

0b110xxxxx
0b1110xxxx
0b11110xxx

10xxxxxx
10xxxxxx

ε∆5Fig. 1. The code automata for preﬁx codes ∆1 , ∆2 , ∆3 , ∆4 , and ∆5 in Example 1,
where ⊥ and ε are the initial and the ﬁnal states, respectively, and labels with wildcard
x ∈ {0, 1}, e.g., 0x00 − 0x7f , represent sets of the corresponding multiple edges.

2

Preliminaries

Basic deﬁnitions. We introduce basic deﬁnitions on suﬃx trees according to [4,6, 11, 14, 17]. We assume that the reader has basic knowledge of the linear time
construction algorithm by Ukkonen [17]. Let Σ be an alphabet of base letters.
We denote by ε the empty string. Let Σ ∗ and Σ + denote the sets of all possibly
empty ﬁnite strings and non-empty ﬁnite strings on Σ. For a string T , if T = xyz
for some x, y, z ∈ Σ ∗ , then we call x, y, and z a preﬁx , a factor (substring), anda suﬃx of T , respectively. Let T = a1 · · · an ∈ Σ ∗ be a string on Σ of length|T |Σ = |T | = n, where T [i] = ai ∈ Σ is the i-th letter for every i = 1, . . . , n.
For any 1 ≤ i ≤ j ≤ n, we denote by T [i..j] = ai · · · aj the factor from i to j of
T . If i > j then we deﬁne T [i..j] = ε. For a set S ⊆ Σ ∗ of strings, the sets ofthe preﬁxes and proper preﬁxes of all strings in S are denoted by Pre(S) and by
PropPre(S), respectively. |S| and ||S|| denote the cardinality and the total size of
S. For strings x, y, we denote by lcp(x, y) the longest common preﬁx of x and y.
Preﬁx Codes. A code is a set ∆ ⊆ Σ + , where each w ∈ ∆ is a non-empty
string, called a codeword (or word , for short) of ∆. A preword is any preﬁxu ∈ Pre(∆) and a proper preword is any proper preﬁx u ∈ PropPre(∆) of a wordin ∆. A code ∆ is either inﬁnite or ﬁnite. ∆ is a preﬁx code if it is preﬁx-free,that is, any codeword is not a preﬁx of some other codeword of ∆.
Example 1. Let Σ be a letter alphabet and B = {1, 0} be a binary alphabet. A
trivial preﬁx code ∆1 = Σ and the ASCII code ∆2 = [0x00 − 0x7f ] ⊆ B8 are
preﬁx codes of ﬁxed-length. For a word delimitor ♯ ̸∈ Σ, a word alphabet ∆3 =
Σ + ♯ is an example of preﬁx-codes of variable-length ([3, 5, 8–10]). A Huﬀman
code ∆4 = {00, 01, 1} for the set of symbols {A, B, C} with probabilities p(A) =1/4, p(B) = 1/4, p(C) = 1/2 ([4]), and the code ∆5 = (10B1 ) ∪ (110B2 ) ∪(1110B3 ), called the three-byte fragment of UTF-8 ([7]), are also examples of
preﬁx-codes of variable-length. As seen later, all of these preﬁx codes are regular(Fig. 1).
Codeword strings. A word string on ∆ (or ∆-string) is a string T ∈ ∆∗ .
Then, an input string or a pre-string of letter length n ≥ 0 is any preﬁx T =3

T [1] · · · T [n] ∈ Pre(∆∗ ) of a word string on ∆, where T [i] ∈ Σ for i = 1, . . . , n.
Since ∆ is a preﬁx code and thus Pre(∆∗ ) = ∆∗ PropPre(∆), we have the unique∆-factoring T = w1 · · · wk wk+1 ∈ Pre(Σ ∗ ) of T , where w1 , . . . , wk ∈ ∆ andwk+1 ∈ PropPre(∆). Then, the proper preword wk+1 is called the tail of T .
Clearly, T is a complete word string if and only if the tail wk+1 is emtpy. We
deﬁne the word length of T by |T |∆ = k, and the letter length by |T |Σ = |T | = n.
∑k+1
where n = i=1 |wi |.
In this paper, construction of a CST is done in online manner through thestage i = 0, . . . , n as in [15, 17]. We deﬁne the current input T i = T [1] · · · T [i] =w1 · · · wk wk+1 , where k ≥ 0, wj ′ ∈ ∆, and wk+1 ∈ PropPre(∆). Let j =1, . . . , k + 1 be any index. The j-th ∆-suﬃx of T is deﬁned as the suﬃx ofT starting at the j-th word boundary, i.e., suf ∆j (T ) = wj · · · wk wk+1 . For ℓ ≥ 1,
the j-th (∆, ℓ)-factor of T is deﬁned as the factor fac∆,ℓj (T ) = wj · · · wh of T ,∆where h = min{j + ℓ − 1, k + 1}. We denote by Suf (T ) and Fac∆ (T, ℓ) the setsof all ∆-suﬃxes and all (∆, ℓ)-factors of T , respectively.
Code suﬃx trees. A code suﬃx tree (CST, for short) for an input string
T ∈ Pre(∆∗ ) w.r.t. a preﬁx code ∆, denoted by CST∆ (T ), is a compacted trie [6]that represents all ∆-suﬃxes of T . Formally, the CST for T is a rooted tree S =CST∆ (T ) = (V, child, root, Label(·), SL(·)) that satisﬁes the following properties.
V is a ﬁnite set of tree nodes (or nodes). Each directed edge e = (u, v) is labeledwith a factor of T , Label(v) ∈ Σ + , stored in v. Every internal node except
the root is branching, i.e., it has at least two children. For every base lettera ∈ Σ, each internal node v has at most one directed edge from v to the achild , u = child(v, a), whose label starts with a. SL(·) is a suﬃx link function,
which will be deﬁned later in Section 3. For each v, we denote by L(v) the string
represented by v, that is, the string obtained by concatenating all labels on thepath from the root to v. All the suﬃxes are represented by the leaves of CST∆ (T )when T ends with the unique marker T [n] that does not appear elsewhere. All
the factors in T that start at word boundaries are represented as the preﬁxes
of all leaves, that is, the elements of the set str(tree) = Pre(Suf ∆ (T)). We givethe naming function [·] below. For any α ∈ str(tree), we deﬁne the locus of α,
denoted by [α], to be the unique tree node v ∈ Q such that L(v) = α. This
mapping [·] is one-one.
Clearly, CST∆ (T ) has at most k leaves and k − 1 internal nodes [11]. To savethe space, we represent Label(v) by a pair ⟨j, i⟩ ∈ N2 of the starting and ending
positions of the label in T such that T [j..i] = Label(v), while ε is represented
by ⟨i + 1, i⟩ for some i. Assuming this, CST∆ (T ) occupies only O(k) space. For
any factor α of T that starts at a word boundary, we represent its location in
CST∆ (T ) by a triple p = ⟨v, j, i⟩ ∈ V ×N2 , called a pointer (or a reference) toα, such that α = L(v)·T [j..i] if it exists. A pointer ⟨v, j, i⟩ is canonical if T [j..i]
is shortest. The locus of a factor α is the canonical pointer for α, and denotedby loc(α). We often call p a virtual node if j ≤ i, i.e., T [j..i] ̸= ε, and real node
if j > i, i.e., T [j..i] = ε.
4

⊥

0

⊥

1

Σ

SL

B

B

A

C

1

C

C

0

0

1

SL

0 1
0 1 SL 0
0
0
0
1
1
1
1

B

B
C

A

ε

0

1
SL

0

SL

ε

A

SL

1

C

(a)

(b)

Fig. 2. Examples of (a) an ordinary suﬃx tree for string S = ABABC on alphabet{A, B, C}, and (b) a code suﬃx tree for coded string T = 000100011 on preﬁx code
∆ = {A/00, B/01, C/1}.

3

A Linear-time Online Algorithm for Code Suﬃx Trees

In this section, we show our algorithm ConstructCST for constructing a code
suﬃx tree CST∆ (T ) on a preﬁx code ∆, which is based on Ukkonen’s online
construction algorithm for suﬃx trees [17]. The only diﬀerence is that it is augmented with a code automaton and code suﬃx links explained below. Let us ﬁx
an input string T = w1 · · · wk wk+1 ∈ Pre(∆∗ ) on a preﬁx code ∆ ⊆ Σ + withletter length n and word length k.
3.1

Code automata and code suﬃx links

Code automata. In our problem setting, a preﬁx code ∆ ⊆ Σ + on Σ is regular if ∆ is recognized by a ﬁnite automaton. A code automaton for a preﬁx code ∆ ⊆ Σ + is a possibly cyclic deterministic ﬁnite automaton (DFA)ˆ root) on a base alphabet Σ, where Q is a ﬁnite set of code
A = (Σ, Q, child, ⊥,ˆ and root are the unique initial and ﬁnal states, called thenodes (or nodes). ⊥source and sink , respectively. The function child : Q × Σ → Q is a transition
function such that for every u, v ∈ Q and a ∈ Σ, child(u, a) = v if and only ifthere exists an a-edge from u to v labeled with a. We extend child to a mapping
child∗ : Q×Σ ∗ → Q in a standard way [4]. If it is clear from context, we refer tothe code automaton A for ∆ as DFA(∆). In the treatment of this paper, DFA(∆)
need not be minimal in general. As a related work, Takeda, Miyamoto et al. [15]used code automata to extend Aho-Corasick pattern matching machines on a
preﬁx code. For example, we show in Fig. 1 the code automata for codes ∆1 ,
∆2 , ∆3 , ∆4 , and ∆5 in Example. 1.
We give the naming function [·] below. We introduce a special element ⊥ ̸∈ Σ
as the inverse of any word of ∆, i.e., ⊥w = ε for every w ∈ ∆. We deﬁne⊥wα = εα = α if w ∈ ∆ and α ∈ Σ ∗ . For a proper preword α ∈ PropPre(∆), ⊥α
is a special element diﬀerent from α. For any α ∈ str(code) = Pre(∆), we deﬁne
the locus of α, denoted by [⊥α], to be the unique code node v ∈ Q such that5ˆ α) = v. Note that the mapping [·] is many-one and naturally induceschild∗ (⊥,an equivalence relation ≡ on the set str(code). Since DFA(∆) has the uniqueﬁnal state root = [ε], we see that [⊥α] = [⊥β] = [ε] holds for any codewords
α, β ∈ ∆. We also note that [⊥α] ̸= [α] for any string α since the former isˆ in DFA(∆) and the latter is the node reachable fromthe node reachable from ⊥∆root in CST (T ). As a note, the above notations are just for analysis of ouralgorithm, and do not aﬀect the behavior and complexity of the algorithm.
By the above encoding, we can represent DFA(∆) as follows: The node set is
Q = { [⊥α] | α ∈ str(code) }. The transition function is given by child([α], a) =[αa] for every α ∈ str(code) and a ∈ Σ. The source and the sink are [⊥] and [ε],respectively. If [α] is either a tree node or a code node and a ∈ Σ is any letter,then we deﬁne [α]·a = [α·a]. We deﬁne the set dom(tree) = {[α] | α ∈ str(tree)} of
all tree nodes, and dom(code) = { [⊥α] | α ∈ (str(code) − ∆) } = Q − {[ε]} of code
nodes. Furthermore, we deﬁne dom(pre) = { [α] | α ∈ PropPre(∆) } ⊆ dom(tree),the domain of all prenodes. By deﬁnition, [ε] ∈ dom(tree) but [ε] ̸∈ dom(code).
In what follows, we often use α and [α] interchangeably if no confusion arises.
Code suﬃx links. Next, we introduce the suﬃx links for CST∆ (T ) as follows. Similarly to Ukkonen’s algorithm, each internal node v = [α] in the CST
has the suﬃx link of v, denoted by SL∆ (v), which is a pointer from v to theinternal node u such that SL∆ ([α]) = [⊥ · α], where α ∈ str(tree). Equivalently,
if v = [wβ] for some w ∈ ∆, β ∈ str(tree) ∪ str(code) then SL∆ ([wβ]) = [β]. Anycode node v ∈ dom(code) does not have a suﬃx link. The next lemma is crucial
to the correctness of our algorithm.
Lemma 1 (existence lemma for code suﬃx links). Let ∆ ⊆ Σ + be a
preﬁx-free code and T be any pre-string on ∆. Then, (i) any tree node v in
CST∆ (T ) has the suﬃx link SL∆ (v) pointing to a branching internal node u ineither CST∆ (T ) or DFA(∆). Furthermore, (ii) v is a preword node if and only
if SL∆ (v) is a code node in DFA(∆), and (iii) v is not a preword node if andonly if SL∆ (v) is a tree node in CST∆ (T ).
Proof. There are two cases on the domain of v. (1) If v = [α] ∈ dom(pre) is aprenode, then SL∆ (v) = [⊥α] belongs to dom(code) by the deﬁnition of DFA(∆).
(2) Suppose that = [wα] ∈ dom(tree)\dom(pre) for some w ∈ ∆, α ∈ Σ ∗ . It
is shown in [11] that a SST has a branching node v if and only if L(v) =∆lcp(suf ∆i (T ), suf j (T )) for some indexes i and j. Since ∆ is preﬁx-free and v =∆[wα], we know that both of suf ∆i (T ) and suf j (T ) start with w, and thus, we have∆
α = lcp(suf ∆⊓⊔i+1 (T ), suf j+1 (T )). From the above claim, the lemma follows.

3.2

Main algorithm

In Fig. 3, we show the algorithm ConstructCST, and in Fig. 4, the subprocedures
Extend and Terminate. The only diﬀerence between our algorithm and Ukkonen’salgorithm is lines 3 and 4 of ConstructCST that attaches DFA(∆) to the CST.
For an input string T = T [1] · · · T [n] = w1 · · · wk wk+1 ∈ Pre(∆∗ ) on ∆ ⊆ Σ + ,6

Algorithm ConstructCST:
input: A preword string T = w1 · · · wk ∈ Pre(∆∗ ) on a preﬁx code ∆ ⊆ Σ;
output: The sparse suﬃx tree CST∆ (T ) for t w.r.t. ∆. ;1: { global variables: Θ, Θ′ : word counters //for ℓ-TCST }2: Create an empty tree CST∆ with the root node root = [ε];ˆ = [⊥] and the sink root = [ε];3: Build DFA(∆) for ∆ with the source ⊥∆ˆ
4: SL (root) = ⊥;5: ϕ ← ⟨root, 1, 0⟩; ψ ← ⟨root, 1, 0⟩;
6: { Reset(Θ); Reset(Θ′ ) //for ℓ-TCST }7: for i = 1, . . . , n do //Stage i
8:
ϕ ← Extend(ϕ, i);{ψ ← Terminate(ψ, i); //for ℓ-TCST}
9: end for
10: return CST∆ ;Fig. 3. A construction algorithm for a code suﬃx tree CST∆ (T ) for a text T
on a preﬁx code ∆ ⊆ Σ + .

the algorithm constructs the CST for Ti = T [1..i] in an online manner for every
stage i = 1, . . . , n. At stage 0, the CST consists only of the root node root = [ε]and DFA(∆). Let T i = T [1..i] be the current input text and CST∆ (T i ) be thecode suﬃx tree for T i obtained at the end of stage i. At each step i, the algorithm
extends α to the new suﬃxes αai by appending the current base letter ai = T [i]for all ∆-suﬃxes in CST∆ (T i ).
This extension process is based on the following idea. Let S ∆ (i) = Suf ∆ (T i )be the set of all ∆-suﬃxes in T i . For every stage i = 0, . . . , n, we deﬁne the set
Bd∆ (i) ⊆ dom(tree) ∪ dom(code), the border , by the following recurrence:• Bd∆ (0) = {⊥, ε},• Bd∆ (i) = (Bd∆ (i − 1)·ai ) ∪ {⊥} if ε ∈ (Bd∆ (i − 1)·ai ),• Bd∆ (i) = Bd∆ (i − 1)·ai otherwise,
where S · a = { αa | α ∈ S } for any set S ⊆ Σ ∗ and a ∈ Σ. Then, we have thefollowing lemma. Recall that dom(tree) is the domain of tree nodes in CST∆ (T i ).
Lemma 2. For every i = 0, . . . , n, S ∆ (i) = Bd∆ (i) ∩ dom(tree).
Proof. From a similar argument to [15, 17], the following recurrence holds:(i) S ∆ (0) = {ε},(ii) S ∆ (i) = (S ∆ (i − 1)·ai ) ∪ {ε} if T i = T [1..i] is a complete word string (*),
(iii) S ∆ (i) = S ∆ (i − 1)·ai otherwise,
By induction on i ≥ 0, we then can show that the condition (*) holds iﬀ w ∈S ∆ (i − 1)·ai for some w ∈ ∆ iﬀ ε ∈ Bd∆ (i − 1)·ai holds. Furthermore, ⊥α ∈Bd∆ (i) iﬀ α ∈ S ∆ (i) for any α ∈ Pre(∆). Thus, the result follows.
⊓⊔7

procedure Extend(ϕ = ⟨s, j, i − 1⟩, i):1: last ← N U LL; //oldp
2: while (child(ϕ, T [i]) is not deﬁned) do
3:
if j ≤ i then begin4:
ϕ ← Split(ϕ);
5:if last ̸= N U LL then begin
6:SL∆ (ϕ) ← last;
7:
last ← ϕ; end
8:
end
9:
create a leaf q with label(q) ← ⟨i, ∞⟩;10:child(ϕ, T [i]) ← q;
11:
ϕ ← Canonize(⟨SL∆ (s), j, i − 1⟩);12:
{Decrement(Θ) //for ℓ-TST}
13: end while
14: ϕ ← Canonize(⟨s, j, i⟩);15: {ChildTrans(Θ, T [i]); //for ℓ-TST}}
16: {if toClose(Θ) then SuﬃxTrans(Θ, ϕ);//for ℓ-TST}
17: return ϕ; {End of Extend}
procedure Canonize(ϕ = ⟨s, j, i⟩):1: while j ≤ i do begin2:
u ← child(s, T [j]);3:⟨q, p⟩ ← label(u);4:if p − q > i − j then5:
break;
6:j ← j + (p − q + 1);
7:s ← u;
8: end9: return ⟨s, j, i⟩; {End of Canonize}

Fig. 4. The subprocedures Extend and Canonize for the code suﬃx tree construction.

We call each suﬃx α in Bd∆ (i) the extension point at stage i. Next, weconsider how we can eﬃciently ﬁnd the extension points and extend them. The
detection of ε is also crucial to the synchronization of word boundaries. We use apointer ϕ to keep track to extension points in Bd∆ (i) from longer to shorter. Let
act∆
i be the active point at stage i as the pointer ϕ such that L(ϕ) is the longest
suﬃx of T i−1 that occurs at least twice in T i . For i = 1, . . . , n, the maintenanceof Bd∆ (i) proceeds in the following way for all extension points ϕ = [αai ] ofthree types 1–3. Let Bd∆ (0) = {⊥, ε}.
• type 1: If α occurs only at the end of T i−1 , then, α is represented by aleaf, and thus so is αai . As in Ukkonen [17], by representing α as an open
leaf ⟨j, ∞⟩, ∞ is interpreted as the current index i, the extension point α
is automatically extended without any management. This correctly extends
all extension points α of type 1.
• type 2: If α occurs at least twice in T i−1 , but αai does not occur in T i ,then by induction on i, we can show that act∆
i is the ﬁrst node of type 2
satisfying this condition. Then, we create the new node for αai extending
α by appending a to the tail of α, while the parent α is materialized byprocedure Split if α is virtual. Repeat this process until we reach the ﬁrst
node ϕ of type 3. This correctly extends all extension points α of type 2.
• type 3: If α occurs in T i−1 at least twice in T i−1 , and αai also occurs in
T i , then we can show as in Ukkonen [17] that all extension points on thesuﬃx links from α to some node in dom(code) ∪ {[ε]}, which is the end of
the border, are already contained in T i . Therefore, these extension points
are correctly extended in CST∆ (T i ) without any explicit extension.
The procedure Extend in Fig. 4 implements the above incremental computation of Bd∆ (i). From the discussion above, we have the next lemma.

8

u

⊥
SL

v

word boundary current input pointer i

SL

ε

u

u

v
w ∈∆

word boundary

Input string Ti

Code suffix tree CST∆(Ti)

Fig. 5. Proof sketch for the time complexity in the case of cyclic code automata

Lemma 3. For every stage i = 1, . . . , n, The procedure Extend in Fig. 4 correctlycomputes the border Bd∆ (i) from Bd∆ (i − 1) and ai = T [i].
Proof. It is easy to see that Extend correctly implements the extensions of suﬃxes
in Bd∆ (i) mentioned above. Then, the most part is shown in a similar way to
Ukkonen [17]. For extension of all three types, the above procedure correctly
extends the original suﬃx [α] ∈ Bd∆ (i − 1) to obtain [αai ] ∈ Bd∆ (i). Remaining
thing is to show the while-loop from lines 2 to 13 of Extend eventually terminates.
If the while-loop is executed repeatedly, the depth of the extension pointer ϕ
become smaller, and ﬁnally, either it ends with extension of type 3 or it enters
the domain dom(code). In the former case, the proof is done. In the latter case,ϕ enters dom(code) and thus ends with extension of type 3, too. This completes
the proof.
⊓⊔
From Lemma 2 and Lemma 3, we show the following theorem.
Theorem 1 (correctness). For every stage i = 1, . . . , n, the algorithm ConstructCST in Fig. 3 correctly constructs CST∆ (T i ).

3.3Time complexity

The remaining task is to estimate the time complexity of ConstructCST in Fig. 3.
Let Ntree and Ncode be the numbers of tree and code edges traversed during thecomputation, respectively. Let N = Ntree + Ncode . In a special case that ∆ is
ﬁnite and thus DFA(∆) is acyclic, the linear time complexity of ConstructCST
can be easily proved by applying the telescope argument on the changes of thedepth D(ϕ) of ϕ as used in [17] with a little twist that D(ϕ) is deﬁned by the
number of the code and tree nodes on the path from [⊥] to ϕ.
In the general case that DFA(∆) = A is possibly cyclic, and consequently∆ is inﬁnite, however, it is not straightforward to show a linear bound of N =Ntree +Ncode because the extension pointer ϕ can move inside a cycle in dom(tree)
many times without monotonically increasing the depth parameter D(ϕ), andthus, it is not suﬃcient to linearly bound Ncode for dom(code). To overcome thisdiﬃculty, we bound the number Ncode by the total number of letters consumed
during the traversal on dom(code). We have the main theorem of this paper.
9

Theorem 2 (linear time construction of code suﬃx trees). Let ∆ ⊆ Σ ∗be a regular preﬁx code on Σ recognized by a code automaton A = DFA(∆). Then,the algorithm ConstructCST in Fig. 3 constructs CST∆ (T ) for an input text T
in O(n log |Σ| + m) time and O(k) space in online manner, where k = |T |∆ ,n = |T |Σ , and m = ||A|| is the size of A.
Proof. We show that the number N = Ntree + Ncode is bounded by i = |T i |for every stage i. We can show that the number Ntree in dom(tree) is linearlybounded by i = |T i |. Therefore, we estimate the total number Ncode of all childand suﬃx links that the algorithm traverses in dom(code) through all stages. Leti = 1, . . . , n be any stage, and let T i = T [1] · · · T [i] = w1 · · · wk uk+1 ∈ Pre(∆∗ )ibe the current input string. At stage i, we denote by ∂Ncodethe number of suﬃx
and child edge traversals added to Ncode . Then, there are three cases below when
ϕ traverses inside dom(code): (a) The case that at stage i − 1, the extension ends
at node ϕ in dom(code) such that ϕ ̸= [ε]. From the construction of DFA∆ andLemma 3, the algorithm executes exactly one extension of type 3 in dom(code) byigoing down a child edge. Thus, ∂Ncode≤ 1 is immediate. (b) Otherwise, at stagei−1, the extension ends at node ϕ ̸∈ dom(code). This implies that ϕ ∈ dom(tree).
In this case, the algorithm repeats extensions of type 2 in the while-loop fromlines 2 to 13 of Extend by traversing suﬃx links in Bd∆ (i − 1), and terminateswith extension of type 3. Let ϕ = [β] be the ﬁnal extension point of type 2.
Then, we have two subclasses below on ϕ: (b.1) The case that ϕ ∈ dom(tree).
Since all the preceding extension for Bd∆ (i − 1) were done in dom(tree), we havei
∂Ncode= 0. (b.2) The case that ϕ ̸∈ dom(tree). Then, ϕ = [β] ∈ dom(code) for a
preword β. Let ϕ = ⟨s, j, i − 1⟩ be the canonical pointer of [β]. From Lemma 3,
we can show that β = uk+1 holds, that is, the string label β = L(ϕ) coincides
the current tail preword uk+1 of T i being scanned. In Extend, we then movefrom ϕ = [β] to SL∆ (β) = [⊥β] by ﬁrstly following one suﬃx link from thereal node s and by successively going down at most |β| child edges by applyingiCanonize(SL∆ (s), j, i − 1) at line 11 (See Fig. 5). Therefore, ∂Ncode
is at most|β| + 1. On the other hand, suppose that we are scanning a preﬁx β = uk+1
of some complete word wk+1 . Then, it is not hard to show that the extension
in the case (b.2), where a jump from dom(tree) into dom(code) is performed,
can occur at most once per complete codeword wk+1 during the whole scan,because once the case (b.2) occurs, only the case (b.3) can occurs iteratively
until ϕ reaches dom(tree). Thus, we can amortize the cost for the case (b.2) over
the whole computation. Combining the above arguments, we have the numberof edge traversals bounded by:
Ncode ≤n∑i=0i
∂Ncode≤(n∑i=01) + (

k+1∑|wj |) ≤ 2n,

j=0

∑k+1
where we used the inequality j=0 |wj | = |T | = n. From similar arguments as in[17], we can show the remaining part that Ntree ≤ 2n. Hence, the total number ofedge traversals is given by N = Ntree + Ncode ≤ 4n. Space complexity is obvious
since CST∆ (T ) has at most O(n) real nodes. For the total time complexity,
10

Algorithm Terminate(ψ = ⟨s, j, i − 1⟩, i):
Input: A terminating point ψ and i ≥ 0;
1: ψ ← Canonize(⟨s, j, i⟩); {type 1 extension by letter ai }2: ChildTrans(Θ′ , T [i]);3: if toClose(Θ′ ) then4:v := child (s, T [j]);5:
if label(v) = ⟨j, ∞⟩ then label(v) ← ⟨j, i⟩;6:
SuﬃxTrans(Θ′ , ψ);
7: return ψ;
Fig. 6. Terminating truncated word suﬃx trees

the algorithm takes O(m) time for the preprocessing A = DFA(∆) takes, andtakes and O(1) time per suﬃx link traversal and O(log |Σ|) time per child edge
traversal with an appropriate dictionary structure. Hence, by construction of themain algorithm, the time complexity is O(n).
⊓⊔For a ﬁxed base alphabet Σ, the algorithm runs in O(n + m) time and O(k)space.

4

Application to Truncated Code Suﬃx Trees

Let T ∈ Pre(∆∗ ) T = T [1] · · · T [n] = w1 · · · wk wk+1 ∈ Pre(∆∗ ) be an input
prestring on ∆ and ℓ > 0 be a ﬁxed integer. Then, the ℓ-truncated code suﬃx
tree (ℓ-TCST) of T on ∆, denoted by ℓ-TCST∆ (T ), is a compacted trie that
represents the set Fac∆ (T, ℓ) of all (∆, ℓ)-factors of T . It is easy to see that the
number of nodes in ℓ-TCST∆ (T ) is linear in the number k ′ = |Fac∆ (T, ℓ)| of
unique (∆, ℓ)-factors of T . Since k ′ is smaller than k = |Suf ∆ (T )| in real data
sets, we expect that ℓ-TCST is more space eﬃcient than CST for small valuesof ℓ.
The modiﬁed algorithm ConstructTCST is obtained from the original ConstructCST of Fig. 3 by inserting Terminate in Fig. 6 after Extend of line 8. The
main diﬀerence of the new algorithm from the old one is the use of the termination pointer ψ for closing suﬃxes in addition to the extension pointer ϕ for
opening suﬃxes. At every stage i = 1, . . . , n, Extend ﬁrst extends each ϕ = α
of type 2 in T i−1 to αai by attaching the i-th letter ai = T [i] ∈ Σ. At thesame time, Terminate keeps track of termination point ψ, which is an open leaf
ψ = ⟨j, ∞⟩ with word depth at most ℓ − 1, and terminates it whenever ϕ reaches
the depth ℓ by replacing ⟨j, ∞⟩ with ⟨j, i⟩, where i is the current index. A keyobservation is that there exists at most one open leaf to be closed at every stage i.
To implement this idea, we have to count the length of the open suﬃxes in
the number of codewords to detect when |L(ψ)| exceeds the limit ℓ. To do thiswe use a data structure Θ = ⟨η, wc⟩, where Θ.η = η ∈ dom(code) is a boundary
pointer to a code node and Θ.wc = wc ∈ N is a word counter , with the following
operations:11• Reset(Θ) ≡ begin Θ.η ← [⊥]; Θ.wc ← 0; end.
• Decrement(Θ) ≡ Θ.wc ← Θ.wc − 1;
• ChildTrans(Θ, C) ≡1: Θ.η ← childDFA(∆) (Θ.η, C);
2: if Θ.η = [ε] then begin Θ.η ← ⊥; Θ.wc ← Θ.wc + 1 end;
• SuﬃxTrans(Θ, ϕ = ⟨s, j, i⟩) ≡1: Θ.wc ← Θ.wc − 1; ϕ ← Canonize(⟨SL∆ (s), j, i⟩); return ϕ;• toClose(Θ) ≡1: return Θ.wc = k and Θ.η = [ε];The meaning of the above operations will be easily understood. Using these
operations, we modify the algorithm ConstructCST and procedures Extend andCanonize by adding comment lines with “for ℓ-TCST.” In Canonize, we replace
the sentence “if p − q > i − j then” at line 4 with “if p − q > i − j or u is a leaf
then.” For time complexity, ChildTrans takes O(log |Σ|) time, and all the otheroperations than SuﬃxTrans takes constant time. By analysis similar to one in
the previous section, we can show that SuﬃxTrans requires amortized constanttime per operation. From a similar discussion in Sec. 3 and in Na et al. [14], we
can show the following theorem.
Theorem 3 (linear time construction of a TCST on preﬁx code). If ∆ bea ﬁxed, possibly inﬁnite preﬁx code, then the modiﬁed algorithm ConstructTCST
constructs a truncated code suﬃx tree ℓ-TCST∆ (T ) for an input text T in O(n)time and O(k) space in online manner, where k = |T |∆ and n = |T |Σ .

5

Experimental Results

We ran experiments on real datasets. Input data were an English text fromthe Pizza & Chili Corpus 1 , where the delimiters are spaces SPC and LF, anda UTF-8 text from the Mainichi Newspaper Corpus 1991 in Japanese 2 . The
length of each text was 50MB. The English text has 336,578 diﬀerent words ofthe average length 5.20 (byte). The UTF-8 text has 4054 diﬀerent codes of theaverage length 2.96 (byte).
We implemented several types of sparse and truncated suﬃx trees. ST is the
suﬃx tree, CST is the code suﬃx tree in Chapter 3, IST is the suﬃx tree over thecode alphabet ∆ using four-byte integers as base letters, HST is the code suﬃx
tree over the (letter-based) Huﬀman code, and IHST is the code suﬃx tree over
the word-based Huﬀman code for ∆. TST, TCST, TIST, THST and TIHST
are their truncated versions with the factor length ℓ = 2, 5, and 10 (words).
These programs were written in C++ and compiled by Microsoft Visual Studio2010. We ran the programs on an Intel Core i7 920 and 12GB of RAM, running
Windows 7 Professional 64bit.
1
2

http://pizzachili.dcc.uchile.cl/
http://www.nichigai.co.jp/sales/corpus.html

12

Table 1. Node count (106 nodes), where ℓ is the length of code factors.
Data

ST CST IST HST IHST ℓ TST TCST TIST THST TIHST
2 28
3.6
2.6
39
4.9
English 87 17 14 105 20
5 56
11
8.3
74
14
10 58
11
8.7
76
14
2 2.5 0.43 0.35 4.0
0.70
UTF-8 85 29 25 105 35
5 43
13
11
58
17
10 70
23
20
89
30
Table 2. Query time (microseconds per query).
Data

ST CST IST HST IHST ℓ TST TCST TIST THST TIHST
1.03 0.827 0.686 1.295 0.624 2 0.889 0.718 0.577 1.139 0.546
English 1.233 0.952 0.827 1.497 0.733 5 1.170 0.905 0.764 1.435 0.718
1.263 0.952 0.827 1.514 0.749 10 1.185 0.904 0.827 1.467 0.718
0.537 0.47 0.441 0.787 0.434 2 0.421 0.341 0.305 0.608 0.304
UTF-8 0.88 0.772 0.803 1.138 0.718 5 0.827 0.72 0.684 1.077 0.677
0.886 0.774 0.767 1.138 0.723 10 0.858 0.755 0.787 1.108 0.705

Tables 1 and 2 show the node counts of the suﬃx trees and the averagequery time for 106 strings of the code lengths ℓ = 2, 5, and 10 (words), respectively. In the experiments, we observed that the sparse suﬃx trees were more
space-eﬃcient and faster than their non-sparse versions, roughly, by the factorof O(n/k). Truncated suﬃx trees also improved space eﬃciency and query timein both full and truncated versions. IHST was the fastest in the algorithms,
even though HST was slowest. CST was slightly slower than IST, however, it iscomparable because it does not need any additional space and preprocessing.

6

Conclusion

In this paper, we presented an online construction algorithm for CSTs and ℓTCSTs on regular, variable-length preﬁx codes that runs in O(n + m) time andO(k) space, where n is the total text size, k is the number of codewords, and mis the size of a code automata.
As future works, Extensions of this approach to other suﬃx indexes, e.g.,
DAWG [9], CDAWG [10], and suﬃx arrays [5] and application to enhanced
suﬃx arrays [1, 12] and property suﬃx trees [2, 16] would be interesting. Also, itwould be an interesting future problem to study lowerbounds of the worst casetime complexity of construction of sparse suﬃx trees with an arbitrary index set
when O(k) space is allowed.
Acknowledgements
The authors are grateful to anonymous referees for many useful comments andsuggestions that signiﬁcantly improve the quality of this paper. They also would
13

like to thank Thomas Zeugmann, Ayumi Shinohara, Masayuki Takeda, Takuya
Kida, Shin-ichi Minato, Makoto Haraguchi, and Osamu Watanabe for their discussions and valuable comments, This research was partly supported by MEXT
Grant-in-Aid for Scientiﬁc Research (A), 20240014, FY2008–2011, and MEXT/JSPS Global COE Program, “Center for Next-Generation Information Technology based on Knowledge Discovery and Knowledge Federation,” FY2007–2011.

References
1. M. I. Abouelhoda, S. Kurtz, and E. Ohlebusch, Replacing suﬃx trees with enhanced suﬃx arrays, J. of Discrete Algorithms, 2(1), 53–86, 2004.
2. A. Amir, E. Chencinski, C. Iliopoulos, T. Kopelowitz, and H. Zhang, Property
machting and weighted matching, Proc. CPM’06, LNCS 4009, 188–199, 2006.
3. A. Andersson, N. J. Larsson, and K. Swanson, Suﬃx trees on words, Algorithmica,
23(3), 246–260, 1999.
4. M. Crochemore and W. Rytter, Jewels of Stringology: Text Algorithms, 2002.
5. F. Ferragina and J. Fischer, Suﬃx arrays on words, Proc. CPM’07, LNCS 4580,
328–339, 2007.
6. D. Gusﬁeld, Algorithms on Strings, Trees, and Sequences, – Computer science andcomputational biology, Cambridge, 1997.
7. IETF, UTF-8, a transformation format of ISO 10646, RFC 3629, 2003.
http://tools.ietf.org/html/rfc3629
8. S. Inenaga and M. Takeda, On-line linear-time construction of word suﬃx trees,
Proc. CPM’06, LNCS, Springer, 60–71, 2006.
9. S. Inenaga and M. Takeda, Sparse directed acyclic word graphs, Proc. SPIRE’06,
LNCS 4209, Springer, 61–73, 2006.
10. S. Inenaga and M. Takeda, Sparse compact directed acyclic word graphs, Jan
Holub, Jan Zdarek (Eds.), Proc. PSC’06, 197-211, 2006.
11. J. Kärkkäinen and E. Ukkonen, Sparse suﬃx trees, Proc. COCOON’96, LNCS,
Springer, 219–230, 1996.
12. T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park, Linear-time longestcommon-preﬁx computation in suﬃx arrays and its applications, Proc. CPM’01,
LNCS 2089, 181–192, 2001.
13. E. M. McCreight, A space-economical suﬃx tree construction algorithm, J. ACM,
23, 262–272, 1976.
14. J.C. Na, A. Apostolico, C.S. Iliopoulos, and K. Park. Truncated suﬃx trees andtheir application to data compression. Theoretical Computer Science, 304:87–101,
July 2003.
15. M. Takeda et al., Processing text ﬁles as is: pattern matching over compressed
texts, multi-byte character texts, and semi-structured texts, Proc. SPIRE’02,
LNCS 2476, 2002.
16. T. Uemura, H. Arimura, A linear-time oﬀ-line construction of property suﬃx trees,
IEICE Trans. Inf. & Syst., J91-D(3), 595–607, 2008 (in Japanese). An English
version appears in Chapter 4, T. Uemura, Eﬃcient Construction of ConstrainedSuﬃx Trees, Ph.D thesis, IST, Hokkaido Univ., Feb. 2011 (submitting).
17. E. Ukkonen, On-line construction of suﬃx-trees, Algorithmica, 14(3), 249-260,
1995.

14