Comparison of LZ77-type Parsings
Dmitry Kosolobova, Arseny M. Shurb
a University

arXiv:1708.03558v2 [cs.IT] 10 Dec 2017

b Ural

of Helsinki, Helsinki, Finland
Federal University, Ekaterinburg, Russia

Abstract
We investigate the relations between different variants of the LZ77 parsing existing in the literature. All of
them are defined as greedily constructed parsings encoding each phrase by reference to a string occurring
earlier in the input. They differ by the phrase encodings: encoded by pairs (length + position of an earlier
occurrence) or by triples (length + position of an earlier occurrence + the letter following the earlier occurring
part); and they differ by allowing or not allowing overlaps between the phrase and its earlier occurrence.
For a given string of length n over an alphabet of size σ, denote the numbers of phrases in the parsings
allowing (resp., not allowing) overlaps by z (resp., ẑ), for “pairs”, and by z3 (resp., ẑ3 ), for “triples”. We
prove the following bounds and provide series of examples showing that these bounds are tight:
n
n
) and z3 ≤ ẑ3 ≤ z3 · O(log z3 log
);
• z ≤ ẑ ≤ z · O(log z log
σ z
σ z3
1
1
• 2 ẑ < ẑ3 ≤ ẑ and 2 z < z3 ≤ z.
Keywords: LZ77, lossless data compression, greedy parsing, non-overlapping phrases
1. Introduction
The Lempel–Ziv parsing [18] (LZ77 for short) is
one of the central techniques in the data compression and it plays an important role in stringology
and algorithms in general. The literature on LZ77
is full of different variations of the parsing originally described by Lempel and Ziv [18] (curiously,
the most popular modern LZ77 modifications differ
from the original one1 ). Some of these LZ77-based
parsings lie at the heart of common compressors
such as gzip, 7-zip, pkzip, rar, etc. and some
serve as a basis for compressed indexes on highly
repetitive data (e.g., see [5, 12, 13]).
Most LZ77 variations have a noticeable optimality property: they have the least number of
phrases among all reference-based parsings with the
same fixed-length coding scheme for phrases (for
details, see [2, 14] or Lemma 2 below). The analysis in [2] shows that many other popular referencebased methods (including LZ78 [19]) are significantly worse than LZ77 in the worst case. Probably, because of these “near-optimal” properties of
Email addresses: dkosolobov@mail.ru (Dmitry
Kosolobov), arseny.shur@urfu.ru (Arseny M. Shur)
1 The original parsing is the LZ parsing defined below.
3
Preprint submitted to Information Processing Letters

LZ77, many authors often implicitly consider different LZ77 variations as somehow equivalent in terms
of the number of produced phrases. Despite the fact
that numerous works have been published in the
last 40 years on this topic (e.g., see [15] and references therein), to our knowledge, until very recently
(see [6, 10]), there were no theoretical comparative
studies of this side of LZ77 modifications. We partially close this gap establishing tight bounds on
the ratios between the numbers of phrases in several popular LZ77 variations. Note that the comparison of the parsings in terms of the bit size of
their variable-length encodings is a different and,
as it seems, more challenging problem (see [4, 11]).
We investigate the relations between the most
popular variants of the LZ77 parsing that one might
find in the existing literature on the subject. All of
them are defined as greedily constructed parsings
that encode each phrase by reference to a string
occurring earlier in the input, but they differ by
the format of the phrase encodings and by the constraints imposed on earlier phrase occurrences. We
primarily investigate four LZ77 variants that, at a
generic step of the left-to-right greedy construction,
define the phrase f starting at the current position
i as follows:
December 12, 2017

1. f is the longest string that starts at position i
and occurs at position j < i (or f is a letter if
such string is empty);

Theorems 1 and 2 are the main results of this
paper. To complete the picture, we also investigate
the relations between the numbers z, z3 and, respectively, ẑ, ẑ3 , proving simple bounds and their
tightness in the following theorem.

2. as in 1, but j ≤ i − |f |;
3. f is the shortest string that starts at position
i and does not have occurrences at positions
j < i (but f can occur earlier if it is the last
phrase in the parsing);

Theorem 3. For any given string, one has 21 z <
z3 ≤ z and 12 ẑ < ẑ3 ≤ ẑ. Moreover, for each k ≥ 1
and each of the four restrictions z3 = z = k; z3 = k
and z = 2k − 1; ẑ3 = ẑ = k; ẑ3 = k and ẑ = 2k − 1
there is a binary string satisfying this restriction.

4. as in 3, but j ≤ i − |f | + 1.
We call these parsings, respectively, LZ parsing,
non-overlapping LZ (novLZ) parsing, LZ3 parsing,
and non-overlapping LZ3 (novLZ3 ) parsing (rigor
formal definitions are given below). For a given
string of length n over an alphabet of size σ, denote
the numbers of phrases in thus defined parsings by,
respectively, z, ẑ, z3 , ẑ3 . The non-one-letter phrases
of LZ and novLZ parsings can be encoded by pairs
of integers: the length of f plus the offset (i − j) to
an earlier occurrence of f . The phrases of LZ3 and
novLZ3 parsings can be encoded by triples (hence
the subscript “3”): the length of f plus the offset
(i − j) to an earlier occurrence of f [1..|f |−1] plus
the letter f [|f |]. We prove that the numbers of
phrases in the considered LZ77 parsings are related
as follows.

It is known that a random string of length n
has Θ(n/ logσ n) phrases in its Lempel–Ziv parsings
(e.g., see [18]). A “reasonably compressible” string
has, say, Ω(n/ logO(1) n) phrases. For these strings
our theorems imply that the sizes of all four considered LZ77 parsings are within O(log log n) factor
from each other; thus, we partially support the intuition that all these LZ77 variations are similar.
The paper is organized as follows. In Section 2 we
formalize the definitions of the LZ77 parsings under consideration and introduce some useful tools.
In Section 3, the proofs of the main results (Theorems 1 and 2) are given. Theorem 3 is proved
in Section 4. We conclude with some remarks and
open problems in Section 5.

Theorem 1. For any given string of length n
over an alphabet of size σ, one has z ≤ ẑ ≤
n
n
2
z ·O(log z log
z ) and z3 ≤ ẑ3 ≤ z3 ·O(log z3 log z3 ).

2. Preliminaries

σ

σ

A string s of length n over an alphabet Σ is a
map {1, 2, . . . , n} 7→ Σ, where n is referred to as the
length of s, denoted by |s|. We write s[i] for the ith
letter of s and s[i..j] for s[i]s[i+1] · · · s[j]. A string
u is a substring of s if u = s[i..j] for some i and j;
the pair (i, j) is not necessarily unique and we say
that i specifies an occurrence of u in s. A substring
s[1..j] (resp., s[i..n]) is a prefix (resp. suffix ) of s.
For any i, j, the set {k ∈ Z : i ≤ k ≤ j} (possibly
empty) is denoted by [i..j]. A decomposition of a
string is its representation as the concatenation of
nonempty substrings; writing a decomposition, we
separate these substrings by dots. Two strings u
and v are called conjugate if u = xy and v = yx
for some x and y. An integer p ∈ [1..|s|] is called
a period of s if s[i] = s[i+p] for any i ∈ [1..|s|−p].
The following lemma is obvious.

n
z)

The bound z ≤ ẑ ≤ z·O(log
was found already
in [6, Fig. 3] but our upper bound is better; in fact,
it is tight, as the following theorem shows.
Theorem 2. For any integers n > 1, σ ∈ [2..n],
z ∈ [σ.. logn n ], there is a string of length n over
σ
an alphabet of size σ such that the sizes of its
LZ and novLZ parsings are, respectively, Θ(z) and
n
Ω(z log z log
). The same result holds for the
σ z
LZ3 /novLZ3 parsings.
Note that while the necessity of the condition
z ≥ σ in this theorem is obvious, the condition
z ≤ logn n is justified by the well-known fact that
σ
the size of the LZ/LZ3 parsing of any string of
length n over an alphabet of size σ is at most
O( logn n ) (e.g., see [11]).
σ

Lemma 1. Suppose that, in a string s, we have
w = s[i..j] = s[i′ ..j ′ ] and i < i′ ≤ j; then i′ − i is a
period of w.

2 Throughout

the paper, all logarithms have base 2 if it is
not explicitly stated otherwise.

2

whenever all αi are equal and maximal, i.e., αi =
for all i ∈ [1..r]. Hence, the result follows.

For a given string s, the LZ (resp., novLZ ) parsing of s is the decomposition s = f1 f2 · · · fr built
from left to right by the following greedy procedure: if a prefix s[1..i−1] = f1 f2 · · · fp−1 is already
processed, then the string fp (which is called a
phrase) is either the letter s[i] that does not occur in s[1..i−1] or is the longest string that starts
at position i and has an occurrence at position j < i
(resp., j ≤ i − |fp |). The LZ3 (resp., novLZ3 ) parsing is constructed by an analogous greedy procedure but the phrase fp is chosen as the longest
string occurring at position i such that the string
fp [1..|fp |−1] has an occurrence at position j < i
(resp., j ≤ i − |fp | + 1).
Consider s = abababc. The LZ, novLZ, LZ3 , and
novLZ3 parsings of s are, respectively, a.b.abab.c,
a.b.ab.ab.c, a.b.ababc, and a.b.aba.bc.
Let s = t1 t2 · · · tr be a decomposition of s into
non-empty strings t1 , . . . , tr . We say that t1 t2 · · · tr
is an LZ-type (resp., novLZ-type) parsing if for each
i ∈ [1..r], the string ti either is a letter or has an
occurrence in the string s[1..|t1 · · · ti |−1] (resp., in
t1 t2 · · · ti−1 ). Analogously, we say that t1 t2 · · · tr is
an LZ3 -type (resp., novLZ3 -type) parsing if for each
i ∈ [1..r], the string ti [1..|ti |−1] has an occurrence
in the string s[1..|t1 · · · ti |−2] (resp., in t1 t2 · · · ti−1 ).
The number of phrases in a parsing is called the
size of the parsing. We write z (resp., ẑ, z3 , ẑ3 )
to denote the size of the LZ (resp., novLZ, LZ3 ,
novLZ3 ) parsing of a given string.
Our main tool in the subsequent analysis is the
following well-known optimality lemma (e.g., see [2,
14, 16]). We omit the proof as it is straightforward.

n
rk

Proof of Theorem 1. Let s be a string of length n
over an alphabet of size σ. The theorem asserts
n
) and z3 ≤
that we have z ≤ ẑ ≤ z · O(log z log
σ z
n
ẑ3 ≤ z3 · O(log z3 log z3 ) for this string.
σ
Let us consider the case of z and ẑ; the proof for
z3 and ẑ3 can be reconstructed by analogy.
Since the novLZ parsing of s is an LZ-type parsing, z ≤ ẑ by Lemma 2. Hence, it suffices to prove
n
that ẑ ≤ z · O(log z log
). The idea of the proof is
σ z
to use the LZ parsing f1 f2 · · · fz of s to construct a
n
); then,
novLZ-type parsing of size z · O(log z log
σ z
the required bound follows from Lemma 2.
We construct a new parsing for s substituting
each phrase fi with a set of new phrases. If a
phrase fi has an occurrence in the string f1 · · · fi−1 ,
then we do not alter fi and include it in the new
parsing. Consider a phrase fi such that the leftmost occurrence of fi in the string f1 · · · fi occurs
at position j such that |f1 · · · fi−1 | − |fi | + 1 < j
(i.e., this occurrence of fi overlaps with fi ). Let
us choose an arbitrary constant α ∈ (0, 1). Denote
k = α logσ z. We first discuss how to process the
case j ≤ |f1 · · · fi−1 | − k (i.e., when the leftmost
occurrence of fi is farther than k letters from fi ).
By Lemma 1, p = |f1 · · · fi−1 | + 1 − j is a period of fi and p ∈ [k..|fi |]. We decompose fi as
follows: fi = t1 · · · tr , where |t1 | = 20 p, |t2 | =
21 p, . . . , |tr−1 | = 2r−2 p, and tr is a non-empty suffix of fi of length ≤2r−1 p. Since p is a period of fi
and the substring of length p preceding the phrase
fi is equal to fi [1..p], any string th from the decomposition occurs at 2h−1 p positions to the left
and, since |th | = 2h−1 p, this occurrence does not
overlap th . Therefore, we can include the strings
t1 , . . . , tr from the decomposition fi = t1 · · · tr as
phrases in the novLZ-type parsing under construction. It is easy to see that r = O(log |fpi | ). Since

Lemma 2. For any given string, the size of its LZ
(resp., novLZ, LZ3 , novLZ3 ) parsing is less than or
equal to the size of any LZ-type (resp., novLZ-type,
LZ3 -type, novLZ3 -type) parsing.
3. Relations Between Overlapping and Nonoverlapping Parsings

p ≥ k, we obtain r = O(log |fki | ). Hence, it follows from Lemma 3 that the number of new phrases
introduced by all such decompositions is upper
Pz
n
) ≤
bounded by O( i=1 log |fki | ) ≤ z · O(log zk
n
z · O(log z log z ), exactly as required.
σ
Now we process each phrase fi whose leftmost occurrence is at position j > |f1 · · · fi−1 |−k and overlaps fi . Again, p = |f1 · · · fi−1 | + 1 − j is a period
of fi . Denote by c the maximal integer such that
cp ≤ k (note that cp ≥ k2 ). Suppose that cp < |fi |.
We decompose fi as fi = t0 t1 · · · tr , where |t0 | =

For the proof of Theorem 1, we need the following
technical lemma.
Lemma 3. Suppose that t1 , . . . , tr is a sequence of
positive numbers such that t1 + t2 + · · · + tr ≤ n for
some
Pr n >ti 0; then, nfor any given k > 0, we have
i=1 log k ≤ r log rk .
Proof. Denote αi = tki . Note that α1 +· · ·+αr ≤ nk .
A well-known corollary of P
the concavity of the funcr
tion log is that the sum i=1 log αi is maximized
3

n
) for ẑ (and of the respective
bound z · O( z log
σz
n
upper bound z3 · O( z3 log
z3 ) for ẑ3 ).

cp, |t1 | = 20 cp, |t2 | = 21 cp, . . . , |tr−1 | = 2r−2 cp, and
tr is a non-empty suffix of fi of length ≤2r−1 cp. As
in the above analysis, it is easy to show that, for
each h ∈ [1..r], the substring th from the decomposition has a non-overlapping left occurrence and,
therefore, we can include the strings t1 , . . . , tr as
phrases in the novLZ-type parsing under construction. If t0 also has a non-overlapping left occurrence, we include t0 in the parsing; otherwise, we
further decompose t0 into one letter phrases. Since
cp > k2 , it follows from the same arguments as in
the case j ≤ |f1 · · · fi−1 | − k that the substrings
t1 , . . . , tr from all such decompositions add at most
n
z · O(log z log
) phrases. Let us show that the subσ z
strings t0 decomposed into letters add o(z) phrases
(the substrings t0 that have non-overlapping left occurrences, obviously, add at most z phrases).
The crucial observation is that the length of each
substring t0 is at most k and there are only at
most kσ k distinct strings of length at most k in
s. Therefore, at most kσ k substrings t0 can be decomposed into letters and, thus, they in total add at
most k 2 σ k = z α α2 log2σ z one letter phrases, which
is o(z), i.e., negligible compared to z.
In the remained case cp ≥ |fi |, we simply decompose fi into |fi | one letter phrases. Due to
the greedy nature of the LZ parsing, all strings
fj fj+1 [1] (a phrase plus the following letter), for
j ∈ [1..z−1], are distinct. Hence, using a counting argument analogous to the above one, it can
be shown that there are at most kσ k such fi with
cp ≥ |fi | and their decompositions add at most o(z)
phrases.

σ

Proof of Theorem 2. The theorem states that, for
any integers n > 1, σ ∈ [2..n], z ∈ [σ.. logn n ], there
σ
is a string of length n over an alphabet of size σ
such that the sizes of its LZ and novLZ parsings
n
); the same result
are, resp., Θ(z) and Ω(z log z log
σ z
holds for the LZ3 /novLZ3 parsings. We describe
such string only for LZ/novLZ; however, our construction can be used for LZ3 /novLZ3 as well and
the analysis is analogous, so we omit the details.
The example for an unlimited alphabet is easy
(for simplicity, we assume here that n is a muln/σ n/σ
n/σ
tiple of σ): the string a1 a2 · · · aσ , where
a1 , . . . , aσ are distinct letters, satisfies z = 2σ and
n
ẑ = Ω(σ log σn ) = Ω(z log z log
).
σ z
We generalize this simple example for alphabets
of restricted size σ replacing each letter ai with
a string of length Θ(logσ z). Let us describe the
strings that serve as replacements. Denote d =
⌈logσ z⌉. In [3] it was shown that all σ d possible
strings of length d over an alphabet of size σ can
be arranged in a sequence v1 , v2 , . . . , vσd (called a
σ-ary Gray code [3, 7]) such that, for any i ∈ [2..σ d ],
the strings vi−1 and vi differ in exactly one position. Moreover, we can choose such sequence so
that v1 = bd , where b is an arbitrarily chosen letter
from the alphabet. The strings ui = abd−1 vi , where
a is a letter that differs from b, serve as the replacements for ai . The important property of ui is that
no two distinct strings ui and uj are conjugates;
this follows from the observation that conjugates
must contain two occurrences of abd−1 , while the
only string ui with this property is (abd−1 )2 .
n
) =
Suppose that z ≤ 8. Since Ω(z log z log
σ z
Ω(log n) in this case (note that σ ≤ z ≤ 8), the
statement of the theorem can be easily proved using the example string an . Now suppose that z > 8.
Denote k = ⌊z/8⌋. Observe that k ≥ 1 and
σ d = σ ⌈logσ z⌉ ≥ z > k. Our example is the following string:

The lower bound z for ẑ (resp., z3 for ẑ3 ) is
obviously tight since the overlapping and nonoverlapping parsings coincide for any string having
no overlaps, and such overlap-free strings of any
length exist for any non-unary alphabet (see [17]).
The following recursively defined family of strings
gives another possible construction with z = ẑ
and z3 = ẑ3 : s1 = a1 and si = si−1 si−1 ai , for
i > 1, where ai are distinct letters; each string si
has length 2i − 1, and its LZ and novLZ (resp.,
LZ3 and novLZ3 ) parsings coincide and have size
2i − 1 = 2 log(|si | + 1) − 1 (resp., i = log(|si | + 1)).
Further, for a1 a2 · · · an , we also obviously have
z = ẑ and z3 = ẑ3 . Combining these two constructions, one can easily describe, for arbitrary given
integers n > 0 and k ∈ [2 log(n + 1) − 1..n], a string
of length n with k = z = ẑ (resp., k = z3 = ẑ3 ).
Theorem 2 proves the tightness of the upper

⌊

n

⌋ ⌊

n

⌋

⌊

n

⌋

s = u1 2kd u2 2kd · · · uk 2kd ,
⌊

n

⌋

which consists of k “blocks” ui 2kd . Since |ui | = 2d,
n
⌋2kd ≤ n. We append enough
the length of s is ⌊ 2kd
letters a to the end of s to make the length equal to
n; such modification does not affect the proof that
follows, so, without loss of generality, we assume
that |s| = n.
4

Since z ≤ logn n and k ≤ z/8, we have kd ≤
σ
(z/8)⌈logσ z⌉ ≤ 8 logn n ⌈logσ n⌉ ≤ n/4. Therefore,
σ

⌊

n

that f1 t2 t′2 · · · tz3 t′z3 , where ti = fi [1..|fi |−1] and
t′i = fi [|fi |], is an LZ-type parsing of s of size at
most 2z3 − 1 (we remove empty strings ti from the
parsing). Hence z < 2z3 by Lemma 2. Further,
the LZ parsing of s is an LZ3 -type parsing of s by
definition. Therefore, again by Lemma 2, we obtain
z3 ≤ z.
Let us show the tightness of the bounds. Let
k ≥ 2 (the case k = 1 is trivial). The restriction
z = 2k − 1, z3 = k is satisfied by the string

⌋

n
⌋ ≥ 2, i.e., each block ui 2kd consists of at least
⌊ 2kd
two copies of ui .
The string s has an LZ-type parsing with
⌊ n ⌋−1
at most 4 phrases per block: a.b.bd−2 .u1 2kd
.
n
n
′
′′ ⌊ 2kd ⌋−1
′
′
′′ ⌊ 2kd ⌋−1
. · · · .uk .ck .uk .uk
, where ui
.u2 .c2 .u2 .u2
(resp., u′′i ) is the longest common prefix (resp., suffix) of ui and ui−1 , and ci is a letter. This shows
that the size of the LZ parsing of s is at most
4k ≤ z2 . On the other hand, let us demonstrate
that the size of the non-overlapping LZ parsing of
n
s is at least k log⌊ 4kd
⌋.
Consider, for i > 1, the leftmost occurrence of ui
in s. It is inside u2j or uj−1 uj for some j ≤ i. In
the first case, the occurrence is a conjugate of uj ,
implying j = i. In the second case, it is a conjugate
of either uj−1 or uj (since uj−1 and uj differ in exactly one position and have the same length 2d); so
again j = i. This means that the first ui in the ith
block cannot have non-overlapping left occurrences.
Hence, this ui contains at least one border between
phrases of the novLZ parsing. Moreover, such a
phrase containing the suffix of this ui has length at
most 4d since if it has length greater than 4d, then
the second string ui in the ith block has a copy at
a distance of more than 4d symbols to the left and,
thus, this copy is inside the first i − 1 blocks, which
is impossible. Analogously, one can show that the
next phrase has length at most 8d, then 16d, and
so on until the phrase border inside or immediately
before the first occurrence of ui+1 . Thus, we have
n
⌋ phrases are needed for
proved that at least log⌊ 4kd
each of the k blocks, as required. Therefore, since
z
n
z
8 − 1 < k ≤ 8 , we obtain ẑ = Ω(z log z logσ z ), i.e.,
the upper bound for ẑ is reached on the string s.

k−2

aabaab3 aab7 · · · aab2

−1

k−2

aab2

,

whose LZ and LZ3 parsings are, respectively,
k−2

a.a.b.aab.b2 .aab3 .b4 . · · · .aab2 −1 .b,
k−3
k−2
a.ab.aabb.baab4.b3 aab8 . · · · .b2 −1 aab2 .
Next, the equalities z = z3 = 2k hold for the string
k−1

abab4 abab10 · · · abab3·2

−2

,

having the following LZ and LZ3 parsings:
k−2

k−2

a.b.ab.b3 .abab4 .b6 . · · · .abab3·2 −2 .b3·2 ,
k−2
k−2
a.b.ab2 .b2 a.bab5 .b5 a. · · · .bab3·2 −1 .b3·2 −1 .
Note that if we delete the last 3 · 2k−1 b’s, both
parsings of the resulting string will have size 2k − 1.
Therefore, the equality z = z3 = k can be achieved
for any k. Further, the string
k−1

a2 ba5 b3 a11 b7 · · · a3·2

−1 2k −1 3·2k −1 2k

b

a

b

satisfies ẑ = 4k + 3, ẑ3 = 2k + 2 as its corresponding
novLZ and novLZ3 parsings look as follows:
a.a.b.a2.a2.ab.b.ba5.a5.ab3.b3.ba11.a11.ab7 . · · · .
k−1
k−1
k
ba3·2 −1.a3·2 −1.ab2 −1.b,
k−1
k−1
k−1
k
a.ab.a3.a2 b2.ba6.a5 b4. · · · .b2 −1 a3·2 .a3·2 −1 b2 .

4. Relations Between Parsings with Pairs
and Triples

If we delete the last phrase of the novLZ3 parsing,
the resulting string will satisfy ẑ = 4k + 1, ẑ3 =
2k + 1. Therefore, the condition ẑ = 2k − 1, ẑ = k
can be satisfied for any k. Finally, it is easy to see
k−1
that one has ẑ3 = ẑ = k for the string (ab)2 .
The theorem is proved.

Now we prove Theorem 3.
Proof of Theorem 3. The theorem asserts that we
always have 12 z < z3 ≤ z and 12 ẑ < ẑ3 ≤ ẑ, and
these bounds are tight since, for each integer k ≥ 1
and each of the four restrictions z3 = z = k; z3 = k
and z = 2k − 1; ẑ3 = ẑ = k; ẑ3 = k and ẑ = 2k − 1
there is a binary string satisfying this restriction.
Let us consider z and z3 ; the analysis of ẑ and
ẑ3 is the same. Let f1 f2 · · · fz3 be the LZ3 parsing
of a string s. It is immediate from the definitions

5. Concluding Remarks
In the literature there is still a lack of information
concerning the relations between different measures
of compressibility for highly repetitive texts. In
5

this paper we investigated the relations between the
most popular versions of LZ77 but, besides LZ77,
there are other popular measures. For instance, it
is a major open problem to find tight relations between an LZ77 parsing of a given string and the
number of runs in its Burrows–Wheeler transform
(see [6]). Further, it is known that the size of the
smallest grammar of any given string of length n is
within O(log n) factor of the size of the LZ parsing
and it is known that this bound is tight to within
a factor O(log log n) (see [1, 2, 8, 14]); but it is
still open whether this bound can be improved to
O( logloglogn n ). The things are not always clear even
in the realm of LZ77-alike parsings: for example,
it is still not known whether, as it was conjectured
in [12], the so-called LZ-End parsing contains at
most 2ẑ phrases. Finally, note a rather unexpected
connection between ẑ and the number of distinct
factors in the Lyndon decomposition of a string [9].
We refer the reader to [6] and [10] and references
therein for further discussion on different measures
of compressibility and their relations; other compression schemes and results on their relations can
also be found in [16].

[8] A. Jeż, Approximation of grammar-based compression
via recompression, Theoretical Computer Science 592
(2015) 115–134, doi:10.1016/j.tcs.2015.05.027.
[9] J. Kärkkäinen, D. Kempa, Y. Nakashima, S. J. Puglisi,
A. M. Shur, On the size of Lempel–Ziv and Lyndon factorizations, in: STACS 2017, vol. 66 of LIPIcs, Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, 45:1–45:13,
doi:10.4230/LIPIcs.STACS.2017.45, 2017.
[10] D. Kempa, N. Prezza, At the roots of dictionary compression: string attractors, arXiv preprint
arXiv:1710.10964 .
[11] D. Kosolobov, Relations between greedy and
bit-optimal
LZ77
encodings,
arXiv
preprint
arXiv:1707.09789 .
[12] S. Kreft, G. Navarro, On compressing and indexing
repetitive sequences, Theoretical Computer Science 483
(2013) 115–133, doi:10.1016/j.tcs.2012.02.006.
[13] G. Navarro, Indexing text using the Ziv-Lempel trie,
J. Discrete Algorithms 2 (1) (2004) 87–114, doi:
10.1016/S1570-8667(03)00066-2.
[14] W. Rytter, Application of Lempel-Ziv factorization
to the approximation of grammar-based compression,
Theoretical Computer Science 302 (1-3) (2003) 211–
222, doi:10.1016/S0304-3975(02)00777-6.
[15] D. Salomon, Data compression: the complete reference,
4th edition, Springer Verlag, 2006.
[16] J. A. Storer, T. G. Szymanski, Data compression via
textual substitution, Journal of the ACM 29 (4) (1982)
928–951, doi:10.1145/322344.322346.
[17] A. Thue, Über die gegenseitige Lage gleicher Teile
gewisser Zeichenreihen, Norske vid. Selsk. Skr. Mat.
Nat. Kl. 1 (1912) 1–67.
[18] J. Ziv, A. Lempel, A universal algorithm for sequential data compression, IEEE Transactions on
Information Theory 23 (3) (1977) 337–343, doi:
10.1109/TIT.1977.1055714.
[19] J. Ziv, A. Lempel, Compression of individual sequences via variable-rate coding, IEEE Transactions
on Information Theory 24 (5) (1978) 530–536, doi:
10.1109/TIT.1978.1055934.

Acknowledgement. The authors would like
to thank anonymous referees for detailed comments
that helped to improve the paper.
References
[1] P. Bille, T. Gagie, I. L. Gørtz, N. Prezza, A separation between run-length SLPs and LZ77, arXiv preprint
arXiv:1711.07270 .
[2] M. Charikar, E. Lehman, D. Liu, R. Panigrahy,
M. Prabhakaran, A. Sahai, a. shelat, The smallest grammar problem, IEEE Transactions on Information Theory 51 (7) (2005) 2554–2576, doi:
10.1109/TIT.2005.850116.
[3] M. Cohn, Affine m-ary Gray codes, Information
and Control 6 (1) (1963) 70–78, doi:10.1016/S00199958(63)90119-0.
[4] P. Ferragina, I. Nitto, R. Venturini, On the bitcomplexity of Lempel–Ziv compression, SIAM Journal on Computing 42 (4) (2013) 1521–1541, doi:
10.1137/120869511.
[5] T. Gagie, P. Gawrychowski, J. Kärkkäinen, Y. Nekrich,
S. J. Puglisi, LZ77-based self-indexing with faster pattern matching, in: LATIN 2014, vol. 8392 of LNCS,
Springer, 731–742, doi:10.1007/978-3-642-54423-1 63,
2014.
[6] T. Gagie, G. Navarro, N. Prezza, Optimal-time text
indexing in BWT-runs bounded space, arXiv preprint
arXiv:1705.10382 (2017) 1–39.
[7] F. Gray, Pulse code communication, US Patent
2,632,058, 1953.

6

