2

I answered a question Calculating entropy Through Huffman Codeword lengths. on this website and then got myself another question. If the alphabet has $5\,$ letters 'A', 'B', 'C', 'D', 'E' occuring with probabilities $\,0.4,\,0.2,\,0.2,\,0.1,\,0.1$, respectively, a letter-by-letter Huffman code gives an average code length of $\,L_1=2.2\,$ bits per letter. This number is greater than the Shannon information

$$S=-\sum_{i=1}^5p_i\log_2p_i=\log_210-1.2=2.1219\mbox{ bits}$$

per letter. My question is: if I group $n$ letters into one word and construct a word-by-word Huffman code, does the average code length per letter $\,L_n/n\rightarrow S\,$ approach Shannon's information content in the $\,n\rightarrow\infty\,$ limit? Is there a proof?

I wrote a C++ program to test this numerically. I assume the occurrence of letters are independent, i.e., the language is a random mixture of the $5$ letters with their individual probabilities. The result is plotted in the graph below:

The average code length $L_n/n$ per letter v.s. the word length $n$

The red dashed line is Shannon's information content $\,S\,$ per letter, which is unbeatable in this model as the letter occurrence is truely random. The blue curve is the average code length $\,L_n/n\,$ per letter of the Huffman tree for $\,n=1,2,\ldots,10$, where $L_n$ is the weighted tree height of the Huffman tree with $5^n$ leaf nodes. The numerical result does not clearly show whether $L_n/n\rightarrow S\;$ or not, as the curve is not monotonic. So a mathematical proof or disproof would be very much appreciated.

Zhuoran He
  • 3,039

1 Answers1

1

Yes, Huffman coding approaches the Shannon limit. This is an immediate consequence of the fact that Huffman coding is optimal, i.e., $L_n$ of your Huffman code is always smaller than (or equal to) the length of any other code (Cover and Thomas, 1991, Theorem 5.8.1).

Now consider the Shannon code and assume that you draw independent realizations of your 5-letter-alphabet. Then, you can assign each length-$n$ sequence $x^n$ a codeword of length $\lceil -\log(\mathbb{P}(X^n=x^n))\rceil$, from which you get that $L^*_n \le nS+1$. Thus, $L^*_n/n\to S$ (Cover and Thomas, 1991, Theorem 5.4.2). Since the Huffman code will be at least as good, you will also get $L_n/n\to S$.

Bernhard
  • 1,134
  • Huffman coding is a word-to-word system. Theoretically, there are context-dependent codes that outperform it. It is best among the word-to-word codes, while Shannon's limit is the best of all possible codes. Increasing the word length helps mitigate the shortcoming of Huffman. There are two limits here that cannot be swapped. The total length of the message goes to infinity first, and then the word length goes to infinity. But still, the $L_n\leq nS+1$ upper bound answers the question. How is it derived (give me a reference)? – Zhuoran He Oct 16 '17 at 17:33
  • You find the derivation in Cover and Thomas' book "Elements of Information Theory", first edition from 1991, Chapter 5. – Bernhard Oct 17 '17 at 14:41