Assignment Eight: Huffman Coding

• Assigned: Wednesday, October 1, 1997
  
• Due: 4pm Thursday, October 16, 1997

This is an optional assignment!

Summary: In our discussion of greedy algorithms, we considered Huffman's algorithm for developing optimal encodings of character strings. In this assignment, you will implement the basic version of that algorithms.

Collaboration: You should work with members of your project group on this assignment. You may also discuss the assignment with members of other project groups.

Assignment

Implement a series of classes that could be used to implement Huffman coding.

• One class (or set of classes) should take a source text as input and output the probabilities of each character appearing. (Optionally, this class could take output the probability of each length n sequence appearing).
• One class (or set of classes) should take an encoding and a source text as input, and output an encoding of the source text.
• One class (or set of classes) should take an encoded text and an encoding as input, and output a decoding of the encoded text.

Demonstrate your classes with an appropriate set of tests.