Assignment 3 Draft version was available October 13, 1999. Due date for the written problems (Part 1) is Wednesday October 20, 1999. Due date for the program (Part 2) is Wednesday, October 27.
Here is a sample program for writing and reading bitstreams.
There are a quite a number of online resources related to Huffman coding. A short summary of the method and its use in coding is here. Here's an online reference for the adaptive Huffman coding scheme alluded to in Lewis & Denenberg, Problem 31 on pages 169-170 (an optional part of Assignment 3).
----------------------------------------------------------
Things to do on Assignment 3, Part 2:
1. To encode a file, first open and scan through the file to determine the frequency of occurrence of each character in the file. Handle any and all ASCII characters that occur in the file.
2. Build a Huffman coding tree using the frequencies just determined. Use a heap (partially ordered binary trees) to implement the priority queue used in constructing the Huffman tree.
3. Create your output file and begin the file by writing out a reasonably concise representation of the code that comes from the Huffman tree.
4. Write out the sequence of characters of the source message, encoded using the Huffman code.
To decode the file, open the file and first read in the description of the code itself. Then use this code to interpret the remaining bits in the file. Write out the decoded file as ASCII text (unless it is an image or binary file, in which case you just write out the binary bytes as if they were ASCII text).
5. Use as test data:
(a) a small
straight text file (Lincoln's Gettysburg Address).
(b) a medium-sized program
file.
(c) a larger
text file.
(d) an image
file (optional)
If you are doing the optional adaptive Huffman coding program, compare the results of your compression with those obtained via the static Huffman coding method on the same files.
Last updated October 20.
S. Tanimoto
