# Lempel-Ziv Parsing for Sequences of Blocks
## 2 LZ77 Parsings  
A _string_\(s\) over an alphabet \(\Sigma\) is a map \(\{1,2,\ldots,n\}\to\Sigma\), where \(n\) is referred to as the _length of_\(s\), denoted by \(|s|\). The string of length zero is called the _empty string_. We write \(s[i]\) for the \(i\)th letter of \(s\) and \(s[i\ldots j]\) for \(s[i]s[i+1]\cdots s[j]\) (which is empty if \(i>j\)). A string \(u\) is a _substring_ of \(s\) if \(u=s[i\ldots j]\) for some \(i\) and \(j\); the pair \((i,j)\) is not necessarily unique, and we say that \(i\) specifies an _occurrence_ of \(u\) in \(s\) starting at position \(i\). We say that substrings \(s[i\ldots j]\) and \(s[i^{\prime}\ldots j^{\prime}]\)_overlap_ if \(j\geq i^{\prime}\) and \(i\leq j^{\prime}\). Throughout the text, substrings are sometimes identified with their particular occurrences; we do not emphasize this explicitly if it is clear from the context. We say that a substring \(s[i\ldots j]\) has an _earlier occurrence_ if there exist \(i^{\prime}\) and \(j^{\prime}\) such that \(s[i^{\prime}\ldots j^{\prime}]=s[i\ldots j]\) and \(j^{\prime}<i\) (note that the occurrences do not overlap). A substring \(s[1\ldots j]\) (respectively, \(s[i\ldots n]\)) is a _prefix_ (respectively, _suffix_) of \(s\). For any \(i\) and \(j\), the set \(\{k\in\mathbb{Z}\colon i\leq k\leq j\}\) (possibly empty) is denoted by \([i\ldots j]\). All logarithms have a base of two. A parsing \(s=f_{1}f_{2}\ldots f_{z}\) of a given string \(s\) is called a _Lempel-Ziv (LZ77)_ parsing if each string \(f_{i}\) (called _phrase_) is non-empty, and it either is one letter or occurs in the string \(f_{1}f_{2}\ldots f_{i-1}\) (i.e., it has an earlier occurrence). The _size_ of the parsing is the number \(z\) of phrases. The parsing is called _greedy_ if it is built greedily from left to right by choosing each phrase \(f_{i}\) as the longest substring that starts at a given position and occurs in \(f_{1}f_{2}\ldots f_{i-1}\) (see [2]). It is known that the greedy parsing is, in a sense, optimal, as it is stated in the following lemma. Lemma 1 (see [4; 10; 13]): _No LZ77 parsing of a string can have smaller size than the greedy LZ77 parsing._  
The defined LZ77 parsing is often called _non-overlapping_ since its non-one-letter phrases have non-overlapping earlier occurrences. An analogously defined _overlapping LZ77 parsing_ is its more popular variant: it is a parsing \(f_{1}f_{2}\ldots f_{z}\) in which each non-one-letter phrase \(f_{i}\) has at least two occurrences in the string \(f_{1}f_{2}\ldots f_{i}\) (so that \"earlier occurrences\" of \(f_{i}\) might overlap \(f_{i}\)). Consider \(s=abababc\) for example. The greedy non-overlapping and overlapping LZ77 parsings of \(s\) are _a.b.ab.ab.c_ and _a.b.ab.ab.c_, respectively. In this paper, we mainly discuss the non-overlapping version and, hence, for brevity, often omit the term \"non-overlapping\", which is assumed by default. Clearly, every LZ77 parsing is an overlapping LZ77 parsing, but the converse is not necessarily true. Indeed, one can show that the non-overlapping and overlapping LZ77 parsings are not equivalent in terms of size (see [14]). Our results, however, hold for both variants. An LZ77 parsing \(f_{1}f_{2}\ldots f_{z}\) is _phrase-aligned_ if each non-one-letter phrase \(f_{i}\) has an earlier occurrence \(f_{i}=f_{i}f_{i+1}\ldots f_{i^{\prime}}\), for some \(j<j^{\prime}<i\). This particular type of parsing is interesting because of its close connections to the grammar compression, another popular compression technique. A _grammar_ is a set of rules of the form \(A\to BC\) and \(A\to a\) with a designated initial rule, where \(a\) denotes a letter and \(A,B,C\) denote non-alphabet non-terminals; see [15]. The _size_ of a grammar is the number of rules in it. A _straight line program (SLP) grammar_ is a grammar that infers exactly one string. The SLP grammars and LZ77 parsings are related as follows. **Lemma 2** (see [4; 10]).