Formal Math behind the use of Huffman Coding

Once, in a show and tell session with my peers and seniors at the Innovation Lab, one of them pointed out that the Huffman Coding is often paired with other coding algorithms. Ofcourse, we all agreed on the fact that it is to achieve better compression ratios, but I wondered: Is there are a formal way to prove it?

Proving the Huffman coding algorithm¶

Note: You could read this part from the textbook! If so, you can jump straight to here

1. Representing Codes as Trees¶

Before we get to the proof, let's establish a few details about Huffman's prefix code tree.

In data compression, a prefix code is a code where no codeword is a prefix of any other codeword. This property is great because it means we can decode a continuous bitstream without needing special delimiter characters or lookahead. A common way to achieve this is by representing any binary prefix code as a full binary tree, where:-

• Leaves represent the characters in our alphabet $C$.
• The path from the root to a leaf specifies the code for that letter: going left corresponds to 0, and going right corresponds to 1.
• The depth of leaf $c$ in tree $T$, denoted by $d_T(c)$, is the length of the code for character $c$.

Let $p(c)$ be the probability of character $c$ occurring (where $\sum_{c \in C} p(c) = 1$).

The expected (average) number of bits per character using tree $T$, called the cost of the tree $L(T)$, is:

$$L(T) = \sum_{c \in C} p(c) \cdot d_T(c)$$

Our goal here with Huffman's algorithm is simple: Find a full binary tree $T$ that minimizes $L(T)$.

2. Lemma 1: The Greedy-Choice Property¶

Huffman's greedy strategy is basically: pick the two characters with the lowest probabilities and merge them first.

Intuitively, characters that appear least should have the longest codewords (i.e., sit deepest in the tree). But does making this greedy choice at the very first step keep us on the path to an optimal tree?

Lemma 16.2 (CLRS, altered): Let $C$ be an alphabet where each character $c \in C$ has probability $p(c)$. Let $x$ and $y$ be two characters in $C$ with the lowest probabilities. Then there exists an optimal prefix code for $C$ in which the codewords for $x$ and $y$ have the same length and differ only in the last bit (meaning $x$ and $y$ are sibling leaves at maximum depth in the code tree).

Proof¶

Let $T$ be an arbitrary optimal prefix code tree.

Since $T$ is a full binary tree, it must have at least two sibling leaves at maximum depth. Let these siblings be $a$ and $b$.

Without loss of generality, let us assume that: $$p(a) \le p(b) \quad \text{and} \quad p(x) \le p(y)$$

Since $x$ and $y$ are the two characters with the lowest probabilities in the entire alphabet $C$, we know that: $$p(x) \le p(a) \quad \text{and} \quad p(y) \le p(b)$$

Now, let's swap the positions of $x$ and $a$ in $T$ to create a new tree $T'$.

$$\begin{aligned} L(T) - L(T') &= \sum_{c \in C} p(c) \cdot d_T(c) - \sum_{c \in C} p(c) \cdot d_{T'}(c) \\ &= p(x) d_T(x) + p(a) d_T(a) - p(x) d_{T'}(x) - p(a) d_{T'}(a) \end{aligned}$$

Since $d_{T'}(x) = d_T(a)$ and $d_{T'}(a) = d_T(x)$:

$$\begin{aligned} L(T) - L(T') &= p(x) d_T(x) + p(a) d_T(a) - p(x) d_T(a) - p(a) d_T(x) \\ &= (p(a) - p(x))(d_T(a) - d_T(x)) \end{aligned}$$

Notice that:

1. $p(a) \ge p(x)$ (because $x$ has the minimal probability), so $(p(a) - p(x)) \ge 0$.
2. $d_T(a) \ge d_T(x)$ (because $a$ is at the maximum depth of the tree), so $(d_T(a) - d_T(x)) \ge 0$.

Since both factors are non-negative, their product is non-negative:

$$L(T) - L(T') \ge 0 \implies L(T') \le L(T)$$

Next, in tree $T'$, swap $y$ with $b$ to produce tree $T''$. Using the exact same argument,

$$L(T') - L(T'') = (p(b) - p(y))(d_{T'}(b) - d_{T'}(y)) \ge 0 \implies L(T'') \le L(T')$$

We combine these inequalities:-

$$L(T'') \le L(T') \le L(T)$$

Because $T$ was already an optimal tree, $L(T)$ is the minimum possible cost, meaning $L(T'') = L(T)$.

Thus, $T''$ is also an optimal prefix code tree, and in $T''$, $x$ and $y$ are sibling leaves at maximum depth! $\blacksquare$

3. Lemma 2: Optimal Substructure¶

Now that we know merging the two lowest-probability characters is a safe greedy move, what happens when we replace them with a single combined node and solve the smaller problem?

Lemma 16.3 (CLRS, modified): Let $C$ be an alphabet with probabilities $p(c)$. Let $x, y \in C$ be two characters with minimum probabilities. Let $C'$ be the alphabet $C$ with $x$ and $y$ replaced by a single new character $z$: $$C' = (C \setminus {x, y}) \cup {z}$$ where $p(z) = p(x) + p(y)$.

Let $T'$ be any tree representing an optimal prefix code for $C'$. Then the tree $T$, obtained from $T'$ by replacing the leaf $z$ with an internal node having children $x$ and $y$, represents an optimal prefix code for the alphabet $C$.

Proof¶

Let's first find the mathematical relation between the cost of $T$ and the cost of $T'$.

For any character $c \in C \setminus {x, y}$, its depth in $T$ is the same as in $T'$ ($d_T(c) = d_{T'}(c)$).

For $x$ and $y$, they are children of $z$, so: $$d_T(x) = d_T(y) = d_{T'}(z) + 1$$

Computing $L(T)$:

$$\begin{aligned} L(T) &= \sum_{c \in C} p(c) \cdot d_T(c) \\ &= \sum_{c \in C \setminus {x, y}} p(c) \cdot d_T(c) + p(x) \cdot d_T(x) + p(y) \cdot d_T(y) \\ &= \sum_{c \in C'} p(c) \cdot d_{T'}(c) - p(z) \cdot d_{T'}(z) + p(x)(d_{T'}(z) + 1) + p(y)(d_{T'}(z) + 1) \\ &= L(T') - (p(x) + p(y))d_{T'}(z) + (p(x) + p(y))(d_{T'}(z) + 1) \\ &= L(T') + p(x) + p(y) \end{aligned}$$

Rearranging them will give:- $$L(T') = L(T) - p(x) - p(y)$$

Now, we prove that $T$ is optimal for $C$ by contradiction:

Suppose $T$ is not optimal for $C$. Then there must exist some tree $T''$ for $C$ such that: $$L(T'') < L(T)$$

By Lemma 1, there exists an optimal tree where $x$ and $y$ are sibling leaves. Without loss of generality, assume $x$ and $y$ are siblings in $T''$.

Let $T'''$ be the tree obtained from $T''$ by replacing $x, y$ and their parent with a single leaf $z$ (where $p(z) = p(x) + p(y)$). Then $T'''$ is a valid prefix code tree for $C'$, and its cost is:

$$L(T''') = L(T'') - p(x) - p(y)$$

Since $L(T'') < L(T)$,

$$L(T''') = L(T'') - p(x) - p(y) < L(T) - p(x) - p(y) = L(T')$$

$$\implies L(T''') < L(T')$$

This contradicts our original assumption that $T'$ is an optimal prefix code tree for $C'$!

Therefore, $T$ must be an optimal prefix code tree for $C$. $\blacksquare$

4. Theorem: Correctness of Huffman's Algorithm¶

With Lemma 1 (Greedy-Choice) and Lemma 2 (Optimal Substructure) established, the overarching theorem follows directly by mathematical induction on the size of the alphabet $|C|$.

Theorem 16.4 (CLRS): Huffman's algorithm produces an optimal prefix code.

• Base Case ($|C| = 2$): The algorithm creates a root with two leaves, assigning 1 bit (0 and 1) to each. Both characters have depth 1, so the expected cost is $L(T) = p(x)\cdot 1 + p(y)\cdot 1 = 1$ bit per character, which is trivially optimal.
• Inductive Step: Assume the algorithm produces an optimal prefix tree for any alphabet of size $n - 1$. Given an alphabet $C$ of size $n$, the algorithm greedily merges the two lowest-probability characters $x$ and $y$ into a single node $z$ with $p(z) = p(x) + p(y)$, reducing the problem to an alphabet $C'$ of size $n - 1$. By the induction hypothesis, the recursive step produces an optimal tree $T'$ for $C'$. By Lemma 2, expanding $z$ back into $x$ and $y$ produces an optimal tree $T$ for $C$.

By induction, Huffman Coding is guaranteed to produce an optimal prefix code for any alphabet! $\blacksquare$

Why Pair Huffman Coding with Other Algorithms?¶

The main question I wanted to answer myself was: if Huffman is proven optimal, why do we almost always pair it with algorithms like LZ77 (DEFLATE) or Burrows-Wheeler Transform (bzip2)?

The answer is that Huffman is optimal only for a memoryless, 0-th order source. Let's try to formally prove why standalone Huffman coding has a mathematical gap on real-world data and how pairing it with another algorithm closes this gap.

1. Marginal Entropy vs. The Entropy Rate¶

Let a source be modeled as a discrete stochastic process $\mathcal{X} = {X_1, X_2, \dots, X_n, \dots}$ where each symbol $X_i$ takes values from an alphabet $C$.

• Marginal (0-th order) Shannon Entropy: The average uncertainty of a single symbol in isolation: $$H(X) = - \sum_{c \in C} P(X = c) \log_2 P(X = c)$$

• Joint Entropy of $n$ symbols: $$H(X_1, X_2, \dots, X_n) = - \sum_{x_1, \dots, x_n \in C^n} P(x_1, \dots, x_n) \log_2 P(x_1, \dots, x_n)$$

• Entropy Rate $\mathcal{H}(\mathcal{X})$: For a stationary stochastic process, the true lower bound on the average number of bits per symbol is: $$\mathcal{H}(\mathcal{X}) = \lim_{n \to \infty} \frac{1}{n} H(X_1, X_2, \dots, X_n) = \lim_{n \to \infty} H(X_n \mid X_{n-1}, \dots, X_1)$$

2. Lemma: Conditioning Reduces Entropy¶

Lemma: For any two discrete random variables $X$ and $Y$, $$H(X \mid Y) \le H(X)$$ with equality if and only if $X$ and $Y$ are statistically independent ($I(X; Y) = 0$).

Proof¶

Let us recall the definition of Mutual Information $I(X; Y)$ and the Kullback-Leibler (KL) Divergence:

$$I(X; Y) = H(X) - H(X \mid Y) = D_{\text{KL}}\big(P(X, Y) \parallel P(X)P(Y)\big)$$

Where, the KL Divergence is defined as

$$D_{\text{KL}}\big(P(X, Y) \parallel P(X)P(Y)\big) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} P(x, y) \log_2 \left( \frac{P(x, y)}{P(x)P(y)} \right)$$

Using the inequality $\ln(t) \le t - 1$ for all $t > 0$ (or equivalently, applying Jensen's inequality to the strictly convex function $-\log_2(t)$):

$$\begin{aligned} - D_{\text{KL}}\big(P(X, Y) \parallel P(X)P(Y)\big) &= \sum_{x, y} P(x, y) \log_2 \left( \frac{P(x)P(y)}{P(x, y)} \right) \\ &\le \frac{1}{\ln 2} \sum_{x, y} P(x, y) \left( \frac{P(x)P(y)}{P(x, y)} - 1 \right) \\ &= \frac{1}{\ln 2} \left( \sum_{x, y} P(x)P(y) - \sum_{x, y} P(x, y) \right) \\ &= \frac{1}{\ln 2} (1 - 1) = 0 \end{aligned}$$

Thus: $$D_{\text{KL}}\big(P(X, Y) \parallel P(X)P(Y)\big) \ge 0 \implies I(X; Y) \ge 0$$

$$\implies H(X) - H(X \mid Y) \ge 0 \implies H(X \mid Y) \le H(X) \quad \blacksquare$$

By applying the Chain Rule of Entropy repeatedly,

$$H(X_n \mid X_{n-1}, \dots, X_1) \le H(X_n \mid X_{n-1}) \le H(X_n) = H(X)$$

And taking the limit $n \to \infty$,

$$\mathcal{H}(\mathcal{X}) \le H(X)$$

Thus, whenever consecutive symbols have statistical dependencies ($I(X_i; X_{i-1}) > 0$), we have the strict inequality:

$$\mathcal{H}(\mathcal{X}) < H(X)$$

3. The Structural Sub-optimality Gap of Standalone Huffman¶

By Shannon's Source Coding Theorem, any prefix code operating symbol-by-symbol on the marginal alphabet $C$ has an expected codeword length $\bar{L}_{\text{symbol}}$ bounded by:

$$H(X) \le \bar{L}_{\text{symbol}} < H(X) + 1$$

Since standalone Huffman codes each symbol $X_i$ purely based on its marginal frequency $P(X_i = c)$, its asymptotic per-symbol bit rate has a lower-bound of $H(X)$.

Consequently, the excess per-symbol redundancy ($\Delta$) of standalone Huffman coding on data with memory is strictly non-zero:

$$\Delta = \lim_{n \to \infty} \left( \bar{L}_{\text{symbol}} - \mathcal{H}(\mathcal{X}) \right) \ge H(X) - \mathcal{H}(\mathcal{X}) > 0$$

This formally proves that no 0-th order Huffman code can ever reach the true compression bound $\mathcal{H}(\mathcal{X})$ for correlated data.

4. Why Not Just Build a $k$-Block Huffman Code?¶

To capture dependencies of length $k$, one could group characters into blocks of length $k$: $W = (X_1, X_2, \dots, X_k) \in C^k$.

Shannon proved that the expected length per source symbol $\frac{1}{k} \bar{L}_k$ satisfies:

$$\frac{1}{k} H(X_1, \dots, X_k) \le \frac{1}{k} \bar{L}_k < \frac{1}{k} H(X_1, \dots, X_k) + \frac{1}{k}$$

As $k \to \infty$, $\frac{1}{k} H(X_1, \dots, X_k) \to \mathcal{H}(\mathcal{X})$, so the per-symbol rate converges to the optimal entropy rate:

$$\lim_{k \to \infty} \frac{1}{k} \bar{L}_k = \mathcal{H}(\mathcal{X})$$

However, the alphabet of $k$-blocks has size $|C|^k$. - The time complexity to build the Huffman tree is $O(|C|^k \log |C|^k) = O(k |C|^k \log |C|)$. - The size of the codebook table to be stored or transmitted is $O(|C|^k)$.

For a standard byte alphabet ($|C| = 256$), even a context of $k = 4$ requires an alphabet of size:

$$256^4 = 4{,}294{,}967{,}296 \text{ symbols}$$

Generating and transmitting a tree with 4.3 billion leaves is computationally intractable.

And the Solution to this problem? Two-Stage Pipeline Optimality¶

To bypass the exponential state explosion of $k$-block Huffman while bridging the gap $\Delta = H(X) - \mathcal{H}(\mathcal{X})$, modern compression pipelines decouple the task into two sequential stages:

1. Structure & Context Decorrelation A deterministic reversible transformation $f: C^n \to \Omega^m$ (such as LZ77 dictionary parsing) maps the sequence $X_{1:n}$ to a sequence of tokens $Y_{1:m}$ such that the inter-symbol mutual information is minimized: $$I(Y_i; Y_{i+1}) \approx 0 \implies \mathcal{H}(Y) \approx H(Y)$$ By the Lempel-Ziv asymptotic optimality theorem, the token representation rate satisfies: $$\lim_{n \to \infty} \frac{m}{n} H(Y) = \mathcal{H}(\mathcal{X})$$

2. Optimal 0-th Order Coding Because the token stream $Y$ is now effectively memoryless ($I(Y_i; Y_{i+1}) \to 0$), Huffman Coding operates on the compact alphabet $\Omega$ (where $|\Omega| \ll |C|^k$) with optimal per-token cost: $$H(Y) \le \bar{L}_{\text{Huffman}}(Y) < H(Y) + 1$$

Multiplying by the token production rate $\frac{m}{n}$:

$$\lim_{n \to \infty} \frac{1}{n} \text{Total Bits} = \lim_{n \to \infty} \frac{m}{n} \bar{L}_{\text{Huffman}}(Y) = \mathcal{H}(\mathcal{X})$$

Conclusion¶

Thus, we can say that Huffman coding is provably optimal for converting independent symbol frequencies into minimum-length prefix codes. However, because it cannot capture inter-symbol dependencies without exponential alphabet explosion ($|C|^k$), it is often paired with a context-decorrelating front-end (like LZ77 or BWT).

The front-end removes the memory, and Huffman compresses the resulting memoryless distribution to the theoretical limit $\mathcal{H}(\mathcal{X})$. $\blacksquare$