Lempel-Ziv complexity


The Lempel-Ziv complexity was first presented in the article On the Complexity of Finite Sequences, by two Israeli computer scientists, Abraham Lempel and Jacob Ziv. This complexity measure is related to Kolmogorov complexity, but the only function it uses is the recursive copy.
The underlying mechanism in this complexity measure is the starting point for some algorithms for lossless data compression, like LZ77, LZ78 and LZW. Even though it is based on an elementary principle of words copying, this complexity measure is not too restrictive in the sense that it satisfies the main qualities expected by such a measure: sequences with a certain regularity do not have a too large complexity, and the complexity grows as the sequence grows in length and irregularity.
The Lempel-Ziv complexity can be used to measure the repetitiveness of binary sequences and text, like song lyrics or prose.

Principle

Let S be a binary sequence, of length n, for which we have to compute the Lempel-Ziv complexity, denoted C. The sequence is read from the left.
Imagine you have a delimiting line, which can be moved in the sequence during the calculation. At first, this line is set just after the first symbol, at the beginning of the sequence. This initial position is called position 1, from where we have to move it to a position 2, which is considered the initial position for the next step. We have to move the delimiter the further possible to the right, so that the sub-word between position 1 and the delimiter position be a word of the sequence that starts before the position 1 of the delimiter.
As soon as the delimiter is set on a position where this condition is not met, we stop, move the delimiter to this position, and start again by marking this position as a new initial position. Keep iterating until the end of the sequence. The Lempel-Ziv complexity corresponds to the number of iterations needed to finish this procedure.
Said differently, the Lempel-Ziv complexity is the number of different sub-strings encountered as the binary sequence is viewed as a stream.

Formal explanations

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. Let S, with, be the sub-word of S from index i to index j. The length n of S is denoted l, and a sequence Q is said to be a fixed prefix of S if:

Reproducibility and producibility

On the one hand, a sequence S of length n is said to be reproducible from its prefix S when S is a sub-word of S. This is denoted S→S.
Said differently, S is reproducible from its prefix S if the rest of the sequence, S, is nothing but a copy of another sub-word of S.
To prove that the sequence S can be reproduced by one of its prefix S, you have to show that:
On the other hand, the producibility, is defined from the reproducibility : a sequence S is producible from its prefix S if S is reproducible from S. This is denoted S⇒S. Said differently, S has to be a copy of another sub-word of S. The last symbol of S can be a new symbol, possibly leading to the production of a new sub-word.

Exhaustive history and complexity

From the definition of productibility, the empty string Λ=S ⇒ S. So by a recursive production process, at step i we have S ⇒ S, so we can build S from its prefixes. And as S ⇒ S is always true, this production process of S takes at most n=l steps. Let m,, 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, defined like this:
A component of S, Hi, is said to be exhaustive if S is the longest sequence produced by S ⇒ S) but so that S does not produce S. 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

Hopefully, there exists a very efficient method for computing this complexity, in a linear number of operation.
A formal description of this method is given by the following algorithm:

// S is a binary sequence of size n
i := 0
C := 1
u := 1
v := 1
vmax := v
while u + v <= n do
if S = S then
v := v + 1
else
vmax := max
i := i + 1
if i = u then // all the pointers have been treated
C := C + 1
u := u + vmax
v := 1
i := 0
vmax := v
else
v := 1
end if
end if
end while
if v != 1 then
C := C+1
end if

Application