Program 5- Huffman Coding

Due: April 25, 2001, 11AM by email


This programming assignment will give you practice with heaps and an interesting algorithm - Huffman Coding - for compressing a text file using variable length codes.

The assignment has three parts:

1.  Read a text input file of letters, and compute their frequencies.
2.  Construct the binary tree representing the Huffman Code for this text, and print the resulting code.
3.  Encode the message using this code and output the string of 0's and 1's that correspond to it. How much compression do you get?
To build the tree, follow the handout and algorithm described in class. Note
that this algorithm makes heavy use of heaps.

Addendum (as noted by Josh in the mailing list): output your characters and the corresponding Huffman code, in order of most to least frequent.  Test the
compression you get by encoding the Gettysburg address text (from the last assignment) and computing the savings. (Do not output the encoded message).