9
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ – arunmoezhi Aug 7 '12 at 1:30
  • $\begingroup$ @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. $\endgroup$ – user1422 Aug 9 '12 at 16:17
  • $\begingroup$ 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 $\endgroup$ – arunmoezhi Aug 9 '12 at 18:59
  • $\begingroup$ @arunmoezhi I have included the probabilities of the characters and they do add up to 1. $\endgroup$ – user1422 Aug 9 '12 at 19:32
  • $\begingroup$ @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) $\endgroup$ – Andrew Dec 3 '20 at 21:17
4
$\begingroup$

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: enter image description here

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – user1422 Aug 9 '12 at 20:56
  • 1
    $\begingroup$ 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. $\endgroup$ – arunmoezhi Aug 9 '12 at 21:03
8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What do you mean by "approximates the population distribution"? $\endgroup$ – user1422 Aug 7 '12 at 20:08
  • 3
    $\begingroup$ 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. $\endgroup$ – Antimony Aug 7 '12 at 23:42
8
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy