1
$\begingroup$

I finished my exam a moment ago and one of the question was to calculate Huffman coding for given probabilities:

A: 0.15
B: 0.2
C: 0.55
D: 0.1

I encoded them as follows:

A: 110
B: 10
C: 0
D: 111

But my lecturer told me that this results seems odd and gave me just a fraction of points for my solution. I argued that all my encodings have unique prefixes. I also said that all my encodings has same length as his (he compared my solution with his reference solution), thus they have same entropy.

Do I really don't understand Huffman codding? I found the theory behind this algorithm amazing so I would like to know.

$\endgroup$
  • 2
    $\begingroup$ Find a different instructor. $\endgroup$ – Yuval Filmus Apr 30 '18 at 8:21
  • $\begingroup$ @YuvalFilmus This was one of the last exam on this university. Even though I would like to study there for a master's degree, he is one of the reason why I applied to different universities. I suspect him that he hate me. $\endgroup$ – user2078693 Apr 30 '18 at 8:32
  • 1
    $\begingroup$ We can't help you with that. Your code is a Huffman code, though perhaps not the one produced by the particular implementation you were taught. $\endgroup$ – Yuval Filmus Apr 30 '18 at 8:33
  • $\begingroup$ @YuvalFilmus Sorry, I know that. I'm just disappointed from that situation. And thank you very much for checking my answer! $\endgroup$ – user2078693 Apr 30 '18 at 8:38
  • $\begingroup$ If you are interested in how to deal with your instructor, you might want to check academia.SE. $\endgroup$ – Sebastian Redl Apr 30 '18 at 13:43
3
$\begingroup$

Huffman's algorithm is actually an "algorithm scheme", that is, a specification for an entire class of algorithms. Roughly speaking, Huffman's algorithm is any instantiation of the following scheme:

While there is more than one symbol, choose (in an unspecified way) two leaves of minimum total probability, and merge then (in an unspecified order).

Any particular instantiation will include a tie-breaking rule for choosing the two leaves, and will order them in some specific way.

In your case, there is only one choice for the two leaves, but there are several choices for the order (two at each of the three iterations of the algorithm). Hence your distribution supports 8 different "Huffman codes". It might be that the one you chose is not the canonical one which is produced by the specific implementation you were taught in class. The 8 Huffman codes for your distribution are: $$ \begin{array}{c|l|l|l|l|l|l|l|l} A & 110 & 111 & 100 & 101 & 010 & 011 & 000 & 001 \\\hline B & 10 & 10 & 11 & 11 & 00 & 00 & 01 & 01\\\hline C & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\\hline D & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000\\ \end{array} $$

An important fact to be aware of is that not while Huffman's algorithm is guaranteed to produce a minimum redundancy code, not all minimum redundancy codes can be produced by Huffman's algorithm. See Gallager's classic paper Variations on a Theme by Huffman.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.