22C:030/115 Computer Science III

Program 3: Huffman Codes

This program requires you to write a program to decode strings encoded with Huffman codes.  A Huffman code represents characters in variable length bit strings.  Frequently occurring characters are represented with short bit strings; characters that occur rarely are represented with long bit strings.  You are required to develop a program with appropriate class definitions that converts  a coded string into it's uncoded representation.

The input to your program will be two files.  One file containing the code and one file containing a coded string to be decoded.

The assignment will give you experience in the use of binary trees, exposure to data compression techniques,  and experience in solving a problem from a specification.
 

What to submit:

You should submit a directory that includes:

1. README: A file giving a overview of the contents of the directory including:
• Your name and section number.
• A short (2-3 sentence description) of the assignment.
• A one sentence description of each file in the directory.
• An explanation of how to compile your programs.
2. Class definition and implementation files.
3. A program that decodes a Huffman coded bit string.
4. Printed copies of the README,class definition and implementation files, and the program to be submitted in lecture on the due date.

Huffman Coding

Using this code, the string ATACG would be represented by the coded bit string 0100010111, where each character is replaced by its bit code.

In this assignment you are to write a program that decodes Huffman coded bit strings.  Your program should take as input a file that specifies a Huffman code and a file that contains a bit string encoded with the given Huffman code.  You can assume the file containing the Huffman  contains one line for each character in the alphabet.  Each line will be begin with the character followed by a single space and then the character's bit code.  The file containing the coded string will consist of one line containing a sequence of 0's and 1's. Example files are available in the directory /group/class/c030/data.

To solve the decoding problem, you must first create a Huffman tree from the table of Huffman codes.  A Huffman tree is an extended binary tree in which the leaf nodes contain the characters of the alphabet.  The tree is structured such that the path to a leaf node is  determined by the bit code, where 0 is interpreted as left and 1 is interpreted as right.  Thus, the code above defines the following Huffman tree:

Note that interior nodes contain no data.  You must devise a method to create a Huffman tree from a Huffman table. You should not assume that the aphabet contains any particular symbols or is of any particular size.

The second part of your assignment is to decode a bit string. To do this you should read bits from the bits sequence and descend the tree in the appropriate direction until a leaf node is found.  Each successive character visited should be printed to an output file.  This process must be repeated until the bit sequence is exhausted.

Huffman codes are optimal in that sense that they produce minimal length encodings given the frequency with which characters occur.  A more detailed explanation of Huffman Coding with illustrations is available here along with descriptions of some other coding methods.

Input/Output

• "codetable"  - A file containing the table of Huffman codes.
• "codedstring" - A file containing a coded bit string.
• "decodedstring" - The output file produced by your program.

Additional Assistance