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.To build the tree, follow the handout and algorithm described in class. Note
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?
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).