Lempel-Ziv Universal Coding

Parse a sequence into phrases and compress to the entropy rate, no model needed.

The idea

The Lempel-Ziv code (LZ78) is a universal compression scheme: it compresses a sequence toward the source's entropy rate without being told the source distribution. Codes built from entropy compute their codeword lengths from the probabilities $p_i$; LZ78 uses no probabilities at all.

Algorithm.

Algorithm: LZ78 Parse Input: a sequence of symbols x1 x2 ... xn Output: its parse into phrases, each encoded as a pair (pointer to an earlier phrase, one new symbol) 1. phrase list = empty; current string w = empty 2. if the sequence is exhausted, record any nonempty w as the final phrase and return the list of pairs // the final phrase may repeat an earlier one 3. append the next symbol to w 4. if w is already on the phrase list, go to step 2 5. record w as a new phrase, encoded as (pointer to w minus its last symbol, that last symbol) // the empty phrase counts as index 0 6. reset w to empty, go to step 2

A phrase is broken off at the shortest string not yet on the list, so the recorded phrases are distinct and each extends an earlier phrase by a single symbol. The compression lies in the number of phrases. A pointer into a list of $c$ phrases costs $\log_{2} c$ bits, so encoding the whole parse takes about $c \log_{2} c$ bits, and a predictable source repeats itself, so its distinct phrases accumulate slowly. For a stationary ergodic source the cost per symbol approaches the entropy rate in bits, which is what makes the code universal.

Ways to work on it

• Walkthrough. The LZ78 parse, the (pointer, symbol) code, and why it is universal.
• Practice. Count the phrases in an LZ78 parse.
• Hardest. Parse a string and size its LZ78 codeword.

Not sure where to start? Take the ten-question placement test.