Huffman codes

Optimality

The optimality of the Huffman code hinges upon the following two properties of optimal prefix-free codes:

• Shorter codewords are assigned to more probable symbols.
• There exists an optimal code in which the codewords assigned to the two smallest probabilities are siblings.

Let us prove the first statement by contradiction. Let us suppose that $l_{1}<l_{2}$ instead for some symbols $x_{1},x_{2}$ such that $p_{1}<p_{2}$. If we calculate the expected length due to all symbols, $x_{1}$ and $x_{2}$ will contribute the term $p_{1}l_{1}+p_{2}l_{2}$. We proceed by showing the term obtained by swapping the assignment, $p_{1}l_{2}+p_{2}l_{1}$, is strictly lower.

$(p_{1}l_{2}+p_{2}l_{1})-(p_{1}l_{1}+p_{2}l_{2})=(p_{1}-p_{2})(l_{2}-l_{1})<0,$

since $p_{1}<p_{2}$ and $l_{1}<l_{2}$. This contradicts the supposed optimality of the code, and so it must be the case that $l_{1}\geq l_{2}$ whenever $p_{1}<p_{2}$.

We only outline the proof for the second statement. First, we must note that there must be at least two codewords which are siblings of each other. Otherwise, we can "trim" the tree by moving up a codeword by one level. Next, we can use the first statement to perform an exchange argument that will give the desired property.

Construction

The construction of a Huffman code is very much aligned with the two properties discussed in the previous section. We initialize the algorithm by forming one node for each symbol with an associated probability. As an example, consider the following distribution over the alphabet $\{a,b,c,d,e\}$:

$x$	$a$	$b$	$c$	$d$	$e$
$p(x)$	0.02	0.22	0.32	0.25	0.19

In the previous section, we learned that there exists an optimal prefix-free code where in the two least probable codewords are siblings. Using our example, there is an optimal prefix-free code where $a$ and $e$ are siblings. As we construct our Huffman code, we merge nodes into "supernodes" with the following properties:

• the supernode will represent the union of symbols of its constituent nodes,
• the supernode will have an associated probability equal to the sum of the probabilities of its constituent nodes.

The general construction of a $D$-ary Huffman code proceeds as follows:

• If there is only one node left, stop.
• Otherwise, merge the $D$ least probable nodes. If there are less than $D$ nodes left, merge all of them.

The figure below summarizes how a Huffman tree is constructed from the source symbols.

Upper bound on Expected Length

We previously saw that the expected length of uniquely decodable codes is bounded below by $H_{D}(X)$, which is the entropy of $X$ using base-$D$ logarithms. In this section, we will show that Huffman codes are bounded above by $H_{D}(X)+1$. The proof will proceed as follows:

• We start with a set of codeword lengths and appeal to Kraft's inequality to argue that a prefix-free code exists.
• Then, we show that the expected length of this (possibly suboptimal) code is less than $H_{D}(X)+1$.

Consider a prefix-free code with lengths $\{l_{i}\}$, where $l_{i}=\lceil -\log _{D}p_{i}\rceil$, where $\lceil \cdot \rceil$ is the ceiling function. Then,

$-\log _{D}p_{i}\leq l_{i}<-\log _{D}p_{i}+1$

Exponentiating all sides, we get $p_{i}\geq D^{-l_{i}}>D^{-1}p_{i}$, which nicely sets us up for Kraft's inequality:

$\sum _{i}D^{-l_{i}}\leq \sum _{i}p_{i}=1$.

Since the codeword lengths satisfy Kraft's inequality, the existence of the prefix-code is guaranteed. Let us now calculate the expected length of this code.

$L=\sum _{i}p_{i}l_{i}<\sum _{i}p_{i}(-\log _{D}p_{i}+1)=\sum _{i}p_{i}-\sum _{i}p_{i}\log _{D}p_{i}=1+H_{D}(X).$

The reader is now enjoined to complete the proof by answering the questions below.

Checkpoint: How does the conclusion follow from the above statement? What is the relation between a Huffman encoder and the prefix-free code constructed above?

It turns out that a Huffman code will only attain the entropy bound if and only if the random variable $X$ follows a $D$-adic distribution, i.e., every probability $p_{i}$ is a perfect power of $D$. Otherwise, the Huffman code will fail to "fully" compress information without redundancy.

Achieving Shannon's limit

Using Huffman codes to encoder every single symbol from ${\mathcal {X}}$ can potentially incur a large penalty since the expected length can be at most 1 D-ary digit away from the entropy bound (using base-$D$ logarithm). If we group symbols together $n$ at a time, we can achieve the Shannon limit to arbitrary precision.

The idea behind achieving Shannon's compression limit is to use a larger source alphabet. If take $n$ symbols at a time and create a Huffman code, we are essentially using the larger input alphabet ${\mathcal {X}}^{n}$. Using the bounds for Huffman code, the expected length $L_{n}$ is given by

$H_{D}(X^{n})\leq L_{n}<H_{D}(X^{n})+1$.

Here, $L_{n}$ accounts for the encoding of a block of $n$ symbols. We can normalize the inequality and obtain a tighter expression:

${\frac {1}{n}}H_{D}(X^{n})\leq L_{n}<{\frac {1}{n}}[H_{D}(X^{n})+1]$.

Since we are encoding $n$ independent and identically distributed symbols at a time, the joint entropy $H(X^{n})=nH(X)$. Hence,

$H_{D}(X)\leq {\frac {1}{n}}L_{n}<H_{D}(X)+{\frac {1}{n}}$,

where the upper bound can be made to approach $H_{D}(X)$ by letting $n$ be sufficiently large.

The proof above is representative of many arguments in information theory that take the blocklength $n$ to arbitrarily large values. In that respect, we can look at $H(X)$ as an asymptotic compression limit. However, it is also important to keep in mind that directly applying the above construction is very impractical. If we take the English alphabet, with 26 letters, and group them five-at-a-time, then the effective alphabet blows up quickly to above 10 million! Fortunately, more modern coding schemes exist that approach the entropy bound without the heavy exponential overhead. The interested student is encouraged to look up "arithmetic coding."