O(n log n)-time Text Compression
by LZ-style Longest First Substitution
Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga,
Hideo Bannai, and Masayuki Takeda
Department of Informatics, Kyushu University, Japan{akihiro.nishi, yuto.nakashima, inenaga, bannai, takeda}@inf.kyushu-u.ac.jp

Abstract. Mauer et al. [A Lempel-Ziv-style Compression Method for Repetitive Texts,
PSC 2017] proposed a hybrid text compression method called LZ-LFS which has bothfeatures of Lempel-Ziv 77 factorization and longest first substitution. They showed that
LZ-LFS can achieve better compression ratio for repetitive texts, compared to somestate-of-the-art compression algorithms. The drawback of Mauer et al.’s method is that
their LZ-LFS compression algorithm takes O(n2 ) time on an input string of length n.
In this paper, we show a faster LZ-LFS compression algorithm that works in O(n log n)time. We also propose a simpler version of LZ-LFS that can be computed in O(n) time.

1

Introduction

Text compression is a task to compute a small representation of an input text (orstring). Given a vast amount of textual data that has been produced to date, text
compression can play central roles in saving memory space and reducing data transmission costs.
Lempel-Ziv 77 (LZ77 ) [12] is a fundamental text compression method that is basedon a greedy factorization of the input string. LZ77 factorizes a given string w of lengthn into a sequence of non-empty substrings f1 , . . . , fk such that (1) w = f1 · · · fk and(2) each factor fi is the longest prefix of w[|f1 · · · fi−1 | + 1..n] that has an occurrence
beginning at a position in range [1..|f1 · · · fi−1 |] (this is a self-reference variant), or
fi = c if it is the leftmost occurrence of the character c in w. Each factor fi in thefirst case is encoded as a reference pointer to one of its previous occurrences in thestring. LZ77 and its variants are basis of many text compression programmes, suchas gzip.
In the last two decades, grammar compression has also gathered much attention. Grammar compression finds a small context-free grammar which generates only
the input string. Since finding the smallest grammar representing a given string is
NP-hard [9,8], various kinds of efficiently-computable greedy grammar compression
algorithms have been proposed. The most well-known method called Re-pair [3] isbased on a most frequent first substitution approach, such that most frequently occurring bigrams (substrings of length 2) are replaced with new non-terminal symbols
recursively, until there are no bigrams with at least two non-overlapping occurrences.
An alternative is a longest first substitution (LFS ) approach, where longest substrings that have at least two non-overlapping occurrences are replaced with new
non-terminal symbols recursively, until there are no substrings of length at least two
with at least two non-overlapping occurrences.
Recently, Mauer et al. [5] proposed a hybrid text compression algorithm called
LZ-LFS, which has both features of LZ77 and LFS. Namely, LZ-LFS finds a longest
substring which occurs at least twice in the string, replaces its selected occurrences
Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda: O(n log n)-time Text Compression by LZ-style Longest First
Substitution, pp. 12–26.
Proceedings of PSC 2018, Jan Holub and Jan Žd’árek (Eds.), ISBN 978-80-01-06484-9 c Czech Technical University in Prague, Czech Republic

A. Nishi et al.: O(n log n)-time Text Compression by LZ-style Longest First Substitution

13

with a special symbol #, and encodes each of them as a reference to its leftmost
occurrence. This is continued recursively, until there are no substrings of length atleast two which occur at least twice in the string. The details on how the occurrences
to replace are selected can be found in [5] as well as in a subsequent section in thispaper. Mauer et al. showed that LZ-LFS can have good practical performance incompressing repetitive texts. Indeed, in their experiments, the compression ratio of
LZ-LFS outperforms that of some state-of-the-art compression algorithms on data setsfrom widely-used corpora. The drawback, however, is that Mauer et al.’s compression
algorithm for LZ-LFS takes O(n2 ) time for input strings of length n.
In this paper, we focus on a theoretical complexity for computing LZ-LFS, andpropose a faster LZ-LFS algorithm which runs in O(n log n) time with O(n) space.
Our algorithm is based on Nakamura et al.’s algorithm for LFS-based grammar compression [7]. Although Nakamura et al.’s algorithm is quite involved, our algorithm
for LZ-LFS is much less involved due to useful properties of LZ-LFS. We also showthat a simplified version of LZ-LFS can be computed in O(n) time and space withslight modifications to our algorithm.

2

Preliminaries

2.1

String notations

Let Σ be an alphabet. An element of Σ ∗ is called a string. Strings x, y, and z are
said to be a prefix, substring, and suffix of string w = xyz, respectively.
The length of a string w is denoted by |w|. The empty string is denoted by ε, that
is, |ε| = 0. Let Σ + = Σ ∗ \ {ε}. The i-th character of a string w is denoted by w[i]for 1 ≤ i ≤ |w|, and the substring 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|.
An occurrence of a substring x of a string w is an interval [i..i + |x| − 1] such thatw[i..i + |x| − 1] = x. For simplicity, we will sometimes call the beginning position i ofx as an occurrence of x in w. Let Occw (x) denote the set of the beginning positionsof the occurrences of x in w. If x does not occur in w, then Occw (x) = ∅.
If |Occw (x)| ≥ 2, then x is said to be a repeat of w. A repeat x of w is said to bea longest repeat (LR) of w if there are no repeats of w that are longer than x. We
remark that there can exist more than one LR for w in general. A repeat y of w is said
to be a maximal repeat of w if for any characters a, b ∈ Σ, |Occw (ay)| < |Occw (y)| and|Occw (yb)| < |Occw (y)|. We also remark that any longest repeat of w is a maximal
repeat of w.
Let I = {i1 , . . . , ik } ⊆ Occw (x) be a (sub)set of occurrences of a repeat x in w
such that k ≥ 2 and i1 < · · · < ik . The occurrences in I are said to be overlapping
if i1 + |x| − 1 ≥ ik , and are said to be non-overlapping if ij + |x| − 1 < ij+1 for all
1 ≤ j < k.
2.2

Suffix trees

Assume that any string w terminates with a unique symbol $ which does not occur
elsewhere in w. The suffix tree of a string w, denoted STree(w), is a path-compressedtrie such that each edge is labeled with a non-empty substring of a string of w, eachinternal node has at least two children, the labels of all out-going edges of each node

14

Proceedings of the Prague Stringology Conference 2018begin with mutually distinct characters, and each suffix of w is spelled out by apath starting from the root and ending at a leaf. Because we have assumed that w
terminates with a unique symbol $, there is a one-to-one correspondence between thesuffixes of w and the leaves of STree(w). The id of a leaf of STree(w) is defined to be
the beginning position of the suffix of w that it represents.
Each node of STree(w) is specifically called as an explicit node, and in contrast
a locus on an edge is called as an implicit node. For ease of explanation, we will
sometimes identify each node of STree(w) with the string obtained by concatenating
the edge labels from the root to that node. In the sequel, the string depth of a node
implies the length of the string that the node represents.
Each edge label x is represented by a pair (i, j) of positions in w such that w[i..j] =x, and in this way STree(w) can be represented with O(n) space. Every explicit
node v of STree(w) except for the root node has an auxiliary reversed edge called
the suffix link, denoted slink(v), such that slink(v) = v ′ iff v ′ is a suffix of v and|v ′ | + 1 = |v|. Notice that if v is a node of STree(w), then such node v ′ always exists in
STree(w). STree(w) can be constructed in O(n) time and space if a given string w oflength n is drawn from an integer alphabet of size nO(1) [1], or in O(n log σ) time andO(n) space if w is drawn from a general ordered alphabet and w contains σ distinct
characters [11,6,10].

3

Text compression by LZ-style longest first substitution

Mauer et al. [5] proposed a text compression method which is a hybrid of the LempelZiv 77 encoding (LZ) [12] and a grammar compression with longest first substitution(LFS) [7], which hereby is called LZ-LFS.
3.1

LZ-LFS

Here we describe how LZ-LFS compresses a given string w.
Let x be an LR of w, and let ℓ be the leftmost occurrence of x in w. Let LGOccw (x)denote the set of non-overlapping occurrences of x in w that are selected in a leftgreedy manner (i.e., greedily from left to right). Notice that ℓ = min(LGOccw (x)) =min(Occw (x)). An occurrence i of w is said to be of– Type 1 if i is the second leftmost occurrence of x (i.e., i = min(Occw (x) \ {ℓ}))and the occurrences ℓ and i overlap (i.e., ℓ + |x| − 1 ≥ i).
Let ℓ′ be the Type 1 occurrence of x in w if it exists, and let(ℓ′ + |x| − 1 if ℓ′ exists,e=ℓ + |x| − 1 otherwise.

(1)

An occurrence i of x in w is said to be of– Type 2 if i is the leftmost occurrence of x after e and there is no non-overlapping
occurrence of x to the right of i (i.e., {i} = LGOccw[e+1..] (x)).
– Type 3 if i is a left-greedily selected occurrence of x after e (i.e., i ∈ LGOccw[e+1..] (x))
and there are at least two such occurrences of x (i.e., |LGOccw[e+1..] (x)| ≥ 2).
– Type 4 otherwise.

A. Nishi et al.: O(n log n)-time Text Compression by LZ-style Longest First Substitution

15

Figure 1. Upper: Type-2 occurrence when Type 1 occurrence exists. Lower: Type 3 occurrences
when Type 1 occurrence exists.

Figure 2. Upper: Type-2 occurrence when Type 1 occurrence does not exist. Lower: Type 3 occurrences when Type 1 occurrence does not exist.

Note that Type 2 and Type 3 occurrences of x cannot simultaneously exist. See
Figures 1 and 2 for illustration.
LZ-LFS is a recursive greedy text compression method which works as follows:
Given an input string w, LZ-LFS first finds an LR x of w and picks up its Type 1
occurrence (if it exists), and either its Type 2 occurrence or its Type 3 occurrences.
Each of these selected occurrences of x is replaced with a special symbol # not
appearing in w, together with a pointer to the leftmost occurrence ℓ of x which still
remains in the modified string. The encoding of this pointer differs for each type ofoccurrences, see [5] for details. We remark that Type 4 occurrences are not selected for
replacement and all the Type 4 occurrences but the leftmost occurrence of x disappear
in the modified string. In the next step, LZ-LFS finds an LR of the modified string
which does not include #, and performs the same procedure as long as there is arepeat in the modified string.
Let wk denote the modified string in the kth step. Namely, w0 = w and wk is thestring after all the selected occurrences of an LR of wk−1 have been replaced with #.
LZ-LFS terminates when it encounters the smallest m such that wm does not containrepeats of length at least two which consists only of characters from the original stringw (i.e., repeats without #’s).
LZ-LFS computes a list Factors as follows: Initially, Factors is an empty list. For
each occurrence i of LR x that has been replaced with #, a pair (ℓ, |x|) of its leftmost
occurrence ℓ and the length |x| is added to Factors if it is of Type 2 or the firstoccurrence of Type 3. Otherwise (if it is of Type 1), then a pair (i − ℓ, |x|) is added to
Factors. These pairs are arranged in Factors in increasing order of the corresponding
occurrences in the input string.
LZ-LFS also computes an array F as follows: Suppose we have computed w′ = wm .
For each 1 ≤ h ≤ |F |, if the h-th # from the left in w′ replaced a Type 1 occurrence

16

Proceedings of the Prague Stringology Conference 2018of an LR, then F [h] = 1. Similarly, if the h-th # from the left in w′ replaced a Type 2
occurrence of an LR, then F [h] = 2. For Type 3 occurrences, F [h] = 2 + j if the h-th
# from the left in w′ replaced the j-th LR that that has Type 3 occurrences. This
array F can be computed e.g., by using an auxiliary array A of length n, where eachentry is initialized to null. For each occurrence i of each LR x that has been replacedwith #, the type of the occurrence (Type 1, 2, or 3) is stored at A[i]. After the final
string w′ = wm has been found, non-null values of A are extracted by a left-to-rightscan, and are stored in F from left to right. A tuple (w′ , Factors, F ) is the output of
the compression phase of LZ-LFS.
To see how LZ-LFS compresses a given string, let us consider a concrete example
with stringw = w1 = abcabcaabcdabcacabc$.
There are two LRs abca and cabc in w, and suppose that abca has been selected toreplace. Below, we highlight the occurrences of abca with underlines:
w1 = abcabca
abcdabcacabc$.
✿✿✿✿
The wavy-underlined occurrence of abca at position 4 is of Type 1 since it overlaps
with the leftmost occurrence of abca which is doubly underlined. Then, pair (3, 4)
is added to Factors, where the first term 3 is the distance from the occurrence at
position 4 to the leftmost occurrence at position 1, and the second term 4 is |abca|.
The singly underlined occurrence of abca at position 12 is of Type 2 since it does
not overlap with the leftmost occurrence of abca, and there are no occurrences of abca
to its right. Then, pair (1, 4) is added to Factors, where 1 is the leftmost occurrenceof abca and 4 = |abca|.
These Type 1 and Type 2 occurrences of abca are replaced with with #, and theresulting string is
w2 = abc#abcd#cabc$,of which abc is an LR. Since neither the second occurrence nor the third one of abc
overlaps with the leftmost occurrence of abc, both of these occurrences are of Type
3. Hence, pair (1, 3) is added to Factors, where 1 is the leftmost occurrence of abc
and 3 = |abc|. Finally, we obtainw3 = abc##d#c#$.
Since w3 has no repeats of length at least two which does not contain #’s, LZ-LFS
terminates here. Together with this final string w′ = w3 , LZ-LFS outputs Factors =h(3, 4), (1, 3), (1, 4)i and F = [1, 3, 2, 3]. Recall that the pairs in Factors are arranged
in increasing order of the corresponding occurrences in the input string w.
Mauer et al. [5] showed how to decompress (w′ , Factors, F ) to get the original
string w in O(n) time. On the other hand, Mauer et al.’s LZ-LFS compression algorithm for computing (w′ , Factors, F ) from the input string w of length n uses O(n2 )time and O(n) space. Their algorithm is based on the suffix array and the LCP arrayof w [4].
In this paper, we propose a faster LZ-LFS compression algorithm for computing′(w , Factors, F ) in O(n log n) time with O(n) space, which is based on suffix trees andNakamura et al.’s algorithm [7] for a grammar compression with LFS.

A. Nishi et al.: O(n log n)-time Text Compression by LZ-style Longest First Substitution

3.2

17

Differences between LZ-LFS and grammar compression with LFS

Here, we briefly describe main differences between LZ-LFS and grammar compression
with LFS. In the sequel, grammar compression with LFS will simply be called LFS.
The biggest difference is that while the output of LFS is a context free grammarthat generates only the input string w, that of LZ-LFS is not a grammar. Namely, in
LFS each selected occurrence of the LR is replaced with a new non-terminal symbol,
but in LZ-LFS each selected occurrence of the LR is represented as a pointer to theleft-most occurrence of the LR in the current string wk . This also implies that in
LZ-LFS the left-most occurrence of the LR can remain in the string wk+1 for the next
(k + 1)-th step. On the other hand, in LFS no occurrences of the LR are left in thestring for the next step.
Because of Type 1 occurrences, a repeat which only has overlapping occurrencesin the current string wk can become an LR in LZ-LFS. On the contrary, since LFS
is a grammar-based compression, LFS always chooses a longest repeat which has
non-overlapping occurrences.
The above differences also affect technical details of the algorithms. Nakamura etal.’s algorithm for LFS maintains an incomplete version of the sparse suffix tree [2] ofthe current string. On the other hand, our algorithm for LZ-LFS maintains the suffix
tree of the current string wk in each k-th step.
3.3

On parameters α and β

The algorithm of Mauer et al. [5] uses the suffix array and the LCP array [4] of the
input string w, and finds an LR xk for wk at each k-th step using a maximal intervalof the LCP array.
The suffix array SA for a string w of length n is a permutation of [1..n] such that
SA[j] = i iff w[i..] is the lexicographically j-th suffix of w. The LCP array LCP for
w is an array of length n such that LCP[1] = 0 and LCP[i] stores the length of thelongest common prefix of w[SA[i − 1]..] and w[SA[i]..] for 2 ≤ i ≤ n.
For a positive integer p, an interval [i..j] of LCP array of w is called a p-intervalif (1) LCP[i − 1] < p, (2) LCP[k] ≥ p for all i ≤ k ≤ j, (3) LCP[k] = p for somei ≤ k ≤ j, and (4) LCP[j + 1] < p or j = n. An interval [i..j] of LCP array of
w is called a maximal interval if it is a p-interval for some p ≥ 1 and the longest
common prefix of length p for all the corresponding suffixes w[SA[i]..], . . . , w[SA[j]..]is a maximal repeat of w. In each step of Mauer et al.’s method, the algorithm picks
up a maximal interval as a candidate for an LR to replace.
Let bit(w′ ), bit(F ), and bit(Factors) respectively denote the average number ofbits to encode a single character from w′ , an element of F , and an element of Factors
with a fixed encoding scheme. The original algorithm by Mauer et al. [5] uses twobit(F )
parameters α and β such that α = bit(Factors)
and β = 1 + bit(w′ ) . In each k-th step,
bit(w′ )their algorithm performs replacement of an LR xk of length len k only if the following
conditions holds:
α(2)len k ≥ + β,swhere s denotes the number of Type 2 or Type 3 occurrences of the LR xk in thecurrent string wk . However, since the values of α and β cannot be precomputed, intheir implementation of LZ-LFS, they use ad-hoc pre-determined values for α andβ. In particular, they set α = 30 and β = 80 as default values in their experiments(see [5] for details).

18

Proceedings of the Prague Stringology Conference 2018

However, we have found that there exist a series of strings for which Mauer et al.’s
algorithm fails to recursively replace LRs for any pre-determined values for α and β.
Consider a series of strings
w = aXab0 aXab1 · · · aXabs $,where s ≥ 1, a, b1 , . . . , bs ∈ Σ, a 6= bi for any 0 ≤ i ≤ s, bi 6= bj for any 0 ≤i 6= j ≤ s, and X ∈ (Σ \ {a, b0 , . . . , bs , $})+ . This string w = w1 has a unique
LR aXa. Hence we have len 1 = r + 2, where r = |X|. Since there are s > 1 nonoverlapping occurrences of aXa which do not overlap with the left most occurrenceof aXa in w, those occurrences are of Type 3. For this LR aXa to be replaced with
#1 , Inequality (2) or alternatively r ≥ αs + β − 2 needs to hold. Now let us choose
1 ≤ |X| = r < β −1 and s ≥ α. Then, since αs ≤ 1, Inequality (2) never holds for suchr. Hence, the original algorithm of Mauer et al. does not replace aXa and tries to finda next LR (which can be shorter than aXa). In this case, the second longest repeats
are aX and Xa of length r + 1 each. However, since neither is aX nor Xa a maximal
repeat of w, it is not represented by a maximal interval of the LCP array. Hence,neither is aX nor Xa selected for replacement. Moreover, note that even X is not a
maximal repeat of w, and that there are no repeats of length at least two consisting
only of a and/or bi (0 ≤ i ≤ s). Therefore, Mauer et al.’s algorithm terminates atthis point and does not compress this string w = aXab0 aXab1 · · · aXabs $ at all, eventhough it is highly repetitive and contains quite long repeats (e.g., for Mauer et al.’s
default value β = 80, X can be as long as 78).
We also remark that one can easily construct instances where more candidates of
LRs have to be skipped, by adding other strings in a similar way to X into the string,e.g., aXab0 aXab1 · · · aXabs aY ac0 aY ac1 · · · aY acs $, and so on.
Given the above observation, in our algorithm that follows, we will omit thecondition of Inequality (2), and will replace Type 1, 2, 3 occurrences of any selectedLR.

4O(n log n)-time algorithm for LZ-LFS

In this section, we show the following result:
Theorem 1. Given a string w of length n, our algorithm for LZ-LFS works inO(n log n) time with O(n) space.
We begin with describing a sketch of our LZ-LFS algorithm. Let w be the input
string of length n and let w1 = w. As a preprocessing, we construct STree(w1 ) inO(n log σ) time and O(n) space [11,6,10], where σ ≤ n is the number of distinct
characters that occur in w.
In the first step of the algorithm, we find an LR x1 of w1 with the aid of STree(w1 ).
Let wk denote the string in the k-th step of the algorithm. For a technical reason,
when computing wk+1 from wk , we use a special symbol #k that does not occur in
wk , and replace the selected occurrences of an LR xk in wk with #k . The reason will
become clear later.
For each k-th step, we denote by len k the length of an LR of wk−1 , namely,len k = |xk |. At the end of each k-th step, we update our tree so that it becomes
identical to STree(wk+1 ), so that we can find an LR xk+1 for the next (k + 1)-th step.

A. Nishi et al.: O(n log n)-time Text Compression by LZ-style Longest First Substitution

4.1

19

How to find an LR xk using STree(wk )Suppose that we maintain STree(wk ) in each k-th step. The two following lemmas are
keys to our algorithm. There, each #k used at each k-th step is regarded as a single
character of length one, rather than a representation of the LR of length len k ≥ 2that was replaced by #k .
Lemma 2. For each k-th step, let v be any internal explicit node of STree(wk ) ofstring depth at least two. Then, the string represented by v does not contain #j withany 1 ≤ j < k.
Proof. Assume on the contrary that the string represented by v contains #j for some
1 ≤ j < k. Since v is an internal explicit node of STree(wk ), v occurs at least twice
in wk . Since |v| ≥ 2, we have that len k ≥ |v| > len j . However, this contradicts thelongest first strategy such that len j ≥ len k must hold.
⊓⊔
Lemma 3. For each k-th step, any LR of wk is represented by an internal node of
STree(wk ).
Proof. Suppose on the contrary that an LR x of wk is represented by an implicit nodeof STree(wk ), and let (u, v) be the edge on which x is represented. Note that |v| > |x|.
Since x is an LR, x must occur at least twice in wk and hence v cannot be a leaf of
STree(wk ). This implies that v is an internal branching node and hence v occurs atleast twice in wk . However, this contradicts that x is an LR of wk .
⊓⊔Based on Lemmas 2 and 3, we can find an LR at each step as follows. In each k-th
step of our algorithm, we maintain an array Bk of length n such that Bk [l] stores a listof all explicit internal nodes of string depth l that exist in STree(wk ). Hence, Bk [len k ]will be the leftmost entry of Bk that stores a non-empty list of existing nodes. We do
not store nodes of string depth one. Any node of string depth one represents eithera single character from the original string w or #j for some 1 ≤ j < k which will
never be replaced in the following steps. Therefore, Bk [1] is always empty at every
k-th step.
The initial array B1 can easily be computed in O(n) time by a standard traversal
on STree(w1 ) = STree(w). We can also compute in O(n) time the length len 1 of an
LR for B1 in a naı̈ve manner. We then pick up the first element in the list stored at
B1 [len 1 ] as an LR x1 of w1 to be replaced with #1 . After the replacement, we remove
x1 from the list, and proceed to the next step. In the next subsection, we will show
how to efficiently update Bk to Bk+1 .
The algorithm terminates when the string contains no repeats of length at least
two. Let wm denote this string, namely, the algorithm terminates at the m-th step.
In this last m-th step, STree(wm ) consists only of the root, the leaves, and possiblyinternal explicit nodes of string depth one.
In the next subsection, we will show how to efficiently update STree(wk ) to
STree(wk+1 ) and Bk to Bk+1 in a total of O(n) time for all k = 1, . . . , m − 1. We
also remark that m cannot exceed n/2 since at least two positions are taken by the
replacement of an LR at each step.
Now, let us focus on how our algorithm works at each k-th step. The next lemmashows how we can find the occurrences of an LR of each step efficiently.
Lemma 4. Given a node of STree(wk ) which represents an LR xk of wk at each k-th
step, we can compute Type 1, 2, 3 occurrences of xk in wk in a total of O(n log n)time and O(n) space for all steps.

20

Proceedings of the Prague Stringology Conference 2018

Proof. It follows from Lemma 3 that all children of the node for xk are leaves in
STree(wk ). We sort all the leaves in increasing order of their id’s (i.e., the beginning
positions of the corresponding suffixes). If dk is the number of the above-mentioned
leaves, then this can be done in O(dk log dk ) time and O(dk ) space by a standard
sorting algorithm. It is clear that we can compute Type 1, 2, and/or 3 occurrences of
xk in wk from this sorted list, in O(dk ) time.
Each occurrence i of xk but the leftmost one either (a) is replaced with #k , or(b) overlaps with another occurrence of xk that is replaced with #k . In case (a), it isguaranteed that there will be no LRs that begin at position i in the following steps,
since LZ-LFS chooses repeats in a longest first manner. In case (b), there is anotheroccurrence j of xk that is replaced with #k and i ∈ [j + 1..j + len k − 1]. Since these
positions in this range [j + 1..j + len k − 1] are already taken by the replacementof xk with #k , there will be no LRs that begin at position i in the following steps.
One delicacy is the leftmost occurrence ℓ of xk , since the corresponding interval[ℓ..ℓ + len k − 1] can contain up to len k occurrences of xk , and these positions may
retain the original characters in the string wk+1 for the next (k + 1)-th step. However,since at least one occurrence of xk is always replaced, the cost of sorting the leaves
whose id’s are in range [ℓ..ℓ + len k − 1] can be charged to an occurrence of xk that is
replaced with #k .
Overall, the time cost to sort all dk children of xk can be charged to the intervals of
the occurrences of xk in wk that are replaced with #k ’s.P
Therefore, the total time costmfor sorting the corresponding leaves in all m steps
Pm is O( k=1 (dk log dk )) = O(n log n),
where the equality comes from the fact that k=1 dk = O(n) and dk ≤ n for each k.
The space complexity is clearly O(n).
⊓⊔4.2

How to update STree(wk ) to STree(wk+1 )In this subsection, we show how to update STree(wk ) to STree(wk+1 ).
Let i be any occurrence (Type 1, 2, or 3) of an LR xk in wk which will be replacedwith #k in the k-th step. Since |xk | = len k ≥ 2, the replacement with #k will always
shrink the string length. However, it is too costly to relabel the integer pairs for thesuffix tree edge labels with the positions in the shrunken string. To avoid this, we
suppose that each selected occurrence of xk is replaced with #k •len k −1 , where • is a
special symbol that does not occur in the original string w. Namely, #k is now at
position i and positions i + 1, . . . , i + len k − 1 are padded with •’s. This ensures thatthe length of wk remains n for each k-th step, and makes it easy for us to design our
LZ-LFS algorithm.
If an occurrence of xk at position i is replaced with #k , then the positions in range[i + 1..i + len k − 1] are taken away from the string. This range [i + 1..i + len k − 1] istherefore not considered in the following steps, and is called a dead zone. Also, since
any LRs in the following steps are of length at most len k , it suffices for us only totake care of the substrings in range [i − len k , ..i]. This range is called as an affected
zone. See Figure 3 for illustration of a dead zone and affected zone.
In our suffix tree update algorithm, we will remove the leaves for the suffixes thatbegin in the dead zones, and modify the leaves for the suffixes that begin in theaffected zones.
Let qk denote the number of selected occurrences (Type 1, 2, or 3) of xk in wk to
be replaced with #k . We will replace the selected occurrences of xk from left to right.
For each 1 ≤ h ≤ qk , let ih denote the h-th selected occurrence of xk from the left,

A. Nishi et al.: O(n log n)-time Text Compression by LZ-style Longest First Substitution

21

i
wk

wk+1

xk

i
#k

Figure 3. An occurrence of LR xk at position i in the current string wk is replaced with #k . In thenext string wk+1 , the range padded with •’s is the dead zone and the gray range is the affected zone
for this occurrence of xk at position i.

and let wkh denote the string where the h occurrences i1 , . . . , ih of xk from the left are
already replaced with #k ’s. Namely, wk0 = wk and wkqk = wk+1 .
Suppose that we have processed the h − 1 occurrences of xk from the left, and weare to process the h-th occurrence ih of xk . Namely, we have maintained STree(wkh−1 )and we are to update it to STree(wkh ).
How to process the dead zones. First, we consider how to deal with the deadzone [ih + 1..ih + len k − 1] for this occurrence ih of xk in wkh−1 . Since the positions in
the dead zone will not exist in the modified string, and since no substrings beginningin this dead zone can be an LR in the following steps, we remove the leaves for thesuffixes that begin at the positions in the dead zone [ih + 1..ih + len k − 1]. In caseih + len k − 1 > n, which can happen only when h = qk , then the dead zone for thisoccurrence is [ih + 1..n]. In any case, we can easily remove those leaves in linear timein the number of the removed leaves.
How to process the affected zones. Next, we consider how to deal with theaffected zone [ih − len k ..ih ] for this occurrence ih of LR xk in wkh−1 . Let y = wkh−1 [ih −len k ..ih − 1], namely, y is the left context of length len k from the occurrence of xk at
position ih . Let y ′ be the longest non-empty suffix of y such that xk down the locus
of y ′ spans more than one edge in the tree. If such a node does not exist, then let
y ′ = ε. For each suffix of y that is longer than y ′ , xk down its locus is represented
on a single edge. Hence, it is “automatically” be replaced with #k by replacing theoccurrence of xk at position ih in the current string wkh−1 with #k •len k −1 . Therefore,
no explicit maintenance on the tree topology is needed for these suffixes of y.
Now we consider the suffixes yj = y[j..len k − 1] of y that are not longer than y ′ ,where j = len k − |y ′ | + 1, . . . , len k − 1. Now xk down the locus of each yj spans morethan one edge, and it will have to be replaced with a (single) special symbol #k . This
introduces some changes in the tree topology. We note that the locus of yj xk in thesuffix tree before the update is on the edge that leads to the leaf with id ih − |yj |,since otherwise yj xk must occur twice in the string, which contradicts our longest
first strategy. Thus, we re-direct the edge that leads to the leaf with id ih − |yj | fromits original parent to the node that represents yj (if it is an implicit node, then wecreate a new explicit node there). See Figure 4 for illustration.
The remaining problem is how to find the loci for the suffixes of y in the tree. We
find them in decreasing order of their length. For the first suffix y[1..len k ] = y, we
find the locus of y by simply traversing y from the root of the suffix tree. There are
two cases to consider:

22

Proceedings of the Prague Stringology Conference 2018

}

}

xk

yj

}

yj

#k

Figure 4. Illustration for a leaf edge redirection, where the circles represent internal explicit nodes
and the square represents the leaf with id ih − |yj |. Since xk down the locus of yj spans more than
one edge, the leaf edge is redirected from its original parent to yj . This figure shows the case wherea new internal node for yj is created.

(A) If this locus for y1 = y is an explicit node in STree(wkh−1 ), then by the property ofthe suffix tree, all suffixes of y are also represented by explicit nodes. Hence, we
can find the loci for all the suffixes using a chain of suffix links from node y down
to the root.
(B) If this locus for y1 = y is an implicit node in STree(wkh−1 ), then we use the suffix
link of the parent u1 of y1 . Let u′2 = slink(u1 ). We go downward from u′2 until
finding the deepest node u2 whose string depth is not greater than |y2 | = len k − 1.
If the string depth u2 equals |y2 | (i.e. |u2 | = |y2 |), then the locus of y2 is on an
explicit node. Hence, we can continue with y3 as in Case (A) above. Otherwise (if|u2 | < |y2 |), then the locus of y2 is on an out-going edge of u2 . We then continue
with y3 in the same way as for y2 .
Suppose we have processed all the qk selected occurrences of xk in wk . The next
lemma guarantees that re-direction of the leaf edges do not break the property of thesuffix tree.
Lemma 5. Let v be any non-root internal explicit node of the the tree obtained by
updating STree(wkh−1 ) as above. Then, the labels of the out-going edges of v begin withmutually distinct characters.
Proof. Notice that in each k-th step, the label of any re-directed edge begins with#k . Since #k 6= #j for any 1 ≤ j < k and #k does not occur in wk , it suffices for us
to show that there is at most one out-going edge of v whose label begins with #k .
If there are two out-going edges of v whose labels begin with #k , then there areat least two leaves whose path label begin with v#k . Thus v#k occurs in wk at least
twice. Since v is not a root, |v| ≥ 1. If xk is the LR that was replaced by #k , then|vxk | > |xk | = len k , which contradicts that xk was an LR at the k-th step.
Thus, the labels of out-going edge of any node v begin with mutually distinct
characters.
⊓⊔
The root of the resulting tree has a new child which represents #k , and the childrenof this new node are the leaves that correspond to the occurrences of the LR thathave been replaced by #k .

A. Nishi et al.: O(n log n)-time Text Compression by LZ-style Longest First Substitution

23

Notice that the affected zone [ih − len k ..ih − 1] for the occurrence ih may overlap
with the dead zone [ih−1 + 1..ih−1 + len k − 1] for the previous occurrence ih−1 . In thiscase, the affected zone for ih is trimmed to [ih−1 + len k ..ih − 1] and we perform thesame procedure as above for this trimmed affected zone.
Lemma 6. Our algorithm updates STree(wk ) to STree(wk+1 ) for every k-th step in a
total of O(n log σ) time with O(n) space.
Proof. First, let us confirm the correctness of our algorithm. It follows from Lemma 3that in each k-th step the new internal explicit nodes that are created in this step
can have string depth at most len k . Therefore, in terms of updating STree(wk ) to
STree(wk+1 ), it suffices for us to consider only the affected zone for each occurrenceof LR xk . Lemma 5 guarantees that the label of the out-going edges of the same node
begin with mutually distinct characters. It is clear that the leaves for the suffixes which
begin in the dead zones have to be removed, and only those leaves are removed. Thus,
our algorithm correctly updates STree(wk ) to STree(wk+1 ).
Second, let us analyze the time complexity of our algorithm. For each occurrence ihof xk , finding the locus for the first suffix y = wkh−1 [ih −len k ..ih −1] takes O(len k log σ)time. Then, the worst case scenario is that Case (B) happens for all len k suffixes of y.
For each shorter suffix y[i..len k ] with i = 2, . . . , len k , the above algorithm traverses atmost |uj |−|u′j | = |uj |−|slink(uj−1 )| = |uj |−|uj−1 |+1 edges. Hence, for all the shorter
P ksuffixes of y, the number of edges traversed is bounded by len
j=2 (|uj | − |uj−1 | + 1) =|ulen k | − |u1 | + len k − 1 < 2len k . Hence, finding the locus for the shorter suffixes ofy also takes O(len k log σ) time. The len k term in the O(len k log σ) complexity canbe charged to each selected occurrence of LR xk , which is replaced with #k •len k −1 .
Therefore, the total time cost to update the suffix tree for all steps is O(n log σ). The
space usage is clearly O(n).
⊓⊔4.3

How to update Bk to Bk+1

Suppose we have Bk in the k-th step, and we would like to update it to Bk+1 for the
next (k + 1)-th step. Let u be an internal branching node of STree(wk−1 ) that is to be
removed in STree(wk ). This can happen when u has only two children, one of which
is a leaf to be removed from the current suffix tree. We then remove u from the list
stored in Bk−1 [|u|], and connect its left and right neighbors in the list.
When we replace an LR xk of wk with #k •len k −1 , an implicit node v of STree(wk )may become branching due to the new symbol #k and hence a new explicit internal
node for v needs to be created to the suffix tree. In this case, we add this new nodefor v at the end of the list stored in Bk [|v|]. After these procedures are performed forall such nodes, we obtain Bk+1 for the next (k + 1)-th step.
Lemma 7. At every k-th step, we can update Bk and maintain len k in a total ofO(n) time and space.
Proof. Initially, at most n−1 internal nodes are stored in B1 . Also, the total number of
newly created nodes is bounded by the total size of the affected zones for the replaced
occurrences of the LRs in all the steps, which can be charged to the positions thatare taken by replacement of LRs for all the steps. As was shown in the previous
subsection, once a position in the original string is taken by replacement of an LR,
then this position will never be considered in the following steps. Thus, the total

24

Proceedings of the Prague Stringology Conference 2018

number of newly created nodes is bounded by n. Clearly, computing the initial array
B1 from STree(w1 ) takes O(n) time, and deletion and insertion of a node on a list
stored at an entry of Bk takes O(1) time each (we use doubly linked lists here).
It follows from Lemma 3 and our suffix tree update algorithm that at each k-th
step any newly created node has string depth at most len k , and len k is monotonically
non-increasing as k grows. Hence, we can easily keep track of len k for all steps in a
total of O(n) time.
The space usage is clearly O(n).
⊓⊔After computing wm for the final m-th step, we replace every #k in wm with #for every k, and obtain the final string w′ for LZ-LFS.
Summing up all the discussions above, we have proved our main result in Theorem 1.

5O(n)-time algorithm for simplified LZ-LFS

In this section, we show that a simplified version of LZ-LFS can be computed in O(n)time and space, by a slight modification to our O(n log n)-time LZ-LFS algorithm
from Section 4.
By a “simplified version” of LZ-LFS, we mean a variant of LZ-LFS where Type 3
non-overlapping occurrences of an LR of each step can be selected arbitrarily (namely,
not necessarily in a left-greedy manner). More formally, in our simplified version of
LZ-LFS, an occurrence i of x in w is said to be of Type 1/2 if the corresponding
condition as in Section 3 holds, and– Type 3 if i is an occurrence of x after e which is not of Type 2,
where e is as defined in Equation (1).
Notice that there can be multiple choices for non-overlapping Type 3 occurrencesof LR xk in wk at each k-th step. Our algorithm takes a maximal set of non-overlapping
Type 3 occurrences of xk in wk at each step, so that no Type 3 occurrences remainin the string. We remark that it is easy to compute a maximal set of size at leastmax{⌈|LGOccwk [e+1..] (xk )|/2⌉, 2}, namely, this strategy allows us to select at least half
the number of left-greedily selected Type 3 occurrences. Since this does not require
to sort the occurrences of xk , we can perform all the steps in a total of O(n) time, as
follows:
Theorem 8. Given a string w of length n over an integer alphabet of size nO(1) , ouralgorithm for a simplified version of LZ-LFS works in O(n) time and space.
Proof. As a preprocessing, we build STree(w) in O(n) time and space [1].
We use essentially the same approach as in the previous section. Namely, we
maintain the suffix tree for each step of our algorithm, and find Type 1, 2, and/or 3
occurrences of a selected LR using the suffix tree that we maintain.
Suppose that we are given a node v that represents an LR xk in wk at the k-th
step. Since all children of v are leaves, we can easily compute the Type 1 occurrenceof xk (if it exists) by a simple scan over the children’s leaf id’s. After this, by anothersimple scan, we can also compute the Type 2 occurrence of xk (if it exists). Then, we
exclude the Type 1 and Type 2 occurrences, and any occurrences that overlap with
the Type 1 and/or Type 2 occurrences, by removing the corresponding leaves which

A. Nishi et al.: O(n log n)-time Text Compression by LZ-style Longest First Substitution

25

are children of v. We then select a maximal set of non-overlapping Type 3 occurrencesof xk by picking up a child of v in an arbitrary order, and choosing it if it does notoverlap with any already-selected occurrences.
Let dk be the number of children of v. As in the standard LZ-LFS, each positionof the original string can be involved in at most one event of the replacement of an
LR. Hence, each step of the above algorithm takes O(dPk ) time, and thus the total
time complexity for all the steps of this algorithm is O( mk=1 dk ) = O(n), where m is
the final step.
The space complexity is clearly O(n).
⊓⊔6Conclusions and further work

LZ-LFS [5] is a new text compression method that has both features of Lempel-Ziv
77 [12] and grammar compression with longest first substitution [7].
In this paper, we proposed a suffix-tree based algorithm for LZ-LFS that runs inO(n log n) time and O(n) space, where n denotes the length of the input string tocompress. This improves on Mauer et al.’s suffix-array based algorithm that requires
O(n2 ) time and O(n) space. We also showed that a simplified version of LZ-LFS, where
Type 3 occurrences may not be selected in a left-greedy manner, can be computed in
O(n) time and space with slight modifications to our LZ-LFS algorithm.
There are interesting open questions with LZ-LFS, including:
1. Does there exist a linear O(n)-time algorithm for (non-simplified) LZ-LFS? The
difficulty here is to select Type 3 occurrences of each selected LR in a left-greedy
manner. We remark that Nakamura et al.’s linear O(n)-time algorithm [7] forgrammar compression with LFS does not always replace the left-greedy occurrences of each selected LR, either. Or, do there exist Ω(n log n) lower bounds,
probably by a reduction from sorting?
2. Does there exist a suffix-array based algorithm for LZ-LFS which works in time
faster than O(n2 )? This kind of algorithm could be of practical significance.

References
1. M. Farach-Colton, P. Ferragina, and S. Muthukrishnan: On the sorting-complexityof suffix tree construction. J. ACM, 47(6) 2000, pp. 987–1011.
2. J. Kärkkäinen and E. Ukkonen: Sparse suffix trees, in Proc. COCOON 1996, 1996, pp. 219–
230.
3. N. J. Larsson and A. Moffat: Offline dictionary-based compression, in DCC 1999, 1999,
pp. 296–305.
4. U. Manber and G. Myers: Suffix arrays: A new method for on-line string searches. SIAM
J. Computing, 22(5) 1993, pp. 935–948.
5. M. Mauer, T. Beller, and E. Ohlebusch: A Lempel-Ziv-style compression method for
repetitive texts, in Proc. PSC 2017, 2017, pp. 96–107.
6. E. M. McCreight: A space-economical suffix tree construction algorithm. J. ACM, 23(2) 1976,
pp. 262–272.
7. R. Nakamura, S. Inenaga, H. Bannai, T. Funamoto, M. Takeda, and A. Shinohara: Linear-time off-line text compression by longest-first substitution. Algorithms, 2(4) 2009,
pp. 1429–1448.
8. J. Storer: NP-completeness results concerning data compression, Tech. Rep. 234, Department
of Electrical Engineering and Computer Science, Princeton University, 1977.
9. J. Storer and T. Szymanski: Data compression via textual substitution. J. ACM, 29(4)1982, pp. 928–951.

26

Proceedings of the Prague Stringology Conference 2018

10. E. Ukkonen: On-line construction of suffix trees. Algorithmica, 14(3) 1995, pp. 249–260.
11. P. Weiner: Linear pattern-matching algorithms, in Proc. of 14th IEEE Ann. Symp. on Switching and Automata Theory, 1973, pp. 1–11.
12. J. Ziv and A. Lempel: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, IT-23(3) 1977, pp. 337–343.