Lab 8

July 22, 2008

Huffman Coding

This lab will work on many of the skills we have learned in this class and in 221. You will use a priority queue, a binary tree, heap, hashtable and a few other tricks. You are to take a text file, compress it using Huffman coding, write out the bits to a file, and then read the bits back in, decompress it and write the text back out to a new file.

Steps

  1. Read in Text file
  2. Parse and store the frequency of each letter
  3. Create a priority Queue
  4. Use the Huffman Algorithm that I gave in class to create a Huffman tree.
  5. Create a key for each letter
  6. Compress the file, writing the bits out to a file.
  7. Read the bits from the file following the tree to decode the letters.
  8. Write the decoded letters back out to a file.
  9. The original and new files should be identical.
I got through step four last night, it took me about an hour. Now that I have the tree created I need to figure out a way to make a key, this turns out to be a little trickier than I first imagined.

Get as much done as you can today. I will check them at the end of class.
The completed lab will be due Thursday.