Re: Huffman Algorithm Help
The code is a little difficult to read, but I will try to explain the Huffman algorithm as I remember it. I'll use an example where we would attempt to optimize the Huffman code for the letters A-F, with the frequencies:
So, we start with 6 root nodes.
The smallest two frequencies are F (5) and either B or C (10). We'll take the first occurence, B.
So, we combine B and F.
The next smallest are 10 (C) and 15 (D)
So, we combine them.
The next smallest are 25 and 15.
We'll use the second 25 because it will make drawing the graph easier.
Next up is 25 (A) and 35 (E).
Finally, combine the 60 and 40 to get the 100%.
This tree happens to be a heap. A heap is a tree where every nodeís parentís value is greater than the nodeís value. This is important when a computer is creating this tree; but, from a human perspective it makes little difference.
Now, write a 0 on every left edge and a 1 on every right edge.
Notice that all of the letters are in leaf nodes. So, to obtain the code for any of the letters simply trace the root from the root down to the letter's node and write the edge's label as you go. For example, to get the code for E you would follow the root to the left (0) then to the right (1), so the code for E is 01.
Notice that the two most frequently used characters in this list have the shortest codes, and the least frequently used characters have the longest codes. Therefore, the average transmission of characters will tend to be shorter.
There is another important property that a Huffman Code has. It's called the "Prefix Property." To put it simply, no code is a prefix of another code. To understand why this is you can take another look at the tree. The only way a code can be a prefix is if it is an ancestor of that node. However, by definition every character is a leaf node so it cannot be the ancestor of any other character. This property is useful when decoding messages because when you encounter a string of 0s and 1s you know that when you find a letter it isn't part of another letter and can just continue on your way.
Hopefully this will help you figure out what you need to do for your program.