Updates


Huffman Codes

In this project, you will, among other things:

For this project, you will write a program that creates a Huffman Code for a given document and then encodes that document using that code. In this course I normally allow you to use whatever programming language you would like. In this case, I'm only requiring that your program run on my laptop and work with standard input and output (i.e., on the command line). Your implementation should take input from standard input (either typed, terminated by EOF, or redirected from a file) create a Huffman code for that input, and output the encoded version of the file using the code that you created.

Requirements

  1. Read the input. As a first step, you might choose to write a program that simlpy reads from standard input and echoes that input to standard output. Your program should work with both typed input from the keyboard as well as with piped input from a file, say.
  2. Construct the Huffman code. Based on a particular input, your program should construct a code that optimally compresses that input. You should be translating plain-text characters into variable-length sequences of ones and zeros.
  3. Output the coding and the compression information. After constructing a Huffman code based on the input text, you should display your resulting code. That is, for each plain-text character in the input, show the encoding that your Huffman code uses as a string of 1’s and 0’s. Your output should be ordered by frequency; each line should have a character followed by its 1-0 encoding. Finally, your output should display the bit-length of the given input (i.e., number of characters times eight) and the bit-length of your encoding using the Huffman code.

Submission

This is an individual assignment. Appropriate expectations on working together apply. If you search for them, you can find many implementations of the Huffman coding algorithm. It is not the goal of this exercise to end up with a compression programm; the goal is for you to learn about Huffman codes and information through the process of implementing the algorithm. Do not short-change your own learning experience by grabbing an implementation from the web and then making a few changes.

Submit a README file together with your program file(s) in either .tgz or .zip format. Your README should describe how to use or run your program. Document your code appropriately. Describe any significant discoveries or learning experiences you encountered during the process.