Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy

Question

Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense of HOW the two scale as you increase entropy? Is this a silly question because I'm missing some piece of the puzzle?

Answer 1

This is my (somewhat unorthodox) answer to the comparison between Huffman. Huffman and arithmetic codings. A Huffman code is only optimal if the frequency of the letters in the input alphabet are $2^{-k}$, for an integer $k$. Otherwise, there are internal nodes in the coding tree whose children have different weights. As a result, the output bit stream does not have an entropy of 1 bin/output bit.

One solution is to combine the input letters into groups and enlarge the alphabet. For example, instead of coding a byte stream (as is usually done), you can combine two bytes into a word and use a larger coding tree for the combined alphabet. The problem is that the size of the tree (e.g. instead of $2^8$ entries, now you have to deal with $2^{16}$ entries). And this is just the beginning.

One may view the arithmetic coding as taking this idea to the extreme. Instead of combining two input letters, here we combine all of them. Of course, now the coding tree is huge and cannot be explicitly built. The details of arithmetic coding deals with generating and traversing a virtual Huffman tree for this combined alphabet.

Answer 2

A Hufman code associates an "integer" number of bits to each message: on some distributions this can sum up to a linear cost in the number of messages being sent (hence the $1$ in the $n(1+H)$ upper bound for the size of the sequence of bits produced.

My understanding is that arithmetic codes overcome this weakness, at the cost of a more complex algorithm to compute the codes, and encoding tables (disclaimer: I am rusty on this, anyone should feel free to correct or complete), reaching $nH+O(1)$.

The difference between $n(1+H)$ and $nH+O(1)$ is more sensible for $H$ small of course, so arithmetical codes are prefered for low entropy distribution, if there are no constaints on the cost of encoding/decoding.