On Two LZ78-style Grammars: Compression Bounds and
Compressed-Space Computation
Golnaz Badkobeh∗1 , Travis Gagie2 , Shunsuke Inenaga3 , Tomasz Kociumaka†4 ,
Dmitry Kosolobov5 , and Simon J. Puglisi‡5

arXiv:1705.09538v2 [] 25 Jul 2017

1

Department of Computer Science, University of Warwick, Coventry, England
g.badkobeh@warwick.ac.uk
2
EIT, Diego Portales University and CeBiB, Santiago, Chile
travis.gagie@mail.udp.cl
3
Department of Informatics, Kyushu University, Fukuoka, Japan
inenaga@inf.kyushu-u.ac.jp
4
Institute of Informatics, University of Warsaw, Warsaw, Poland
kociumaka@mimuw.edu.pl
5
Department of Computer Science, University of Helsinki, Helsinki, Finland
dkosolobov@mail.ru puglisi@cs.helsinki.fi

Abstract
We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by
Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally
produce a grammar for a string of length n; we show that the size of this grammar can be larger
1
2
than the size of the smallest grammar by a factor Ω(n 3 ) but is always within a factor O(( logn n ) 3 ).
In addition, we show that the standard algorithms using Θ(z) working space to construct the LZD
5
and LZMW parsings, where z is the size of the parsing, work in Ω(n 4 ) time in the worst case.
We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses O(z log n) space and
O(n + z log2 n) time with high probability.
Keywords: LZMW, LZD, LZ78, compression, smallest grammar

1

Introduction

The LZ78 parsing [19] is a classic dictionary compression technique, discovered by Lempel and Ziv in
1978, that gained wide use during the 1990s in, for example, the Unix compress tool and the GIF image
format. Not written about until much later was that LZ78 actually produces a representation of the
input string as a context-free grammar. In recent years, grammar compressors have garnered immense
interest, particularly in the context of compressed text indexing: it is now possible to eﬃciently execute
many operations directly on grammar-compressed strings, without resorting to full decompression (e.g.,
see [3, 4, 6, 7, 10, 16]).
A wide variety of grammar compressors are now known, many of them analyzed by Charikar et al. [5]
in their study of the smallest grammar problem, which is to compute the smallest context-free grammar
that generates the input string (and only this string). Charikar et al. show that this problem is NP-hard,
and further provide lower bounds on approximation ratios for many grammar compressors. LZ78 is
shown to approximate the smallest grammar particularly poorly, and can be larger than the smallest
2
2
grammar by a factor Ω(n 3 / log n) (in [9] this bound was improved to Ω(( logn n ) 3 )), where n is the input
length.
Our focus in this paper is on the LZD [8] and LZMW [14] grammar compression algorithms, two
variants of LZ78 that usually outperform LZ78 in practice. Despite their accepted empirical advantage
over LZ78, no formal analysis of the compression performance of LZD and LZMW in terms of the size
∗ Supported

by the Leverhulme Trust on the Leverhulme Early Career Scheme.
by Polish budget funds for science in 2013–2017 under the ‘Diamond Grant’ program.
‡ Supported by the Academy of Finland via grant 294143.
† Supported

1

of the smallest grammar exists. This paper addresses that need. Moreover, we show that the standard
algorithms for computing LZD and LZMW have undesirable worst case performance, and provide an
alternative algorithm that runs in log-linear randomized time. In particular the contributions of this
article are as follows:
1. We show that the size of the grammar produced by LZD and LZMW can be larger than the size of
1
2
the smallest grammar by a factor Ω(n 3 ) but is always within a factor O(( logn n ) 3 ). To our knowledge
these are the ﬁrst non-trivial bounds on compression performance known for these algorithms.
2. Space usage during compression is often a concern. For both LZD and LZMW, parsing algorithms
are known that use O(z) space, where z is the size of the ﬁnal parsing. We describe strings for
5
which these algorithms require Ω(n 4 ) time. (The only previous analysis is an O(n2 / log n) upper
bound [8].)
3. We describe a Monte-Carlo parsing algorithm for LZD/LZMW that uses a z-fast trie [2] and an
AVL-grammar [15] to achieve O(z log n) space and O(n + z log2 n) time for inputs over the integer
alphabet {0, 1, . . . , nO(1) }. This algorithm works in the streaming model and computes the parsing
with high probability. Using the Monte-Carlo solution, we obtain a Las Vegas algorithm that, with
high probability, works in the same space and time.
In what follows we provide formal deﬁnitions and examples of LZD and LZMW parsings. Section 2
then establishes bounds for the approximation ratios for the sizes of the LZD/LZMW grammars. In
Section 3 we consider the time eﬃciency of current space-eﬃcient parsing schemes for LZD/LZMW.
Section 4 provides an algorithm with signiﬁcantly better (albeit randomized) performance. Conclusions
and reﬂections are oﬀered in Section 5.

1.1

Preliminaries.

We consider strings drawn from an alphabet Σ of size σ = |Σ|. The empty string is denoted by ǫ. The
ith letter of a string s is denoted by s[i] for i such that 1 ≤ i ≤ |s|, and the substring of s that begins at
position i and ends at position j is denoted by s[i..j] for 1 ≤ i ≤ j ≤ |s|. Let s[i..j] = ǫ if j < i. For any
i, j, the set {k ∈ Z : i ≤ k ≤ j} (possibly empty) is denoted by [i..j].
For convenience, we assume that the last letter of the input string s is $, where $ is a special delimiter
letter that does not occur elsewhere in the string.
Definition 1.1. The LZD (LZ–Double) parsing [8] of a string s of length n is the parsing s = p1 p2 · · · pz
such that, for i ∈ [1..z], pi = pi1 pi2 where pi1 is the longest preﬁx of s[k..n] and pi2 is the longest
preﬁx
S of s[k + |pi1 |..n] with pi1 , pi2 ∈ {p1 , . . . , pi−1 } ∪ Σ where k = |p1 · · · pi−1 | + 1. We refer to the set
Σ ∪ i∈[1..z] {pi } as the dictionary of LZD.
Definition 1.2. The LZMW (LZ–Miller–Wegman) parsing [14] of a string s of length n is the parsing
s = p1 p2 · · · pz such that, for i ∈ [1..z], pi is the longest S
preﬁx of s[k..n] with pi ∈ {pj pj+1 : 1 ≤ j ≤
i − 2} ∪ Σ where k = |p1 · · · pi−1 | + 1. We refer to the set i∈[2..z] {pi−1 pi } as the dictionary of LZMW.
Example 1.3. The LZD parsing of the string s = abbaababaaba$ is p1 = ab, p2 = ba, p3 = abab, p4 = aab,
and p5 = a$. This can be represented by (a, b), (b, a), (1, 1), (a, 1), (a, $). The LZMW parsing of s is the
following: p1 = a, p2 = b, p3 = b, p4 = a, p5 = ab, p6 = ab, p7 = aab, p8 = a, and p9 = $. This can be
represented by (a, b, b, a, 1, 1, 4, a, $).
Notice that the LZD/LZMW parsing of string s can be seen as a grammar that only generates s,
with production rules of form pi → pj pk (j < i, k < i) or pi → a (∈ Σ) for each phrase pi , and the start
rule S → p1 p2 · · · pz . The size of a grammar is the total number of symbols in the right-hand side of the
production rules. Thus, the size of the LZD (resp., LZMW) grammar is only by a constant factor larger
than the number of phrases in the LZD (resp., LZMW) parsing.

2

Approximating the Smallest Grammar

The following theorem shows that, although LZD and LZMW have good compression performance in
practice on high-entropy strings, their performance on low-entropy strings can be very poor.
2

Theorem 2.1. For arbitrarily large n, there are strings s of length n for which the size of the grammars
produced by the LZD and LZMW parsings is larger than the size of the smallest grammar generating s
1
by a factor Ω(n 3 ).
Proof. Our proof is inspired by [5, Section VI, C]. Let k ≥ 4 be an integer that is a power of 2. We will
1
construct a string s of length n = Θ(k 3 ) that can be encoded by a grammar of size O(k) = O(n 3 ), but for
2
2
which the LZMW parsing produces a grammar of size Ω(k ) = Ω(n 3 ). The input alphabet is {a, b, c, d};
the letters c and d serve as separators. Denote δi = ai bbak−i and γi = bai a ai b c ba ba2 ba3 · · · bai . The
string s is as follows:
x = δk δk−1 δk δk−2 δk δk−3 · · · δk δk/2+1 δk ak−1 ,
i
i
i
k
k
k
k
s = γ0 γ1 · · · γk−1 δ0 dδ1 d · · · δk d caa caa2 a2 · · · ca2 −1 a2 a2 · · · ca 2 −1 a 2 a 2 dc x 2 .
We have |s| = Θ(k 3 ). Consider the preﬁx γ0 γ1 · · · γk−1 δ0 dδ1 d · · · dδk d, which will ensure the strings
δi are in the LZMW dictionary.
We will show by induction on i that each substring γi of the preﬁx γ0 γ1 · · · γk−1 is composed of the
phrases bai , a, ai b, cbaba2 · · · bai in the parsing of the string s. It is trivial for i = 0. Suppose that
i > 0 and the assertion holds for all γi′ and i′ < i. It follows from the inductive hypothesis that bai is
the longest preﬁx of γi that is equal to a concatenation of two adjacent phrases introduced before the
starting position of γi . Hence, by the deﬁnition of LZMW, the string γi starts with the phrase bai . In
the same way we deduce that the phrase bai is followed by the phrases a, ai b, and cbaba2 · · · bai .
By a similar inductive argument, one can show that each substring δi d of the substring δ0 dδ1 d · · · δk dc
is composed of the phrases ai b, bak−i , d. Since the phrases ai b and bak−i are adjacent, the LZMW
dictionary now contains the strings δi = ai bbak−i for all i = 0, 1, . . . , k.
i
i
i
k
k
k
Similarly, the substring caacaa2 a2 · · · ca2 −1 a2 a2 · · · ca 2 −1 a 2 a 2 dc is parsed as c, a, a, ca, a2 , a2 , . . . ,
k
k
k
2i −1 2i
2i
−1
ca
, a , a , . . . , ca 2 , a 2 , a 2 , dc. In what follows we need only the string ak introduced to the
k
dictionary by the pair of phrases a 2 .
k
Finally, consider the substring x 2 . Observe that the ﬁrst occurrence of x is parsed in (almost) the
way it is written, i.e., it is parsed as δk , δk−1 , δk , δk−2 , . . . , δk , δk/2+1 , δk . But the last phrase is ak instead
of ak−1 . In other words, the parsing of the second occurrence of x starts from the second position of x
and, therefore, the ﬁrst phrases of this parsing are as follows:
δk−1 , δk−2 , δk−1 , δk−3 , . . . , δk−1 , δk/2 , δk−1 .
Again, the last phrase is ak and, hence, the parsing of the third occurrence of x starts with the third
position of x, and so on.
The LZMW parsing of s, therefore, consists of Ω(k 2 ) phrases and the size of the LZMW grammar is
Ω(k 2 ). But there is a grammar of size O(k) producing s:
S → Γ0 Γ1 · · · Γk−1 ∆0 d∆1 d · · · ∆k dcA2 cA5 cA11 · · · cAk/2+k−1 dcX k/2 ,
A0 → ǫ, B0 → c, Ai → Ai−1 a, Bi → Bi−1 bAi for i ∈ [1..2k],
Γi → bA2i+1 bBi , ∆i → Ai bbAk−i for i ∈ [0..k],
X → ∆k ∆k−1 ∆k ∆k−2 · · · ∆k ∆k/2+1 ∆k Ak−1 .
Using similar ideas we can describe a troublesome string for the LZD scheme:
k

s = (a2 c2 a3 c3 · · · ak ck )(bb abb a2bb a3 · · · bbak−1 bb)(δ0 d2 δ1 d3 · · · δk dk+2 )x 2 .
As above, the size of the grammar corresponding to the LZD parsing of s is Ω(k 2 ) whereas the size
of the smallest grammar is O(k); hence, the result follows.
S → A2 C2 A3 C3 · · · Ak Ck bbA1 bbA2 · · · bbAk−1 bb∆0 D2 ∆1 D3 · · · ∆k Dk+2 X k/2 ,
A0 → ǫ, C0 → ǫ, D0 → ǫ, Ai → Ai−1 a, Ci → Ci−1 c, Di → Di−1 d for i ∈ [1..k+2],
∆i → Ai bbAk−i for i ∈ [0..k], X → ∆k ∆k−1 ∆k ∆k−2 · · · ∆k ∆k/2+1 ∆k Ak−1 .
The analysis is similar to the above but simpler, so, we omit it. To additionally verify the correctness of
both constructions, we conducted experiments on small k and, indeed, observed the described behavior;
the code can be found in [1].
3

We can also show that the upper bound for the approximation ratio of the LZ78 parsing given in [5]
also applies to the LZD and LZMW parsings. For this, we will use the following known results.
Lemma 2.2 ([5]). If there is a grammar of size m generating a given string, then this string contains
at most mk distinct substrings of length k.
Lemma 2.3 ([8]). All phrases in the LZD parsing of a given string are distinct.
Lemma 2.4. Let p1 p2 · · · pz be the LZMW parsing of a given string. Then, for any i ∈ [2..z] and
j ∈ [i+2..z], we have pi−1 pi 6= pj−1 pj .
Proof. If pi−1 pi = pj−1 pj for i < j − 1, then, by the deﬁnition of LZMW, the phrase pj−1 either is equal
to pi−1 pi or contains pi−1 pi as a preﬁx, which is a contradiction.
Now we are ready to show an upper bound on the approximation ratio of the LZD and LZMW
parsings.
Theorem 2.5. For all strings s of length n, the size of the grammar produced by the LZD/LZMW
parsing is larger than the size of the smallest grammar generating s by at most a factor O((n/ log n)2/3 ).
Proof. The theorem can be shown by an analogous way as for the upper bound of the LZ78 parsing
against the smallest grammar [5] (which is especially straightforward for LZD due to Lemma 2.3), but
we provide a full proof for completeness.
Let us consider LZMW. Suppose that s is a string of length n and m∗ is the size of the smallest
grammar generating s. Let p1 , p2 , . . . , pz be the LZMW parsing of s. It suﬃces to evaluate the number
z of phrases since the total size of the grammar produced by LZMW is only by a constant factor larger
than z.
Consider the multiset S = {p1 p2 , p2 p3 , . . . , pz−1 pz } (recall that a multiset can contain an element
more than one time). Let pi1 pi1 +1 , pi2 pi2 +1 , . . . , piz−1 piz−1 +1 be a sequence of all strings from S sorted
in increasing order of their lengths (again, some strings may occur more than once in the sequence). We
partition the sequence by grouping the ﬁrst 2 · m∗ strings, then the next 2 · 2m∗ strings, the next 2 · 3m∗
strings, and so forth. Let r be the minimal integer satisfying 2(1m∗ + 2m∗ + · · · + rm∗ + (r + 1)m∗ ) > z.
This implies that z = O(r2 m∗ ).
By Lemma 2.4, any string has at most two occurrences in the multiset S. Also, it follows from
Lemma 2.2 that s contains at most km∗ distinct substrings of length k. Thus, for any k ≥ 1, there are
at most 2km∗ strings from S that generate substrings of length k. This implies that each string in the
kth group generates a substring of length at least k. Hence, we have that
2n ≥ |pi1 pi1 +1 | + |pi2 pi2 +1 | + · · · + |piz−1 piz−1 +1 | ≥ 2(12 m∗ + 22 m∗ + · · · + r2 m∗ ),
which implies that r = O((n/m∗ )1/3 ). By plugging this into z = O(r2 m∗ ), we obtain z = O((n/m∗ )2/3 m∗ )
and thus the approximation ratio of the grammar produced by LZMW is O((n/m∗ )2/3 ). Since m∗ =
Ω(log n), we ﬁnally get the desired bound O((n/ log n)2/3 ).
Let us sketch the analysis of LZD, which is very similar. In this case, we consider the set S ′ of all
phrases p1 , p2 , . . . , pz (not pairs as in LZMW) of the LZD parsing. Let pi1 , . . . , piz be the sequence of all
strings from S ′ sorted by the increasing order of lengths. We partition the sequence into groups of size
1m∗ , 2m∗ , 3m∗ , . . . (without the factor 2 as in LZMW). It follows from Lemma 2.3 that any string occurs
in S ′ at most once. Therefore, similar to the case of LZMW, we obtain n = |pi1 | + |pi2 | + · · · + |piz | ≥
12 m∗ + 22 m∗ + · · · + r2 m∗ , which implies the result in the same way as above.

3

Small-Space Computation

In this section we analyze the time required to compute the LZD and LZMW parsings using the O(z)space algorithms described by Goto et al. [8] and Miller and Wegman [14], where z is the number of
phrases. We focus on LZD throughout, but a very similar algorithm and analysis applies for LZMW.
Goto et al. upperbound the runtime at O(z(m + min(z, m) log σ)), where m is the length of the longest
LZD (or LZMW) phrase and σ is the size of the input alphabet. Because m = O(n) and z = O(n),

4

the runtime is upper bounded by O(n2 ). Below we provide a lower bound of Ω(n5/4 ) on the worst-case
runtime, but before doing so we provide the reader with a description of Goto et al.’s algorithm [8].1
Naı̈ve parsing algorithms. In the compacted trie for a set of strings, each edge label ℓ is represented
as a pair of positions delimiting an occurrence of ℓ in the set. In this way we can store the trie for
s1 , . . . , sk in O(k) space. During parsing Goto et al. [8] maintain the dictionary of LZD phrases in a
compacted trie. The trie is of size O(z), but read-only random access to the input string is also required
in order to determine the actual values of the strings on the edge labels.
Initially the trie is empty, consisting of only the root. At a generic step during parsing, when we go
to compute the phrase pi = pi1 pi2 starting at position j = |p1 p2 . . . pi−1 | + 1, the trie contains nodes
representing the phrases p1 , p2 , . . . , pi−1 and all the distinct symbols occurring in s[1..j − 1], and all these
nodes (corresponding to phrases and symbols) are marked. Note that there may also be some nodes in
the trie that do not correspond to any phrase, i.e., branching nodes. Let s[j..k] be the longest preﬁx of
s[j..n] that can be found by traversing the trie from the root. If s[j..k] cannot be matched even for k = j,
then s[j] is the leftmost occurrence of symbol c = s[j] in s, and we add a child node of the root labelled
with c, mark the node, and set it as the ﬁrst element of the new phrase, i.e., pi1 = c. Otherwise, the ﬁrst
element of pi , pi1 , is the string written on the path connecting the root and the lowest marked node on
the path that spells s[j..k]. The second element, pi2 , of the phrase is computed in a similar manner, by
searching for s[j + |pi1 | + 1..n] in the trie.
After computing pi we modify the trie by a standard procedure so that there is a marked node
representing pi : ﬁrst, we traverse the trie from the root ﬁnding the longest preﬁx of pi present in the
trie, then, possibly, create one or two new nodes, and, ﬁnally, mark the node (which, probably, did not
exist before) corresponding to pi (the details can be found in any stringology textbook).
The time taken to compute a new phrase and update the trie afterwards is bounded by O(m +
min(z, m) log σ), where m = O(n) is the length of the longest phrase (and therefore an upper bound on
the length of the longest path in the trie), min(z, m) is an upper bound on the number of branching
nodes, and log σ is the time taken to ﬁnd the appropriate outgoing edge at each branching node during
downward traversal. Over all z phrases the runtime is thus O(z(m + min(z, m) log σ)).
The LZMW construction algorithm of Miller and Wegman [14] is analogous but, unlike the LZD
algorithm, when we go to compute the phrase pi , the trie contains the strings p1 p2 , p2 p3 , . . . , pi−2 pi−1
and the nodes corresponding to these strings are marked. One can easily show that the running time of
this algorithm is O(z(m + min(z, m) log σ)), where z and m are deﬁned analogously as for LZD.
We call both these algorithms naı̈ve.
Worst-case time of the naı̈ve algorithms. Now let us investigate the worst-case time complexity
of the naı̈ve LZD and LZMW construction algorithms.
5

Theorem 3.1. The naı̈ve LZD and LZMW construction algorithms take time Ω(n 4 ) in the worst case.
Proof. Let k ≥ 8 be an integer that is a power of two. We will describe a string s of length n = Θ(k 4 )
5
for which the basic LZD construction algorithm (see the above discussion) spends Θ(n 4 ) time to process.
The string s is composed of pairwise distinct letters ai,j , for i, j ∈ [1..k], and “separator” letters, all
of which are denoted ⋄ and supposed to be distinct. We will ﬁrst construct a preﬁx s′ of s that forces
the algorithm to ﬁll the dictionary with a set of strings that are used as building blocks in further
constructions. To this end, denote (with parentheses used only for convenience):
wi = ai,1 ai,2 · · · ai,k for i = 1, 2, . . . , k and w = w1 w2 · · · wk ,
spre,i = wi [1..2]wi [1..3] · · · wi [1..k] for i = 1, 2, . . . , k,
ssuf,i = wi [k−1..k]wi [k−2..k] · · · wi [2..k] for i = 1, 2, . . . , k,
p = (spre,1 spre,2 · · · spre,k )(ssuf,1 ssuf,2 · · · ssuf,k ),
q = (wk−2 wk−1 )(wk−3 wk−2 wk−1 ) · · · (w1 w2 · · ·wk−1 )(w),
1
2
s′ = pq · w2 w2 · · · wk (wk [2..k]wk )(wk [3..k]wk ) · · · (wk [k..k]wk ).
Analyzing the preﬁx p of s′ , it is clear that the LZD construction algorithm adds to the dictionary exactly
all preﬁxes and suﬃxes of the strings wi for i = 1, 2, . . . , k; parsing the string q, the algorithm adds the
1 We

concern ourselves here with LZD parsing, but it should be easy for the reader to see that the algorithms are trivially
adapted to instead compute LZMW.

5

strings wk−2 wk−1 , wk−3 wk−2 wk−1 , . . . , w1 w2 · · · wk−1 , and w1 w2 · · · wk = w; then, processing the string
1
2
1
2
w2 w2 · · · wk , the algorithm adds w2 , w2 , . . . , wk (we are interested only in wk ); ﬁnally, the strings
k
k
k
wk [2..k]w , wk [3..k]w , . . . , wk [k..k]w are added. So, the algorithm adds to the dictionary exactly the
following strings:
• all preﬁxes and suﬃxes of wi (including wi itself) for i = 1, 2, . . . , k;
• wk−2 wk−1 , wk−3 wk−2 wk−1 , . . . , w1 w2 · · · wk−1 , and w;
2

• wk along with wk/2 , . . . , w2 , w2 (we use only wk in what follows);
• wk [2..k]wk , wk [3..k]wk , . . . , wk [k..k]wk .
It is easy to verify that |w| = k 2 , |wk | = k 3 , and |s′ | = Θ(k 4 ). (The string wk [2..k]wk wk [3..k]wk · · · wk [k..k]wk contributes the most to the length.)
We ﬁrst provide an overview of our construction. The main load on the running time of the algorithm
is concentrated in the following strings zi :
zi = wi [2..k]wi+1 · · · wk wk−2 w1 · · · wi for i = 1, 2, . . . , k − 2.
Put s = s′ x1 z1 ⋄⋄x2 z2 ⋄⋄ · · · xk−2 zk−2 ⋄⋄, where x1 , . . . , xk are auxiliary strings deﬁned below. Before
processing of zi , the algorithm processes xi and adds the strings wi [j..k]wi+1 · · · wk−1 wk [1..j−1] and
wk [j..k]w1 · · · wi−1 wi [1..j] for j ∈ [2..k] to the dictionary (see below). So, analyzing zi , the algorithm consecutively “jumps”, for j = 2, 3, . . . , k, from the string wi [j..k]wi+1 · · · wk−1 wk [1..j−1] to
wk [j..k]w1 · · · wi−1 wi [1..j] and so on. The crucial point is that, while analyzing wk [j..k]w1 · · · wi−1 wi [1..j],
the algorithm does not know in advance that the string wk [j..k]wk from the dictionary does not occur at this position and, since the length of the longest common preﬁx of the strings wk [j..k]wk and
wk [j..k]wk−j w1 · · · wi ⋄⋄ is Θ(k − j + 1 + |wk−j |), spends Θ(|wk−j |) = Θ((k − j)k 2 ) time verifying this.
P
Therefore, the analysis of the string s takes Θ((k − 2) kj=2 (k − j)k 2 ) = Θ(k 5 ) time overall. Since
|zi | = O(k 3 ) and, as it is shown below, |xi | = O(k 3 ), we have n = |s| = Θ(k 4 ) and the processing time is
5
Θ(n 4 ) as required. We now describe this in more detail.
We prove by induction that the following invariant is maintained: when the algorithm starts the
processing of the suﬃx xi zi ⋄⋄ · · · xk−2 zk−2 ⋄⋄ of the string s (xi are deﬁned below), the dictionary contains
the following set of strings:
• “building blocks” constructed during the processing of s′ ;
• pairs of separators ⋄⋄ (recall that all separators are distinct);
• for each i′ ∈ [1..i−1] and j ∈ [2..k]:
wi′ [j..k]wi′ +1 · · · wk−1 wk [1..j−1] and wk [j..k]w1 · · · wi′ −1 wi′ [1..j],
wi′ [j..k]wi′ +1 · · · wk−1 and wk [j..k]w1 · · · wi′ −1 ,
wi′ [j..k]wi′ +1 · · · wk w1 · · · wi′ −1 wi′ [1..j].
The strings from the last two lines in the above list are not used and appear as byproducts. (But
it is still important to have them in mind to verify that the algorithm works as expected.) So, assume
that, by inductive hypothesis, the invariant holds for all i′ ∈ [1..i−1] (it is trivial for i = 1).
Deﬁne xi as follows (the parentheses are only for visual ease):
u′i,j = (wk [j..k]w1 · · · wi−1 wi [1..j]),
ui,j = (wk [j..k]w1 · · · wi−2 wi−1 [1..j])(wi−1 [j+1..k])u′i,j ,
vi,j = (wi [j..k]wi+1 · · · wk−1 )(wi [j..k]wi+1 · · · wk−1 wk [1..j−1]),
x1 = (u′1,2 ⋄⋄u′1,3 ⋄⋄ · · · u′1,k−1 ⋄⋄u′1,k ⋄⋄)(v1,2 ⋄⋄v1,3 ⋄⋄ · · · v1,k ⋄⋄),
xi = (ui,2 ⋄⋄ui,3 ⋄⋄ · · · ui,k−1 ⋄⋄u′i,k ⋄⋄)(vi,2 ⋄⋄vi,3 ⋄⋄ · · · vi,k ⋄⋄), for i 6= 1.
Observe that |xi | = O(k 3 ). Using the inductive hypothesis, one can prove that the algorithm
adds the strings wk [j..k]w1 · · · wi−1 (for j 6= k), wk [j..k]w1 · · · wi−1 wi [1..j], wi [j..k]wi+1 · · · wk−1 , and
wi [j..k]wi+1 · · · wk−1 wk [1..j−1] for j ∈ [2..k] to the dictionary after the processing of xi (plus several pairs
6

⋄⋄). It remains to show that the algorithm adds exactly the strings wi [j..k]wi+1 · · · wk w1 · · · wi−1 wi [1..j],
for j ∈ [2..k], to the dictionary when processing zi .
Observe that, for j ∈ [2..k], wi [j..k]wi+1 · · · wk−1 wk [1..j−1] is the longest string from the dictionary
that has preﬁx wi [j..k], and wk [j..k]w1 · · · wi−1 wi [1..j] is the longest string from the dictionary that has
preﬁx wk [j..k] and does not coincide with wk [j..k]wk . Hence, the algorithm consecutively “jumps” over
the substrings w of the string zi adding after each such “jump” the string wi [j..k]wi+1 · · · wk w1 · · · wi−1 wi [1..j]
to the dictionary (for j = 2, 3, . . . , k). No other strings are added.
Each time the algorithm processes a substring wk [j..k]w1 · · · wi−1 wi [1..j], it also veriﬁes in Θ(ki +
|wk−j |) time whether the string wk [j..k]wk occurs at this position. Therefore, by the above analysis,
5
processing takes Θ(|s| 4 ) time.
An analogous troublesome string for the naı̈ve LZMW construction algorithm is as follows (again, all
separators ⋄ are assumed to be distinct letters):
wi = ai,1 ai,2 · · · ai,k and w = w1 w2 · · · wk ,
spre,i = wi [1..2]⋄wi [1..3]⋄ · · · ⋄wi [1..k]⋄,
ssuf,i = wi [k−1..k]⋄wi [k−2..k]⋄ · · · ⋄wi [2..k]⋄,
p = spre,1 spre,2 · · · spre,k ssuf,1 ssuf,2 · · · ssuf,k ,
q = wk−2 wk−1 ⋄wk−3 wk−2 wk−1 ⋄ · · · ⋄w1 w2 · · ·wk−1 ⋄w⋄,
1
2
s′ = pqw2 ⋄w2 ⋄ · · · ⋄wk ⋄wk [2..k]wk ⋄wk [3..k]wk ⋄ · · · ⋄wk [k..k]wk ⋄,
yj = wk [j..k]w1 ⋄wk [j..k]w1 w2 [1..j]⋄,
ti,j = wi−2 [j+1..k]wi−1 [1..j]⋄wi−1 [j+1..k]wi [1..j],
ui,j = (wk [j..k]w1 · · · wi−3 wi−2 [1..j])(wi−2 [j+1..k]wi−1 [1..j]),
vi,j = wi [j..k]wi+1 · · · wk−1 ⋄wi [j..k]wi+1 · · · wk−1 wk [1..j−1],
xi = ti,2 ⋄ti,3 ⋄ · · · ⋄ti,k−1 ⋄ui,2 ⋄ui,3 ⋄ · · · ⋄ui,k ⋄vi,2 ⋄vi,3 ⋄ · · · ⋄vi,k ⋄,
zi = wi [2..k]wi+1 · · · wk wk−2 w1 · · · wi ⋄,
s = s′ y2 y3 · · · yk x4 z4 x6 z6 · · · x2j z2j · · · xk−2 zk−2 .
Let us explain on a high level why the LZMW algorithm works slowly on s. While analyzing the preﬁx
s′ y2 y3 · · · yk , the algorithm adds a number of “building block” strings into the LZMW dictionary, including the strings w[j..k]wk for j = 2, 3, . . . , k (recall that, unlike the LZD dictionary containing phrases,
the LZMW dictionary contains pairs of adjacent phrases). Before the processing of zi , the algorithm processes xi and adds the strings wi [j..k]wi+1 · · · wk−1 wk [1..j−1] (from vi,j ), wk [j..k]w1 · · · wi−2 wi−1 [1..j]
(from ui,j ), and wi−1 [j+1..k]wi [1..j] (from ti,j ) to the dictionary. The concatenation of these three
strings is wi [j..k]wi+1 · · · wk w1 · · · wi−1 wi [1..j], so, analyzing zi , the algorithm consecutively “jumps”, for
j = 2, 3, . . . , k, from the string wi [j..k]wi+1 · · · wk−1 wk [1..j−1] to wk [j..k]w1 · · · wi−2 wi−1 [1..j] and then
to wi−1 [j+1..k]wi [1..j], thus producing three new phrases (and then moves on to j+1). The point is
that, while analyzing the string wk [j..k]w1 · · · wi−2 wi−1 [1..j], the algorithm does not know in advance
that the string wk [j..k]wk from the dictionary does not occur at this position and, since the length of
the longest common preﬁx of the strings wk [j..k]wk and wk [j..k]wk−j w1 · · · wi ⋄⋄ is Θ(k − j + 1 + |wk−j |),
spends Θ(|wk−j |) = Θ((k − j)k 2 ) time verifying this. Therefore, the analysis of the string s takes
P
5
Θ((k/2) kj=2 (k − j)k 2 ) = Θ(k 5 ) time overall. Since n = |s| = Θ(k 4 ), the processing time is Θ(n 4 ) as
required. We omit the detailed proof since it is very similar to the LZD case.
To additionally verify the correctness of both constructed examples, we performed the naı̈ve LZD
and LZMW algorithms (with some diagnostics to track their execution) on the examples for small k and,
indeed, observed the expected “bad” behavior in the special positions described above. Our verifying
code (it can be found in [1]) thoroughly checks the correspondence of the behavior of the parsers in the
special positions to the behavior discussed in the above text. Thus, we hope that the correctness of both
our constructions is well supported.
We now explain how to decrease the alphabet size in the examples of Theorem 3.1. The construction
for both parsing schemes relies on the following reduction.
Lemma 3.2. Consider the parsing scheme LZD or LZMW and a string s ∈ Σ∗ . There exists a string
t ∈ {0, 1}∗ of length Θ(|Σ| log |Σ|) and a morphism φ with φ(Σ) ⊆ {0, 1}ℓ for ℓ = Θ(log |Σ|) such that
the parsing of t · φ(s) consists of the parsing of t followed by the image with respect to φ of the parsing
of s.

7

L

Proof. We analyze the two parsing schemes separately. For LZD, we recursively deﬁne AL ⊆ {0, 1}2 ,
setting A0 = {0, 1} and AL = {xy : x, y ∈ AL−1 ∧ x ≤ y} for L > 0. Let (αi )∞
i=1 be the inﬁnite sequence
of all elements of AL , for all L ≥ 1, with members of each set AL listed in the lexicographic order; e.g.,
α1 , . . . , α12 = 00, 01, 11, 0000, 0001, 0011, 0101, 0111, 1111, 00000000, 00000001, 00000011. We will deﬁne
t = α1 · · · αm for some m. Let us characterize parsings of such strings.
Claim. For any non-negative integer m and any string w ∈ {0, 1}∗, the ﬁrst m phrases of the LZD
parsing of the binary string α1 · · · αm · w are α1 , . . . , αm .
Proof. We proceed by induction on m; the base case of m = 0 is trivial.
For m > 0, the inductive assumption implies that the ﬁrst m − 1 phrases are α1 , . . . , αm−1 . Our
goal is to prove that the mth phrase is αm . Before processing αm , the LZD dictionary is D =
{0, 1, α1 , . . . , αm−1 }. Suppose that αm = xy ∈ AL with x, y ∈ AL−1 . Recall that x ≤ y; consequently,
D ∩ (y · {0, 1}∗) = {y} and
D ∩ (x · {0, 1}∗) = {x} ∪ {xy ′ : y ′ ∈ AL−1 ∧ x ≤ y ′ < y}.
Thus, the longest preﬁx of αm · w contained in D is x, and the longest preﬁx of y · w contained in D is
y. This means that the mth phrase is indeed αm = xy.
Consider a string s ∈ Σn . We choose the smallest L with |AL | ≥ |Σ| and deﬁne t = α1 · · · αm so that
t is shortest possible and the LZD dictionary after processing t contains at least |Σ| elements of AL . The
morphism φ is then deﬁned by injectively mapping
AL .
PL−1 Σ to these dictionary strings from
Note that |AL−1 | ≤ |Σ| and m ≤ |Σ| + ℓ=1
|Aℓ |, so we have m = Θ(|Σ|), ℓ = 2L = Θ(log |Σ|), and
|t| = Θ(|Σ| log |Σ|), as desired.
We are to prove that the LZD parsing of t · φ(s) is α1 , . . . , αm , φ(p1 ), . . . , φ(pz ), where p1 , . . . , pz is the
LZD parsing of s. For this, we inductively prove that the LZD dictionary D after parsing p1 · · · pi is related
to the LZD dictionary D̂ after parsing t·φ(p1 · · · pi ) by the following invariant: D̂∩(φ(Σ) · {0, 1}∗ ) = φ(D).
The base case follows from the claim (D̂ ∩ (φ(Σ) · {0, 1}∗ ) = φ(Σ) = φ(D)), and the inductive step is
straightforward. This completes the proof for the LZD scheme.
The construction for LZMW is more involved, but the idea is the same. We recursively deﬁne
L
L−1
L−1
BL ⊆ {0, 1}2 , setting B0 = {0, 1} and BL = {xy : x, y ∈ BL−1 ∧ xy 6= 12 02 } for L > 0. Let
(βi )∞
i=1 be the inﬁnite sequence that lists all elements of BL consecutively for all L ≥ 0, with members
∞
of each BL listed in the lexicographic order (i.e., (βi )∞
i=1 is deﬁned by analogy with (αi )i=1 for LZD but
L
starting with L = 0). For βm ∈ BL , deﬁne b(βm ) = βM βm · βM+1 βm · · · βm−1 βm · βm , where βM = 02 is
∞
the ﬁrst element of BL in (βi )i=1 . For example, b(β1 ) · · · b(β6 ) = 0·0 1 1·00·00 01 01·00 11 01 11 11·0000.
Claim. For m ≥ 1, consider a binary string b(β1 ) · · · b(βm ) · 0|βm | · w for w ∈ {0, 1}∗. The LZMW parsing
decomposes its fragments b(βi ) into phrases of length |βi |.
Proof. We proceed by induction on m. The base case m = 1 is straightforward: it suﬃces to note that
the ﬁrst phrase of 0 · 0 · w is 0. Below, we consider m > 1.
L
L−1
L−1
First, suppose that βm = 02 , i.e., βm−1 = 12
∈ BL−1 . Note that b(βm ) starts with 02 , so
the inductive hypothesis yields that the preﬁx b(β1 ) · · · b(βm−1 ) is parsed as desired. Observe that after
SL
ℓ−1
ℓ
parsing this preﬁx, the LZMW dictionary is D = {12 02 : 0 < ℓ < L} ∪ ℓ=0 Bℓ . Consequently, we
obtain D ∩ (BL · {0, 1}∗ ) = BL and, therefore, b(βm ) = βm is parsed as claimed.
L
L
Finally, suppose that βm ∈ BL \{02 }. In this case, βm−1 ∈ BL and βM = 02 for some M < m. Since
L
b(βm ) starts with βM = 02 , the inductive hypothesis lets us assume that the preﬁx b(β1 ) · · · b(βm−1 ) is
L−1
L
parsed as desired. Due to 12 02 −1 ∈
/ BL , after parsing this preﬁx, the LZMW dictionary D satisﬁes:
D ∩ (BL · {0, 1}∗) = BL ∪ {βk βk′ : M ≤ k, k ′ < m ∧ (k, k ′ ) 6= (m−1, M )}.
L

L

Let us consider the parsing of b(βm )02 w = βM βm · βM+1 βm · · · βm−1 βm · βm · 02 w. One can inductively
prove that before parsing βk βm · βk+1 · · · , for M ≤ k < m, we have D ∩ (βk · {0, 1}∗) = {βk } ∪ {βk βk′ :
M ≤ k ′ < m}, so the subsequent phrase is βk . Next, before parsing βm · βk+1 · · · , for M ≤ k < m, we
have D ∩ (βm · {0, 1}∗) = {βm } ∪ {βm βk′ : M < k ′ ≤ k}, so the subsequent phrase is βm . Finally, before
L
parsing βm · 02 w, we have D ∩ (βm · {0, 1}∗) = {βm } ∪ {βm βk′ : M < k ′ < m}, so the last phrase is also
βm . Thus, b(βm ) is parsed as claimed.
8

Consider a string s ∈ Σn . We choose the smallest L with |BL | ≥ |Σ| and deﬁne t = b(β1 ) · · · b(βm )
so that t is shortest possible and the LZMW dictionary after processing t contains at least |Σ| members
of BL (note that βm ∈ BL−1 in this case). The morphism φ is then deﬁned by injectively mapping Σ
L
to these dictionary strings from BL . Moreover, we put φ(s[1]) = 02 so that the claim is applicable for
t · φ(s). The remaining proof is analogous to the LZD counterpart. We only need to observe that the
L
L−1
LZMW dictionary additionally contains βm 02 , but βm 02
∈
/ φ(Σ) and, hence, this does not aﬀect the
parsing of t · φ(s).
The hard binary examples are now straightforward to derive.
Theorem 3.3. The naı̈ve LZD and LZMW parsing algorithms take time Ω(n5/4 / log1/4 n) in the worst
case even on a binary alphabet.
Proof. We apply Lemma 3.2 for a string s ∈ Σ∗ of length n constructed in the proof of Theorem 3.1 for
the appropriate parsing algorithm, which results in a binary string ŝ := t·φ(s). Without loss of generality,
we may assume |Σ| ≤ n, so n̂ := |ŝ| = Θ(|Σ| log |Σ| + n log |Σ|) = Θ(n log |Σ|). Recall that the naı̈ve
parsing algorithm traverses at least Ω(n5/4 ) trie edges while parsing s. Since the parsing of the suﬃx
φ(s) of ŝ is the φ-image of the parsing of s, this algorithm traverses at least Ω(n5/4 log |Σ|) trie edges
while parsing ŝ. In terms of n̂, the running time is at least Ω(n̂5/4 / log1/4 |Σ|), which is Ω(n̂5/4 / log1/4 n̂)
due to |Σ| ≤ n < n̂.

4

Faster Small-Space Computation

In this section we describe a new parsing algorithm that works in O(n + z log2 n) time (randomized,
in expectation) and uses O(z log n) working space to parse the input string over the integer alphabet
{0, 1, . . . , nO(1) }. Before getting to the algorithm itself, we review four tools that are essential for it:
Karp–Rabin hashing [11], AVL-grammars of Rytter [15], the dynamic z-fast trie of Belazzougui et al. [2],
and the dynamic marked ancestor data structure of Westbrook [17].
Pn
Karp–Rabin hashing. A Karp–Rabin [11] hash function φ has the form φ(s[1..n]) = i=1 s[i]δ i−1 mod
p, where p is a ﬁxed prime and δ is a randomly chosen integer from the range [0..p−1] (this is a more
popular version of the original hash proposed in [11]). The value φ(s) is called s’s Karp–Rabin hash. It
is well-known that, for any c > 3, if p > nc , then the probability that two distinct substrings of the given
1
.
input string of length n have the same hash is less than nc−3
We extensively use the property that the hash of the concatenation s1 s2 of two strings s1 and s2
can be computed as (φ(s1 ) + δ |s1 | φ(s2 )) mod p. Therefore, if the values φ(s1 ) and φ(s2 ) are known and
p ≤ nO(1) , then φ(s1 s2 ) can be calculated in O(1) time provided the number (δ |s1 | mod p) is known.
AVL-grammars. Consider a context-free grammar G that generates a string s (and only s). Denote
by T ree(G) the derivation tree of s. We say that G is an AVL-grammar (see [15]) if G is in the Chomsky
normal form and, for every internal node v of T ree(G), the heights of the trees rooted at the left and
right children of v diﬀer by at most 1. The following result straightforwardly follows from the algorithm
of Rytter described in [15].
Lemma 4.1 (see [15, Th. 2]). Let G be an AVL-grammar generating a prefix s[1..i−1] of a string s.
Suppose that the string s[i..k] occurs in s[1..i−1]; then one can construct an AVL-grammar generating
the string s[1..k] in O(log i) time modifying at most O(log i) rules in G.
Let G be an AVL-grammar generating a string s. It is well-known that, for any substring s[i..j],
one can ﬁnd in O(log n) time O(log n) non-terminals A1 , . . . , Ak such that s[i..j] is equal to the string
generated by A1 · · · Ak . Hence, if each non-terminal A of G is augmented with the Karp–Rabin hash
φ(t) of the string t generated by A and with the number δ |t| mod p, then we can compute φ(s[i..j]) in
O(log n) time. One can show that, during the reconstruction of the AVL-grammar in Lemma 4.1, it is
easy to maintain the described integers augmenting the non-terminals (see [15]).

9

Z-fast tries. Let x be a string such that one can compute the Karp–Rabin hash of any preﬁx of x in
O(tx ) time. The z-fast trie [2] is a compacted trie containing a dynamic set of variable-length strings
that supports the following operations:
• we can ﬁnd (w.h.p.) in O(tx log |x|) time the highest explicit node v such that the longest preﬁx
of x present in the trie is written on the root-v path;
• we can insert x into the trie in O(|x| + tx log |x|) randomized time.
The space occupied by the z-fast trie is Θ(k), where k is the number of strings inserted in the trie.
Dynamic marked ancestor. Let T be a dynamic compacted trie (or just tree) with k nodes. The
dynamic marked ancestor data structure of [17] supports the following two operations on T (both in
O(log k) time): for a given node v, (1) mark v, (2) ﬁnd the nearest marked ancestor of v (if any).
Algorithm. Our faster parsing algorithm computes the LZD phrases from left to right one by one,
spending O(logO(1) n) time on each phrase. We maintain an AVL-grammar G for the preﬁx s[1..i−1]
of s we have already parsed, and a z-fast trie T containing the ﬁrst phrases p1 , p2 , . . . , pr of the LZD
parsing of s such that s[1..i−1] = p1 p2 · · · pr . We augment T with the dynamic marked ancestor data
structure and mark all nodes corresponding to phrases (i.e., all nodes v such that the string written on
the path from the root to v is equal to t ∈ {p1 , . . . , pr }). We augment each non-terminal of G with the
Karp–Rabin hash φ(t) of this non-terminal’s expansion t and with the number δ |t| mod p, so that the
hash of any substring of s[1..i−1] can by calculated in O(log n) time.
Suppose we are looking for the ﬁrst part of the next phrase and that, in addition to having parsed
s[1..i−1], we have already read s[i..j−1] without parsing it — but we have found the endpoints of an
occurrence of s[i..j−1] in s[1..i−1]. (Notice s[i..j−1] can be empty, i.e., i = j.) Denote by x the longest
preﬁx of s[i..j−1] that is also a preﬁx of some of the phrases p1 , . . . , pr . Since we can compute quickly
with G the hash of any preﬁx of s[i..j−1], we can use the z-fast search to ﬁnd in O(log 2 n) time a node v
of T such that x is written on the path connecting the root and v. Let s[ℓv ..rv ] be a substring of s[1..i−1]
corresponding to v (the numbers ℓv and rv are stored with the node v). Using hashes and the binary
search, we ﬁnd the longest common preﬁx of the strings s[i..j−1] and s[ℓv ..rv ] (with high probability) in
O(log2 n) time; this preﬁx must be x.
If s[i..j−1] 6= x, then we perform a marked-ancestor query on the vertex corresponding to x (which
can be found in O(log 2 n) time in the same way as v) and thus ﬁnd the longest phrase that is a preﬁx of
s[i..j−1]. We take that phrase as the ﬁrst part of the next phrase and start over, looking for the second
part, with the remainder of s[i..j−1] now being what we have read but not parsed (of which we know
an occurrence in s[1..i−1]). On the other hand, if s[i..j−1] = x, then we read s[j..n] in blocks of length
log2 n, stopping when we encounter an index k such that s[i..k] is not a preﬁx of a phrase p1 , . . . , pr ; the
details follow.
Suppose that we have read q blocks and the concatenation s[i..j + q log2 n − 1] of s[i..j−1] and the
q previous blocks is a preﬁx of a phrase t ∈ {p1 , . . . , pr }. We compute in O(log2 n) time the hashes of
all the preﬁxes of the block s[j + q log2 n..j + (q + 1) log2 n − 1], which allows us to compute the hash of
any preﬁx of s[i..j + (q + 1) log2 n − 1] in O(log n) time. Therefore, again using z-fast search and binary
search, we can check in O(log2 n) time if the block s[j + q log2 n..j + (q + 1) log2 n − 1] contains such a
k — and, if so, ﬁnd it. If k is not found, then using information from the search, we can ﬁnd a phrase
t′ ∈ {p1 , . . . , pr } — which may or may not be equal to t — such that s[i..j + (q + 1) log2 n − 1] is a preﬁx
of t′ ; we then proceed to the (q+2)nd block.
Once we have found such a k, we conceptually undo reading the characters from s[k] onwards (which
causes us to re-read later those O(log2 n) characters), then perform a search and marked-ancestor query
in T , which returns the longest phrase that is a preﬁx of s[i..k−1]. We take that longest phrase as the
ﬁrst part of the next phrase and start over, looking for the second part, with the remainder of s[i..k−1]
now being what we have read but not parsed (of which we know an occurrence in s[1..i−1]).
Once we have found both the ﬁrst and second parts of the next phrase — say, p′1 and p′2 — we add
the next phrase pr+1 = p′1 p′2 to G (by Lemma 4.1) and to T , which takes O(|pr+1 | + log2 n) time. In
total, since processing each block takes O(log2 n) time and the algorithm processes at most z + logn2 n
blocks, we parse s in O(n + z log2 n) time. Our space usage is dominated by G, which takes O(z log n)

10

space. Finally, we verify in a straightforward manner in O(n) time whether the constructed parsing
1
indeed encodes the input string. If not (which can happen with probability nc−3
, where p > nc ), we
choose a diﬀerent random δ ∈ [0..p−1] for the Karp–Rabin hash and execute the whole algorithm again.
The computation of the LZMW parsing in O(n + z log2 n) expected time and O(z log n) space is
similar: the z-fast trie stores pairs p1 p2 , p2 p3 , . . . , pz−1 pz of adjacent phrases in this case and the nodes
corresponding to these pairs are marked. We omit the details as they are straightforward.

5

Concluding Remarks

We believe that our new parsing algorithms can be implemented eﬃciently, and we leave this as future
work. Perhaps a more interesting question is whether there exists an LZD/LZMW parsing algorithm
with better working space and the same (or better) runtime. We note that the algorithmic techniques
we have developed here can also be applied to, e.g., develop more space-eﬃcient parsing algorithms for
LZ-End [13], a variant of LZ77 [18] with which each phrase s[i..j] is the longest preﬁx of s[i..n] such
that an occurrence of s[i..j−1] in s[1..i−1] ends at a phrase boundary. Kempa and Kosolobov [12] very
recently gave an LZ-End parsing algorithm that runs in O(n log ℓ) expected time and O(z + ℓ) space,
where ℓ is the length of the longest phrase and z is the number of phrases.
To reduce Kempa and Kosolobov’s space bound, we keep an AVL-grammar (again augmented with
the non-terminals’ Karp–Rabin hashes, meaning our algorithm Monte-Carlo) of the preﬁx of s we have
processed so far; a list of the endpoints of the phrases so far, in the right-to-left lexicographic order of
the preﬁxes ending at the phrases’ endpoints; and an undo stack of the phrases so far. For each character
s[k] in turn, for 1 ≤ k ≤ n, in O(logO(1) n) time we use the grammar and the list to ﬁnd the longest suﬃx
s[j..k] of s[1..k] such that an occurrence of s[j..k−1] in s[1..j−1] ends at a phrase boundary. We use the
undo stack to remove from the grammar, the list, and the stack itself, all the complete phrases lying
in the substring s[j..k−1], and then add the phrase consisting of the concatenation of those removed
phrases and s[k]. By [12, Lemma 3], we remove at most two phrases while processing s[k], so we still use
a total of O(logO(1) n) worst-case time for each character of s. Again, the space bound is dominated by
the grammar, which takes O(z log n) words. We leave the details for the full version of this paper.
Regarding compression performance, we have shown that like their ancestor, LZ78, both LZD and
LZMW sometimes approximate the smallest grammar poorly. This, of course, does not necessarily detract
from their usefulness in real compression tools; now however, practitioners have a much clearer picture of
these algorithms’ possible behavior. The future work includes closing the gap between the lower bound
2
1
Ω(n 3 ) and the upper bound O((n/ log n) 3 ) for the approximation ratio and designing parsing algorithms
with better guarantees.

Acknowledgements
We thank H. Bannai, P. Cording, K. Dabrowski, D. Hücke, D. Kempa, L. Salmela for interesting discussions on LZD at the 2016 StringMasters and Dagstuhl meetings. Thanks also go to D. Belazzougui for
advice about the z-fast trie and to the anonymous referees.

References
[1] Supplementary materials for the present paper:
https://bitbucket.org/dkosolobov/lzd-lzmw.

C++ code for described experiments.

[2] Djamal Belazzougui, Paolo Boldi, and Sebastiano Vigna. Dynamic z-fast tries. In Proc. 17th
International Symposium on String Processing and Information Retrieval (SPIRE), volume 6393 of
LNCS, pages 159–172. Springer, 2010. doi:10.1007/978-3-642-16321-0_15.
[3] Djamal Belazzougui, Patrick Hagge Cording, Simon J. Puglisi, and Yasuo Tabei.
Access, rank, and select in grammar-compressed strings.
In Proc. 23rd Annual European
Symposium on Algorithms (ESA), volume 9294 of LNCS, pages 142–154. Springer, 2015.
doi:10.1007/978-3-662-48350-3_13.

11

[4] Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren
Weimann. Random access to grammar-compressed strings and trees. SIAM Journal on Computing,
44(3):513–539, 2015. doi:10.1137/130936889.
[5] Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and abhi
shelat. The smallest grammar problem. IEEE Transactions on Information Theory, 51(7):2554–2576,
2005. doi:10.1109/TIT.2005.850116.
[6] Francisco Claude and Gonzalo Navarro. Self-indexed grammar-based compression. Fundamenta
Informaticae, 111(3):313–337, 2011. doi:10.3233/FI-2011-565.
[7] Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Yakov Nekrich, and Simon J. Puglisi. A
faster grammar-based self-index. In Proc. 6th International Conference on Language and Automata Theory and Applications (LATA), volume 7183 of LNCS, pages 240–251. Springer, 2012.
doi:10.1007/978-3-642-28332-1_21.
[8] Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda. LZD factorization: simple
and practical online grammar compression with variable-to-ﬁxed encoding. In Proc. 25th Annual
Symposium on Combinatorial Pattern Matching (CPM), volume 9133 of LNCS, pages 219–230.
Springer, 2015. doi:10.1007/978-3-319-19929-0_19.
[9] Danny Hücke, Markus Lohrey, and Carl Philipp Reh. The smallest grammar problem revisited.
In Proc. 23rd International Symposium on String Processing and Information Retrieval (SPIRE),
volume 9954 of LNCS, pages 35–49. Springer, 2016. doi:10.1007/978-3-319-46049-9_4.
[10] Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Eﬃcient Lyndon factorization of grammar compressed text. In Proc. 24th Annual Symposium on
Combinatorial Pattern Matching (CPM), volume 7922 of LNCS, pages 153–164. Springer, 2013.
doi:10.1007/978-3-642-38905-4_16.
[11] Richard M. Karp and Michael O. Rabin. Eﬃcient randomized pattern-matching algorithms. IBM
Journal of Reseach and Development, 31(2):249–260, 1987. doi:10.1147/rd.312.0249.
[12] Dominik Kempa and Dmitry Kosolobov. LZ-End parsing in compressed space. In Proc. Data
Compression Conference (DCC), pages 350–359. IEEE, 2017. doi:10.1109/DCC.2017.73.
[13] Sebastian Kreft and Gonzalo Navarro. On compressing and indexing repetitive sequences. Theoretical Computer Science, 483:115–133, 2013. doi:10.1016/j.tcs.2012.02.006.
[14] Victor S. Miller and Mark N. Wegman. Variations on a theme by Ziv and Lempel. In Proc. NATO
Advanced Research Workshop on Combinatorial Algorithms on Words, volume 12 of NATO ASI,
pages 131–140. Springer, 1985. doi:10.1007/978-3-642-82456-2_9.
[15] Wojciech Rytter.
Application of Lempel-Ziv factorization to the approximation of
grammar-based compression.
Theoretical Computer Science, 302(1-3):211–222, 2003.
doi:10.1016/S0304-3975(02)00777-6.
[16] Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing
convolution on grammar-compressed text. In Proc. Data Compression Conference (DCC), pages
451–460. IEEE, 2013. doi:10.1109/DCC.2013.53.
[17] Jeﬀery Westbrook. Fast incremental planarity testing. In Proc. 19th International Colloquium on
Automata, Languages and Programming (ICALP), volume 623 of LNCS, pages 342–353. Springer,
1992. doi:10.1007/3-540-55719-9_86.
[18] Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. IEEE
Transactions on Information Theory, 23(3):337–343, 1977. doi:10.1109/TIT.1977.1055714.
[19] Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE
Transactions on Information Theory, 24(5):530–536, 1978. doi:10.1109/TIT.1978.1055934.

12

