In Huffman's algorithm, we form a tree and than replace each character with the tree value of 1 and 0. Why don't we simply use the binary digits like $a=0$, $b=1$, $c=10$, $d=01$, $e=11$ and so on than replace them with the characters and when decompressing aplly the reverse and replace the binary digits with the alphabets?

  • $\begingroup$ There are definitely many possible codes. $\endgroup$ – Raphael Apr 8 '15 at 10:54
  • 6
    $\begingroup$ Have you looked at en.wikipedia.org/wiki/Huffman_coding? You have to read a bit if you want to understand. The first sentance says: a Huffman code is an optimal prefix code. What does it mean, and why is it important? $\endgroup$ – babou Apr 8 '15 at 10:55

Suppose we code, as you suggest, $a=0$, $b=1$, $c=10$, $d=01$, $e=11$, etc., and I send you the message $1001$. You can't tell if I said $10\,0\,1=cab$, $1\,0\,01=bad$. The point of the Huffman scheme is that it's a prefix code, so it's uniquely decodable (and, further, you can always decode the start of the message based on the bits you've already seen, without having to look into the future).

| cite | improve this answer | |
  • 3
    $\begingroup$ The underlying concept is that of prefix (free) codes. $\endgroup$ – Raphael Apr 8 '15 at 10:54
  • $\begingroup$ Huffman code for "abcd" is "000110111110" there is a chance of ambiguity as well isn't it? $\endgroup$ – Waqar Haider Apr 8 '15 at 10:58
  • $\begingroup$ There is no unique Huffman code for any given string. Huffman coding depends completely on the distribution of letters in the string you're encoding. $\endgroup$ – David Richerby Apr 8 '15 at 10:59

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.