CS 141 - Lab 5

Huffman Coding

Directions

Find a partner. Solve the following programming problem in C++. When you finish, turn it in electronically, one copy per team. When you are done, you should work on Homework 3 or Programming Assignment 3.

Overview

Fill in the blanks on a nearly-completed version of the Huffman Coding algorithm.

Details

Download huffman.cc. Search through the huffman function for the string "TODO", and follow the directions at each of those steps.

You will need to look at the "Heap operations" section of the STL reference page. Remember that the STL heap is a max heap, and thus you'll have to alter (hint: think multiplication) the frequencies so they sort properly.

If you finish, you may change the huffman function to return the binary-coded string rather than the length of the string. This is worth 2 extra lab points (20%).

Testing

Test cases can be found here. Run these using regular UNIX redirection & testing:

./lab4 < inputFile

Where inputFile will be one of these: winter.txt (Should compress to 55 bits)
shortlist.txt (Should compress to 224 bits)
longlist.txt (Should compress to 27662 bits)