Maximum size of Huffman codes for an alphabet containing 256 letters

Question

I made a Huffman algorithm for data compression: it takes the content of a file as an input and outputs a compressed string. More important, it generates optimal prefix codes (made of 0 and 1) for every possible character, that is to say for every number between 0 and 255.

While the size of a code cannot exceed 256, it is possible to encode every character with a code of size 8 at most.

However, it is impossible that the algorithm generates a code of size 256 because then the codes wouldn't be optimal. It will give to the most likely chars, codes of size < 8 and it will give codes of size > 8 to the others (intuitively).

My question thus is, how can we get an upper bound of the maximum size a code can have, better than 256? I don't see how to approach the problem.

PS: the upper bound I'm looking for doesn't depend on the probability distribution. It has to be an upper bound for every possible probability distribution. As I said, I doubt that there is a probability distribution for which there is a code of size 256, so there has to be an upper bound.

I think I found the solution: For an alphabet of size $n$, the longest possible code is of size $n-1$, so here the answer is 255. So I was actually wrong in my intuition. You just need to arrange the weights so that each one is at least twice as much as the precedent and you get a Huffman tree which outputs a code of maximal size.

Answer 1

I don't see how to approach the problem.

OK, here is how you can approach the problem. Can you solve this problem if you replace the number 256 with the number 3? How about 4? 5? Try solving those special cases, then see if you spot a pattern...

This is a useful, general pattern. When a problem is too hard, try to find a simpler version of it and think about that. When you see a constant in the problem, try solving simpler versions where the constant is smaller (so the problem becomes easier to think about), then look for a pattern, try to generalize, form a hypothesis, and see if you can prove your hypothesis.

Answer 2

The maximum possible code size for a 256 symbol alphabet is 256 bits. Consider the case when the most frequent symbol has frequency 1/2, the next most frequent symbol has frequency 1/4, then 1/8 ....

This get encoded as:

1
01
001
0001
...
<255 0 bits>1

Answer 3

In theory, 256 characters can have probabilities $2^{-1}$, $2^{-2}$, ..., $2^{-255}$, $2^{-255}$ (yes, the last one is $2^{-255}$, not $2^{-256}$), so there could be two codes of 255 bits.

In practice, if you compress let's say a document of 1 Gigabyte, no character can have a probability less than $2^{-30}$, so the maximum length would be 30 bits.

And again in practice, you can make a decoder faster if it has a limited maximum number of bits, say 14. That's called "length limited Huffman codes". There's a rather complicated algorithm that can be given the maximum length l of any code that you want to achieve (obviously ≥ 8 for 256 codes), and it will calculate the optimal codes under that restriction. Obviously not optimal globally, but usually very close, if you limit the length to 14 bits, for example.

Answer 4

The maximum size of the code should be the size of the code for the least probable symbol.

PS: The above answer was before the question was clarified, and is still accurate for any one probability distribution. CWallach's answer describes a probability distribution that results in the longest code of any possible probability distribution.

The key is the resulting Huffman tree has to be as unbalanced as possible. This happens when every internal node generated has a probability less than or equal to the lowest probability leaf node in the queue.