Lempel–Ziv Complexity

The Lempel–Ziv complexity is a measure that was first presented in the article ''On the Complexity of Finite Sequences'' (IEEE Trans. On IT-22,1 1976), 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 (i.e., the shallow 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. Fractal dimension estimates of real-world data have also been shown to correlate with Lempel–Ziv complexity.

Principle

Let S be a binary sequence, of length n, for which we have to compute the Lempel–Ziv complexity, denoted C(S). 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 (and so on). We have to move the delimiter (starting in position 1) the furthest 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 (i.e., position 1). 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 (or sub-words) encountered as the binary sequence is viewed as a stream (from left to right).

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 (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, Example of reproducibilit
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 < j+1) of S(1,n−1).

To prove that the sequence S can be reproduced by one of its prefix S(1,j), you have to show that:

$\exists p\leq j, S(j+1,n)=S(p,l(S(j+1,n))+p-1)$

Image:Productibilité.svg, 200px, Example of Productibilit
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, Comparison between reproducibility and producibilit
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 \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_)S(h_+1,h_)\dotsm S(h_+1,h_)$
$H_(S)=S(h_+1,h_),i=1,2\dotsm m, \; h_=0,h_=1,h_=l(S),.$

Image:Hist_exh&complexite1.svg, 200px, Comparison between reproductibility and productibilit
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_-1)\nrightarrow S(1,h_)$ 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

Fortunately, there exists a very efficient method for computing this complexity, in a linear number of operation ($\mathcal(n)$ for $n=l(S)$ length of the sequence S).

A formal description of this method is given by the following algorithm:
* i = p − 1, p is the pointer (see above)
* u is the length of the current prefix
* v is the length of the current component for the current pointer p
* vmax is the final length used for the current component (largest on all the possible pointers p)
* and C is the Lempel–Ziv Complexity, incremented iteratively.

// 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 + v= S + vthen
v := v + 1
else
vmax := max(v, vmax)
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

See also

* LZ77 and LZ78 – Compression algorithms that use a similar idea of finding matching substrings.

Notes and references

References

Bibliography

* Abraham Lempel and Jacob Ziv, « On the Complexity of Finite Sequences », IEEE Trans. on Information Theory, January 1976, p. 75–81, vol. 22, n°1

Application

« Are Pop Lyrics Getting More Repetitive? », By Colin Morris
is a blog post explaining how to use the Lempel–Ziv complexity to measure repetitiveness of song lyric
(with source code available)

* Burns & Rajan (2015) Combining complexity measures of EEG data: multiplying measures reveal previously hidden information. F1000Research. 4:137

(with public MATLAB code available).
* Burns & Rajan (2019) A Mathematical Approach to Correlating Objective Spectro-Temporal Features of Non-linguistic Sounds With Their Subjective Perceptions in Humans. Frontiers in Neuroscience 13:794

(with public MATLAB code available).

External links

Example of a Python implementation and discussion on StackOverflow #41336798

Open-Source (MIT) implementation on Python and Cython on GitHubavailable on PyPi

{{DEFAULTSORT:Lempel-Ziv complexity
Computability theory
Information theory
Computational complexity theory