Eﬃcient Computation of Substring EquivalenceClasses with Suﬃx Arrays
Kazuyuki Narisawa1, Shunsuke Inenaga2, Hideo Bannai1 , andMasayuki Takeda1,3
1

Department of Informatics, Kyushu University, Fukuoka 819-0395, Japan2
Department of Computer Science and Communication Engineering,
Kyushu University, Fukuoka 819-0395, Japan
3
SORST, Japan Science and Technology Agency (JST){k-nari, bannai, takeda}@i.kyushu-u.ac.jp
inenaga@c.csce.kyushu-u.ac.jp

Abstract. This paper considers enumeration of substring equivalenceclasses introduced by Blumer et al. [1]. They used the equivalence classes
to deﬁne an index structure called compact directed acyclic word graphs(CDAWGs). In text analysis, considering these equivalence classes isuseful since they group together redundant substrings with essentially
identical occurrences. In this paper, we present how to enumerate thoseequivalence classes using suﬃx arrays. Our algorithm uses rank and lcp
arrays for traversing the corresponding suﬃx trees, but does not need
any other additional data structure. The algorithm runs in linear time inthe length of the input string. We show experimental results comparing
the running times and space consumptions of our algorithm, suﬃx tree
and CDAWG based approaches.

1

Introduction

Finding distinct features from text data is an important approach for text analysis, with various applications in literary studies, genome studies, and spam detection [2]. In biological sequences and non-western languages such as Japaneseand Chinese, word boundaries do not exist, and thus all substrings of the text
are subject to analysis. However, a given text contains too many substrings tobrowse or analyze. A reasonable approach is to partition the set of substrings
into equivalence classes under the equivalence relation of [1] so that an expert
can examine the classes one by one [3]. This equivalence relation groups together
substrings that correspond to essentially identical occurrences in the text. Sucha partitioning is very beneﬁcial for various text mining approaches whose mining criterion is based on occurrence frequencies, since each element in a given
equivalence class will have the same occurrence frequency.
In this paper, we develop an eﬃcient algorithm for enumerating the equivalence classes of a given string, as well as useful statistics such as frequency andsize for each class. Although the number of equivalence classes in a string w oflength n is at most n + 1, the total number of elements in the equivalence classes

2

is O(n2 ), that is, the number of substrings in w. However, each equivalence classcan be expressed by a unique maximal (longest) element and multiple minimal
elements. Further, these elements can be expressed by a pair of integers representing the beginning and end positions in the string. Thus, we consider these
succinct expressions of the equivalence classes, which require only O(n) space.
The succinct expressions can easily be computed using the CDAWG data structure proposed by [1], which is an acyclic graph structure whose nodes correspondto the equivalence classes. Although CDAWGs can be constructed in O(n) timeand space [4], we present a more eﬃcient algorithm based on suﬃx arrays.
In Section 3, we ﬁrst describe an algorithm using suﬃx trees with suﬃx links(Algorithm 1), for computing the succinct expressions. Although suﬃx trees canalso be constructed and represented in O(n) time and space [5, 6], it has beenshown that many algorithms on suﬃx trees can be eﬃciently simulated on suﬃx
arrays [7] with the help of auxiliary arrays such as lcp and rank arrays [8, 9].
However, previous methods require extra time and space for maintaining suﬃx
link information. In Section 4, we give an algorithm to simulate Algorithm 1 using
the suﬃx, lcp and rank arrays (Algorithm 2). A key feature of this algorithm isthat it does not require any extra data structure other than these arrays, making
it quite space economical. Section 5 gives results of computational experimentsof Algorithm 1, 2, and an algorithm using CDAWGs.

2

Preliminaries

2.1

NotationsLet Σ be a ﬁnite set of symbols, called an alphabet. An element of Σ ∗ is calleda string. Strings x, y and z are said to be a preﬁx, substring, and suﬃx ofthe string w = xyz, respectively, and the string w is said to be a superstringof substring y. The sets of preﬁxes, substrings and suﬃxes of a string w are
denoted by Preﬁx (w), Substr(w) and Suﬃx (w), respectively. The length of astring w is denoted by |w|. The empty string is denoted by ε, that is, |ε| = 0. Let
Σ + = Σ ∗ − {ε}. The i-th symbol of a string w is denoted by w[i] for 1 ≤ i ≤ |w|,
and the substring of w that begins at position i and ends at position j is denotedby w[i : j] for 1 ≤ i ≤ j ≤ |w|. Also, let w[i :] = w[i : |w|] for 1 ≤ i ≤ |w|. For
any string w ∈ Σ ∗ and x ∈ Substr(w), a reference pair of x w.r.t. w is a pair
i, j such that w[i : j] = x. For any strings x, y ∈ Σ ∗ , the longest string inPreﬁx (x) ∩ Preﬁx (y) is called the longest common preﬁx (LCP ) of x and y.
2.2

Equivalence Relations on Strings

In this subsection, we recall the equivalence relations introduced by Blumer et
al. [10, 1], and then state their properties. Throughout this paper, we consider
the equivalence classes of the input string w that ends with a distinct symbol $that does not appear anywhere else in w.

3

For any string x ∈ Substr(w), let,
BegPos(x) = {i | 1 ≤ i ≤ |w|, x = w[i : i + |x| − 1]}, andEndPos(x) = {i | 1 ≤ i ≤ |w|, x = w[i − |x| + 1 : i]}.
For any string y ∈/ Substr(w), let BegPos(y) = Endpos(y) = ∅.
Now we deﬁne two equivalence relations and classes based on BegPos and
EndPos.
Deﬁnition 1. The equivalence relations ≡L and ≡R on Σ ∗ are deﬁned by:x ≡L y ⇔ BegPos(x) = BegPos(y), andx ≡R y ⇔ EndPos(x) = EndPos(y),where x, y are any strings in Σ ∗ . The equivalence class of a string x ∈ Σ ∗ withrespect to ≡L and ≡R is denoted by [x]≡L and [x]≡R , respectively.
Notice that any strings not in Substr(w) form one equivalence class under≡L , called the degenerate class. Similar arguments hold for ≡R . The above
equivalence classes [x]≡L and [x]≡R correspond to the nodes of suﬃx trees [5]and directed acyclic word graphs (DAWGs) [10], respectively. For any string→−x ∈ Substr(w), let −x and ←
x denote the unique longest member of [x]≡L and→x = αxβ such that[x]≡R , respectively. For any string x ∈ Substr(w), let ←
←
−
→
−
∗
α, β ∈ Σ are the strings satisfying x = αx and x = xβ.
→
Intuitively, ←x = αxβ means that:– Every time x occurs in w, it is preceded by α and followed by β.
– Strings α and β are longest possible.
←
−− −−
→
→
−
→
Note that (−x ) = (←x) =←x.
Now we deﬁne another equivalence relation, whose equivalence classes correspond to the nodes of compact directed acyclic word graphs (CDAWGs) [1].
Deﬁnition 2. For any string x, y ∈ Σ ∗ , we denote x ≡ y, if and only if
1. x ∈/ Substr(w) and y ∈/ Substr(w), or→→
2. x, y ∈ Substr(w) and ←x =←y.
The equivalence class of a string x with respect to ≡ is denoted by [x]≡ . For any→x ∈ Substr(w), the unique longest member ←x of [x]≡ is called the representativeof the equivalence class.
Now we consider a succinct representation of each non-degenerate equivalenceclass under ≡. For any x ∈ Substr(w), let Minimal ([x]≡ ) denote the set ofminimal elements of [x]≡ , that is,
Minimal ([x]≡ ) = {y ∈ [x]≡ | z ∈ Substr(y) and z ∈ [x]≡ implies z = y}.
Namely, Minimal ([x]≡ ) is the set of strings y in [x]≡ such that there is no stringz ∈ Substr(y) − {y} with z ≡ x.
The following lemma shows that the strings in every non-degenerate equiv→
x andalence class [x]≡ can be represented by a pair of its representative ←Minimal ([x]≡ ).

4

Lemma 1 ([3]). For any x in Substr(w), let y1 , . . . , yk be the elements of
Minimal ([x]≡ ). Then,→→x ) ∪ · · · ∪ P incer(yk , ←x ),[x]≡ = P incer(y1 , ←→→x ) is the set of strings z such that z ∈ Substr(←x ) and yi ∈where P incer(yi , ←Substr(z).
Now, a succinct representation of a non-degenerate equivalence class [x]≡ is→→x and all strings in Minimal ([x]≡ ) area pair of ←x and Minimal ([x]≡ ), where ←represented by their reference pairs w.r.t. w. We have the following lemma about
the total space requirement for the succinct representations of all the equivalenceclasses under ≡.
Lemma 2. A list of succinct representations of all non-degenerate equivalenceclasses under ≡ requires only O(|w|) space.
Let the size of non-degenerate equivalence class [x]≡ be the number of substrings that belong to [x]≡ , that is, |[x]≡ |. Let Freq(x ) denote the occurrence
frequency of x in w. If x ≡ y, then Freq(x ) = Freq(y). Therefore, we consider
the frequency of an equivalence class [x]≡ and denote this by Freq([x ]≡ ).
2.3

Data Structures

We use the following data structures in our algorithms.
Deﬁnition 3 (Suﬃx Trees and Suﬃx Link Trees). For any string w, thesuﬃx tree of w, denoted ST (w), is an edge-labeled tree structure (V, E) such that→V = {x | x = −x , x ∈ Substr(w)}, and→ = xβ},E = {(x, β, xβ) | x, xβ ∈ V, β ∈ Σ + , a = β[1], −xawhere the second component β of each edge (x, β, xβ) in E is its label, and thesuﬃx link tree of w, denoted SLT (w), is a tree structure (V, E ) such thatE = {(ax, x) | x, ax ∈ V, a ∈ Σ}.
It is well known that ST (w) with SLT (w) can be computed in linear timeand space [11, 6].
→
The root node of ST (w) and SLT (w) is associated with ε = −ε . Since theend-marker $ is unique in w, every nonempty suﬃx of strings in w corresponds
to a leaf of ST (w), and only such a leaf exists in ST (w). Therefore, each leaf
can be identiﬁed by the beginning position of the corresponding suﬃx of w. The
values Freq(x ) for all nodes x ∈ V of ST (w) can be computed in linear time andspace by a post-order traversal on ST (w).
For any node xβ with incoming edge (x, β, xβ) of ST (w), let Paths(xβ) =→z ={xβ  | β  ∈ Preﬁx (β) − {ε}}. Note that Paths(xβ) = [xβ]≡L , and therefore −xβ for any z ∈ Paths(xβ). It is easy to see that |Paths(xβ)| = |xβ| − |x| = |β|.
For any node x of ST (w) such that x = ε, let Parent (x) denote the parent
of x.

5

Deﬁnition 4 (Suﬃx Arrays). The suﬃx array [7] SA of any string w is anarray of length |w| such that SA[i] = j, where w[j :] is the i-th lexicographicallysmallest suﬃx of w.
The suﬃx array of string w can be computed in linear time from ST (w), byarranging the out-going edges of any node of ST (w) in the lexicographicallyincreasing order of the ﬁrst symbols of the edge labels. This way all the leaves of
ST (w) are sorted in the lexicographically increasing order, and they correspondto SA of w. Linear-time direct construction of SA has also been extensively
studied [12–14].
Deﬁnition 5 (Rank and LCP Arrays). The rank and lcp arrays of any
string w are arrays of length |w| such that rank [SA[i]] = i, and lcp[i] is the lengthof the longest common preﬁx of w[SA[i − 1] :] and w[SA[i] :] for 2 ≤ i ≤ |w|, andlcp[1] = −1.
Given SA of string w, the rank and lcp arrays of w can be computed in linear
time and space [8].

3Computing Equivalence Classes under ≡ Using Suﬃx
Trees

In this section we present a suﬃx tree based algorithm to compute a succinct
representation of each non-degenerate equivalence class, together with its sizeand frequency. This algorithm will be the basis of our algorithm of Section 4,
which uses suﬃx arrays instead of trees.
The following lemma states how to check the equivalence relation ≡ between
two substrings using ST (w).
→→Lemma 3. For any x, y ∈ Substr(w), x ≡ y if and only if Freq(−x ) = Freq(−
y)
→
−
→
−
and x ∈ Suﬃx ( y ) or vise versa.
→→→→
Proof. The case that −x = −y is trivial. We consider the case that −
x = −
y.
→
−
→
−
Assume w.l.o.g. that | x | < | y |.
←
−−
←
−−
→
→
→
→
y ), which implies that
Assume x ≡ y. Then we have (−x) = ←x =←y = (−
→
−
→
−
→
−
→
→
→
EndPos( x ) = EndPos( y ). Thus we have Freq( x ) = Freq(−y ). Since |−x | < |−
y |,
→
−
→
−
x ∈ Suﬃx ( y ).
→
→
→
→
→
→
Now assume Freq(−x ) = Freq(−y ) and −x ∈ Suﬃx (−y ). Since −x ∈ Suﬃx (−
y ),
→
−
→
−
→
−
→
−
we have EndPos( x ) ⊇ EndPos( y ). Moreover, since Freq( x ) = Freq( y ), we
←
−− ←
−− ←
→
→
→
→
→
get EndPos(−x ) = EndPos(−y ). Hence ←x = (−x ) = (−
y)= →
y.


→
Lemma 4. For any node x ∈ V of ST (w) such that ←x = x, let  = max{i |
Freq(x [i :]) = Freq(x )}. Then, [x]≡ = y∈[x]≡ [y]≡L = i=1 Paths(x[i :]).
R

Proof. By Lemma3.




6

For each node x of ST (w), |Paths(x)| = |Parent (x)| − |x| and it can beprecomputed by a post-order traversal on ST (w). Thus, by the above lemma,
the size of each non-degenerate equivalence class can be computed by a postorder traversal on SLT (w).
In what follows, we show how to check whether or not a given node x in thesuﬃx link tree traversal is the representative of the equivalence class under ≡,→namely, whether or not x = ←x.
→Lemma 5. For any node x ∈ V of ST (w), x = ←x if and only if Freq(ax ) <Freq(x ) for any a ∈ Σ such that ax ∈ V .
Proof. By Lemma 3.



The following two lemmas follow from Lemma 5.
→
Lemma 6. For any leaf node x ∈ V of SLT (w), x = ←x.
→
Proof. Since x is also a node of ST (w), x = −x . We show that for any symbol−a ∈ Σ, Freq(ax ) < Freq(x ), and therefore, x = ←x . Since x is a leaf of SLT (w),
we have ax ∈ V for any a ∈ Σ, for which there are the two following cases:
1. ax ∈ Substr(w). Then, Freq(ax ) = 0 while Freq(x ) > 0.
→ = axβ ∈ V . Then, we have
2. ax ∈ Substr(w). Consider β ∈ Σ + such that −axthat Freq(ax ) = Freq(ax β) ≤ Freq(x β) < Freq(x ).
→In both cases we have Freq(ax ) < Freq(x ), and hence x = ←x from Lemma 5. Lemma 7. For any internal node x ∈ V of SLT (w) and for any a ∈ Σ with→ax ∈ V , x = ←x if and only if Freq(ax ) = Freq(x ).
→Proof. (⇒) Sincex = ←x , we have Freq(bx ) = Freq(x ) for any b ∈ Σ. (⇐)
Since Freq(x ) ≥ b∈Σ Freq(bx ) and Freq(x ) > Freq(ax ) > 0, we have Freq(x ) >Freq(bx ) for any b ∈ Σ.

We have the following lemma concerning the minimal members of the nondegenerate equivalence classes.
Lemma 8. For any nodes x, ax ∈ V of ST (w) with a ∈ Σ, and let yb be
the shortest member in Paths(ax) where y ∈ Σ ∗ and b ∈ Σ. Then, yb ∈Minimal ([ax]≡ ) if and only if (1) |Paths(ax)| > |Paths(x)| or (2) Freq(ax ) <Freq(x ).
Proof. It is clear when y = ε. We consider the case where y = ε. Let y = ay  fory ∈ Σ ∗.
(⇒) Assume ay  b ∈ Minimal ([ax]≡ ), which implies ay  ∈/ [ax]≡ and y  b ∈/[ax]≡ . First, consider the case where x ∈ [ax]≡ . Then clearly (2) holds. For the−→/ [ax]≡ = [x]≡ , and there exists a nodecase where x ∈ [ax]≡ , y  b = x since y  b ∈−→corresponding to y  b on the path from y  to x. Therefore (1) holds.
(⇐) Since ay  b is the shortest member in Paths(ax), ay  ∈ [ax]≡ . It remains
to show y  b ∈ [ax]≡ . If we assume (2), Freq(ax ) < Freq(x ) ≤ Freq(y  b) since y  b

7Algorithm 1: Algorithm for computing a succinct representation, the sizeand frequency of each non-degenerate equivalence class using suﬃx trees
Input: ST(w),SLT(w) : suﬃx tree and suﬃx link tree of w
Output: a succinct representation, the size and frequency of eachnon-degenerate equivalence class
1 foreach node v ∈ V in post-order of ST(w) do
2
calculate and store the values Freq(v) and |Paths (v)|;
3 size := 0; freq := 0;
4 foreach node v ∈ V in post-order of SLT(w) do
5
if v is a leaf of SLT(w) or freq = Freq(v) then6
if size = 0 then7
report size as the size of [rep v]≡ ;8minimal := minimal ∪ {i, j} s.t. w[i : j] is the shortest string in
Paths (old v);
9report (i, j, minimal) as a succinct representation of [rep v]≡ ,where w[i : j] = rep v;
10minimal := ∅;11
freq := Freq(v); report freq as the frequency of [rep v]≡ ;12size := |Paths (v)|; len := |Paths (v)|; old v := v; rep v := v;
13
else
14
if len > |Paths (v)| then15
minimal := minimal ∪ {i, j} s.t. w[i : j] is the shortest string in
Paths (old v);
16
size := size + |Paths (v)|; len := |Paths (v)|; old v := v;
17end
18 endis a preﬁx of x. Therefore, we have y  b ∈ [ax]≡ because Freq(y  b) = Freq(ax ).
Next, assume (1) when (2) does not hold, that is, Freq(y  b) = Freq(ax ). Then,−→y  b = x or else, |Paths(ax)| = |Paths(x)|. Therefore, y  b ∈ [x]≡ = [ax]≡ .
A pseudo-code of the algorithm to compute a succinct representation of eachnon-degenerate equivalence class together with its size and frequency is shownas Algorithm 1. The above arguments lead to the following theorem.
Theorem 1. Given ST (w) and SLT (w), Algorithm 1 computes succinct representations of all non-degenerate equivalence classes under ≡, together with theirsizes and frequencies in linear time.

4

Computing Equivalence Classes under ≡ Using Suﬃx
Array

In this section, we develop an algorithm that simulates Algorithm 1 using sufﬁx arrays. Our algorithm is based on the algorithm by Kasai et al. [8] which
simulates a post-order traversal on suﬃx trees with SA, rank and lcp arrays. A

8

key feature of our algorithm is that it does not require any extra data structureother than the suﬃx, rank and lcp arrays, making it quite space economical.
For any string x ∈ Substr(w), letLbeg(x) = SA[min{rank [i] | i ∈ BegPos(x)}] andRbeg(x) = SA[max{rank [i] | i ∈ BegPos(x)}].
Recall that Algorithm 1 traverses SLT (w). Our suﬃx array based algorithm→
simulates traversal on ST (w), and when reaching any node x such that x = ←x,it simulates suﬃx link tree traversal until reaching node y ∈ Suﬃx (x) such thaty ≡ x.
The next lemma states that for any node x of ST (w), Freq(x ) is constanttime computable using rank array.
Lemma 9. For any node x ∈ V of ST (w),
Freq(x ) = rank [Rbeg(x)] − rank [Lbeg(x)] + 1.
→
When reaching any node x such that x = ←x in the post-order traversal on
ST (w), we compute a succinct representation of [x]≡ due to Lemma 3. Examina→tion of whether x = ←x can be done in constant time according to the following
lemma.
Lemma 10. For any node x ∈ V of ST (w), let l = Lbeg(x) and r = Rbeg(x).
→We have x = ←x if and only if at least one of the following holds: (1) l − 1 = 0 or
r−1 = 0, (2) w[l−1] = w[r−1], or (3) rank [r]−rank [l] = rank [r−1]−rank[l−1].
→
Proof. (⇒) First, let us assume x = ←x . If (1) and (2) do not hold, that is,l − 1 = 0, r − 1 = 0 and w[l − 1] = w[r − 1] = a, then Freq(x ) > Freq(ax ) due toLemma 3. This implies rank [r] − rank [l] > rank [Rbeg(ax)] − rank [Lbeg(ax)] ≥rank [r − 1] − rank [l − 1] from Lemma 9, showing (3).
−(⇐) To show the reverse, we have only to show ←x since x is a node of→−→
ST (w), and therefore x = x . First, we show (1) ⇒ x = ←x . If l = 1, then−. Thex|x| ∈ EndPos(x) while |x| ∈ EndPos(ax) for any a ∈ Σ, implying x = ←same applies for r = 1.
→
Next, we show (2) ⇒ x = ←x when (1) does not hold, that is, l − 1 = 0 andr − 1 = 0. Since w[l − 1] = w[r − 1], we have that l − 1 + |x| ∈ EndPos(x) whilel − 1 + |x| ∈ EndPos(w[r − 1]x) and r − 1 + |x| ∈ EndPos(w[r− 1]x). Therefore,
Freq(x ) > Freq(w [r − 1 ]x ) > 0, and since Freq(x ) ≥ a∈Σ Freq(ax ), we have−.
Freq(ax ) < Freq(x ) for all a ∈ Σ, thus implying x = ←x←→Finally, we show (3) ⇒ x = x when (1) and (2) do not hold, that is, l−1 = 0,
r − 1 = 0 and w[l − 1] = w[r − 1] = a. (3) implies that rank [r] − rank [l] >rank [Rbeg(ax)] − rank [Lbeg(ax)] ≥ rank [r − 1] − rank [l − 1], and from Lemma 9
we have that Freq(x ) > Freq(ax ) > 0. Therefore x ≡ ax from Lemma 3, implying
−
x=←
x.
→
Therefore, we have x = ←x if we assume at least one of (1)–(3).
9Now we consider to check whether or not ax ≡ x for any nodes ax, x of
ST (w), where a ∈ Σ and x ∈ Σ ∗ . By deﬁnition, it is clear that Lbeg(ax) + 1 ∈BegPos(x) and Rbeg(ax) + 1 ∈ BegPos(x). However, note that Lbeg(ax) + 1 =Lbeg(x) does not always hold (same for Rbeg).
To check if ax ≡ x, we need to know whether or not Lbeg(ax) + 1 = Lbeg(x),and it can be done by the following lemma:
Lemma 11. For any nodes ax, x ∈ V of ST (w) such that a ∈ Σ and x ∈ Σ ∗ ,let l = Lbeg(ax). Then, lcp[rank [l + 1]] < |ax| − 1 if and only if Lbeg(x) = l + 1.
Proof. If Lbeg(x) = l + 1, then clearly lcp[rank [l + 1]] < |x| = |ax| − 1.
Now, assume on the contrary that Lbeg(x) = l + 1. Then, rank [Lbeg(x)] <rank [l + 1], and since w[Lbeg (x) :] and w[l + 1 :] share x as a preﬁx, we havelcp[rank [l + 1]] ≥ |x| = |ax| − 1 which is a contradiction.

The following lemma can be shown in a similar way to the above lemma:
Lemma 12. For any nodes ax, x ∈ V of ST (w) such that a ∈ Σ and x ∈ Σ ∗ ,let r = Rbeg(ax). Then, lcp[rank [r + 1] + 1] < |ax| − 1, if and only if Rbeg(x) =r + 1.
Now we have the following lemma on which our examination of equivalence
relation is based.
Lemma 13. For any nodes ax, x ∈ V of ST (w) such that a ∈ Σ and x ∈ Σ ∗ ,we have ax ≡ x if and only if(1) |ax| − 1 > lcp[rank [l + 1]],(2) |ax| − 1 > lcp[rank [r + 1] + 1], and(3) rank [r] − rank [l] = rank [r + 1] − rank [l + 1],
where l = Lbeg(ax) and r = Rbeg(ax).
Proof. (⇒) Assume ax ≡ x. Then, Freq(ax ) = Freq(x ) and thus we haverank [Rbeg(ax)]−rank[Lbeg(ax)] = rank [Rbeg(x)]−rank[Lbeg(x)] from Lemma 9.
From Freq(ax ) = Freq(x ), we have Rbeg(x) = Rbeg(ax) + 1 = r + 1 andLbeg(x) = Lbeg(ax) + 1 = l + 1. By Lemma 11 and Lemma 12 we get |ax| − 1 >lcp[rank [l + 1]] and |ax| − 1 > lcp[rank [r + 1] + 1].
(⇐) From Lemma 11, if |ax|−1 > lcp[rank [l + 1]], then Lbeg(x) = l+1. From
Lemma 12, if |ax| − 1 > lcp[rank [r + 1] + 1], then Rbeg(x) = r + 1. Therefore,
if rank [r] − rank [l] = rank [r + 1] − rank [l + 1], then Freq(ax ) = Freq(x ) byLemma 9. Consequently, we get ax ≡ x from Lemma 3.

Next, we consider how to compute |Paths(x)| = |x| − |Parent (x)|. When→x=←x , we know |x| and |Parent (x)| which are computed in post-order traversal→
on ST (w) simulated by the algorithm of [8]. When x = ←x , namely, when x has
been reached in suﬃx link traversal simulation, we have that |x| = |ax|− 1 whereax is the node reached immediately before x in the suﬃx link tree traversal
simulation. We have the following lemma for computation of |Parent (x)|.

10Algorithm 2: Algorithm for computing a succinct representation, the sizeand frequency of each non-degenerate equivalence class using suﬃx, lcp andrank arrays
Input: SA[1 : |w|], lcp[1 : |w|], rank [1 : |w|] : suﬃx, lcp and rank arrays of string w
Output: a succinct representation, the size and frequency of eachnon-degenerate equivalence class
1 Stack initialization (Left, Height) := (−1, −1);
2 for i = 1, . . . , n do
3
Lnew := i − 1; Hnew := lcp[i]; Left := Stack.Left; Height := Stack.Height;
4
while Height > Hnew do
5
Pop Stack;6
if Stack.Height > Hnew then parent := Stack.Height;
7
else parent = Hnew;
8
L := Left; R := i − 1; freq := R − L + 1; rlen := Height;
9
if (SA[L] = 1)&(SA[R] = 1) then10
BL := rank [SA[L] − 1]; BR := rank [SA[R] − 1];
11
if (BR−BL+1 = freq) or (w[BL] = w[BR]) or (SA[L] = 1) or (SA[R] = 1) then12
Let x = w[SA[L] : SA[L] + rlen − 1];
13report freq as the frequency of [x]≡ ;14
size := rlen − parent; mlen := rlen − parent; len := rlen; minimal := ∅;15
FL := rank [SA[L] + 1]; FR := rank [SA[R] + 1]; BL := L; BR := R;
16
while (len−1 > lcp[FL])&(len−1 > lcp[FR+1])&(FR−FL+1 = freq) do
17
if lcp[FL] ≥ lcp[FR + 1] then parent := lcp[FL];18else parent := lcp[FR + 1];
19
len := len − 1; size := size + len − parent;20
if mlen > len − parent then21
minimal := minimal ∪ {SA[BL], SA[BL] + parent};22
BL := FL; BR := FR;
23
if (SA[FL] + 1 ≥ |w|) or (SA[FR] + 1 ≥ |w|) then break;24
FL := rank [SA[FL]+1]; FR := rank [SA[FR]+1]; mlen := len−parent;
25
report size as the size of [x]≡ ;26
minimal := minimal ∪ {SA[BL], SA[BL] + parent};27
report(SA[L], SA[L] + rlen − 1, minimal) as a succinct
representation of [x]≡ ;28
Lnew := Left; Left := Stack.Left; Height := Stack.Height;
29
if Height < Hnew then Push(Lnew, Hnew) to Stack;30
Push(i, |w| − SA[i]) to Stack;
31 endLemma 14. For any node x ∈ V of ST (w), let l = Lbeg(x) and r = Rbeg(x).
Then, |Parent (x)| = max{lcp[rank [l]], lcp[rank [r] + 1]}.
Proof. For all 1 ≤ i < rank [l], the length of the longest common preﬁx of
w[SA[i] :] and x is at most lcp[rank [l]]. Similarly for rank [r] < j ≤ |w|, the lengthof the longest common preﬁx of w[SA[j] :] and x is at most lcp[rank [r] + 1]. Also,
for all rank [l] ≤ k ≤ rank [r], the longest common preﬁx of w[SA[k] :] and x is|x|, and therefore lcp[k] ≥ |x| for all rank [l] < k ≤ rank [r]. This implies that

11

|Parent (x)| is equal to either lcp[rank [l]] or lcp[rank [r] + 1] and hence the lemma
follows.

A pseudo-code of the algorithm is shown in Algorithm 2. The for and whileloops on line 2 and line 4 simulate a post-order traversal on ST (w) using SA,
rank and lcp arrays, and it takes linear time due to [8]. Checking whether or not→x=←
x for any node x reached in the post-order traversal on ST (w), is done inline 11 due to Lemma 10. Thus, we go into the while loop on line 16 only when→x=←x , and this while loop continues until reaching y ∈ Suﬃx (x) such thaty ≡ x due to Lemma 13. It is clear that all calculations in the while loop canbe done in constant time.
Theorem 2. Given SA, rank and lcp arrays of string w, Algorithm 2 computes
succinct representations of all non-degenerate equivalence classes under ≡, together with their sizes and frequencies in linear time.

5

Experimental Results

We performed preliminary experiments on corpora [15, 16], to compare practicaltime and space requirements of suﬃx tree, CDAWG, and suﬃx array based approaches to compute a succinct representation of for each non-degenerate equivalence class under ≡, together with its size and frequency.
We constructed suﬃx trees using Ukkonen’s algorithm [6], and ran Algorithm 1. CDAWGs were constructed using the CDAWG construction algorithmof [4]. We computed suﬃx arrays using the qsufsort program by [17]. All theexperiments were conducted on a RedHat Linux desktop computer with a 2.8
GHz Pentium 4 processor and 1 GB of memory.
Table 1 shows the running time and memory usage of the algorithms foreach data structure. The enumeration column shows the time eﬃciency of thealgorithms computing succinct representations of all equivalence classes together
with their sizes and frequencies. For all the corpora the suﬃx array approach
was the fastest. In addition, the suﬃx array algorithm uses the least memory
space for all the corpora.

References
1. Blumer, A., Blumer, J., Haussler, D., Mcconnell, R., Ehrenfeucht, A.: Complete
inverted ﬁles for eﬃcient text retrieval and analysis. J. ACM 34(3) (1987) 578–595
2. Narisawa, K., Bannai, H., Hatano, K., Takeda, M.: Unsupervised spam detection
based on string alienness measures. Technical report, Department of Informatics,
Kyushu University (2007)
3. Takeda, M., Matsumoto, T., Fukuda, T., Nanri, I.: Discovering characteristic expressions in literary works. Theoretical Computer Science 292(2) (2003) 525–546
4. Inenaga, S., Hoshinoa, H., Shinohara, A., Takeda, M., Arikawa, S., Mauri, G.,
Pavesi, G.: On-line construction of compact directed acyclic word graphs. Discrete
Applied Mathematics 146(2) (2005) 156–179

12Table 1. The comparison of the computation time and memory space for suﬃx trees,
CDAWGs and suﬃx arrays.
corpora data
namedata size(Mbytes)cantrby/plrabn12

0.47

ProteinCorpus/sc

2.8

large/bible.txt

3.9

large/E.coli

4.5

data
Time (seconds)
memorystructure construction enumeration total (Mbytes)
Suﬃx Tree
0.95
0.21
1.16 21.446
CDAWG
0.97
0.18
1.15 9.278
Suﬃx Array
0.43
0.14
0.57 5.392
Suﬃx Tree
12.08
1.43
13.51 121.877
CDAWG
12.76
1.12
13.88 69.648
Suﬃx Array
3.08
0.63
3.71 33.192
Suﬃx Tree
7.33
2.23
9.56 191.869
CDAWG
6.68
1.62
8.30 56.255
Suﬃx Array
4.71
1.50
6.21 46.319
Suﬃx Tree
8.17
2.91
11.08 232.467
CDAWG
8.58
2.31
10.89 139.802Suﬃx Array
5.95
1.46
7.41 53.086

5. Weiner, P.: Linear pattern matching algorithms. In: Proc. 14th IEEE Annual
Symp. on Switching and Automata Theory. (1973) 1–11
6. Ukkonen, E.: On-line construction of suﬃx trees. Algorithmica 14(3) (1995) 249–260
7. Manber, U., Myers, G.: Suﬃx arrays: a new method for on-line string searches.
SIAM J. Computing 22(5) (1993) 935–948
8. Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time LongestCommon-Preﬁx Computation in Suﬃx Arrays and Its Applications. In: Proc. of
CPM’01. Volume 2089 of LNCS., Springer-Verlag (2001) 181–192
9. Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suﬃx trees with enhanced
suﬃx arrays. Journal of Discrete Algorithms 2(1) (2004) 53–86
10. Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.:
The smallest automaton recognizing the subwords of a text. Theoretical Computer
Science 40 (1985) 31–55
11. McCreight, E.M.: A space-economical suﬃx tree construction algorithm. J. ACM
23(2) (1976) 262–272
12. Kärkkäinen, J., Sanders, P.: Simple linear work suﬃx array construction. In: Proc.
ICALP’03. Volume 2719 of LNCS., Springer-Verlag (2003) 943–955
13. Kim, D.K., Sim, J.S., Park, H., Park, K.: Linear-time construction of suﬃx arrays.
In: Proc. CPM’03. Volume 2676 of LNCS. (2003) 186–199
14. Ko, P., Aluru, S.: Space eﬃcient linear time construction of suﬃx arrays. In: Proc.
CPM’03. Volume 2676 of LNCS. (2003) 200–210
15. Arnold, R., Bell, T.: A corpus for the evaluation of lossless compression algorithms.
In: Proc. DCC ’97. (1997) 201–210 http://corpus.canterbury.ac.nz/.
16. Nevill-Manning, C., Witten, I.: Protein is incompressible. In: Proc. DCC ’99.
(1999) 257–266 http://www.data-compression.info/Corpora/ProteinCorpus/
index.htm.
17. Larsson, N.J., Sadakane, K.: Faster suﬃx sorting. Technical Report LU-CS-TR:99214, LUNDFD6/(NFCS-3140)/1–20/(1999), Department of Computer Science,
Lund University, Sweden (1999) http://www.larsson.dogma.net/qsufsort.c.