# Huffman Coding question

• Apr 6th 2008, 10:28 PM
angel.white
Huffman Coding question
Question: Construct two different Huffman codes for these symbols and frequencies: t: 0.2, u: 0.3, v: 0.2, w: 0.3

http://img230.imageshack.us/img230/2953/huffmanqkj2.jpg

I came up with the two on the top, the back of the book had the one on the bottom and said: "There are four possible answers in all, the one shown here and three more obtained from this one by swapping t and v and / or swapping u and w."

I can't figure out how they got that graph, t and v should be the first combined, and their combined weight should be 0.4 forcing u and w to be the next two combined for .6 Then the two subgraphs should be combined.

At least, thats how I understand it, I may be confused, but I got the other questions correct, so IDK.

Edit: if anyone needs it, here is the algorithm they gave for Huffman Coding.

Procedure Huffman(C: symbols $a_i$ with frequencies $w_i$, i=1,...,n)
F := forest of n rooted trees, each consisting of the single vertex $a_i$ and assigned weight $w_i$
while F is not a tree
begin
Replace the rooted trees T and T' of least weights from F with w(T) > w(T') with a tree
having a new root that has T as its left subtree and T' as its right subtree. Label the new edge
to T with 0 and the new edge to T' with 1
Assign w(T) + w(T') as the weight of the new tree.
end
{the Huffman coding for the symbol $a_i$ is the concatenation of the labels of the edges in the unique path from the root to the vertex $a_i$}
• Apr 6th 2008, 11:16 PM
angel.white
Well, I've decided the book is wrong. I found this page here The Squeeze Page which gave the same answer I have (except backwards, but I checked their algorithm, and it codes in reverse order -- even though their explanation codes in the same order, I checked by plugging their example into their applet, and it spit out the reverse answer of their example as well -- so really it is the same answer)
• Apr 7th 2008, 09:07 AM
shawn
Quote:

Originally Posted by angel.white
Well, I've decided the book is wrong. I found this page here The Squeeze Page which gave the same answer I have (except backwards, but I checked their algorithm, and it codes in reverse order -- even though their explanation codes in the same order, I checked by plugging their example into their applet, and it spit out the reverse answer of their example as well -- so really it is the same answer)

Here's an algorithm in Java..
The Laws of Cryptography: Huffman Coding Algorithm