Source Coding and Compression

Entropy is the theoretical lower bound for lossless compression—no encoding’s expected code length can escape H(X). Kraft’s inequality governs whether prefix codes can exist, Huffman greedily approximates it, and arithmetic coding nearly touches the entropy rate. The deepest insight is this: language models are compression; the cross-entropy loss of a perfect LLM is an estimate of the data’s entropy rate.

Introduction: Who is Compression Really Fighting?

The number entropy H(X) has appeared repeatedly in the first two chapters. It has been described as "the average number of questions to ask" or "the average number of bits to spend." This chapter turns that abstraction into something concrete: compression.

The task is simple: encode a sequence of symbols into binary, minimizing the average code length, while ensuring perfect (lossless) reconstruction. The question is: how short can we go? Is there a wall that no one can climb over?

Yes. That wall is entropy. This chapter clarifies three things: where the wall is (the source coding theorem), how to build codes to approach it (Huffman and arithmetic coding), and why "language models" and "compressors" are essentially the same thing.

Prefix Codes and Kraft’s Inequality

First, let’s address "whether unambiguous decoding is possible." The most practical class of codes is prefix codes: no codeword is a prefix of another. This allows the decoder to split the stream immediately upon reading a complete codeword, without needing any delimiters.

Which combinations of code lengths can form a prefix code? Kraft’s inequality provides the necessary and sufficient condition: for a binary prefix code with code lengths l_1, l_2, \ldots, l_n, such a code exists if and only if

\sum_i 2^{-l_i} \leq 1

Intuition: Think of codewords as leaves on a binary tree. A codeword of length l_i occupies a proportion 2^{-l_i} of the "code space." The total occupancy cannot exceed 1, otherwise codeword collisions are inevitable.

This inequality also quietly tells us something: if you want some codewords to be shorter (reduce l_i), you must make others longer. Code lengths are zero-sum—if it’s shorter in one place, it must be compensated elsewhere.

Shannon’s Source Coding Theorem: Entropy as the Lower Bound

Shannon’s Source Coding Theorem (lossless) states that for any uniquely decodable code, the expected code length L satisfies

L \geq H(X)

Moreover, there always exists a code such that H(X) \leq L < H(X) + 1.

This statement has two layers. The first: Entropy is the hard lower bound for lossless compression; no one can compress below entropy. The second: this lower bound is almost achievable—the gap of +1 can be diluted to an arbitrarily small amount by "grouping multiple symbols together before encoding."

Proof skeleton (worth remembering): Combine Kraft’s inequality with Gibbs’ inequality,

L - H(X) = \sum_x p(x)(l_x + \log_2 p(x)) \geq 0

Equality holds when l_x = -\log_2 p(x)—the ideal code length is self-information.

The trouble is that self-information is usually not an integer, while code lengths must be integers. This "rounding loss" is exactly what Huffman and arithmetic coding are grappling with.

Huffman Coding: Greedy Approximation

Huffman coding uses a greedy process to construct an optimal integer prefix code in terms of expected code length. The rule: repeatedly take the two nodes with the smallest current probabilities, merge them into a parent node (summing their probabilities), until only one root remains; label the two branches with 0 and 1, and the path from root to leaf is the codeword.

The result is naturally: high-frequency symbols are closer to the root with shorter codewords; low-frequency symbols are further away with longer codewords.

In this example, the probabilities happen to be powers of 2. Calculating the expected code length:

L = 0.5\times 1 + 0.25\times 2 + 0.125\times 3 + 0.125\times 3 = 1.75\ \text{bit}

This exactly equals the entropy H = 1.75 bit—perfectly hitting the lower bound.

But this is a special case. Once probabilities are not powers of 2, integer code lengths cannot match the ideal -\log_2 p(x), and Huffman wastes at most 1 bit per symbol. Where does this waste come from? It’s the "rounding loss" from the previous section.

Arithmetic Coding: Escaping Integer Bits

Arithmetic coding directly bypasses Huffman’s integer bottleneck.

Its approach is different: instead of assigning integer codewords to individual symbols, it maps the entire message to a small sub-interval within [0,1). For each symbol read, the current interval is subdivided proportionally according to the symbol’s probability, and the corresponding sub-interval is selected; after reading the entire message, a binary fraction sufficient to uniquely identify that interval is output.

This brings two key advantages:

• No requirement for integer bits. A symbol with probability 0.9 can cost only about 0.15 bits, which Huffman cannot do (it requires at least 1 bit).
• Approaches the entropy rate. For long messages, the average code length can get arbitrarily close to H(X), almost eliminating the +1 gap of Huffman.

There are two costs: computation is more complex than Huffman; and it requires an accurate probability model. Remember the second point—providing an accurate probability model is exactly what language models do, which connects to the next section. Modern practical variants are range coding and ANS (Asymmetric Numeral Systems), the latter being a staple in zstd and LLM compression benchmarks.

Entropy Rate: Dependencies Between Symbols

Up to this point, we have assumed symbols are independent, and H(X) is the entropy of a single symbol. But in real data (text, audio), symbols have strong dependencies, requiring a different measure: entropy rate.

H_\text{rate} = \lim_{n\to\infty} \frac{1}{n} H(X_1, X_2, \ldots, X_n)

It is the average conditional entropy per symbol, accounting for all historical dependencies.

English is the best example. Under the independent single-character assumption, it is about 4.7 bits; considering letter frequencies, it drops to about 4.1; considering context dependencies, Shannon’s estimated entropy rate is only about 1.0–1.3 bits/character. The stronger the dependency, the lower the entropy rate, and the larger the compressible space. All practical compressors (and language models) squeeze out this redundancy.

Language Models Are Compression

Connecting the dots above yields one of the most beautiful equivalences in information theory.

A language model outputs a probability distribution q for each token at every step. If used to drive arithmetic coding, the average code length to compress a piece of text is exactly the cross-entropy H(p,q) of the model on that text (see Cross-Entropy). And the source coding theorem states that the lower bound for this code length is the true entropy rate of the data H_\text{rate}. Thus:

The model’s cross-entropy loss = the bit rate for lossless compression using it. Lower loss = better compression = closer to the data’s entropy rate. A "perfect" language model has a cross-entropy equal to the lower bound of the data’s entropy rate.

This is not a metaphor. Models like GPT / Claude are essentially ultimate lossless compressors. For this reason, the stronger the model, the better it performs on compression benchmarks (such as the Hutter Prize, which targets enwik9 wiki text)—these two things are two sides of the same coin.

BPE at the tokenization layer is also an engineering approximation of this logic: it uses greedy merging to compress high-frequency substrings into single tokens, heuristically reducing the bit cost of the sequence—a coarse-grained entropy optimization. See Tokens and Sampling for BPE algorithm details; here, just remember the connection that "BPE is an engineering approximation of the compression problem." How the compression perspective explains scaling laws is expanded in Information Theory in LLMs.

References

• Paper: "A Mathematical Theory of Communication" (Shannon, 1948 — the original source for the source coding theorem and English entropy rate estimation)
• Textbook: "Elements of Information Theory" (Cover & Thomas — Chapter 5 Data Compression, Kraft/Huffman/Arithmetic Coding)
• Benchmark/Project: "Hutter Prize" and "Language Modeling Is Compression" (Delétang et al., 2023 — using LLMs for lossless compression, empirically showing loss equals bit rate)

Keywords: prefix code, Kraft’s inequality, source coding theorem, Huffman coding, arithmetic coding, ANS, entropy rate, lossless compression, language models are compression, Hutter Prize, BPE