Encoding Text Files using Huffman Trees

Purpose

The goal of this lab is to implement the Huffman Tree Encoding. Some of the skills you will practice in this lab are:

• Implementation and use of the Tree Data Structure


• Using files for input and output


• Design a program from scratch


• Use command line parameters

Design

You are free to create the design to solve this problem. The general steps for this program are:

1. 
   

   Open the file for input and create the Frequency Table. This table counts the occurrences of each character in the file.

   
   


2. 
   

   Sort the Frequency Table on frequency. To sort the table use the following comparison:

   
   

   if (tableElement1.frequency == tableElement2.frequency)  return tableElement1.element > tableElement2.element; else  return tableElement1.frequency > tableElement2.frequency;

   
   

   Basically, by using that comparison, you will be sorting your Frequency Table first by frequency and then by element. Example:

   
   

   Before Sorting

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   Element	Frequency
   a	10
   b	2
   c	2
   d	9
   e	12

   
   

   After Sorting

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   Element	Frequency
   e	12
   a	10
   d	9
   c	2
   b	2

   
   

   Notice that b and c have the same frequency, since we are sorting first by frequency and then by element, c ends up higher in the table as it is greater than b.

   
   


3. 
   

   Using the Frequency Table create the Huffman Tree from bottom up.

   
   


4. 
   

   Once the tree is created, traverse it to create the code for each of the symbols (characters) found in the file. This will result in a Encoding Table.

   
   


5. 
   

   Using the Encoding Table read the input file, and for each character use the table to get the encoding and write the encoding into the output file.

   
   

Extra Challenge

1. Add an option to decode the encoded file.


2. To be able to decode you are going to need to store the Huffman Tree in the encoded file.


3. The resulting file must be identical to the original file.

Ultra - Extra Challenge

1. Using bitwise operations, convert the binary string generated by the encoding phase into actual binary representation, this will result in a compressed file, that should be smaller than the original file.


2. You need to provide the decoding to verify that your program is working.

What is given?

You are given sixteen files:

• 
  test-file-0.txtthe first input file, the beginning of a song


• 
  test-file-0.tablethe output to screen of theencoding tablefor the first file


• 
  test-file-0.encodedthe encoded file produced from the first file


• 
  test-file-0.frequencythe output to screen of thefrequency tablefor the first file


• 
  test-file-1.txtthe first input file, A Tale of Two Cities


• 
  test-file-1.tablethe output to screen of theencoding tablefor the first file


• 
  test-file-1.encodedthe encoded file produced from the first file


• 
  test-file-1.frequencythe output to screen of thefrequency tablefor the first file


• 
  test-file-2.txtthe first input file, The Complete Works of William Shakespeare


• 
  test-file-2.tablethe output to screen of theencoding tablefor the first file


• 
  test-file-2.encodedthe encoded file produced from the first file


• 
  test-file-2.frequencythe output to screen of thefrequency tablefor the first file


• 
  test-file-3.txtthe first input file, The King James Bible


• 
  test-file-3.tablethe output to screen of theencoding tablefor the first file


• 
  test-file-3.encodedthe encoded file produced from the first file


• 
  test-file-3.frequencythe output to screen of thefrequency tablefor the first file