46.02.04 · information-theory / 02-source-coding

Arithmetic Coding and Lempel-Ziv Universal Source Coding

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §13.1-13.5; Wyner & Ziv 1989 Some Asymptotic Properties of the Lempel-Ziv Algorithm (IEEE Trans. IT); Lempel & Ziv 1976 On the Complexity of Finite Sequences (IEEE Trans. IT)

Intuition Beginner

Huffman coding is optimal for lossless compression, but it has a weakness: each symbol gets its own codeword. If your source has probabilities like 0.4, 0.3, 0.2, 0.1, Huffman assigns codewords of length 1, 2, 3, 3. The average length is 2.0 bits, while the entropy is 1.85 bits. You waste 0.15 bits per symbol because you cannot assign fractional-length codewords to individual symbols.

Arithmetic coding fixes this. Instead of assigning a codeword to each symbol separately, it encodes the entire message as a single number between 0 and 1. As each symbol arrives, the current interval shrinks by a factor equal to that symbol's probability. After processing the whole message, you pick any number inside the final interval and transmit its binary expansion. Because the interval width equals the product of all the symbol probabilities, the number of bits needed is approximately the negative log of that product, which is the total information content. You can get within two bits of the entropy for the entire message, regardless of alphabet size.

Now consider a different problem. What if you do not know the source statistics? You cannot assign probabilities because you do not have them. Lempel-Ziv coding solves this by building a dictionary as it reads the input. It works by breaking the message into phrases: the first time you see a pattern, you add it to the dictionary. The next time you see the same pattern, you refer back to it. The longer the input, the better the dictionary becomes. No probability model is needed.

The remarkable fact is that Lempel-Ziv is universal. For any stationary ergodic source (a source whose statistics are time-invariant in the long run), the compression ratio of LZ converges to the entropy rate as the message length grows. You do not need to know anything about the source beforehand. The algorithm learns the statistics from the data itself.

Visual Beginner

Coding method	Knows source stats?	Uses codewords?	Bits per symbol
Huffman	Yes	Yes, one per symbol	$\leq H + 1$
Arithmetic	Yes	No, encodes whole message	$\leq H + 2/ n$
Lempel-Ziv (LZ78)	No	Yes, dictionary phrases	$\to H$ as $n \to \infty$

Figure: interval subdivision in arithmetic coding for the message "ABA" over alphabet {A, B} with p(A) = 0.6, p(B) = 0.4. Start with [0, 1). After A: [0, 0.6). After B: [0.36, 0.6). After A: [0.36, 0.504). The width of the final interval is 0.144 = 0.6 * 0.4 * 0.6. The number of bits needed is $⌈ - lo g_{2} (0.144)⌉ = 3$ bits.

Worked example Beginner

Encode the message "BAAB" using arithmetic coding over the alphabet {A, B} with p(A) = 0.6, p(B) = 0.4.

Step 1. Set up the initial interval [0, 1). Partition it: A gets [0, 0.6), B gets [0.6, 1.0).

Step 2. Process B. The current interval becomes [0.6, 1.0). Subdivide: A gets [0.6, 0.84), B gets [0.84, 1.0).

Step 3. Process A. The current interval becomes [0.6, 0.84). Subdivide: A gets [0.6, 0.744), B gets [0.744, 0.84).

Step 4. Process A. The current interval becomes [0.6, 0.744). Subdivide: A gets [0.6, 0.6864), B gets [0.6864, 0.744).

Step 5. Process B. The final interval is [0.6864, 0.744). Width = 0.0576 = 0.4 * 0.6 * 0.6 * 0.4. The number of bits needed is $⌈ - lo g_{2} (0.0576)⌉ = 5$ bits. The midpoint 0.7152 in binary is 0.10110111..., so transmitting the first 5 bits suffices.

The entropy of this four-symbol message is $- 4 \times (0.6 lo g_{2} 0.6 + 0.4 lo g_{2} 0.4) = 4 \times 0.971 = 3.88$ bits. We used 5 bits, which is within the guaranteed 2-bit overhead.

Check your understanding Beginner

Formal definition Intermediate+

Let $X$ be a finite source alphabet with known conditional probabilities $p (x_{i} ∣ x^{i - 1})$ (reducing to $p (x_{i})$ for a memoryless source). The source emits a sequence $x^{n} = (x_{1}, x_{2}, \dots, x_{n})$ .

Definition (Arithmetic coding). Arithmetic coding maps $x^{n}$ to a sub-interval of $[0, 1)$ as follows. Let $F (x) = \sum_{a < x} p (a)$ be the cumulative distribution function (for memoryless sources; the conditional version uses $F (x_{i} ∣ x^{i - 1})$ ). Initialize $[l_{0}, h_{0}) = [0, 1)$ . For each symbol $x_{i}$ , update:

[l_{i}, h_{i}) = [l_{i - 1} + (h_{i - 1} - l_{i - 1}) F (x_{i}^{-}), l_{i - 1} + (h_{i - 1} - l_{i - 1}) F (x_{i}^{+})),

where $F (x_{i}^{-})$ is the cumulative probability up to but not including $x_{i}$ , and $F (x_{i}^{+})$ includes $x_{i}$ . The final interval $[l_{n}, h_{n})$ has width:

w_{n} = i = 1 \prod n p (x_{i} ∣ x^{i - 1}) .

Encode $x^{n}$ by transmitting any number in $[l_{n}, h_{n})$ using $⌈ - lo g_{2} w_{n} ⌉ + 1$ bits.

Definition (LZ78 parsing). Given an infinite source sequence $x_{1}, x_{2}, \dots$ , the LZ78 parsing produces a sequence of distinct phrases $w_{1}, w_{2}, \dots, w_{c (n)}$ where $w_{j}$ is the longest prefix of the remaining input that already appears in the dictionary $D_{j - 1} = {w_{1}, \dots, w_{j - 1}}$ , concatenated with the next symbol. Formally, if $w_{j} = w^{*} \cdot a$ where $w^{*}$ is a previous phrase (or empty) and $a \in X$ , then the encoder transmits the pair (index of $w^{*}$ , $a$ ). The new phrase $w_{j}$ is added to $D_{j}$ .

The number of bits for phrase $w_{j}$ is $⌈ lo g_{2} j ⌉ + ⌈ lo g_{2} ∣ X ∣ ⌉$ (pointer plus new symbol), and the total encoded length for $n$ source symbols is:

L_{n} = j = 1 \sum c (n) (⌈ lo g_{2} j ⌉ + ⌈ lo g_{2} ∣ X ∣ ⌉) .

Counterexamples to common slips

Arithmetic coding is not Huffman coding. Huffman assigns a fixed codeword to each symbol. Arithmetic coding encodes the entire message jointly. The gap between Huffman's $H + 1$ bound and arithmetic coding's $H + 2/ n$ bound grows when symbol probabilities are very different from inverse powers of two.
LZ78 is not LZ77. LZ77 uses a sliding window and back-references; LZ78 builds an explicit dictionary that grows monotonically. Their universality properties differ in convergence rate.
Universality does not mean optimal for finite lengths. LZ achieves the entropy rate asymptotically. For finite block lengths, a code designed with knowledge of the source distribution will outperform LZ. The universality advantage is that LZ works without such knowledge.

Key theorem with proof Intermediate+

Theorem (Arithmetic coding near-optimality). Let $x^{n}$ be drawn from a source with known probabilities. The arithmetic code for $x^{n}$ has length $l (x^{n})$ satisfying:

- lo g_{2} p (x^{n}) \leq l (x^{n}) \leq - lo g_{2} p (x^{n}) + 2.

Therefore the expected length per symbol satisfies $H (X) \leq E [l (X^{n})] / n \leq H (X) + 2/ n$ .

Proof. The final interval $[l_{n}, h_{n})$ has width $w_{n} = p (x^{n})$ . The number of bits needed to specify a point in an interval of width $w$ is $⌈ - lo g_{2} w ⌉$ . By choosing the midpoint $m = (l_{n} + h_{n}) /2$ and transmitting its binary expansion:

- lo g_{2} w_{n} \leq l (x^{n}) \leq - lo g_{2} w_{n} + 1.

Accounting for the one-bit ambiguity in terminating the binary expansion adds at most one more bit, giving the bound $l (x^{n}) \leq - lo g_{2} p (x^{n}) + 2$ . Taking expectations and dividing by $n$ yields the per-symbol bound. $□$

Theorem (LZ78 universality). For any stationary ergodic source with entropy rate $H (X)$ , the compression rate of LZ78 satisfies:

\frac{L _{n}}{n} ⟶ H (X) almost surely as n \to \infty.

Proof sketch. The proof proceeds in three stages. (1) The number of phrases $c (n)$ satisfies $c (n) \to \infty$ and $c (n) / n \to 0$ for stationary sources (each phrase is at least one symbol long, and new phrases are always added). (2) The entropy of the first $n$ symbols decomposes as $H (X^{n}) = \sum_{j} H (W_{j} ∣ W^{j - 1})$ where $W_{j}$ is the $j$ -th phrase. Since LZ78 phrases are distinct, the set of phrases grows, and the conditional entropy of each new phrase is bounded. (3) The encoding cost for phrase $j$ is approximately $lo g_{2} j + lo g_{2} ∣ X ∣$ , and the combinatorial bound $c (n) lo g c (n) \geq n H (X) - o (n)$ (from the entropy of the phrase process) combined with the upper bound on $L_{n}$ gives:

H (X) \leq \frac{L _{n}}{n} \leq \frac{c ( n ) ( lo g _{2} c ( n ) + lo g _{2} ∣ X ∣ )}{n} ⟶ H (X) . □

Bridge. The universality of LZ78 builds toward the rate-distortion framework in 46.02.05 by establishing that lossless compression at the entropy rate is achievable even without source knowledge, and appears again in 46.04.04 where the Blahut-Arimoto algorithm provides a computational method for finding the rate-distortion function; the foundational reason arithmetic coding achieves the entropy bound is the interval-subdivision mechanism whose width equals the source probability product, which generalises to the joint typicality encoding used in channel coding 46.03.02; the central insight is that universality emerges from the growth rate of the dictionary matching the entropy rate of the source, putting these together gives a landscape where compression, estimation, and communication share the same entropy-theoretic backbone.

Exercises Intermediate+

Exercise (medium, numeric).

Apply LZ78 parsing to the binary string 0110100010. List the phrases and compute the number of encoded bits (using $⌈ lo g_{2} j ⌉ + 1$ bits per phrase, binary alphabet).

Hint

Start with an empty dictionary. Parse greedily: the first phrase is the longest prefix not yet seen, plus one new symbol.

Answer

Phrases: (1) 0, (2) 1, (3) 01, (4) 10, (5) 00, (6) 10 (already seen), so 101 → (6) 10, and remaining 0 → actually let us re-parse carefully.

String: 0 1 1 0 1 0 0 0 1 0.

Phrase 1: "0" (new). Dict: {0}
Phrase 2: "1" (new). Dict: {0, 1}
Phrase 3: "10" — longest prefix "1" is in dict, plus "0" → "10" (new). Dict: {0, 1, 10}
Phrase 4: "100" — longest prefix "10" in dict, plus "0" → "100" (new). Dict: {0, 1, 10, 100}
Phrase 5: "10" — in dict already, so longest prefix "10" plus next is "10" → phrase is "10"? No: "10" is in dict, check "100" — that is also in dict. Next char: "1". So phrase is "1001" (new). Wait, let us re-read: the string is 0 1 1 0 1 0 0 0 1 0.

Positions: 1:0, 2:1, 3:1, 4:0, 5:1, 6:0, 7:0, 8:0, 9:1, 10:0.

Phrase 1 (pos 1): 0 → w* = "", a = 0. Dict: {0}. Cost: 0 + 1 = 1 bit.
Phrase 2 (pos 2): 1 → w* = "", a = 1. Dict: {0, 1}. Cost: 1 + 1 = 2 bits.
Phrase 3 (pos 3-4): longest match "1" (pos 3), next is "0" (pos 4). Phrase = "10". Dict: {0, 1, 10}. Cost: $⌈ lo g_{2} 3 ⌉ + 1 = 2 + 1 = 3$ bits.
Phrase 4 (pos 5-6): longest match "10" (pos 5-6). Next is "0" (pos 7). Phrase = "100". Dict: {0, 1, 10, 100}. Cost: $⌈ lo g_{2} 4 ⌉ + 1 = 2 + 1 = 3$ bits.
Phrase 5 (pos 8-9): longest match "0" (pos 8), next is "1" (pos 9). Phrase = "01". Dict: {0, 1, 10, 100, 01}. Cost: $⌈ lo g_{2} 5 ⌉ + 1 = 3 + 1 = 4$ bits.
Phrase 6 (pos 10): "0" → w* = "", a = 0. But "0" is already in dict. So phrase is "0" plus next... there is no next. In standard LZ78, the last incomplete phrase is handled as a special case. Phrase = "0" with pointer to dict entry 1. Cost: $⌈ lo g_{2} 6 ⌉ + 1 = 3 + 1 = 4$ bits. (Or omit the new symbol if at end of input.)

Total bits: $1 + 2 + 3 + 3 + 4 + 4 = 17$ bits for 10 source symbols = 1.7 bits/symbol.

Exercise (hard, short answer).

Let $c (n)$ denote the number of LZ78 phrases for a sequence of length $n$ from a stationary ergodic source with entropy rate $H > 0$ . Prove the lower bound $c (n) lo g c (n) \geq n H - o (n)$ .

Hint

Use the fact that the phrases are distinct and apply the entropy bound: the total entropy $H (X^{n}) = n H$ is bounded above by the entropy of the phrase representation.

Answer

The phrases $W_{1}, \dots, W_{c (n)}$ form a partition of $X^{n}$ , and each phrase is distinct. The entropy of $X^{n}$ satisfies $H (X^{n}) \leq H (W_{1}, \dots, W_{c (n)})$ since the phrase sequence determines $X^{n}$ . By the chain rule and the fact that each $W_{j}$ takes values in a set of size at most $j \cdot ∣ X ∣$ (the prefix pointer has at most $j - 1$ choices and the new symbol has $∣ X ∣$ choices), we get $H (W_{j} ∣ W^{j - 1}) \leq lo g (j \cdot ∣ X ∣) = lo g j + lo g ∣ X ∣$ . Summing: $n H = H (X^{n}) \leq \sum_{j = 1}^{c (n)} (lo g j + lo g ∣ X ∣) \leq c (n) lo g c (n) + c (n) lo g ∣ X ∣$ . Since $c (n) / n \to 0$ , the second term is $o (n)$ , giving $c (n) lo g c (n) \geq n H - o (n)$ .

Lean formalization Intermediate+

Mathlib has no formalisation of arithmetic coding, the Lempel-Ziv algorithm, or the concept of universal source coding. The interval arithmetic underlying arithmetic coding requires precise reasoning about floating-point-like representations on $[0, 1)$ , which is absent. The LZ78 parsing algorithm requires inductive definitions on streams and dictionary growth, neither of which exists in Mathlib. The universality theorem relies on the Shannon-McMillan-Breiman theorem for stationary ergodic sources, which is not formalised in Mathlib's probability theory library. The gap between what Mathlib has (basic measure theory, PMF types) and what is needed (streaming algorithms, ergodic theorems, phrase-count asymptotics) is substantial. This unit ships without a lean_module.

Advanced results Master

Precision and implementation of arithmetic coding

The theoretical description of arithmetic coding uses infinite-precision real arithmetic on $[0, 1)$ . Practical implementations use finite-precision integer arithmetic with a technique called bit-stuffing or E3 scaling. Whenever the interval $[l, h)$ lies entirely within $[0, 0.5)$ or $[0.5, 1)$ , the encoder doubles the interval (shifts one bit out) and continues. When $[l, h) \subset [0.25, 0.75)$ , a more subtle rescaling (the E3 mapping) prevents the interval from collapsing around 0.5.

The key implementation result is that arithmetic coding can be performed using fixed-precision integer registers of width $W$ bits, where $W$ is typically 16 or 32. The encoder outputs bits incrementally as the interval narrows, without waiting for the entire message. The decoder reads bits incrementally as well, maintaining its own interval. The throughput is linear in the message length, making arithmetic coding practical for real-time applications.

LZ78 and the entropy rate: sharp convergence

The Wyner-Ziv 1989 paper established the sharp convergence rate of LZ78 compression. For a memoryless source with entropy $H$ , the compression rate satisfies:

\frac{L _{n}}{n} = H + O (\frac{lo g lo g n}{lo g n}) .

This is slower than the $O (1/ n)$ convergence of arithmetic coding with known statistics, but the advantage is universality. The redundancy (excess bits over entropy) vanishes logarithmically.

The proof technique connects LZ78 to the Ornstein isomorphism theorem in ergodic theory. The phrase parsing creates a tree whose growth rate is governed by the entropy rate of the source. The key identity is:

\frac{c ( n ) lo g c ( n )}{n} \to H (X),

which holds almost surely for any stationary ergodic source. This result also connects to Kolmogorov complexity 42.04.08: the LZ78 compression length is an upper bound on the Kolmogorov complexity $K (x^{n})$ , since any universal Turing machine can decompress the LZ78 encoding. Therefore $K (x^{n}) \leq L_{n} (x^{n}) + O (1)$ , and the universality of LZ78 provides an algorithmic proof that $K (x^{n}) / n \to H (X)$ for computable stationary ergodic sources.

LZW and practical variants

The LZW variant (Welch 1984) modifies LZ78 by removing the explicit transmission of the new symbol. Instead, the encoder always transmits a dictionary index, and the decoder infers the new symbol from the next phrase. This saves $lo g ∣ X ∣$ bits per phrase and is the basis of the Unix compress utility, GIF image encoding, and the PKZIP/ZIP format (as one of the available algorithms).

The LZ77 variant (Ziv & Lempel 1977) uses a sliding window of fixed size $W$ instead of a growing dictionary. Each phrase is encoded as a triple (offset, length, next symbol), where offset and length refer back into the window. LZ77 achieves universality with a different convergence rate and is the algorithm behind gzip and DEFLATE.

Relationship to the entropy power inequality

The entropy power inequality (EPI), studied in 46.01.04, states that $2^{2 h (X + Y)} \geq 2^{2 h (X)} + 2^{2 h (Y)}$ for independent continuous random variables. The EPI bounds the performance of universal coding for mixed sources: if a source is a mixture of two component sources, the entropy power of the mixture controls the compression rate. Arithmetic coding on the mixture distribution achieves this rate, while LZ78 achieves it adaptively.

Synthesis. Arithmetic coding achieves the entropy bound to within two bits for the entire message by mapping it to a sub-interval of $[0, 1)$ whose width equals the probability product; this builds toward the joint typicality encoding of channel coding where similar interval constructions appear; the central insight is that Lempel-Ziv universality emerges from the interplay between dictionary growth and source entropy rate, putting these together we see that lossless compression, universal estimation, and Kolmogorov complexity share the same entropy-theoretic foundation; the foundational reason arithmetic coding outperforms Huffman is that joint encoding of the entire message avoids the integer-length penalty per symbol, and this generalises to any block coding scheme where the block length determines the resolution of the probability partition.

Full proof set Master

Proposition (Arithmetic coding interval width). After encoding $n$ symbols from a source with conditional probabilities $p (x_{i} ∣ x^{i - 1})$ , the interval $[l_{n}, h_{n})$ produced by arithmetic coding has width $w_{n} = \prod_{i = 1}^{n} p (x_{i} ∣ x^{i - 1}) = p (x^{n})$ .

Proof. By induction on $n$ . Base case: $n = 0$ , interval $[0, 1)$ has width 1 = $p (\emptyset)$ . Inductive step: assume $[l_{n - 1}, h_{n - 1})$ has width $w_{n - 1} = p (x^{n - 1})$ . After processing $x_{n}$ , the new interval is:

[l_{n}, h_{n}) = [l_{n - 1} + w_{n - 1} F (x_{n}^{-} ∣ x^{n - 1}), l_{n - 1} + w_{n - 1} F (x_{n}^{+} ∣ x^{n - 1})) .

The new width is:

w_{n} = w_{n - 1} (F (x_{n}^{+} ∣ x^{n - 1}) - F (x_{n}^{-} ∣ x^{n - 1})) = w_{n - 1} \cdot p (x_{n} ∣ x^{n - 1}) .

By the inductive hypothesis, $w_{n} = p (x^{n - 1}) \cdot p (x_{n} ∣ x^{n - 1}) = p (x^{n})$ . $□$

Proposition (LZ78 phrase-count lower bound). For a source with entropy rate $H (X) > 0$ , the number of LZ78 phrases $c (n)$ satisfies $c (n) \geq \frac{n H ( X )}{l o g n + l o g ∣ X ∣}$ for all sufficiently large $n$ .

Proof. Each phrase $W_{j}$ can be specified by a pointer (at most $lo g_{2} j$ bits) and a new symbol ( $lo g_{2} ∣ X ∣$ bits), so the description length of $W_{j}$ is at most $lo g_{2} j + lo g_{2} ∣ X ∣$ . Since the phrases partition the input, the total description length $L_{n} \leq \sum_{j = 1}^{c (n)} (lo g_{2} j + lo g_{2} ∣ X ∣) \leq c (n) (lo g_{2} c (n) + lo g_{2} ∣ X ∣)$ .

But by the source coding theorem, $L_{n} \geq n H (X) - o (n)$ . Therefore:

c (n) (lo g_{2} c (n) + lo g_{2} ∣ X ∣) \geq n H (X) - o (n) .

For the crude bound, note that $lo g_{2} c (n) \leq lo g_{2} n$ , so $c (n) \geq \frac{n H ( X ) - o ( n )}{l o g _{2} n + l o g _{2} ∣ X ∣}$ . $□$

Connections Master

46.02.02 — Shannon's source coding theorem establishes $H (X)$ as the fundamental compression limit; arithmetic coding achieves it and LZ78 achieves it universally.
42.04.08 — Kolmogorov complexity $K (x)$ is lower-bounded by the LZ78 compression length minus a constant; the universality of LZ78 provides an algorithmic approximation to incompressibility.
46.02.05 — Rate-distortion theory generalises the lossless compression framework to lossy coding, where the entropy $H (X)$ is replaced by the rate-distortion function $R (D)$ .
46.01.04 — Differential entropy and the entropy power inequality provide the continuous-source analogues of the discrete-source results here.
46.08.01 — LDPC codes use graphical structures for iterative decoding; the phrase-tree of LZ78 is a simpler graph-based data structure that also achieves information-theoretic limits.

Historical & philosophical context Master

Arithmetic coding was introduced by Jorma Rissanen in 1976 at IBM Research ("Generalized Kraft Inequality and Arithmetic Coding," IBM Journal of Research and Development 20(3):198-203). Rissanen recognised that the Kraft inequality could be satisfied not only by assigning integer-length codewords (Huffman) but by mapping messages to sub-intervals of the unit interval. The idea had been foreshadowed by Shannon's 1948 paper, which described encoding by cumulative probability evaluation, but Rissanen made it practical by developing the incremental encoding and decoding algorithms.

The Lempel-Ziv algorithm was introduced by Abraham Lempel and Jacob Ziv in their 1976 and 1977 papers ("On the Complexity of Finite Sequences," IEEE Trans. IT 22(1):75-81, 1976; "A Universal Algorithm for Sequential Data Compression," IEEE Trans. IT 23(3):337-343, 1977). Their insight was that compression could be achieved by exploiting the repeat structure of the input without any probabilistic model. The LZ78 variant (the 1978 paper "Compression of Individual Sequences via Variable-Rate Coding," IEEE Trans. IT 24(5):530-536) built an explicit dictionary, as described in this unit.

The universality proof was completed by Ziv in 1978 and sharpened by Wyner and Ziv in 1989 ("Some Asymptotic Properties of the Lempel-Ziv Algorithm," IEEE Trans. IT 35(6):1252-1259). The connection to Kolmogorov complexity was recognised early: the LZ78 compression length provides a computable upper bound on the Kolmogorov complexity of any string, making it an approximation to the uncomputable $K (x)$ .

Terry Welch's 1984 variant (LZW), published as "A Technique for High-Performance Data Compression" (IEEE Computer 17(6):8-19), became the most widely deployed compression algorithm of the 1990s, appearing in GIF, Unix compress, and early versions of ZIP. The patent encumbrance of LZW (Unisys, 1985-2003) motivated the adoption of DEFLATE (a combination of LZ77 and Huffman coding) in later formats.

Bibliography Master

@article{rissanen1976,
  author  = {Rissanen, J.},
  title   = {Generalized {Kraft} Inequality and Arithmetic Coding},
  journal = {IBM Journal of Research and Development},
  volume  = {20},
  number  = {3},
  pages   = {198--203},
  year    = {1976},
}
@article{lempel-ziv1976,
  author  = {Lempel, A. and Ziv, J.},
  title   = {On the Complexity of Finite Sequences},
  journal = {IEEE Transactions on Information Theory},
  volume  = {22},
  number  = {1},
  pages   = {75--81},
  year    = {1976},
}
@article{ziv-lempel1977,
  author  = {Ziv, J. and Lempel, A.},
  title   = {A Universal Algorithm for Sequential Data Compression},
  journal = {IEEE Transactions on Information Theory},
  volume  = {23},
  number  = {3},
  pages   = {337--343},
  year    = {1977},
}
@article{ziv-lempel1978,
  author  = {Ziv, J. and Lempel, A.},
  title   = {Compression of Individual Sequences via Variable-Rate Coding},
  journal = {IEEE Transactions on Information Theory},
  volume  = {24},
  number  = {5},
  pages   = {530--536},
  year    = {1978},
}
@article{wyner-ziv1989,
  author  = {Wyner, A. D. and Ziv, J.},
  title   = {Some Asymptotic Properties of the {Lempel-Ziv} Algorithm},
  journal = {IEEE Transactions on Information Theory},
  volume  = {35},
  number  = {6},
  pages   = {1252--1259},
  year    = {1989},
}
@article{welch1984,
  author  = {Welch, T. A.},
  title   = {A Technique for High-Performance Data Compression},
  journal = {IEEE Computer},
  volume  = {17},
  number  = {6},
  pages   = {8--19},
  year    = {1984},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}

Prerequisites

46.02.02
42.04.08

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §13.1-13.3 (the idea of encoding by narrowing an interval, the LZW dictionary example)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §13.1-13.4 (arithmetic coding interval subdivision, LZ78 parsing and tree growth, universality theorem)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §13.1-13.5; Wyner & Ziv 1989 Some Asymptotic Properties of the Lempel-Ziv Algorithm (IEEE Trans. IT); Lempel & Ziv 1976 On the Complexity of Finite Sequences (IEEE Trans. IT)

References

Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 13.1: arithmetic coding encodes a message $x_{1}^{n}$ by mapping it to a sub-interval of $[0, 1)$ whose width equals the product $\prod_{i = 1}^{n} p (x_{i} ∣ x^{i - 1})$ ; the midpoint of that interval, expressed in binary, requires at most $⌈ - lo g \prod p (x_{i} ∣ x^{i - 1})⌉ + 2$ bits. Section 13.3: LZ78 parsing partitions the input into distinct phrases $w_{1}, w_{2}, \dots$ where each $w_{i}$ is the longest prefix of the remaining input that already appears in the dictionary, plus one new symbol. Section 13.4: the number of phrases $c (n)$ satisfies $c (n) lo g c (n) / n \to H (X)$ for stationary ergodic sources, establishing universality.
Lempel, A. & Ziv, J. — On the Complexity of Finite Sequences · IEEE Transactions on Information Theory 22(1):75-81 (1976). Introduces the Lempel-Ziv complexity measure $c (n)$ counting the number of distinct phrases in a sequential parsing of a string; proves that for a stationary ergodic source the normalised complexity $c (n) lo g c (n) / n$ converges to the entropy rate $H (X)$ , providing a universal compressor that needs no prior knowledge of the source distribution.
Wyner, A. D. & Ziv, J. — Some Asymptotic Properties of the Lempel-Ziv Algorithm · IEEE Transactions on Information Theory 35(6):1252-1259 (1989). Sharpens the convergence rate of the LZ78 compression ratio to the entropy rate; shows that the redundancy vanishes as $O (lo g lo g n / lo g n)$ for memoryless sources and establishes the relationship between Lempel-Ziv complexity and the orbit of the shift transformation.
Rissanen, J. — Generalized Kraft Inequality and Arithmetic Coding · IBM Journal of Research and Development 20(3):198-203 (1976). Introduces arithmetic coding as a practical alternative to Huffman coding; shows that encoding by recursively bisecting the unit interval achieves an expected codeword length within two bits of the entropy, independent of the alphabet size.

Estimated time

beginner: 15m
intermediate: 40m
master: 90m