Simple Linear-Time Off-Line Text Compression
by Longest-First Substitution
Ryosuke Nakamura1 , Hideo Bannai1 , Shunsuke Inenaga2 , and Masayuki 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){r-naka, bannai, shunsuke.inenaga, takeda}@i.kyushu-u.ac.jp

Abstract
We consider grammar based text compression with longest first substitution, where non-overlapping
occurrences of a longest repeating substring of the input text are replaced by a new non-terminal
symbol. We present a new text compression algorithm by simplifying the algorithm presented in [4].
We give a new formulation of the correctness proof introducing the sparse lazy suffix tree data
structure. We also present another type of longest first substitution strategy that allows better compression. We show results of preliminary experiments comparing grammar sizes of the two versionsof the longest first strategy and the most frequent strategy.

1

Introduction

In this paper we consider text compression by longest first substitution (named LFS). Given astring, we construct a context-free grammar by substituting new characters for the longest factorsthat are repeating without overlapping. For example, for w = abaaabbababb$, we construct thefollowing grammar: S → BaaABA$; A → abb; B → ab, which generates only w. Bentley and
McIlroy [3] gave an algorithm for this compression scheme, but Nevill-Manning and Witten [7]stated that it does not run in linear time. They also claimed the algorithm by Bentley and McIlroy
can be improved so as to run in linear time, but they only noted a too short sketch for how, whichis unlikely to give a shape to the idea of the whole algorithm.
In [4], details of an algorithm achieving linear time longest-first substitution were given. The
algorithm made extensive use of the suffix tree data structure [9]. However, the algorithm was toocomplicated for practical implementations, and moreover, the correctness of the algorithm was noteasy to see. In this paper, we show a simplified algorithm for longest-first substitution which runs
in linear time. The new algorithm is based on the previous algorithm, and uses some properties
of suffix trees shown in the previous paper. This paper presents several new tricks and a new,simplified formulation of the algorithm by introducing the sparse lazy suffix tree data structure.
Moreover, this paper deals with another type of longest-first text compression (named LFS2),
where we also consider repeating factors of the righthand of the existing production rules. Thismethod allows better compression since the total grammar size becomes smaller. For the runningstring abaaabbababb$, we obtain the following grammar: S → BaaABA$; A → Bb; B → ab. This
paper presents the first algorithm that accomplishes LFS2 in linear time and space.
1.1

Related Work

It is well known that, given a string w, computing the smallest grammar that generates w is
NP-hard [8]. Thus, linear-time greedy strategies for text compression is of significant practicalimportance. Larsson and Moffat [6] presented a linear-time algorithm called Re-pair. It recursively
substitutes non-terminal symbols for the factors of length 2 whose non-overlapping occurrences are
the most among the factors of length 2. This strategy is called the most frequent first substitution(called MFFS). Apostolico and Lonardi [1] presented a text compression technique where factorsof the largest “area” are recursively replaced by non-terminal symbols. Here the area of a factor
refers to the product of the length of the factor by the number of its non-overlapping occurrencesin the input string. To the best of our knowledge, no linear-time algorithm for largest-area-firstsubstitution based compression is known.
Figure 1 shows a table that compares the grammar sizes generated by MFFS, LFS, and LFS2.
The input texts files are from the Canterbury Corpus [2].
Filealice29.txt
asyoulik.txt
cp.htmlfields.cgrammar.lsp
kennedy.xls
lcet10.txt
plrabn12.txt
ptt5
sum
xargs.1

Size(Bytes)152090125179
24603
11150
3721
102974442675448186151321638240
4227

total grammar size
MFFS
LFS
LFS2
38750
88333
45225
35245
74747
41755
8006
14559
7977
3535
6525
3307
1597
2332
1431
165589 291536 166250
84923 235112 103602
116128 276714 144078
42813 266040
47885
13023
20846
12103
2096
2772
1906

Figure 1. Comparison of the grammar sizes generated by the greedy text compression
algorithms.

2

Preliminaries

2.1

NotationsLet Σ be a finite alphabet of symbols. We assume that Σ is fixed and |Σ| is constant. An elementof Σ∗ is called a string. Strings x, y, and z are said to be a prefix, factor, and suffix of stringw = xyz, respectively.
The length of a string w is denoted by |w|. The empty string is denoted by ε, that is, |ε| = 0.
Also, we assume that all strings end with a unique symbol $ ∈ Σ that does not occur anywhere elsein the strings. Let Σ+ = Σ∗ \{ε}. The i-th symbol of a string w is denoted by w[i] for 1 ≤ i ≤ |w|,and the factor of a string w that begins at position i and ends at position j is denoted by w[i : j]for 1 ≤ i ≤ j ≤ |w|. For convenience, let w[i : j] = ε for j < i, and w[i :] = w[i : |w|] for 1 ≤ i ≤ |w|.
For any strings x, w, let BP w (x) denote the set of the beginning positions of all the occurrences of
x in w. That is, BP w (x) = {i | x = w[i : i + |x| − 1]}.
We say that strings x, y overlap in w if there exist integers i, j such that x = w[i : i + |x| − 1],
y = w[j : j + |y| − 1], and i ≤ j ≤ i + |x| − 1.
Let #occ w (x) denote the possible maximum number of non-overlapping occurrences of x in w.
If #occ w (x) ≥ 2, then x is said to be repeating in w. We abbreviate a longest repeating factor of w
to an LRF of w. Remark that there can exist more than one LRF for w.
Let Σ and Π be the set of terminal and non-terminal symbols, respectively, so that Σ ∩ Π = ∅. A
context free grammar G is a formal grammar in which every production rule is of the form A → v,
where A ∈ Π and v ∈ (Σ ∪ Π)∗ . The length of production rule A → v, denoted |A| = |v|, is thelength of the string x ∈ Σ∗ derived from the production rule. The size of the production rule is thenumber of terminal and non-terminal symbols v contains. Any non-terminal symbol A in G has |A|positions. We denote A[1] = A and A[i] = • for any 1 < i ≤ |A|. Similarly, any string w ∈ (Σ ∪ Π)∗
has |w| positions and w[i] ∈ Σ ∪ Π ∪ {•} denotes the symbol of the i-th position of w.
2.2

Data Structures

Our text compression algorithm uses a data structure based on suffix trees [9]. The suffix treeof string w, denoted by STree(w), is defined as follows:
Definition 1 (Suffix Trees) STree(w) is a tree structure such that: (1) every edge is labeled by anon-empty factor of w, (2) every internal node has at least two child nodes, (3) all out-going edge
labels of every node begin with mutually distinct symbols, and (4) every suffix of w is spelled out ina path starting from the root node.
Assuming any string w terminates with the unique symbol $ not appearing elsewhere in w, there
is a one-to-one correspondence between a suffix of w and a leaf node of STree(w). It is easy to seethat the numbers of the nodes and edges of STree(w) are linear in |w|. Moreover, by encoding everyedge label x of STree(w) with an ordered pair (i, j) of integers such that x = w[i : j], each edge
only needs constant space. Therefore, STree(w) can be implemented with total of O(|w|) space.
Also, it is well known that STree(w) can be constructed in O(|w|) time (e.g. see [9]).
STree(w) for string w = ababa$ is shown in Figure 2. For any node v of STree(w), str (v) denotes
the string obtained by concatenating the labels of the edges in the path from the root node to nodev. The length of node v, denoted len(v), is defined to be |str (v)|. It is an easy application of the
Ukkonen algorithm [9] to compute the lengths of all nodes while constructing suffix trees. The leaf
node ` such that str (`) = w[i :] is denoted by leaf i , and i is said to be the id of the leaf. Every node
v of STree(w) except for the root node has a suffix link, denoted by suf (v), such that suf (v) = v 0
where str (v 0 ) is a suffix of str (v) and len(v 0 ) + 1 = len(v). Linear-time suffix tree construction
algorithms (e.g., [9]) make extensive use of the suffix links.
A sparse suffix tree [5] of w ∈ Σ∗ is a kind of suffix tree which represents only a subset of thesuffixes of w. The sparse suffix tree of w ∈ (Σ ∪ Π)∗ represents a subset {w[i :] | w[i] ∈ Σ}. Let `be the length of the LRFs of w. A reference node v of the sparse suffix tree of w ∈ (Σ ∪ Π)∗ is anode such that len(v) ≥ ` + 1, and there is no node u such that str (u) is a proper prefix of str (v)and len(u) ≥ ` + 1.
Our algorithm uses the following data structure.

$

a

b
6

a
b

$

a
b

$

5

b
a

a
$

$

4

$
3
1

2

Figure 2. STree(w) with w = ababa$. Solid arrows represent edges, and dotted arrows are
suffix links.
Definition 2 (Sparse Lazy Suffix Trees) A sparse lazy suffix tree (SLSTree) of string w ∈(Σ∪Π)∗ , denoted by SLSTree(w), is a kind of sparse suffix tree such that: (1) All paths from the root
node to the reference nodes coincide with those of the sparse suffix tree of w, and (2) Every reference
node v stores an ordered triple hmin(v), max(v),card(v)i¯¯ such that min(v) = min BP w (str (v)),¯
max(v) = max BP w (str (v)), and card(v) = BP w (str (v))¯.
Proposition 1 For any string w ∈ Σ∗ , SLSTree(w) can be obtained from STree(w) in O(|w|) time.
Proof. By a standard postorder traversal on STree(w), propagating the id of each leaf node.

¤Since STree(w) can be constructed in O(|w|) time [9], we can build SLSTree(w) in total of O(|w|)
time.

3

Off-Line Compression by Longest-First Substitution

Given a text string w ∈ Σ∗ , we here consider a greedy approach to construct a context-freegrammar which generates only w. The key is how to select a factor of w to be replaced by anon-terminal symbol from Π. Here, we consider the longest-first-substitution approach where werecursively replace as many LRFs as possible with non-terminal symbols.
Example. Let w = abaaabbababb$. At the beginning, the grammar is of the following simple form
S → abaaabbababb$, where the righthand of the production rule consists only of terminal symbols
from Σ. Now we focus on the righthand of S which has two LRFs aba and abb. Let us herechoose abb for being replaced by non-terminal A ∈ Π, and then we obtain the following grammar:
S → abaaAabA$; A → abb. The other LRF aba of length 3 is no longer present in the righthandof S. Thus we focus on an LRF ab of length 2. Replacing ab by non-terminal B ∈ Π results in thefollowing grammar: S → BaaABA$; A → abb; B → ab. Since the righthand of S has no repeating
factor longer than 1, we are done.
Let w0 = w, and let wk denote the string obtained by replacing an LRF of wk−1 with a nonterminal symbol Ak . LRF (wk−1 ) denotes the LRF of wk−1 that is replaced by Ak , namely, we
create a new production rule Ak → LRF (wk−1 ). In the above example, w0 = w = abaaabbababb$,
LRF (w0 ) = abb, A1 = A, w1 = abaaAabA$, LRF (w1 ) = ab, A2 = B, and w2 = BaaABA$.

Due to the property of the longest first approach, we have the following observation.
Observation 1 Let A1 , . . . , Ak ∈ Π be the non-terminal symbols which replace LRF (w0 ), . . . ,LRF (wk−1 ), respectively. For any 1 ≤ i ≤ k, the righthand of the production rule of Ai contains
none of A1 , . . . , Ai−1 .
3.1

Algorithm

In this section we show our algorithm which outputs a context free grammar which generates agiven string. Our algorithm heavily uses the SLSTree structure.
3.1.1

Finding LRF Using SLSTrees

Lemma 1 Suppose x is an LRF of wk represented by none of the nodes of SLSTree(wk ). Then,
there exists another LRF y of wk that is represented by a node of SLSTree(wk ) such that |x| = |y|and #occ wk (y) ≥ #occ wk (x) = 2. Moreover, x is no longer present in wk+1 after the substitution
for y.
The above lemma implies that it suffices to consider the strings corresponding to the nodes of
SLSTree(wk ) as candidates for LRF (wk ).
After constructing SLSTree(w0 ) = SLSTree(w), we create a bin-sorted list of the internal nodes
of SLSTree(w) in the increasing order of their lengths. It can be done in linear time by a standard
traversal on SLSTree(w). We remark that a new internal node v may appear in SLSTree(wk ) forsome k ≥ 1. However, we have that len(v) ≤ LRF (wk−1 ). Thus, we can maintain the bin-sorted
list by inserting node v in constant time .
Using SLSTree(wk ), for any node v in the bin-sorted list it is easy to determine whether or not
str (s) is repeating. Let s1 , . . . , s` be the children of s. If and only if max{max(si ) | 1 ≤ i ≤`} − min{min(sj ) | 1 ≤ j ≤ `} ≥ len(s), str (s) is repeating. The following lemma can be shown ina similar way as in [4].
Lemma 2 For any node s of SLSTree(wk−1 ) such that |LRF (wk )| ≤ len(s) ≤ |LRF (wk−1 )|, ittakes amortized constant time to check whether or not str(s) is an LRF of wk .
In what follows we show our greedy strategy of selecting which occurrences of an LRF we replacewith a new non-terminal symbol.
The following lemma can be shown by a similar idea mentioned in [4].
Lemma 3 For any non-repeating factor x of wk , BP wk (x) forms a single arithmetic progression.
Therefore, for any non-repeating factor x of wk , BP wk (x) can be expressed by an ordered triple
consisting¯¯ of minimum element min BP wk (x), maximum element max BP wk (x), and cardinality¯BP w (x)¯.
k
The following lemma is a direct adaptation from [4].
Lemma 4 Let s be any node of SLSTree(wk ) that is at most as long as the LRFs of wk , andlet s1 , . . . , s` be the children of s. Then BP wk (str (s)) is a disjoint union of BP wk (str (s1 )), . . . ,BP wk (str (s` )), each forming a single arithmetic progression.
Lemma 5 Let s be the node of SLSTree(wk ) such that str (s) is an LRF of wk , and s0 be any
child of s. Then, BP (str (s0 )) contains at most two positions corresponding to non-overlapping
occurrences of str (s) in wk .

Proof. Assume for contrary that BP (str (s0 )) contains three occurrences of str (s), and let them be
i1 , i2 , i3 in the increasing order. Then we havei3 − (i1 + len(s) − 1) ≥ i3 − i2 ≥ len(s) ≥ 1,
which implies that w[i1 : i1 + len(s)] and w[i3 : i3 + len(s)] are non-overlapping. Moreover, sincelen(s0 ) > len(s) and from Lemma 4, we have w[i1 : i1 + len(s)] = w[i3 : i3 + len(s)]. However, thiscontradicts that str (s) is an LRF.
¤
From Lemma 5, each child s0 of node s such that str (s) is an LRF, corresponds to at most two
non-overlapping occurrences of str (s). Thus, by checking all children s1 , . . . , s` , we can greedily
obtain occurrences of str (s) to be replaced, and it takes amortized constant time for each node s.
Note that we have to select occurrences of str (s) so that no occurrences of str (s) remain in the
text string, and at least two occurrences of str (s) are selected. We remark that we can greedilychoose at least max{2, #occ(str (s))/2} occurrences.
3.1.2

Updating SLSTree(wki−1 ) to SLSTree(wki )Let L be the set of the greedily selected occurrences of LRF (wk ) in wk . For any 0 ≤ i ≤ |L|,i
wk denote the string obtained after replacing the first i occurrences of LRF (wk ) with non-terminal|L|symbol Ak+1 . Namely, wk0 = wk and wk = wk+1 .
In this section we show how to update SLSTree(wki−1 ) to SLSTree(wki ). Let p be the beginning
position of the i-th largest occurrence in L. Assume that we have SLSTree(wki−1 ), and that we have
replaced wki−1 [p : p+|LRF (wk )|−1] with non-terminal symbol Ak+1 such that |Ak+1 | = |LRF (wk )|.
We now have wki , and we have to update SLSTree(wki−1 ) to SLSTree(wki ).
To obtain SLSTree(wki ), the most intuitive way is to remove all the suffixes of wki−1 from the tree
and insert all the suffixes of wki into it. However, since only the nodes not longer than LRF (wk )are important for SLSTree(wki ), only the suffixes wki−1 [p − t :] such that 1 ≤ t ≤ |LRF (wk )| andwki−1 [r] ∈ Σ for any p − t ≤ r < p, have to be removed and only the suffixes wki [p − t :] have to beinserted into the tree.

Proposition 2 For any wki [p − t :], there is a node s in SLSTree(wki ) such that str (s) = wki [p − t :p − 1] and s has an edge labeled with wki [p :] = Ak wki [p + |Ak | :] and leading to leaf p−t . Moreover,this edge never exists in SLSTree(wki−1 ).
Lemma 6 For each t, we can locate node s such that str (s) = wki [p−t : p−1] in amortized constanttime.
Let v be the reference node in the path from the root to some leaf p−t . Assume that leaf p−t
is removed from the subtree of v, and redirected to node s in the same path, such that str (s) =wki [p − t : p − 1]. In order to update SLSTree(wki−1 ) to SLSTree(wki ), we have to maintain triple
hmin(v), max(v), card(v)i for node v. One may be concerned that if p − t is neither min(v) ormax(v) and card(v) ≥ 4 in SLSTree(wki−1 ), the occurrences of str (v) in SLSTree(wki ) do not forma single arithmetic progression any more. However, we have the following lemma. For any factor
y of wki , let Dead wi (y) = BP wi−1 (y)\BP wi (y), namely, Dead wi (y) denotes the occurrences of y in
k

k

k

k

wki−1 that overlap with the i-th greedily selected occurrence of LRF (wk ) in wk .

str(v)w[a:b]wmam+|str(v)|-1
str(v)bw[a': b']
n

a'

b'

n+|str(v)|-1

Figure 3. Illustration of proof for Lemma 7.
Lemma 7 Let v be any reference node of SLSTree(wki ) such that #occ wi (str (v)) = 1. For anykinteger m, n, if m, n ∈ BP wi (str (v)), then there is no integer r such that m < r < n and r ∈kDead wi (str (v)). (See Figure 3.)k

Proof. Assume for contrary that there exists integer r such that r ∈ Dead wi (str (v)) and m < r < n.
kSince r ∈ Dead wi (str (v)), there exist integers a, b such that a ≤ r ≤ b, and b − a + 1 = 2|LRF (wk )|.
kFor any integer j such that a ≤ j ≤ b and j ∈ BP wi−1 (str (v)), we have j ∈ Dead wi (str (v)). Sincekkm, n ∈/ Dead wi (str (v)), m < a < b < n. As str (v) is non-repeating, n < m + len(v) − 1. Sincekm < a < b < m + len(v) − 1, w[a : b] is a factor of str (v). Therefore, there exist two integers a0 , b0
such that w[a0 : b0 ] = w[a : b]. Since m < a < b < n < a0 < b0 < n + len(v) − 1, w[a : b] is repeatingand |w[a : b]| = b − a + 1 = 2|LRF (wk )| > |LRF (wk )|. It contradicts that LRF (wk ) is an LRF ofwk .
¤Recall that p is the beginning position of the i-th largest greedily selected occurrence of LRF (wk )in wk . Also, for any 1 ≤ t ≤ |LRF (wk )| such that wki−1 [r] ∈ Σ for every p − t ≤ r < p, we haveremoved leaf p−t from the subtree rooted at the reference node v and have reconnected it to nodes such that str (s) = wki [p − t : p − 1]. According to the above lemma, if min(v) < p − t < max(v),leaf j for every p − t ≤ j ≤ max(v) is removed from the subtree of v. After processing leaf p−t , thenmax(v) is updated to p − t − d where d = (min(v) + max(v))/card(v) is the step of the progression,and card(v) is updated to (max(v) − (p − t))/d + 1.
Notice that leaf p+h for every 0 ≤ h ≤ |LRF (wk )| − 1 has to be removed from the tree, sinceiwk [p + h] ∈/ Σ and therefore this leaf node should not exist in SLSTree(wki ). Removing each leaf
can be done in constant time. Maintaining the information about the triple for the arithmetic
progression of the reference nodes can be done in the same way as mentioned above.
The following lemma states how to locate each reference node.
Lemma 8 Let p be the i-th greedily selected occurrence of LRF (wk ) in wk . For any integer ` suchthat wki−1 [`] ∈ Σ, let v(`) denote the reference node of SLSTree(wki−1 ) in the path from the root
spelling out suffix wki−1 [` :]. For each j such that p − |LRF (wk )| ≤ j ≤ p + |LRF (wk )| − 1, we canlocate the reference node v(j) in amortized constant time.
Proof. Let ` = |LRF (wk )|. We find v(p − `) by spelling out wki−1 [p − ` :] from the root in O(`)
time, since there can be at most ` + 1 nodes in the path from the root to v(p − `).
Suppose we have found v(j − 1). We find v(j) as follows. Let u(j − 1) be the parent node ofv(j − 1). We have len(u(j − 1)) ≤ ` and len(v(j − 1)) ≤ ` + 1. We go to suf (u(j − 1)). Sincelen(suf (u(j − 1))) + 1 = len(u(j − 1)), we have len(suf (u(j − 1))) ≤ ` + 1. Thus, we can find v(j)by going down the path starting from suf (u(j − 1)) and spelling out wki−1 [j − 1 + len(u(j − 1)) :j − 1 + len(v(j − 1))] = wki−1 [j + len(suf (u(j − 1))) : j − 1 + len(v(j − 1))]. (See also the left
illustration of Figure 4.)

w[p-1]
Ah࡮࡮࡮

|LRF(wk)||LRF(wk)||LRF(wk)|u(j-1)

leafp-1 = v(p-1)

u(j-1)v(j)v(j-1)v(j-1)Ah࡮࡮࡮

leafj-1
leafj-1

leafj
leafj = v(j)Figure 4. The left figure illustrates how to find v(j) from v(j − 1). The right one illustrates
a special case where v(j) = leaf j . Once v(j) = leaf j , it stands that v(k) = leaf k for any
j ≤ k ≤ p − 1.
A special case happens when there exists a node s in the path from the root to leaf j , such thatlen(s) = ` and the edge from s in the path starts with some non-terminal symbol Ah with h < k.
Namely, wki [j + `] = Ah . Due to the property of the longest first approach, we have |Ah | ≥ `.
Thus vj = leaf j . Moreover, for any j ≤ k ≤ p − 1, v(k) = leaf k . (See also the right illustration of
Figure 4.) It is thus clear that each v(k) can be found in constant time. Since |Ah | ≥ ` = LRF (wk ),the leaves corresponding to wki−1 [p + x − 1 :] with 1 ≤ x ≤ ` do not exist in SLSTree(wki−1 ).
¤From the above discussions, we conclude that:
Theorem 1 For any string w ∈ Σ∗ , the proposed algorithm for text compression by longest first
substitution runs in O(|w|) time using O(|w|) space.
Pseudo-codes of our algorithms are shown in Algorithms 1, 2 and, 3.
3.2

Reducing Grammar Size

In the above sections we considered text compression by longest first substitution, where weconstruct a context free grammar G that generates only a given string w. By Observation 1, forany production rule Ak → xk of G, xk contains only terminal symbols from Σ. In this section, we
take the factors of xk into consideration for candidates of LRFs, and also replace LRFs appearing
xk . This way we can reduce the total size of the grammar. In so doing, we consider an LRF of
string zk = wk x1 $1 · · · xk $k , where z0 = w0 = w and each $i appears nowhere else in zk .
Example. Let w = w0 = z0 = abaaabbababb$0 . We replace an LRF abb with A, and obtainthe following grammar: S → abaaAabA$0 ; A → abb. Then, w1 = abaaAabA$0 and LRF (z0 ) =abb. Now, z1 = abaaAabA$0 abb$1 . We replace an LRF ab of z1 with a non-terminal B, getting
S → BaaABA$0 ; A → Bb; B → ab. Then, w2 = BaaABA$0 and LRF (z1 ) = ab. Now,z2 = BaaABA$0 Bb$1 ab$2 . Since there is no LRF of length more than 1 in z2 , we are done.
We call this new method of text compression LFS2.
Theorem 2 Given a string w, the LFS2 strategy compresses w in linear time and space.

Algorithm 1: Recursively find longest repeating factors.
Input: String w ending with a unique symbol
Output: Set of grammar rules which produce w, greedily selected by substituting longest
repeating factors
1 SLSTree := sparse lazy suffix tree of w; bins := bin-sorted nodes; len := |w|; rules := ∅;2 while true do
3
while (n = bins.getNextOfLength(len)) = null do
4
if len ≤ 2 then return rules;
5
foreach x ∈ bins(len) do update x.min, x.max, x.card from children;6len--;
7
update n.min, n.max, n.card from children;8
if n.max − n.min ≥ n.pathlen /* n is repeating factor */ then9
nonTerm := new non-terminal symbol;
10
rules := rules ∪ {nonTerm → n.path };11
gso := getGreedilySelectedOccurrences(n);12updateSLSTree(w, n.pathlen, nonTerm, gso, SLSTree, bins);
13
14

Algorithm 2: updateSLSTree
Input: (w, LRFlen, nonTerm, gso, SLSTree, bins)
1 foreach occpos ∈ gso do
2for pos = max{1, occpos − LRFlen} to min{|w|, occpos + LRFlen − 1} do
3v := find first node on path to leaf pos such that v.pathlen > LRFlen;
4
delete leaf pos; maintain v.card, v.min, v.max;
5
if pos < occpos && notDead(pos) then6s := find/create node on path to leaf pos such that s.pathlen = occpos − pos;7
if s was newly created then bins(s.pathlen).addNode(s);8recreate leaf pos:hmin, max, cardi = hpos, pos, 1i; add edge (s, nonTerm, pos);
9
if pos > occpos then w[pos] = •; markDead(pos);10
w[occpos] := nonTerm; markDead(occpos);
11 return
Proof. We modify the algorithm proposed in the previous sections. If we have a generalized SLSTreefor set {wk , x1 $1 , . . . , xk $k } of strings, we can find an LRF of zk = wk x1 $1 · · · xk $k . It follows fromthe property of the longest first substitution strategy that |xi | ≥ |xj | for any i < j. Therefore,
any new node inserted into the generalized SLSTree for {wk , x1 $1 , . . . , xk−1 $k−1 } is shorter than
the reference nodes of the tree. Thus, using the Ukkonen on-line algorithm [9], we can obtain
the generalized SLSTree of {wk , x1 $1 , . . . , xk $k }, by inserting the suffixes of each xk $k into thegeneralized SLSTree of {wk , x1 $1 , . . . , xk−1 $k−1 } in O(|xk $k |) time. It is easy to see that the total
length of x1 $1 , . . . , xk $k , . . . is O(|w|).
¤

Algorithm 3: getGreedilySelectedOccurrences
Input: LRFnode
Output: Set of greedily selected occurrences of LRFnode.path
1 gso := ∅;2 foreach c ∈ LRFnode.children do
3
occ := 0;4
if notDead(c.min) then occ := c.min;5else occ := find first occurrence of LRFnode.path after c.min + endOfDeadArea[c.min];6
if occ 6= 0 && notDead(occ + LRFnode.pathlen −1) then7
gso := gso ∪ {occ};
8
for pos = occ to occ + LRFnode.pathlen −1 do
9markEndOfDeadArea(pos, occ + LRFnode.pathlen −1);
10
occ := occ + LRFnode.pathlen;11
if notDead(occ) && notDead(occ + LRFnode.pathlen −1) then gso := gso ∪ {occ};
12
13 return gso;

References[1] A. Apostolico and S. Lonardi. Off-line compression by greedy textual substitution. Proc. IEEE,
88(11):1733–1744, 2000.
[2] R. Arnold and T. Bell. A corpus for the evaluation of lossless compression algorithms. In Proc. Data
Compression Conference ’97 (DCC’97), pages 201–210, 1997.
[3] J. Bentley and D. McIlroy. Data compression using long common strings. In Proc. Data Compression
Conference ’99 (DCC’99), pages 287–295. IEEE Computer Society, 1999.
[4] S. Inenaga, T. Funamoto, M. Takeda, and A. Shinohara. Linear-time off-line text compression by longestfirst substitution. In Proc. SPIRE’03, volume 2857 of LNCS, pages 137–152. Springer-Verlag, 2003.
[5] J. Kärkkäinen and E. Ukkonen. Sparse suffix trees. In Proc. COCOON’96, volume 1090 of LNCS, pages
219–230. Springer-Verlag, 1996.
[6] N. J. Larsson and A. Moffat. Offline dictionary-based compression. Proc. IEEE, 88(11):1722–1732, 2000.
[7] C. G. Nevill-Manning and I. H. Witten. Online and offline heuristics for inferring hierarchies of repetitions
in sequences. Proc. IEEE, 88(11):1745–1755, 2000.
[8] J. Storer, NP-completeness Results Concerning Data Compression, Technical report 234, Department
of Electrical Engineering and Computer Science, Princeton University, 1977.
[9] E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995.