Huffman Coding

[far2004]

LAB#09: Huffman Coding
Objectives:

1. To gain experience with encoding and decoding strings manually using the Huffman coding technique.

2. To study the implementation of the Huffman encoding algorithm.

3. To implement the Huffman decoding algorithm.

4. Downloadables:
   Download lab09.zip and unzip it under the ics202 main folder.
   After unzipping, the following files will be updated/added to the ics202 package:
   HuffmanChar.java
   HuffmanNode.java
   HuffmanCode.java
   The file TestHuffmanCode.java will be placed in ics202.lab09 package.

5. Task1
   Study each of the files HuffmanChar.java , HuffmanNode.java, HuffmanCode.java, and
   TestHuffmanCode.java carefully.
   Notice that the method encode() in HuffmanCode.java is almost a straight forward translation of the algorithm
   demonstrated in the Huffman Lecture.

6. Task2
   Write a visitor class HuffmanCodePrinter (in ics202.lab09). An instance of this class will be used in
   an inorder traversal
   of a HuffmanCode tree to display its leaves. Note: Remember that the binary tree to be traversed holds
   HuffmanNode
   objects.

7. Task3
   (a) Complete case 1 of the switch statement in TestHuffmanCode.java. Compile the program and run it
   supplying the
   following 7 characters and their associated frequencies (as given in the Huffman Lecture):

Character a e l n o s t
Frequency 45 65 13 45 18 22 53

Notice that your program may not generate exactly the same code words generated in the Lecture. However,
if your
program is correct the generated code words must have the prefix property [Note: To get exactly the same
code words
as those generated by the program, you must create the min heap top down, and then create a resulting heap
tree as
each key is deleted, i.e., A DETAILED TRACING OF THE encode METHOD IS REQUIRED]

(b) Draw the HuffmanCode tree generated in Task 3(a)

(c) Manually draw the HuffmanCode tree and then generate code words for the characters in the following table:

Character s e a r g t
Frequency 5 30 15 10 5 20

Use your program to verify the correctness of your manually generated code words.

5. Task4
   In this task, you will improve the program so that input can be supplied to it from the keyboard as well as from a
   file. In both these cases, the program should process the input to obtain the statistical information required by the
   Huffman algorithm.
   (a) Complete the following method in the HuffmanCode class.

public MySearchableContainer updateContainer(String
text, MySearchableContainer container)

This method updates a MySearchableContainer of characters with new characters provided in its
string argument. The method is used
by the two calculateFrequency methods of the HuffmanCode class.

(b) Complete case 2 of the switch statement in TestHuffmanCode.java. Compile and test your program using the
input string:

MUZZAMMILU

Your output should be :

Character frequency CodeWord
U 2 00
A 1 010
I 1 011
M 3 10
L 1 110
Z 2 111

(c) Complete case 3 of the switch statement in TestHuffmanCode.java. Compile and test your program using a
textfile that contains the string MUZZAMMILU. Your output should be the same as that in Task4(b)

6. Task5
   In this task, you are required to write a decoder for Huffman codes. Recall that the prefix property of Huffman
   codes makes them unambiguous to decode.
   To accomplish this task:
   (a) complete the method decode() in the HuffmanCode class, which given a sequence of bits, returns the
   sequence of
   characters represented by the encoded bits.
   (b) Complete case 4 of the switch statement in TestHuffmanCode.java .

Use Huffman code tree generated in Task 3(c) above to recover the strings encoded by the following bit sequence:
11101110101000100

Verify the correctness of your decode method by decoding the bit sequence manually.