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?
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:
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.
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).