The method proposed by Lempel and Ziv uses three notions: reproducibility, producibility and exhaustive history of a sequence, that we defined here.
Notations Let S be a binary sequence of length n (i.e., n symbols taking value 0 or 1). Let S(i,j), with 1\leq i,j\leq n, be the sub-word of S from index i to index j (if j is the
empty string). The length n of S is denoted l(S), and a sequence Q is said to be a fixed prefix of S if: \exists j
Reproducibility and producibility Image:Reproductibilité1.svg|200px|thumb|Example of reproducibility Click here On the one hand, a sequence S of length n is said to be reproducible from its prefix S(1,j) when S(j+1,n) is a sub-word of S(1,j). This is denoted S(1,j)→S. Said differently, S is reproducible from its prefix S(1,j) if the rest of the sequence, S(j+1,n), is nothing but a copy of another sub-word (starting at an index i \exists p\leq j, {\text{ s.t. }}S(j+1,n)=S(p,l(S(j+1,n))+p-1) Image:Productibilité.svg|200px|thumb|Example of Productibility Click here On the other hand, the producibility, is defined from the reproducibility: a sequence S is producible from its prefix S(1,j) if S(1,n−1) is reproducible from S(1,j). This is denoted S(1,j)⇒S. Said differently, S(j+1,n−1) has to be a copy of another sub-word of S(1,n-2). The last symbol of S can be a new symbol (but could not be), possibly leading to the production of a new sub-word (hence the term producibility). Image:Prod_reprod1.svg|200px|thumb|Comparison between reproducibility and producibility Click here
Exhaustive history and complexity From the definition of productibility, the empty string Λ=S(1,0) ⇒ S(1,1). So by a recursive production process, at step i we have S(1,hi) ⇒ S(1,hi+1), so we can build S from its prefixes. And as S(1,i) ⇒ S(1,i+1) (with hi+1 =hi + 1) is always true, this production process of S takes at most n=l(S) steps. Let m, 1\leq {\text{m}}\leq l(S), be the number of steps necessary for this product process of S. S can be written in a decomposed form, called history of S, and denoted H(S), defined like this: H(S)=S(1,h_{1})S(h_{1}+1,h_{2})\dotsm S(h_+1,h_{m}) H_{i}(S)=S(h_+1,h_{i}),i=1,2\dotsm m, {\text{where} }\; h_{0}=0,h_{1}=1,h_{m}=l(S),{\text{ is called component of } H(S)}. Image:Hist_exh&complexite1.svg|200px|thumb|Comparison between reproductibility and productibility Click here A component of S, Hi(S), is said to be exhaustive if S(1,hi) is the longest sequence produced by S(1,hi−1) (i.e., S(1,hi−1) ⇒ S(1,hi)) but so that S(1,hi−1) does not produce S(1,hi) (denoted). S(1,h_{i}-1)\nrightarrow S(1,h_{i}) The index p which allows to have the longest production is called pointer. The history of S is said to be exhaustive if all its component are exhaustive, except possibly the last one. From the definition, one can show that any sequence S has only one exhaustive history, and this history is the one with the smallest number of component from all the possible histories of S. Finally, the number of component of this unique exhaustive history of S is called the Lempel–Ziv complexity of S. == Algorithm ==