Huffman Code
1 Description of Assignment
Design and implement efficient data structure and algorithm for computing Huffman code for each symbol in the input file. Then compress the input file, print out the compression ratio, and decode the encoded file.
2 Input
Choose text files of different sizes as the input to your program.
3 Output
For each input file, do the followings.
1. Compute the frequency an then the Huffman code for each symbol in the file. The symbols must include all characters in the file, including end-of-line and end-of-file.
2. Compress the input file, and print out the compression ratio. The compression ratio in this assignment is defined as the ratio of the size of the original file and the size of the compressed file. Note that the size of a file is measured in bytes. For simplicity, the Huffman code
1
table can be excluded in the counting of the size of the compressed file. To verify the sizes of the original file and the compressed file, use “dir” in Windows or “ls -Fla” in Unix/Linux systems.
3. Decompress the file generated in the previous step, and write it out to another file.
4. Show the compression and decompression of your program is correct by using “cmp in-file out-file” in Windows or “diff in-file out-file” in Unix/Linux systems, where “in-file” is the original input file, and “outfile” is the output file of your decode program.
Notes
(a) Description of the design of your program and the data structures used in your program.
(b) List of your program with comments.
(c) Outputs of the compilation and the executions of your program.
(d) In addition to the basic requirements specified in the assignment, functions or features you have implemented.
(e) Interesting thing you have learned from this assignment.
2. The output of the program execution should indicate the correctness of your program. In other words, a set of comprehensive (but not necessarily exhaustive) annotated test data for the problem should be provided to show that your program is indeed correct. This can be done by carefully selecting a set of test data.
3. Include assignment number, your name, student number and email address on the first page of your report.
4. Print or write the report on A4 papers. Bind them together in the upper left corner.
2
