Source Coding and Compression

Entropy is the theoretical lower bound for lossless compression—no coding scheme can achieve an expected code length below H(X). The Kraft inequality determines whether prefix codes can exist, Huffman coding greedily approaches this bound, and arithmetic coding nearly reaches the entropy rate. Language models provide probabilistic predictions, which, when paired with an entropy encoder, form a compression system; the model’s cross-entropy corresponds to its ideal average code length on the data.

Introduction: Who is Compression Fighting Against?

The number entropy H(X) has appeared repeatedly in the previous two chapters. It has been described as "the average number of questions to ask" or "the average number of bits required." This chapter turns that abstract concept 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 the Kraft 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 immediately split the stream upon reading a complete codeword, without needing any delimiters.

Which combinations of codeword lengths can form a prefix code? The Kraft inequality provides a necessary and sufficient condition: for a binary prefix code with 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 a zero-sum game—shorter lengths somewhere must be compensated for 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)

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

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

Proof skeleton (worth remembering): Combining the Kraft 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 the 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 struggling with.

Huffman Coding: Greedy Approximation

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

The result is naturally: high-frequency symbols are closer to the root with shorter codewords; low-frequency symbols are further from the root 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{bits}

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

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

Arithmetic Coding: Escaping Integer Bits

Arithmetic coding directly bypasses Huffman's integer bottleneck.

Its approach is quite 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 its 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).
• Approaching the entropy rate. For long messages, the average code length can approach H(X) arbitrarily closely, almost eliminating the +1 gap of Huffman coding.

There are two costs as well: 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 include range coding and ANS (Asymmetric Numeral Systems), the latter being a common feature 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. However, in real data (text, audio), symbols have strong dependencies, so we need a different measure: entropy rate.

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

For common stationary sources, it also equals the average conditional entropy under infinite history, accounting for dependencies between symbols. The limit and equivalence here require conditions like stationarity; for a personal knowledge base, it suffices to remember the intuition of "how much unpredictability remains per symbol in the long run."

English is the best example. Under the assumption of independent single characters, it is about 4.7 bits; considering letter frequencies, it drops to about 4.1; further 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.

AEP and the Typical Set: Why Long Sequences Approach Entropy

The ideal code length for a single symbol, -\log_2p(x), is often not an integer. Why does the average code length approach entropy when sequences are lengthened? Connecting these two concepts is the Asymptotic Equipartition Property (AEP).

For long sequences X^n=(X_1,\ldots,X_n) generated by an i.i.d. source, with high probability we observe:

-\frac{1}{n}\log_2 p(X^n)\approx H(X)

That is, most of the probability mass is concentrated in a set of typical sequences. There are approximately 2^{nH(X)} such sequences, each with a probability of about 2^{-nH(X)}. Therefore, only about nH(X) bits are needed to index the typical sequences; the few atypical sequences are handled separately, and their additional cost is diluted as n increases.

This is the reason behind "single symbols can only achieve H\leq L<H+1, while long blocks can compress the per-symbol code length to H." For stationary ergodic sources with dependencies, the same intuition is governed by the entropy rate. The AEP also explains why the subsequent Channel Coding Theorem always discusses long codewords and asymptotic limits.

How Language Models Connect to Compression

Connecting the chain 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 ideal code length for a piece of text is the sum of -\log_2q(x_i\mid x_{<i}) per token; ignoring finite precision and tail overheads, the average code length per token is the cross-entropy of the model on that text (see Cross-Entropy). And the source coding theorem states that the lower bound of this code length is the true entropy rate of the data H_\text{rate}. Thus:

The model's cross-entropy loss corresponds to the ideal compression bit rate when used as a probabilistic model. Lower loss = better prediction = typically better compression when paired with an entropy encoder. If the model exactly matches the data distribution, its cross-entropy reaches the data's entropy rate.

This is not just a metaphor, but roles must be distinguished: language models provide probabilities, while arithmetic coding / ANS converts probabilities into reconstructible bitstreams. The decoder must also share the same model, and the storage and transmission costs of the model weights must be accounted for; only after amortizing over large amounts of data can this fixed cost be approximately ignored. Therefore, predictive capability and compression capability are highly correlated, but they cannot be unconditionally equated in every scenario.

The BPE at the tokenization layer also carries the lineage of compression algorithms: it greedily merges high-frequency adjacent symbols, allowing common fragments to be represented with fewer tokens. However, shorter sequences do not necessarily mean lower information content per byte—vocabulary size, token probabilities, and model capabilities also change. More accurately, BPE makes engineering trade-offs between sequence length, vocabulary size, and learnability. Algorithmic details are in Tokens and Sampling, and how the compression perspective helps understand scaling laws is expanded in Information Theory in LLMs.

References

• Paper: "A Mathematical Theory of Communication" (Shannon, 1948 — the original source of 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 inequality, source coding theorem, Huffman coding, arithmetic coding, ANS, entropy rate, AEP, typical set, lossless compression, language models and compression, Hutter Prize, BPE