1
$\begingroup$

I have the phrase "abracadabra" and I want to encode it through the Huffman method. I first took the frequencies of each letters; $$a=5$$ $$b=3$$ $$c=1$$ $$d=2$$ $$r=2$$ But I'm not sure as to how the diagram should look like. I made a few and some of them are correct. Also what determines the direction the branches take? Is there any fixed criteria for it?

enter image description here enter image description here

$\endgroup$
  • 1
    $\begingroup$ Why is $v$ 100 in your second tree? Why do $c,d,r$ begin with 11 rather than 01 in your third tree? $\endgroup$ – xskxzr Mar 30 '18 at 17:58
1
$\begingroup$

Huffman's algorithm is non-deterministic — at several junctures you have more than one admissible choice. For example, at the first step, you can merge either $c$ and $d$ or $c$ and $r$. As another example, you can choose which child is left and which is right arbitrarily. Any particular implementation of Huffman's algorithm has some tie-breaking rule which makes it deterministic, but any choice would lead to a minimum redundancy code, and the generic Huffman algorithm doesn't specify any specific tie-breaking rule.

Huffman's algorithm is guaranteed to produce a minimum redundancy code, but not every minimum redundancy code can be produced by an admissible run of 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.