In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. In this project, you will implement the Huffman encoder and decoder with the following details.

1. Huffman Coding

The first step in this project is to develop a program that generates Huffman codes. The algorithm for this was discussed in Lecture 7. For this project, you need to evaluate which of the following priority queue structures gives best performance: Binary Heap, 4-way cache optimized heap (lecture 10 slides 23 and 24), and Pairing Heap (lecture 15). Write code to generate Huffman trees using these three data structures and then measure run time using input data of sample_input_large.txt. Use the following code as reference (this is in C++, use a similar approach if you are using some other programming language):

clock_t start_time; // binary heap start_time = clock();for(int i = 0; i < 10; i++){ //run 10 times on given data set build_tree_using_binary_heap(freq_table);} cout << Time using binary heap (microsecond): << (clock() start_time)/10 << endl; // 4-way heap start_time = clock();for(int i = 0; i < 10; i++){ //run 10 times on given data set build_tree_using_4way_heap(freq_table);} cout << Time using 4-way heap (microsecond): << (clock() start_time)/10 << endl; // pairing heap start_time = clock();for(int i = 0; i < 10; i++){ //run 10 times on given data set build_tree_using_pairing_heap(freq_table);}cout << Time using pairing heap (microsecond): << (clock() start_time)/10 << endl;

Once you have determined which data structure gives the best performance, finalize your Huffman code program using that data structure. The finalized Huffman code program will take as input a frequency table and output a code table. Include the timings and conclusions in your report. Once the Huffman code program is finalized, you should proceed to write the encoder and decoder.

2. Encoder

The encoder reads an input file that is to be compressed and generates two output files the compressed version of the input file and the code table. Your encoder can follow this diagram:

Input format

Input file name will be given as a command line argument. This file can have up to 100,000,000 lines and each line will contain an integer in the range of 0 to 999,999. Consider the following input for the rest of the document:

<input_file>
	0224509999992245002245224534446 34446349999992

Building frequency table

First step towards Huffman encoding is to build the frequency table for each value in input. As values will be within 0 to 999999, an array can be used for storing frequency for each value. Frequency mapping for the given input file is:

0 ==> 4

2245 ==> 4

999999 ==> 2

34 ==> 3

446 ==> 2

2 ==> 1

Build Huffman tree and code table

Use the data structure with best timing from section 1 to build the Huffman code table. For the sample input given, one possible Huffman tree and corresponding code table mapping is given below. The code table can be built from the Huffman tree by doing a traversal of the tree.

2 ==> 000999999 ==> 0010 ==> 012245 ==> 10446 ==> 11034 ==> 111

Huffman tree code table

Encode data

Once the code table is built, it can be used to encode the original input file by replacing each input value by its code. Please note that the values are not ASCII characters, rather binary values. You can use ios::binary flag in C++, or OutputStream in Java.

0110010011001011010111110111110111001000

Output format

Encoder program has two output files. One is encoded message in binary format. It must be saved as encoded.bin. As mentioned in Encode Data phase, output encoded.bin for given data will be:

encoded.bin
	0110010011001011010111110111110111001000

Second output is the code table. Each line in this output file will contain value of a leaf node of Huffman tree, and its code separated by a space. It must be saved as code_table.txt.

code_table.txt
	2 000999999 0010 012245 10446 11034 111

Note: Both encoded.bin and code_table.txt are NOT unique. They will not be used for grading directly. However, the size of encoded.bin is unique, so this size will be used for grading purpose. code_table.txt will be used by your decoder program to decompress the encoded file.

3. Decoder

The decoder reads two input files encoded message and code table. The decoder first constructs the decode tree using the code table. Then the decoded message can be generated from the encoded message using the decode tree. Your report should include a description of the algorithm used to construct the decode tree from the code table together with the complexity of this algorithm.

Input format

The decoder takes two input files encoded message and code table. File names will be given as command line arguments. The format of these files is the same as the output format of the encoder, so that the output files of the encoder program can be directly used by the decoder program. Note that the input encoded message will be in binary format, not ASCII characters. You can use ios::binary flag for C++ or InputStream for Java.

Output format

Output of decoder program is the decoded message. It should be saved as decoded.txt. The format of this file is same as the input format for the encoder. For any sample input, the following scenario should be true:

<input_file>			decoded.txt
	0224509999992245002245224534446 34446349999992			022450999999224500224522453444634446349999992

4. Files provided in elearning

sample1/..i. sample_input_small.txt ii. encoded.bin iii.code_table.txt iv.decoded.txt	;inputs/outputs mentioned in this document
sample2/..	;large inputs/outputs set
i. sample_input_large.txt ii. encoded.bin iii.code_table.txt iv.decoded.txt	;use this file for performance measurement
COP5536_FA20_Project.pdf	;this file

5. Run environment

Your code must be able to run in the linux environment. You can test your program either on CISE storm.cise.ufl.edu or thunder.cise.ufl.edu server (for which you need to login using your CISE account). Write a Makefile so that we can build your code using following command at terminal:

$ make

This command should produce two binary files: encoder and decoder.

As mentioned before, encoder should take one input file. We will run it using following command:

$ ./encoder <input_file_name> [For C++]

$ java encoder <input_file_name> [For Java]

Running encoder program must produce the output files with exact name encoded.bin and code_table.txt. On the other hand, decoder will take two input files. We will run it using following command:

$ ./decoder <encoded_file_name> <code_table_file_name> [For C++]

$ java decoder <encoded_file_name> <code_table_file_name> [For Java]

Running decoder program must produce output file with exact name decoded.txt.