Cosc 2P03 Fall 2017
Assignment#5

(Due date for assignment is Friday Dec. 1st 4:00 p.m., Late date Monday Dec. 4th, 4:00 p.m.)

Objective

To implement a Huffman compression decompression.

The Assignment

>Using the input data, create a table of observations of each character as it corresponds to the ASCII alphabet. The ASCII alphabet ranges from ordinal value 0 which is the null character, to character 127 the delete character. Once the table is processed, create a linked list of the observations in priority order from least to most observed. The PQ is ordered from least (head) to most. The Huffman algorithm can now be run. The 2 nodes at the head are removed, combined to form a new node with the sum of the observed frequencies forming the new key for insert into the PQ. This process is repeated until only 1 element exists in the PQ, this element forms the root of the Huffman tree. Below is the suggested node structure.

Node {

    char c;                 //character which the node represents
    int observations;      //Number of times the character was observed in the input text.
    Node next;              //Links each node to the next in the PQ
    Node left, right;          //the left and right down pointers used t create the tree.

}

Create a code table, which lists all characters in the input followed by the binary code for that character. For consistency, label the tree using a left 0 and right 1 for the branches.

Encode the input text, using the generated prefix codes from your code table. The encoded text will produce a stream of 0's and 1's. For simplicity we will use readable text. Do not create a binary file, this is overkill. The output should be written to a file.

Read the file back in, and decompress it using the Huffman tree, to reproduce the original data. Your input data and output from the decompressing should match.
<
Your input data will consist of all characters between the > and < above.

Submission Requirements:

Good Luck