You are urged to work in groups of two. Each group should submit ONE program per group. Be sure to include name and login id of each person in your group in the README file that belongs with the submission.
Every group member must submit a README, only one group member submits the code
For a complete description of Huffman coding for use in a Compsci 100 assignment see this online description developed in the mid 90's for use at Duke. This has seen widespread adoption in similar courses elsewhere.
The assignment writeup begins below the description of Huffman and Huffman coding.
Several algorithms for data compression have been patented, e.g., to use the MP3 codec to compress audio (which uses Huffman encoding as one of the steps in the algorithm) legitimately you must pay for a license from mp3licensing.com which coordinates licensing at least in the US and Europe.
Huffman coding was invented by David Huffman while he was a graduate student at MIT in 1950 when given the option of a term paper or a final exam. For details see this 1991 Scientific American Article. In an autobiography Huffman had this to say about the epiphany that led to his invention of the coding method that bears his name:
"-- but a week before the end of the term I seemed to have nothing to show for weeks of effort. I knew I'd better get busy fast, do the standard final, and forget the research problem. I remember, after breakfast that morning, throwing my research notes in the wastebasket. And at that very moment, I had a sense of sudden release, so that I could see a simple pattern in what I had been doing, that I hadn't been able to see at all until then. The result is the thing for which I'm probably best known: the Huffman Coding Procedure. I've had many breakthroughs since then, but never again all at once, like that. It was very exciting."
Huffman's original paper is available, though it's a tough read. The Wikipedia reference is extensive as is this online material developed as one of the original Nifty Assignments. Both jpeg and mp3 encodings use Huffman Coding as part of their compression algorithms. In this assignment you'll implement a complete program to compress and uncompress data using Huffman coding.
For this assignment you'll build what are conceptually two programs: one to compress (huff) and the other to uncompress (unhuff) files that are compressed by the first program. However, there is really just a single program with the choice of compressing a file or uncompressing a file specified by choosing a menu-option in the GUI front-end to the code you write. Abstractly you're writing a program to read an input file and create a corresponding output file --- either from uncompressed to compressed or vice versa. For extra credit you'll add another step to the compression process: the Burrows-Wheeler transform.
The Huff
class is a simple
main that launches a GUI with a connected IHuffProcessor
implementation. The implementation corresponds to a model in the
model-view architecture we've been using in class: the view/GUI makes calls
on the model/IHuffProcessor
methods which in turn
may display information
in the view/GUI. The code you write will also create files of compressed
or uncompresse data when the GUI-front end calls methods you will write.
You'll implement methods and store state in your
IHuffProcessor
implementation so that it can either
compress/huff or uncompress/unhuff. You're welcome to implement
additional classes as well, but you don't need to (except for the
Burrows-Wheeler transform which is optional.)
You're writing code based on the greedy Huffman algorithm discussed in class and in this detailed online explanation of Huffman Coding. Be sure to read that explanation, the notes from class, and refer appropriately to the howto for this assignment.
The resulting program will be a complete and useful compression program although not, perhaps, as powerful as standard programs like winrar or zip which use slightly different algorithms permitting a higher degree of compression than Huffman coding. However, for bonus/A credit you can implement algorithms that use a Burrows Wheeler Transform to change data into a format that makes it more amenable to Huffman coding for better compression.
Huff
main program
has a GUI front-end whose menu offers three choices: count characters,
compress, uncompress (and quit as a fourth choice). You can't compress
until you can count/create a tree, so make sure
counting/tree-creation/encoding works. The howto
document has details on how the program works.
The benchmarking program skips files with .hf suffixes, but you may want to remove these eventually. In your README you should discuss your benchmark results and provide some insight as to their meaning. Your analysis is worth nearly 20% of your grade on this assignment, so you should try to come to some conclusions in addition to simply listing your results.
If you use different methods to store information in the header of your compressed file, e.g., you store the tree and you also store counts, then reporting on differences is a good idea. Information on how to create the header is in the howto.
description | points |
---|---|
compression/decompression of any text file | 15 points |
compression/decompression of any file (including binary files) | 15 points |
robustness (crash on non-huffed files, force compression..) | 5 points |
program style (design, documentation, etc.) | 5 points |
empirical analysis | 10 points |
README | 5 points |
Your README file should include the names of all the people with whom you collaborated, and the TAs/UTAs you consulted with. You should include an estimate of how long you spent on the program and what your thoughts are about the assignment.
Submit your README and all of your source code using Eclipse with assignment name huff. Remember that each person in a group should submit a separate README, this must include the names of the people in the group. Only one group member submits code.