On the Approximation Ratio
of Greedy Parsings ?
Gonzalo Navarro1,2 and Nicola Prezza3
1

Center for Biotechnology and Bioengineering (CeBiB), Chile
Department of Computer Science, University of Chile, Chile
3
Department of Computer Science, University of Pisa, Italy

arXiv:1803.09517v1 [cs.DS] 26 Mar 2018

2

Abstract. Shannon’s entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based
compression. A plausible lower bound is b, the least number of phrases of
a general bidirectional parse of a text, where phrases can be copied from
anywhere else in the text. Since computing b is NP-complete, a popular
gold standard is z, the number of phrases in the Lempel-Ziv parse of the
text, which is the optimal one when phrases can be copied only from the
left. While z can be computed in linear time with a greedy algorithm, almost nothing has been known for decades about its approximation ratio
with respect to b. In this paper we prove that z = O(b log(n/b)), where n
is the text length. We also show that the bound is tight as a function of
n, by exhibiting a string family where z = Ω(b log n). Our upper bound
is obtained by building a run-length context-free grammar based on a
locally consistent parsing of the text. Our lower bound is obtained by relating b with r, the number of equal-letter runs in the Burrows-Wheeler
transform of the text. We proceed by observing that Lempel-Ziv is just
one particular case of greedy parse, and introduce a new parse where
phrases can only be copied from lexicographically smaller text locations.
We prove that the size v of the smallest parse of this kind has properties
similar to z, including the same approximation ratio with respect to b.
Interestingly, we also show that v = O(r), whereas r = o(z) holds on
some particular classes of strings. On our way, we prove other relevant
bounds between compressibility measures.

1

Introduction

Shannon [44] defined a measure of entropy that serves as a lower bound to the
attainable compression ratio on any source that emits symbols according to a
certain probabilistic model. An attempt to measure the compressibility of finite
texts T [1..n], other than the non-computable Kolmogorov complexity [29], is the
notion of empirical entropy [8], where some probabilistic model is assumed and
?

Partially funded by Basal Funds FB0001, Conicyt, by Fondecyt Grant 1-170048,
Chile, by the Danish Research Council Fund DFF-4005-00267, and by the project
MIUR-SIR CMACBioSeq, grant n. RBSI146R5L. An early version of this paper
appeared in Proc. LATIN’18 [16].

its parameters are estimated from the frequencies observed in the text. Other
measures that, if the text is generated from a probabilistic source, converge to its
Shannon entropy, are derived from the Lempel-Ziv parsing [32] or the grammarcompression [26] of the text.
Some text families, however, are not well modeled as coming from a probabilistic source. A very current case is that of highly repetitive texts, where most
of the text can be obtained by copying long blocks from elsewhere in the same
text. Huge highly repetitive text collections are arising from the sequencing of
myriads of genomes of the same species, from versioned document repositories
like Wikipedia, from source code repositories like GitHub, etc. Their growth is
outpacing Moore’s Law by a wide margin [45]. Understanding the compressibility of highly repetitive texts is important to properly compress those huge
collections.
Lempel-Ziv and grammar compression are particular cases of so-called dictionary techniques, where a set of strings is defined and the text is parsed as a
concatenation of those strings. On repetitive collections, the empirical entropy
ceases to be a relevant compressibility measure; for example the kth order persymbol entropy of T T is the same as that of T , if k  n [31, Lem. 2.6], whereas
this entropy measure is generally meaningless for k > log n [13]. Some dictionary
measures, instead, capture much better the compressibility of repetitive texts.
For example, while an individual genome can rarely be compressed to much less
than 2 bits per symbol, Lempel-Ziv has been reported to compress collections
of human genomes to less than 1% [12]. Similar compression ratios are reported
in Wikipedia.4
Despite the obvious practical relevance of these compression methods, there
is not a clear entropy measure useful for highly repetitive texts. The number
z of phrases generated by the Lempel-Ziv parse [32] is often used as a gold
standard, possibly because it can be implemented in linear time [40] and is
never larger than g, the size of the smallest context-free grammar that generates
the text [41, 7]. However, z is not so satisfactory as an entropy measure: the value
changes if we reverse the text, for example. A much more robust lower bound
on compressibility is b, the size of the smallest bidirectional (macro) scheme
[46]. Such a scheme parses the text into phrases such that each phrase appears
somewhere else in the text (or it is a single explicit symbol), in a way that
makes it possible to recover the text by copying source to target positions in an
appropriate order. This is arguably the strongest possible dictionary method,
but finding the smallest bidirectional scheme is NP-complete [18]. A relevant
question is then how good is the Lempel-Ziv parse as an efficiently implementable
approximation to the smallest bidirectional scheme. Almost nothing is known in
this respect, except that there are string families where z is nearly 2b [46].
In this paper we finally give a tight approximation ratio for z, showing
that the gap is larger than what was previously known. We prove that z =
O(b log(n/b)), and that this bound is tight as a function of n, by exhibiting a
string family where z = Ω(b log n). To prove the upper bound, we show how
4

https://en.wikipedia.org/wiki/Wikipedia:Size of Wikipedia

to build a run-length context-free grammar [38] (i.e., allowing rules of the form
X → Y t that count as size 1) of size grl = O(b log(n/b)). This is done by carrying
out several rounds of locally consistent parsing [22] on top of T , reducing the
resulting blocks to nonterminals in each round, and showing that new nonterminals appear only in the boundaries of the phrases of the bidirectional scheme. We
then further prove that z ≤ 2grl , by extending a classical proof [7] that relates
grammar with Lempel-Ziv compression. To prove the lower bound, we consider
another plausible compressibility measure: the number r of equal-symbol runs in
the Burrows-Wheeler transform (BWT) of the text [6]. We prove that the BWT
induces a valid bidirectional scheme, and thus r = Ω(b). Then the bound follows
from known string families where z = Ω(r log n) [39].
We then show that Lempel-Ziv is just one valid example of interesting greedy
parsings that can be built in linear time. In particular, we define v, the size of
the optimal lexicographic parse of the text, where each phrase must point to
a lexicographically smaller one (both seen as text suffixes). We show that v
can be computed in linear time (with a very practical algorithm) and that it
holds v ≤ min(r, g) and v = O(b log(n/b)). Since z can be asymptotically larger
than r, our bounds show that our new greedy parse asymptotically improves
the Lempel-Ziv parse on some string families while never being worse than a
run-length Burrows-Wheeler transform representation.

2

Basic Concepts

A string is a sequence S[1..`] = S[1]S[2] . . . S[`] of symbols. A substring S[i] . . . S[j]
of S is denoted S[i..j]. A suffix of S is a substring of the form S[i..`]. The juxtaposition of strings and/or symbols represents their concatenation. We will consider
compressing a string T [1..n], called the text.
2.1

Bidirectional Schemes (b)

A bidirectional scheme [46] partitions T [1..n] into b chunks B1 , . . . , Bb , such that
each Bi = T [ti ..ti + `i − 1] (called a target) is either (1) copied from another
substring T [si ..si + `i − 1] (called a source) with si 6= ti , which may overlap
T [ti ..ti + `i − 1], or (2) formed by `i = 1 explicit symbol.
We define the function f : [1..n] → [1..n] so that, in case (1), f (ti +j) = si +j
for all 0 ≤ j < `i , and in case (2), f (ti ) = −1. Then, the bidirectional scheme
is valid if there is an order in which the sources si + j can be copied onto the
targets ti + j so that all the positions of T can be inferred.
Being a valid scheme is equivalent to saying that f has no cycles, that is,
there is no k > 0 and p such that f k (p) = p: Initially we can set all the explicit
positions (type (2)), and then copy sources with known values to their targets.
If f has no cycles, we will eventually complete all the positions in T because, for
every T [p], there is a k > 0 such that f k (p) = −1, so we can obtain T [p] from
the symbol explicitly stored for T [f k−1 (p)].
We use b to denote the smallest bidirectional scheme, which is NP-complete
to compute [18].

2.2

Lempel-Ziv Parsing (z, zno )

Lempel and Ziv [32] define a parsing of T into the fewest possible phrases T =
Z1 . . . Zz , so that each phrase Zi is a substring (but not a suffix) of Z1 . . . Zi ,
or a single symbol. This means that the source T [si ..si + `i − 1] of the target
Zi = T [ti ..ti + `i − 1] must satisfy si < ti , but sources and targets may overlap.
It turns out that the greedy left-to-right parsing indeed produces the optimal
number z of phrases [32, Thm. 1]. Further, the parsing can be obtained in O(n)
time [40, 46].
If we disallow that a phrase overlaps its source, that is, Zi must be a substring
of Z1 . . . Zi−1 or a single symbol, then we call zno the number of phrases obtained.
In this case it is also true that the greedy left-to-right parsing produces the
optimal number zno of phrases [46, Thm. 10 with p = 1]. Since the Lempel-Ziv
parsing allowing overlaps is optimal among all left-to-right parsings, we also have
that zno ≥ z. This parsing can also be computed in O(n) time [9]. Note that, on
a text family like T = an , it holds that zno = Ω(z log n).
Little is known about the relation between b and z except that z ≥ b by
definition (z is the smallest left-to-right parsing) and that, for any constant
 > 0, there is an infinite family of strings for which b < ( 12 + ) · min(z, z R ) [46,
Cor. 7.1], where z R is the z value of the reversed string.
Apart from being used as a gold standard to measure repetitiveness, the size
of the Lempel-Ziv parse is bounded by the statistical entropy [32]. In particular,
if Hk (T ) denotes the k-th order empirical entropy of the text [36], then it holds
zno log2 n ≤ nHk (T ) + o(n logσ n) whenever k = o(logσ n) [30].

2.3

Grammar Compression (g, grl )

Consider a context-free grammar (CFG) that generates T and only T [26]. Each
nonterminal must be the left-hand side in exactly one rule, and the size g of the
grammar is the sum of the right-hand sides of the rules. In general, we will use
g to denote the minimum possible size of a grammar that generates T , which is
NP-complete to compute [41, 7].
If we allow, in addition, rules of the form X → Y t , of size 1, the result is a
run-length context-free grammar (RLCFG) [38]. We will use grl to denote the
size of the smallest RLCFG that generates T . Thus, it is clear that grl ≤ g.
Further, on the string family T = an it holds that g = Ω(grl log n).
A well-known relation between zno and g is zno ≤ g = O(zno log(n/zno )) [41,
7]. Further, it is known that g = O(z log(n/z)) [19, Lem. 8]. Those papers exhibit
O(log n)-approximations to the smallest grammar, as well as several others [43,
22, 23]. A negative result about the approximation are string families where
g = Ω(zno log n/ log log n) [7, 20] and even grl = Ω(zno log n/ log log n) [4].
The size g is also bounded in terms of the statistical entropy [26].

2.4

Suffix Arrays and Runs in the Burrows-Wheeler Transform (r)

Assume that T is terminated by the special symbol T [n] = $, which is lexicographically smaller than all the others. This makes any lexicographic comparison
between suffixes well defined.
The suffix array [34] of T [1..n] is an array SA[1..n] storing a permutation of
[1..n] so that, for all 1 ≤ i < n, the suffix T [SA[i]..] is lexicographically smaller
than the suffix T [SA[i + 1]..]. Thus SA[i] is the starting position in T of the ith
smallest suffix of T in lexicographic order. The suffix array can be built in O(n)
time [27, 28, 24].
The inverse permutation of SA, ISA[1..n], is called the inverse suffix array, so
that ISA[j] is the lexicographical position of the suffix T [j..n] among the suffixes
of T . It can be built in linear time by inverting the permutation SA.
The longest common prefix array, LCP [1..n], stores at LCP [i] the length of
the longest common prefix between T [SA[i]..] and T [SA[i−1]..], with LCP [1] = 0.
It can be built in linear time from T and ISA [25].
The Burrows-Wheeler Transform of T [1..n], BWT [1..n] [6], is a string defined
as BWT [i] = T [SA[i] − 1] if SA[i] > 1, and BWT [i] = T [n] = $ if SA[i] = 1.
That is, BWT has the same symbols of T in a different order, and is a reversible
transform.
The array BWT can be easily obtained from T and SA, and thus also be
built in linear time. To obtain T from BWT [6] in linear time, one considers two
arrays, L[1..n] = BWT and F [1..n], which contains all the symbols of L (or T )
in ascending order. Alternatively, F [i] = T [SA[i]], so F [i] follows L[i] in T . We
need a function that maps any L[i] to the position j of that same symbol in F .
The formula is LF (i) = C[c] + rank[i], where c = L[i], C[c] is the number of
occurrences of symbols less than c in L, and rank[i] is the number of occurrences
of symbol L[i] in L[1..i]. Once C and rank are computed, we reconstruct T [n] = $
and T [n − k] ← L[LF k−1 (1)] for k = 1, . . . , n − 1.
The number of equal-symbol runs r in the BWT of T can be bounded in
terms of the empirical entropy, r ≤ nHk (T ) + σ k [33]. However, the measure is
also interesting on highly repetitive collections (where, in particular, z and zno
are small). For example, there are string families where z = Ω(r log n) [39], and
others where r = Ω(zno log n) [1, 39].
2.5

Locally consistent parsing

A string can be parsed in a locally consistent way, in the sense that equal substrings are largely parsed in the same form. We use a variant of locally consistent
parsing called recompression [22, 21].
Definition 1. A repetitive area in a string is a maximal run of the same symbol,
of length 2 or more.
Definition 2. Two segments contained in [1..n] overlap if they are not disjoint
nor one contained in the other.

Lemma 1 ([22]). We can partition a string S[1..`] into at most (3/4)` blocks
so that, for every pair of identical substrings S[i..j] = S[i0 ..j 0 ], if neither S[i +
1..j − 1] or S[i0 + 1..j 0 − 1] overlap a repetitive area, then the sequence of blocks
covering S[i + 1..j − 1] and S[i0 + 1..j 0 − 1] are identical.
Proof. The parsing is obtained by, first, creating new symbols that represent
the repetitive areas. On the resulting sequence, the alphabet (which contains
original symbols and created ones) is partitioned into two subsets, left-symbols
and right-symbols. Then, every left-symbol followed by a right-symbol are paired
in a block. It is then clear that, if S[i+1..j −1] and S[i0 +1..j 0 −1] do not overlap
repetitive areas, then the parsing of S[i..j] and S[i0 ..j 0 ] may differ only in their
first position (if it is part of a repetitive area ending there, or if it is a rightsymbol that becomes paired with the preceding one) and in their last position (if
it is part of a repetitive area starting there, or if it is a left-symbol that becomes
paired with the following one). Jez [22] shows how to choose the pairs so that S
contains at most (3/4)` blocks.
t
u
The lemma ensures a locally consistent parsing into blocks as long as the substrings do not overlap repetitive areas, though the substrings may fully contain
repetitive areas.

3

Upper Bounds

In this section we obtain our main upper bound, z = O(b log(n/b)), along with
other byproducts. To this end, we first prove that grl = O(b log(n/b)), and
then that z ≤ 2grl . To prove the first bound, we build a RLCFG on top of a
bidirectional scheme. The grammar is built in several rounds of locally consistent
parsing on the text. In each round, the blocks of the locally consistent parsing
are converted into nonterminals and fed to the next round. The key is to prove
that distinct nonterminals are produced only at the boundaries of the phrases of
the bidirectional scheme. The second bound is an easy extension to the known
result zno ≤ g.
Theorem 1. Let T [1..n] have a bidirectional scheme of size b. Then there exists
a run-length context-free grammar of size grl = O(b log(n/b)) that generates T .
Proof. Recalling Lemma 1, consider a locally consistent parsing of W = T into
blocks. We will count the number of different blocks we form, as this corresponds
to the number of nonterminals produced in the first round.
Recall from Section 2.1 that our bidirectional scheme represents T as a sequence of chunks, by means of a function f . To count the number of different
blocks produced, we will pessimistically assume that the first two and the last
two blocks intersecting each chunk are all different. The number of such bordering blocks is at most 4b. On the other hand, we will show that non-bordering
blocks do not need to be considered, because they will be counted somewhere
else, when they appear near the extreme of a chunk.
We show that this is true in both types of non-bordering blocks resulting
from Lemma 1:

1. The block is a pair of left- and right-alphabet symbols.5 As these symbols can
be an original symbol or a repetitive area, let us write the pair generically as
X = a`a b`b , for some `a , `b ≥ 1, and let ` = `a + `b be the length of the block
X. If W [p..p + ` − 1] = X is not bordering, then it is strictly contained in a
chunk. Thus, by the definition of a chunk, it holds that [f (p − 1)..f (p + `)] =
[f (p) − 1..f (p) + `], and that W [f (p) − 1..f (p) + `] = W [p − 1..p + `]. That
is, the block appears again at [f (p)..f (p) + ` − 1], surrounded by the same
symbols. Since, by the way Lemma 1 works, it must be W [f (p) − 1] =
W [p − 1] 6= a and W [f (p) + `] = W [p + `] 6= b, and a`a is a left-symbol and
b`b is a right-symbol, the locally consistent parsing must also form a block
W [f (p)..f (p) + ` − 1] = X. If this block is bordering, then it will be counted.
Otherwise, by the same argument, W [f (p) − 1..f (p) + `] will be equal to
W [f 2 (p)−1..f 2 (p)+`] and a block will be formed with W [f 2 (p)..f 2 (p)+`−1].
Since f has no cycles, there is a k > 0 for which f k (p) = −1. Thus for some
l < k it must be that X = W [f l (p)..f l (p) + ` − 1] is bordering. At the
smallest such l, the block W [f l (p)..f l (p) + ` − 1] will be counted. Therefore,
X = W [p..p + ` − 1] is already counted somewhere else and we do not need
to count it at W [p..p + ` − 1].
2. The block is a single (original or maximal-run) symbol W [p..p + ` − 1] = a` ,
for some ` ≥ 1. It also holds that [f (p−1)..f (p+`)] = [f (p)−1..f (p)+`] and
W [f (p) − 1..f (p) + `] = W [p − 1..p + `], because a` is strictly inside a chunk.
Since W [f (p) − 1] = W [p − 1] 6= a and W [f (p) + `] = W [p + `] 6= a, the
parsing forms the same maximal run a` = W [f (p)..f (p) + ` − 1]. Moreover,
since W [p..p + ` − 1] is not bordering, the previous and next blocks produced
by the parsing, X = W [p0 ..p − 1] and Y = [p + `..p00 ], are also strictly inside
the same chunk, and therefore they also appear preceding and following
W [f (p)..f (p) + ` − 1], at X = W [f (p0 )..f (p) − 1] and Y = [f (p) + `..f (p00 )].
Since a` was not paired with X nor Y at W [p..p + ` − 1], the parsing will
also not pair them at W [f (p)..f (p) + ` − 1]. Therefore, the parsing will
leave a` as a block also in [f (p)..f (p) + ` − 1]. If W [f (p)..f (p + ` − 1)] is
bordering, then it will be counted, otherwise we can repeat the argument
with W [f 2 (p) − 1..f 2 (p) + `] and so on, as in the previous item.
Therefore, we produce at most 4b distinct blocks, and the RLCFG has at
most 12b nonterminals (for X = a`a b`b we may need 3 nonterminals, A → a`a ,
B → b`b , and C → AB).
For the second round, we create a reduced sequence W 0 from W by replacing
all the blocks of length 2 or more by their corresponding nonterminals. The new
sequence is guaranteed to have length at most (3/4)n by Lemma 1.
We define a new bidirectional scheme (recall Section 2.1) on W 0 , as follows:
1. For each bordering block in W , its nonterminal symbol position in W 0 is
made explicit in the bidirectional scheme of W 0 . Note that this includes the
blocks covering the explicit symbols in the bidirectional scheme of W .
5

For this case, we could have defined bordering in a stricter way, as the first or last
block of a chunk.

2. For the chunks Bi = W [ti ..ti + `i − 1] of W containing non-bordering blocks
(note Bi cannot be an explicit chunk), let Bi0 be obtained by trimming from
Bi the bordering blocks near the extremes of Bi . Then Bi0 appears inside
W [si ..si + `i − 1] (with si = f (ti )), where the same sequence of blocks is
formed by our arguments above. We then form a chunk in W 0 with the sequence of nonterminals associated with the blocks of Bi0 (all of which are
non-bordering), pointing to the identical sequence of nonterminals that appear as blocks inside W [si ..si + `i − 1].
To bound the total number of nonterminals generated, let us call Wk the
sequence W after k iterations (so T = W0 ) and Nk the number of distinct
blocks created when converting Wk into Wk+1 .
In the first iteration, since there may be up to 4 bordering blocks around
each chunk limit, we may create N1 ≤ 4b distinct blocks. Those blocks become
new explicit chunks in the bidirectional scheme of W 0 = W1 . Note that those
explicit chunks are grouped into b regions of up to 4 consecutive chunks. In each
new iteration, Wk is parsed into blocks again. We have shown that the blocks
formed outside regions (i.e., non-bordering blocks) are not distinct, so we can
focus on the number of new blocks produced to parse each of the b regions. The
parsing produces at most 4 new distinct blocks extending each region. However,
the parsing of the regions themselves may also produce new distinct blocks. Our
aim is to show that the number of those blocks is also bounded because they
decrease the length of the regions, which only grow by 4b per iteration.
Let nk be the number of new distinct blocks produced when parsing the
regions themselves. Therefore it holds that the number of distinct blocks Nk
produced in the kth iteration is at most
4b + nk , and thePtotal number of distinct
Pk−1
k−1
blocks created up to building Wk is i=0 Ni ≤ 4bk + i=0 ni .
On the other hand, for each of the nk blocks created when parsing a region,
the length of the region decreases at least by 1 in Wk+1 . Let us call Ck the
number of explicit chunks in Wk . Since only the 4 new bordering blocks at each
region are converted into explicit chunks, it holds that Ck ≤ 4bk for all
k > 0.
Pk−1
Moreover, it holds Ck+1 ≤ Ck + 4b − nk , and thus 0 ≤ Ck ≤ 4bk − i=0 ni .
Pk−1
Pk−1
Therefore,
i=0 ni ≤ 4bk and thus
i=0 Ni ≤ 8bk. Since each nonterminal
may need 3 rules to represent a block, a bound on the number of nonterminals
created is 24bk.
After k rounds, the sequence is of length at most (3/4)k n and we have
generated at most 24bk nonterminals. Therefore, if we choose to perform k =
log4/3 (n/b) rounds, the sequence will be of length at most b and the grammar
size will be O(b log(n/b)). To complete the process, we add O(b) nonterminals
to reduce the sequence to a single initial symbol.
The idea is illustrated in Figure 1.
t
u
With Theorem 1, we can also bound the size z of the Lempel-Ziv parse [32]
that allows overlaps. The size without allowing overlaps is known to be bounded
by the size of the smallest CFG, zno ≤ g [41, 7]. We can easily see that z ≤ 2grl
also holds by extending an existing proof [7, Lem. 9] to handle the run-length

. . . . .
.....
.....

. . . . .
.....
.....

Fig. 1. Illustration of Theorem 1. On top we see the limit between two long chunks
of W0 . In this example, the blocking always pairs two symbols. We show below W0
the 4 bordering blocks formed with the symbols nearby the limit. Below, in W1 , those
blocks are converted into 4 explicit chunks (of length 1). This region of 4 symbols is
then parsed into 2 blocks. The parsing also creates 4 new bordering blocks from the
ends of the long chunks. In W2 , below, we have now a region of 6 explicit chunks. They
could have been 8, but we created 2 distinct blocks that reduced their number to 6.

rules. We call left-to-right parse of T any parsing in which each new phrase is a
symbol or it occurs previously in T .
Theorem 2. Let a RLCFG of size grl expand to a text T . Then the Lempel-Ziv
parse (allowing overlaps) of T produces z ≤ 2grl phrases.
Proof. Consider the parse tree of T , where all internal nodes representing any
but the leftmost occurrence of a nonterminal are pruned and left as leaves. The
number of nodes in this tree is precisely grl . We say that the internal node of
nonterminal X is its definition. Our left-to-right parse of T is a sequence Z[1..z]
obtained by traversing the leaves of the pruned parse tree left to right. For a
terminal leaf, we append the symbol to Z. For a leaf representing nonterminal
X, we append to Z a reference to the area T [x..y] expanded by the leftmost
occurrence of X.
Rules X → Y t are handled as follows. First, we expand them to X → Y ·Y t−1 ,
that is, the node for X has two children for Y , and it is annotated with t−1. Since
the right child of X is not the first occurrence of Y , it must be a leaf. The left
child of X may or may not be a leaf, depending on whether Y occurred before or
not. Now, when our leaf traversal reaches the right child Y of a node X indicating
t − 1 repetitions, we append to Z a reference to T [x..y + (t − 2)(y − x + 1)], where
T [x..y] is the area expanded by the first child of X. Note that source and target
overlap if t > 2. Thus a left-to-right parse of size 2grl exists, and Lempel-Ziv is
the optimal left-to-right parse [32, Thm. 1].
t
u
By combining Theorems 1 and 2, we obtain a result on the long-standing
open problem of finding the approximation ratio of Lempel-Ziv compared to the
smallest bidirectional scheme.
Theorem 3. Let T [1..n] have a bidirectional scheme of size b. Then the LempelZiv parsing of T allowing overlaps has z = O(b log(n/b)) phrases.

φ
ISA

SA

y x
q−1 q

y−1 x−1

p q
x−1 x

p−1q−1
y−1 y

p−1 p

LF

Fig. 2. Illustration of Lemma 2.

We can also derive upper bounds for g, the size of the smallest CFG, and for
zno , the size of the Lempel-Ziv parse that does not allow overlaps. It is sufficient
to combine the previous results with the facts that g = O(z log(n/z)) [19, Lem. 8]
and zno ≤ g [41, 7].
Theorem 4. Let T [1..n] have a bidirectional scheme of size b. Then there exists
a context-free grammar of size g = O(b log2 (n/b)) that generates T .
Theorem 5. Let T [1..n] have a bidirectional scheme of size b. Then the LempelZiv parsing of T without allowing overlaps has zno = O(b log2 (n/b)) phrases.

4

Lower Bounds

In this section we prove that the upper bound of Theorem 3 is tight as a function
of n, by exhibiting a family of strings for which z = Ω(b log n). This confirms that
the gap between bidirectionality and unidirectionality is significantly larger than
what was previously known. The idea is to define phrases in T accordingly to the
r runs in the BWT, and to show that these phrases induce a valid bidirectional
macro scheme of size 2r. This proves that r = Ω(b). Then we use a well-known
family of strings where z = Ω(r log n).
Definition 3. Let p1 , p2 , . . . , pr be the positions that start runs in the BWT, and
let t1 < t2 < . . . < tr be the corresponding positions in T , {SA[pi ], 1 ≤ i ≤ r},
in increasing order. Note that t1 = 1 because BWT [ISA[1]] = $ is a size-1 run,
and assume tr+1 = n + 1, so that T is partitioned into phrases T [ti ..ti+1 − 1].
Let also φ(p) = SA[ISA[p] − 1] if ISA[p] > 1 and φ(p) = SA[n] otherwise. Then
we define the bidirectional scheme of the BWT:
1. For each 1 ≤ i ≤ r, T [ti ..ti+1 − 2] is copied from T [φ(ti )..φ(ti+1 − 2)].
2. For each 1 ≤ i ≤ r, T [ti+1 − 1] is stored explicitly.
We build on the following lemma, illustrated in Figure 2.
Lemma 2. Let [q − 1..q] be within a phrase of T . Then it holds that φ(q − 1) =
φ(q) − 1 and T [q − 1] = T [φ(q) − 1].

Proof. Consider the pair of positions T [q − 1..q] within a phrase. Let them be
pointed from SA[x] = q and SA[y] = q − 1, therefore ISA[q] = x, ISA[q − 1] = y,
and LF (x) = y. Now, since q is not a position at the beginning of a phrase, x is
not the first position in a BWT run. Therefore, BWT [x − 1] = BWT [x], from
which it follows that LF (x − 1) = LF (x) − 1 = y − 1. Now let SA[x − 1] = p, that
is, p = φ(q). Then φ(q − 1) = SA[ISA[q − 1] − 1] = SA[y − 1] = SA[LF (x − 1)] =
SA[x − 1] − 1 = p − 1 = φ(q) − 1. It also follows that T [q − 1] = BWT [x] =
BWT [x − 1] = T [p − 1] = T [φ(q) − 1].
t
u
Theorem 6. The bidirectional scheme of the BWT is a valid bidirectional scheme,
thus 2r ≥ b.
Proof. By Lemma 2, it holds that φ(q−1) = φ(q)−1 if [q−1..q] is within a phrase,
and that T [q − 1] = T [φ(q) − 1]. Therefore, we have that φ(ti + k) = φ(ti ) + k for
0 ≤ k < `i = ti+1 − ti − 1, and then T [φ(ti )..φ(ti+1 − 2)] is indeed a contiguous
range of length `i . We also have that T [φ(ti )..φ(ti+1 − 2)] = T [ti ..ti+1 − 2], and
therefore it is correct to make the copy.
Finally, it is easy to see that we can recover the whole T from those 2r
directives. We can, for example, follow the cycle φk (n), k = n − 1, . . . , 1, and
copy T [φk (n)] from T [φk+1 (n)] unless the former is explicitly stored (note that
T [φn (n)] = T [φ0 (n)] = T [n] is stored explicitly).
Since the bidirectional scheme of the BWT is of size 2r, it follows by definition
that 2r ≥ b.
t
u
We are now ready to obtain the lower bound on bidirectional versus unidirectional parsings.
Theorem 7. There is an infinite family of strings over an alphabet of size 2 for
which z = Ω(b log n).
Proof. Consider the family of the Fibonacci stings, F1 = a, F2 = b, and Fk =
Fk−1 Fk−2 for all k > 2. As observed by Prezza [39, Thm. 25], for Fk we have
r = O(1) [35] and z = Θ(log n) [11]. By Theorem 6, it also holds that b = O(1),
and therefore z = Ω(b log n).
t
u
Finally, we can also prove the following lower bound that connects r with g.
Lemma 3. There is an infinite family of strings over an alphabet of size 2 for
which r = Ω(g log n/ log log n).
Proof. On a de Bruijn sequence of order k on a binary alphabet we have r = Θ(n)
[1], z = O(n/ log n), and thus g = O(z log(n/z)) = O(n log log n/ log n).
t
u

5

Lexicographic Bidirectional Parses

In this section we expand the universe of useful greedy parses by introducing another parsing that is left-to-right not in the text order, but in the lexicographical
order. Let us first define such a family of parses.

Definition 4. A lexicographic parse of T [1..n] is a bidirectional scheme partitioning T into v phrases B1 , . . . , Bv , such that each target Bi = T [ti ..ti + `i − 1]
that is not an explicit symbol is copied from a source T [si ..si + `i − 1] that satisfies T [si ..] < T [ti ..] in the lexicographic order, or which is the same, ISA[si ] <
ISA[ti ].
Note that the usual left-to-right parses require instead that si < ti . In fact,
any parse satisfying such lexicographic order is a bidirectional scheme.
Lemma 4. Any parsing satisfying ISA[si ] < ISA[ti ] is a valid bidirectional
scheme.
Proof. Let us define, as in Section 2.1, the function f : [1..n] → [1..n] so that,
when T [ti ..ti +`i −1] is copied from T [si ..si +`i −1], it holds that f (ti +j) = si +j
for all 0 ≤ j < `i , and for explicit symbols T [ti ] it holds that f (ti ) = −1. To
show that T can be reconstructed from the parse, it is then sufficient to prove
that f has no cycles.
For this sake, it is enough to show that T [f (p)..] < T [p..] in lexicographic
order. This is clearly the case when p = ti and f (p) = si for some i, by hipothesis.
In general, if p = ti + j and f (p) = si + j for some 0 < j < `i , since T [si ..si +
j − 1] = T [ti ..ti + j − 1] and T [si ..] < T [ti ..], it must also hold that T [f (p)..] =
T [si + j..] < T [ti + j..] = T [p..].
t
u
One example of a lexicographic parse is the bidirectional scheme based on
the BWT we introduced in Section 4.
Lemma 5. The bidirectional scheme induced by the BWT in Def. 3 is a lexicographic parse of size 2r.
Proof. The definition uses function f (p) = φ(p) = SA[ISA[p] − 1] to copy from
T [φ(ti )..φ(ti )+`i −1] to T [ti ..ti +`i −1], where `i = ti+1 −ti −1 (recall Theorem 6).
Therefore it holds that ISA[si ] = ISA[φ(ti )] = ISA[ti ] − 1 < ISA[ti ].
t
u
Another lexicographic parse is lcpcomp [10]. This algorithm uses a queue
to find the largest entry in the LCP array. This information is then used to
define a new phrase of the factorization. LCP entries covered by the phrase
are then removed from the queue, LCP values affected by the creation of the
new phrase are decremented, and the process is repeated until there are no
text substrings that can be replaced with a pointer to lexicographically-smaller
positions. The output of lcpcomp is a series of source-length pairs interleaved
with plain substrings (that cannot be replaced by pointers).
Lemma 6. The lcpcomp factorization [10] is a lexicographic parse.
Proof. The property can be easily seen from step 2 of the algorithm [10, Sec. 3.2]:
the authors report a phrase (i.e., source-length pair) (SA[i−1], LCP 0 [i]) expanding to text substring T [SA[i]..SA[i] + LCP 0 [i] − 1]. We write LCP 0 [i] because
entries of the LCP array may be decremented in step 4, therefore LCP 0 [i] ≤

LCP [i] at any step of the algorithm for any 1 ≤ i ≤ n. This however preserves
the two properties of lexicographic parsings: T [SA[i]..SA[i] + LCP 0 [i] − 1] =
T [SA[i − 1]..SA[i − 1] + LCP 0 [i] − 1] (phrases are equal to their sources) and,
clearly, i − 1 < i (sources are lexicographically smaller than phrases).
t
u
It is natural to ask how difficult is to find the optimal lexicographic parse,
that is, the one that minimizes v. It turns out that this is surprisingly simple.
Definition 5. The lex-parse of T [1..n], with arrays SA, ISA, and LCP , is defined as a partition T = B1 . . . Bv such that Bi = T [ti ..ti + `i − 1], satisfying (1)
t1 = 1 and ti+1 = ti + `i , and (2) `i = LCP [ISA[ti ]], with the exception that if
`i = 0 we set `i = 1 and make Bi an explicit phrase. The non-explicit phrases
T [ti ..ti + `i − 1] are copied from T [si ..si + `i − 1], where si = SA[ISA[ti ] − 1].
Since ISA and LCP can be built in linear time, it is clear that the lex-parse
of T can be built in O(n) time. Let us show that it is indeed a valid lexicographic
parse.
Lemma 7. The lex-parse is a valid lexicographic parse.
Proof. First, the parse covers T and it copies sources to targets with the same
content: Let x = ISA[ti ] and y = ISA[ti ] − 1. Then `i = LCP [x] is the length
of the shared prefix between ti = SA[x] and si = SA[y]. Therefore we can
copy T [si ..si + `i − 1] to T [ti ..ti + `i − 1]. Second, the parse is lexicographic:
ISA[si ] = ISA[ti ] − 1 < ISA[ti ].
t
u
From now on we will use v as the size of the lex-parse. Let us show that the
lex-parse is indeed optimal.
Theorem 8. The lex-parse is the smallest lexicographic parse. Thus, v ≤ 2r.
Proof. Since the first phrase always starts at position 1, if there is a parse Bi0 =
T [t0i ..t0i +`0i −1] for 1 ≤ i ≤ v 0 and v 0 < v, then there must be a first phrase where
t0i+1 > ti+1 . Since it is the first, it must hold that t0i ≤ ti < ti+1 < t0i+1 . Let us
call δ = ti − t0i < `0i = t0i+1 − t0i . Therefore, there is a source T [s0i ..s0i + `0i − 1] =
T [t0i ..t0i +`0i −1] such that T [s0i ..] < T [t0i ..]. Since T [s0i ..s0i +δ −1] = T [t0i ..t0i +δ −1],
it also holds that T [s0i + δ..s0i + `0i − 1] = T [ti ..t0i + `0i − 1] = T [ti ..t0i+1 − 1] and
that T [s0i + δ..] < T [ti ..]. Therefore, there exists a suffix T [s0i + δ..] that shares
with T [ti ..] a prefix of length t0i+1 − ti > ti+1 − ti = `i and is lexicographically
smaller than T [ti ..]. This is not possible, because `i = LCP [ISA[ti ]], and a suffix
T [SA[p]..] cannot share a prefix longer than LCP [p] with any other suffix of T
that is lexicographically smaller than it.
Since the BWT induces a lexicographic parse of size 2r, we obtain v ≤ 2r. t
u
Note that, unlike v, z can be Ω(r log n), and thus v offers a better asymptotic
bound with respect to the number of runs in the BWT. The following corollary
of Theorem 7 is immediate.

Lemma 8. There is an infinite family of strings over an alphabet of size 2 for
which z = Ω(v log n).
Another bound we obtain is v ≤ |lcpcomp|, since lcpcomp [10] is just a particular lexicographic parse (see Lemma 6). We can also easily prove that v ≤ g,
just like it holds that z ≤ g, by using a similar technique.
Lemma 9. Let a CFG of size g expand to a text T . Then the lex-parse of T
produces v ≤ g phrases.
Proof. It suffices to show how to build a lexicographic parse of size at most g.
Analogously to the proof of Theorem 2, consider the parse tree of T , where all
internal nodes labeled by a nonterminal X and expanding to T [xi ..zi ] are pruned
and left as leaves, except for the lexicographically smallest suffix T [xi ..]. The
number of nodes in this tree is precisely g. We then define a lexicographic parse
of T by converting every terminal leaf to an explicit phrase and every pruned
node labeled by nonterminal X to a phrase that points to the area T [xi ..zi ]
corresponding to only non-pruned occurrence of X. Thus a lexicographic parse
of size ≤ g exists, and therefore v ≤ g.
t
u
Note that this is a general technique that can be applied to any bidirectional
scheme that imposes a well-founded order between phrases. We now show that
v is also upper-bounded by 2grl , which implies v = O(b log(n/b)).
Theorem 9. Let a RLCFG of size grl expand to a text T . Then the lex-parse
of T produces v ≤ 2grl phrases, and thus v = O(b log(n/b)).
Proof. We extend the proof of Lemma 9 so as to consider the rules X → Y t .
These are expanded either to X → Y · Y t−1 or to X → Y t−1 · Y . In both
cases, the child Y is handled as usual (i.e., pruned if its suffix is not the smallest
labeled Y , or expanded otherwise). If we choose X → Y · Y t−1 , let Y expand to
T [x..y − 1] and Y t−1 expand to T [y..z]. Then we define T [y..z] as the target of
source T [x..x + z − y]. If we instead choose X → Y t−1 · Y , let Y t−1 expand to
T [x..y − 1] and Y expand to T [y..z]. Then we define T [x..y − 1] as the target of
source T [x + z − y + 1..z]. In both cases, the target overlaps the source if t > 2.
We show that one of those two cases must copy a source to a lexicographically
larger target. Let us call e(·) the string to which a nonterminal expands, and
Z = T [z + 1..]. If the first case induces an invalid copy, then it holds that
e(Y t ) · Z > e(Y t−1 ) · Z. If the second case also induces an invalid copy, then it
holds that e(Y t ) · Z < e(Y t−1 ) · Z. Clearly only one of the two may hold.
Since we have created two nonterminals for each run-length rule, a lexicographic parse of size ≤ 2grl exists, and therefore v ≤ 2grl . By Theorem 1, we
also have v = O(b log(n/b)).
t
u
Let us now show that v can be asymptotically smaller than r. We prove the
following crude upper bound on v, which is well-known to hold for zno .
Lemma 10. It holds that v = O(n/ logσ n).

Proof. Let us define a partition T = B1 . . . Bs similarly to Def. 5, but here we
add an extra symbol to the targets: `i = LCP [ISA[ti ]] + 1 in all cases. Note that
this is not a bidirectional parse, just a partition of T .
In this partition, every phrase (that is not an explicit symbol) is distinct.
Otherwise, let T [ti ..ti + `i − 1] = T [tj ..tj + `j − 1] and assume w.l.o.g. that
T [ti ..] < T [tj ..]. Then, there exists a suffix T [ti ..] lexicographically smaller than
T [tj ..] sharing more than `j − 1 = LCP [ISA[tj ]] symbols with T [tj ..], which
contradicts the definition of LCP .
Since there are s distinct phrases in the partition, it follows that s = O(n/ logσ n)
[32].
While this is not necessarily a bidirectional parse, we can build one of size
v ≤ 2s by cutting each target T [ti ..ti + `i − 1] into T [ti ..ti + `i − 2] and the
explicit symbol T [ti + `i − 1] (if `i = 1 then it is just an explicit symbol). Then
we also have v = O(n/ logσ n).
t
u
Since on a de Bruijn sequence of order k on a binary alphabet we have
r = Θ(n) [1], we also obtain the following result.
Lemma 11. There is an infinite family of strings over an alphabet of size 2 for
which r = Ω(v log n) and r = Ω(zno log n).
This crude upper bound can be significantly refined. A consequence of Lemma 9
is that v can also be related, just like z, with the empirical entropy of T .
Lemma 12. For any text T , it holds that v log2 n ≤ 2nHk + o(n log σ) for any
k = o(logσ n).
Proof. Let z78 be the size of the Lempel-Ziv 1978 (LZ78) parsing [47] of T . Then,
it holds that [30, Thm. A.4]6 z78 log2 n ≤ nHk (T ) + o(n log σ) for k = o(logσ n).
Since this parsing can be converted into a CFG of twice the size, it holds that
v ≤ 2z78 .
t
u
Note that the factor 2 is an artifact due to the model. The LZ78 parse
includes, for each phrase, a pointer and a final letter. Those count as two elements
when converting the parse into a CFG, but they count as just one phrase.
An interesting remaining question is whether v is always O(z) or there is a
string family where z = o(v). While we have not been able to settle this question,
we can exhibit a string family for which z < 53 v.
Lemma 13. On the alphabet {1, . . . , σ + 1}, where σ is not a multiple of 3,
consider the string B1 = (2 3 . . . σ 1)3 . Then, for i = 1, . . . , σ − 1, string Bi+1 is
formed by changing Bi [3σ −3i] to σ +1. Our final text is then T = B1 ·B2 · · · Bσ ,
of length n = 3σ 2 . In this family, z = 3σ − 2 and v = 5σ − 2.
6

Noting that c = O(n/ logσ n) and assuming k = o(logσ n).

Proof. In the LZ77 parse of T , we first have σ + 1 phrases of length 1 to cover
the first third of B1 , and then a phrase that extends in T until the first edit of
B2 . Since then, each edit forms two phrases: one covers the edit itself (since σ
is not a multiple of 3, each edit is followed by a distinct symbol), and the other
covers the range until the next edit. This adds up to z = 3σ − 2.
A lex-parse starts similarly, since the LZ77 phrases indeed point to lexicographically smaller ones. However, it needs 2σ further phrases to cover Bσ =
2 3 (σ + 1) 5 6 (σ + 1) . . . with phrases of alternating length 2 and 1: each such
pair of suffixes Bσ [3i + 1..] and Bσ [3i + 3..], for i = 0, . . . , σ − 1, do appear in
previous substrings Bj , but all these are lexicographically larger (because σ is
not a multiple of 3, and thus symbols 1 are never replaced by σ + 1). Therefore, only length-2 strings of symbols not including σ + 1 can point to, say, B1
(this reasoning has been verified computationally as well). This makes a total of
v = 5σ − 2 phrases.
t
u
5.1

Experimental Comparison with LZ77

As a test on the practical relevance of the lex-parse, we measured v, z, and r
on various synthetic, pseudo-real, and real repetitive collections obtained from
PizzaChili (http://pizzachili.dcc.uchile.cl) and on four repetitive collections (boost, bwa, samtools, sdsl) obtained by concatenating the first versions
of four github repositories (https://github.com) until obtaining a length of
5 · 108 characters for each collection.
Table 1 shows the results. Our new lex-parse performs better than LZ77 on
the synthetic texts, especially on the Fibonacci strings (fib41), the family for
which we know that v = o(z) (recall Theorem 7 and Lemma 8). On the others
(Run-Rich String and Thue-Morse sequences), z is about 30% larger than v.
Pseudo-real texts are formed by taking a real text and replicating it many
times; then a few random edits are applied on the copies. The fraction of edits is
indicated after the file name, e.g., sources.001 indicates a probability of 0.001
of applying an edit at each position. In the names with suffix .1, the edits are
applied on the base version to form the copy, whereas in those with suffix .2, the
edits are cumulatively applied on the previous copy. It is interesting to note that,
in this family, v and z are very close under the model of edits applied on the
base copy, but z is generally significantly smaller when the edits are cumulative.
The ratios actually approach the 53 = 0.6 we obtained in Lemma 13 using a
particular text that, incidentally, follows the model of cumulative edits.
On real texts, both measures are very close. Still, it can be seen that in
collections like einstein.de and einstein.en, which feature cumulative edits
(those collections are formed by versions of the Wikipedia page on Einstein in
German and English, respectively), z is about 8% smaller than v. On the other
hand, v is about 3%–4% smaller than z on biological datasets such as cere,
escherichia coli and para, where the model is closer to random edits applied
to a base text. The lex-parse is also about 1% smaller than the LZ77 parse on
github versioned collections, except bwa.

file
fib41
rs.13
tm29
dblp.xml.00001.1
dblp.xml.00001.2
dblp.xml.0001.1
dblp.xml.0001.2
sources.001.2
dna.001.1
proteins.001.1
english.001.2
boost
einstein.de
einstein.en
bwa
sdsl
samtools
world leaders
influenza
kernel
cere
coreutils
escherichia coli
para

n
r
z
v
z/v
267,914,296
4
41
4 > 10
216,747,218
77
52
40 1.300
268,435,456
82
56
43 1.302
104,857,600
172,489
59,573
59,821 0.996
104,857,600
175,617
59,556
61,580 0.967
104,857,600
240,535
78,167
83,963 0.931
104,857,600
270,205
78,158
100,605 0.777
104,857,600 1,213,428
294,994
466,643 0.632
104,857,600 1,716,808
308,355
307,329 1.003
104,857,600 1,278,201
355,268
364,093 0.976
104,857,600 1,449,519
335,815
489,034 0.687
500,000,000
61,814
22,680
22,418 1.012
92,758,441
101,370
34,572
37,721 0.917
467,626,544
290,239
89,467
97,442 0.918
438,698,066
311,427
106,655
107,117 0.996
500,000,000
345,325
113,591
112,832 1.007
500,000,000
458,965
150,988
150,322 1.004
46,968,181
573,487
175,740
179,696 0.978
154,808,555 3,022,822
769,286
768,623 1.001
257,961,616 2,791,368
793,915
794,058 1.000
461,286,644 11,574,641 1,700,630 1,649,448 1.031
205,281,778 4,684,460 1,446,468 1,439,918 1.005
112,689,515 15,044,487 2,078,512 2,014,012 1.032
429,265,758 15,636,740 2,332,657 2,238,362 1.042

Table 1. Various repetitiveness measures obtained from synthetic, pseudo-real, and
real texts (each category forms a block in the table).

To conclude, the comparison between r and v shows that the sub-optimal
lexicographic parse induced by the Burrows-Wheeler transform is often much
larger (more than 7 times on the biological datasets) than the optimal lex-parse.
Interestingly, on Fibonacci strings the optimal parse is already found by the
Burrows-Wheeler transform.

6

Conclusions

We have essentially closed the question of which is the approximation ratio of
the (unidirectional, left-to-right) Lempel-Ziv parse with respect to the optimal
bidirectional parse, therefore contributing to the understanding of the quality of
this popular heuristic that can be computed in linear time, whereas computing
the optimal bidirectional parse is NP-complete. Our bounds, which are shown
to be tight, show that the gap is in fact wider than what was previously known.
We also introduced a new heuristic, the lex-parse, that is the optimal left-toright parse in another domain: the lexicographical order of the involved suffixes.

b log 2 (n/b)
log

z log(n/z)

og n

r

log n

n

g

gl
log n / lo

g rl

log n / lo
gl

og n

z no

log

n

b log(n/b)
g
log

g rl

v

z

z no

z

r
log n

r

n

b

v
b

Fig. 3. Known and new asymptotic bounds between repetitiveness measures. The
bounds on the left hold for every string family: an edge means that the lower measure is of the order of the upper. The thicker lines were proved in this paper. The
dashed lines on the right are lower bounds that hold for some string family. The solid
lines are inherited from the left, and since they always hold, they permit propagating
the lower bounds. Note that r appears twice on the right.

This new parse is shown to be computable in linear time and to hold many
of the good bounds of the Lempel-Ziv parse with respect to other measures,
and even some better ones. We exhibit a family of strings where the lex-parse
is asymptotically smaller than the LZ77 parse, and another where the latter is
smaller than the lex-parse, though only by a constant factor. Experimentally, the
lex-parse is shown to behave very similarly to the LZ77 parse, being somewhat
larger on versioned document collections with cumulative edits.
Figure 3 (left) illustrates the known asymptotic bounds that relate the repetitiveness measures we have studied: b, z, zno , g, grl , r, and v. Figure 3 (right)
shows lower bounds that hold for specific string families. These include the
lower bounds mentioned in Section 2 and those proved throughout the paper.
From the upper bounds that hold for every string family, we can also deduce
that, for example, there are string families where r = Ω({z, v, b} log n) (since
r = Ω({zno , v} log n)); {g, grl , zno } = Ω({r, v} log n) (since z = Ω(r log n)) and
z = Ω({b, v} log n) (since r = Ω(v)).
There are various interesting avenues of future work. For example, it is unknown if there are string families where z = o(v), or at least b = o(v). We have
also no upper bounds on r in terms of other measures, e.g., can r be more than
O(log n) times larger than z or g? It might also be that our Theorem 1 can be
proved without using run-length rules, then yielding g = O(b log(n/b)).
Another interesting line of work is that of greedy bidirectional parses that
can be built efficiently and compete with z, which has been the gold-standard
approximation for decades. Are there other convenient parses, apart from our

lex-parse? In particular, are there parses that can compete with z while offering
better random access time to T ? Right now, only parses of size O(g) (and surely
O(grl )) allow for efficient (O(log n) time) access to T ; all the other measures
need a superlinear blowup in the space to support efficient access [2, 5, 3, 42, 14,
15, 17]. This is also crucial to build small and efficient compressed indexes on T
[37, Sec. 13.2].
One could also try to generalize our results to any greedy parse that can be
computed from a suitable potential function that assigns a numerical value to
each text position, so that the potential of the source is smaller than that of
the corresponding phrase; note that examples of such a potential function are
the identity function for LZ77 and ISA for our lex-parse. Is it true that all such
greedy parses approximate b to within a logarithmic factor? Given a text T ,
can we find a potential function optimizing the size of the corresponding greedy
parse for T ?

References
1. D. Belazzougui, F. Cunial, T. Gagie, N. Prezza, and M. Raffinot. Composite
repetition-aware data structures. In Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 26–39, 2015.
2. D. Belazzougui, T. Gagie, P. Gawrychowski, J. Kärkkäinen, A. Ordóñez, S. J.
Puglisi, and Y. Tabei. Queries on LZ-bounded encodings. In Proc. 25th Data
Compression Conference (DCC), pages 83–92, 2015.
3. D. Belazzougui, S. J. Puglisi, and Y. Tabei. Access, rank, select in grammarcompressed strings. In Proc. 23rd Annual European Symposium on Algorithms
(ESA), LNCS 9294, pages 142–154, 2015.
4. P. Bille, T. Gagie, I. Li Gørtz, and N. Prezza. A separation between run-length
SLPs and LZ77. CoRR, abs/1711.07270, 2017.
5. P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. S. Rao, and O. Weimann.
Random access to grammar-compressed strings and trees. SIAM Journal on Computing, 44(3):513–539, 2015.
6. M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm.
Technical Report 124, Digital Equipment Corporation, 1994.
7. M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and
A. Shelat. The smallest grammar problem. IEEE Transactions on Information
Theory, 51(7):2554–2576, 2005.
8. T. Cover and J. Thomas. Elements of Information Theory. Wiley, 2nd edition,
2006.
9. M. Crochemore, C. S. Iliopoulos, M. Kubica, W. Rytter, and T. Waleń. Efficient
algorithms for three variants of the LPF table. Journal of Discrete Algorithms,
11:51–61, 2012.
10. P. Dinklage, J. Fischer, D. Köppl, M. Löbel, and K. Sadakane. Compression with
the tudocomp framework. In Proc. 16th International Symposium on Experimental
Algorithms, (SEA 2017), 2017.
11. G. Fici. Factorizations of the Fibonacci infinite word. Journal of Integer Sequences,
18(9):article 3, 2015.
12. M. H.-Y. Fritz, R. Leinonen, G. Cochrane, and E. Birney. Efficient storage of high
throughput DNA sequencing data using reference-based compression. Genome
Research, pages 734–740, 2011.

13. T. Gagie. Large alphabets and incompressibility. Information Processing Letters,
99(6):246–251, 2006.
14. T. Gagie, P. Gawrychowski, J. Kärkkäinen, Y. Nekrich, and S. J. Puglisi. A faster
grammar-based self-index. In Proc. 6th International Conference on Language and
Automata Theory and Applications (LATA), LNCS 7183, pages 240–251, 2012.
15. T. Gagie, P Gawrychowski, J. Kärkkäinen, Y. Nekrich, and S. J. Puglisi. LZ77based self-indexing with faster pattern matching. In Proc. 11th Latin American
Symposium on Theoretical Informatics (LATIN), pages 731–742, 2014.
16. T. Gagie, G. Navarro, and N. Prezza. On the approximation ratio of LempelZiv parsing. In Proc. 13th Latin American Symposium on Theoretical Informatics
(LATIN), LNCS, 2018. To appear.
17. T. Gagie, G. Navarro, and N. Prezza. Optimal-time text indexing in bwt-runs
bounded space. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1459–1477, 2018.
18. J. K. Gallant. String Compression Algorithms. PhD thesis, Princeton University,
1982.
19. P. Gawrychowski. Pattern matching in Lempel-Ziv compressed strings: fast, simple,
and deterministic. CoRR, abs/1104.4203, 2011.
20. D. Hucke, M. Lohrey, and C. P. Reh. The smallest grammar problem revisited.
In Proc. 23rd International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 9954, pages 35–49, 2016.
21. T. I. Longest common extensions with recompression. In Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 78, pages 18:1–18:15,
2017.
22. A. Jez. Approximation of grammar-based compression via recompression. Theoretical Computer Science, 592:115–134, 2015.
23. A. Jez. A really simple approximation of smallest grammar. Theoretical Computer
Science, 616:141–150, 2016.
24. J. Kärkkäinen, P. Sanders, and S. Burkhardt. Linear work suffix array construction.
Journal of the ACM, 53(6):918–936, 2006.
25. T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Linear-time longestcommon-prefix computation in suffix arrays and its applications. In Proc. 12th
Annual Symposium on Combinatorial Pattern Matching (CPM), LNCS 2089, pages
181–192, 2001.
26. J. C. Kieffer and E.-H. Yang. Grammar-based codes: A new class of universal
lossless source codes. IEEE Transactions on Information Theory, 46(3):737–754,
2000.
27. D. K. Kim, J. S. Sim, H. Park, and K. Park. Constructing suffix arrays in linear
time. Journal of Discrete Algorithms, 3(2-4):126–142, 2005.
28. P. Ko and S. Aluru. Space efficient linear time construction of suffix arrays. Journal
of Discrete Algorithms, 3(2-4):143–156, 2005.
29. A. N. Kolmogorov. Three approaches to the quantitative definition of information.
Problems on Information Transmission, 1(1):1–7, 1965.
30. R. Kosaraju and G. Manzini. Compression of low entropy strings with Lempel-Ziv
algorithms. SIAM Journal on Computing, 29(3):893–911, 2000.
31. S. Kreft and G. Navarro. On compressing and indexing repetitive sequences. Theoretical Computer Science, 483:115–133, 2013.
32. A. Lempel and J. Ziv. On the complexity of finite sequences. IEEE Transactions
on Information Theory, 22(1):75–81, 1976.
33. V. Mäkinen and G. Navarro. Succinct suffix arrays based on run-length encoding.
Nordic Journal of Computing, 12(1):40–66, 2005.

34. U. Manber and G. Myers. Suffix arrays: a new method for on-line string searches.
SIAM Journal on Computing, 22(5):935–948, 1993.
35. S. Mantaci, A. Restivo, and M. Sciortino. Burrows-Wheeler transform and Sturmian words. Information Processing Letters, 86(5):241–246, 2003.
36. G. Manzini. An analysis of the Burrows-Wheeler transform. Journal of the ACM,
48(3):407–430, 2001.
37. G. Navarro. Compact Data Structures – A practical approach. Cambridge University Press, 2016.
38. T. Nishimoto, T. I, S. Inenaga, H. Bannai, and M. Takeda. Fully dynamic data
structure for LCE queries in compressed space. In Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 72:1–
72:15, 2016.
39. N. Prezza. Compressed Computation for Text Indexing. PhD thesis, University of
Udine, 2016.
40. M. Rodeh, V. R. Pratt, and S. Even. Linear algorithm for data compression via
string matching. Journal of the ACM, 28(1):16–24, 1981.
41. W. Rytter. Application of Lempel-Ziv factorization to the approximation of
grammar-based compression. Theoretical Computer Science, 302(1-3):211–222,
2003.
42. K. Sadakane and R. Grossi. Squeezing succinct data structures into entropy
bounds. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1230–1239, 2006.
43. H. Sakamoto. A fully linear-time approximation algorithm for grammar-based
compression. Journal of Discrete Algorithms, 3(24):416–430, 2005.
44. C. E. Shannon. A mathematical theory of communication. Bell Systems Technical
Journal, 27:398–403, 1948.
45. Z. D. Sthephens, S. Y. Lee, F. Faghri, R. H. Campbell, Z. Chenxiang, M. J. Efron,
R. Iyer, S. Sinha, and G. E. Robinson. Big data: Astronomical or genomical? PLoS
Biology, 17(7):e1002195, 2015.
46. J. A. Storer and T. G. Szymanski. Data compression via textual substitution.
Journal of the ACM, 29(4):928–951, 1982.
47. J. Ziv and A. Lempel. Compression of individual sequences via variable length
coding. IEEE Transactions on Information Theory, 24(5):530–536, 1978.

