# Is Huffman Encoding always optimal?

The requirement of the encoding to be prefix free results in large trees due to the tree having to be complete. Is there a threshold where fixed-length non-encoded storage of data would be more efficient than encoding the data?

• In general 'no'. For an average data, frequency of each character would be >1 and its good to use Huffman Encoding rather than fixed-length codes
– arunmoezhi
Aug 7 '12 at 1:30
• @arunmoezhi Could you please address the example I have provided above? Frequency of each character is greater than 1, yet fixed-length is more optimal.
– user1422
Aug 9 '12 at 16:17
• This example is interesting. But can you provide such a scenario with the probabilities of each character instead of frequency and make sure the probabilities of all characters add to 1
– arunmoezhi
Aug 9 '12 at 18:59
• @arunmoezhi I have included the probabilities of the characters and they do add up to 1.
– user1422
Aug 9 '12 at 19:32
• @arunmoezhi - doesn't in general no mean in theory yes? That there would be possible cases, for very small and mostly unique data inputs, where the fixed length encoding would be more efficient than Huffman encoded - say the English alphabet encoded in ASCII (26(8) bits) vs Huffman encoded, along with the tree to decode back to ascii (6(4)+20(5) bits for encoded data + at least 6(12) + 20(13) bits for the tree) Dec 3 '20 at 21:17

The entropy H(A) for this problem is 1.998. Both Huffman coding and fixed length coding for this problem has avg codeword length as 2. And FYI the coding you have got using Huffman Encoding is wrong. Huffman Encoding also produces codes similar to fixed length for this problem. It uses greedy approach. So a doesn't get a code as 0 but instead it gets 00. Rework on the tree you generate using Huffman Coding. The tree you should get is:

• Thank You. Could you provide some kind of proof that Huffman Encoding is always more optimal than fixed length, or atleast refer me to one?
– user1422
Aug 9 '12 at 20:56
• You can refer to Introduction to Algorithms by CLRS. In the chapter that talks on greedy algorithms you can get the formal proof for Huffman algorithm. Its a lengthy proof and needs patience to read.
– arunmoezhi
Aug 9 '12 at 21:03

Huffman coding approximates the population distribution with powers of two probability. If the true distribution does consist of powers of two probability (and the input symbols are completely uncorrelated), Huffman coding is optimal. If not, you can do better with range encoding. It is however optimal among all encoding that assign specific sets of bits to specific symbols in the input.

• What do you mean by "approximates the population distribution"?
– user1422
Aug 7 '12 at 20:08
• There is a theoretical true distribution of message that could hypothetically be sent. Ideally, each message should be encoded in a way that is proportional to the log of its probability, but since Huffman codes are an integer number of bits, that implicitly corresponds to probabilities that are powers of two. Hence an approximation. Look up Shannons Coding Theorem.
– Antimony
Aug 7 '12 at 23:42

Yes, it is always optimal.

No, there is no threshold where it would use less space to use fixed length non-encoded data.

I found a number of proofs on the Web, but there is sufficient discussion in the Wikipedia article Huffman coding.

This also covers other techniques which achieve higher compression (working outside the space for which the Huffman code is optimal).