Lempel–Ziv complexity
How complex is a sequence: an EEG recording, a series of “warmer or colder”, a genome? In 1976 Abraham Lempel and Jacob Ziv proposed a measure that does not depend on any model: how many new pieces have to be introduced while reading the sequence from left to right. Since then it has been computed in signal analysis and in genomics, and a year later the LZ77 compression algorithm grew out of the same idea.
A string s of length n is split into phrases from left to right. Let the next phrase start at position p. Find the longest piece s[p..p + L) that occurs in s starting at some position j < p; the occurrence may run past p and overlap the piece itself. The phrase is this piece plus one more following letter, that is, L + 1 letters; if fewer remain to the end of the string, the phrase is the whole remainder. The Lempel–Ziv complexity is the number of phrases.
For example, 0001101001000101 splits into 0 · 001 · 10 · 100 · 1000 · 101: six phrases. A string of a hundred thousand “a”s splits into two: “a” and the whole remainder, because it repeats itself shifted by one letter.
The tests include genomes of phages and of human mitochondria, the series “warmer than yesterday?” and “was there rain?” for Almaty over 1941–2025, a piece of War and Peace and strings on which the quadratic algorithm of Kaspar and Schuster (1987) runs out of time.
Input
The first line holds the number of strings t (1 ≤ t ≤ 1000). Each of the next t lines holds a non-empty string without whitespace, in UTF-8. The total length of the strings is at most 100,000 characters; length is counted in characters, not bytes.
Output
For each string, its Lempel–Ziv complexity.
Examples
Example 1
1 0001101001000101
6
Example 2
4 aaaa abcabc ACGT TTAGGGTTAGGGTTAGGG
2 4 4 5
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The length of a phrase depends on just one number, the longest piece that starts at p and occurred earlier. If this number is known for each position, the splitting is one pass.
2Hint 2
This number is called LPF, the longest previous factor. A piece that starts at p and earlier is a common prefix of suffix p and some suffix j < p. Where in the suffix array should you look for the best such j?
3Hint 3
The common prefix with a suffix is longer the closer it is in the array. So the best j is the nearest to p in the array, above or below, among those that start earlier in the text than p. They are found with a stack, as in problems about the nearest smaller element.
4The idea
Build the suffix array and the LCP, then the LPF by the algorithm of Crochemore and Ilie (2008). Go along the array with a stack of suffixes whose positions in the text increase from bottom to top. A new suffix pops off the stack everyone who starts later in the text than it does: for a popped suffix the nearest “earlier” one below is the new suffix, and above it the new top of the stack. The LPF of a popped suffix is the maximum of the two common prefixes, and the common prefix with the new suffix shrinks along the way to the minimum LCP over the stretch. Each suffix enters and leaves the stack once.
5Walkthrough
The splitting: p = 0, and while p < n, shift by min(LPF[p] + 1, n − p) and add one to the phrase counter. The suffix array and Kasai come from the article on the suffix array.
The answers are worth comparing with what a random text of the same length would give: for it the number of phrases is close to n/logk n, where k is the alphabet size. A hundred thousand random bits give 6134 phrases, almost exactly that. The lambda genome gives 5988 phrases on 48,502 letters, 96% of random: the phage’s DNA has few repeats. And the series “warmer than yesterday?” over 50,000 days in Almaty gives 2050 phrases, about 64% of random: the weather repeats its patterns.
5+Solution
6Complexity
The array is O(n log n), the LCP and LPF O(n), the splitting O(n). The algorithm of Kaspar and Schuster tries all earlier starts for each phrase and on a random text makes about n²/2 comparisons.
7Common mistakes
- No overlap. If the piece is sought only in the text before p, a string of nothing but “a”s splits into phrases of length 1, 2, 4, 8…, not into two. By definition the occurrence may run past p.
- The last phrase. If the remainder of the string occurred earlier as a whole, it is the last phrase, without an extra letter. The string has to be counted to the end without running past it.
- Only the neighbour above. The nearest earlier suffix may also be below in the array; both are needed, and the better common prefix is taken.