C++ Homework for Week 7. 



Be prepared to demonstrate this program for your TA in your designated tutorial slot in week 8.

Over the next few weeks I will be asking you to implement various stages of a Huffman data compression scheme. Last week all you had to do is to was compute the so called "probabilities" of characters in some text. This week you will use the frequencies to build a Huffman tree. Recall that Huffman's algorithm operates on a forest of trees. At each iteration two trees of minimum weight are replaced by a new tree that is a merge of the two trees. See section 11.2 of your text for the detailed algorithm. An efficient way to implement the forest of trees is to build a heap of trees as illustrated in figure 11.5. That said, to satisfy the requirements of this assignment you may implement the forest of trees using an array, or a linked list, or a heap. I will leave this choice up to you. There is no need to implement the compress/decompress routine sin this assignment. To demonstrate that your program works simply print out the code for each symbol. An interesting statistic that you can also print is the compression rate, or the average number of bits used per symbol.

I wrote this program over reading week. In the interest of simplifying your programming experience I have decided to provide you with my code.
Huffman.cpp


You will notice that I used STL classes and methods to achieve a very compact solution. There is an interesting article about using the C++ STL in a program for obtaining a Huffman tree, here .

On the surface using a heap to implement Huffman's algorithm seems like an important improvement to the running time of the algorithm. However, as will be asked on this week's data structures homework, using a heap will make a minimal difference, if any at all, of a "real" Huffman encoder/decoder.  

Posted: Thu - February 15, 2007 at 01:32 PM          

©