PA 8: Huffman Encoding and Compression
Due Date: November 26th (Tuesday, 11:59 PM)
Checkpoint Submission: November 24th (Sunday, 11:59 PM)
PA Quiz: November 23rd (Saturday, 11:59 PM)
100 points
Overview
In this assignment you will implement a classic lossless compression algorithm Huffman
Encoding. It’s an optimal lossless compression strategy discovered by David A.
Huffman and his students. After finishing this assignment, you can compress and
decompress any file using the algorithm that you implemented.

This assignment is an individual assignment.​ You may ask Professors/TAs/Tutors
for some guidance and help, but you can’t copy code. You may discuss the assignment
conceptually with your classmates, including bugs that you ran into and how you fixed
them. ​However, do not look at or copy code.​ This constitutes an Academic Integrity
Violation.

START EARLY!


Style Requirements
You will be graded on your code’s style. ​Style Guide

IntelliJ has ​a great plugin​ to check your style automatically. Use it!
There are style considerations beyond indentation and such.
● Choose names for test methods and for variables that are descriptive and useful
when you see them in test output.
● Consider writing helper methods if you repeatedly use the same set of
statements.
● Use Javadoc comments for descriptions of your methods and classes and inline
comments if the logic of your program is not captured by your variable names
and the natural flow of code.

Part 0 - Get Starter Code
Our starter code will be distributed from
https://github.com/ucsd-ets/dsc30fa19-startercode​.

Please follow the same procedures as before to get your starter code and set up intelliJ.
Part 1 - PA Quiz
Fill out this quiz about the PA to make sure you have understood the assignment
thoroughly. You have 5 attempts to complete it.

PA Quiz on Canvas

Part 2 - Huffman Coding Tree

In this part, you will need to implement methods in ​HCTree.java​ and the ​compareTo
method in the inner class ​HCNode​ to help you build and use a Huffman Coding Tree.

We have provided most of the inner class ​HCNode​ for you. Please read through the
Javadoc comments in starter code to understand the purpose of each instance variable
in ​HCNode​. After that implement the following methods:

public void buildTree(int[] freq)

This method takes in an int array of size 256, which is​ the ​size of extended ​ASCII​.
(Since each byte is 8 bits, then the number of all the possible bytes is simply 2^8 =
256). The given array was used to keep track of the ​frequency of each byte from
the input file​. For example, if ‘a’ appears in the input file 7 times, then the element at
index 97 (which is the ASCII value of ‘a’) of ​freq​ would be 7. Note that to get the
symbol ‘a’ of type byte back from its ASCII value 97, you can simply cast the int to
byte by doing : ​byte a = (byte)97

1. In this method, you first need to create all leaf nodes of your ​HCTree​ with
frequency values corresponding to each symbol in the ​freq​ array. Note that
HCTree​ contains an instance variable called ​leaves​, which is an array to
reference each of the leaf nodes in your ​HCTree​ (It will be useful later in your
encode​ method). You need to think about where to store each leaf node in the
leaf array so that when given a symbol, you can immediately find the reference
to the leaf node containing that particular symbol.

2. After creating these ​HCNodes​, then you need to add them to a Java built-in
priority queue to help you build the tree later. (The documentation of priority
queue can be found ​here​). ​Remember that this priority queue should give
higher priority to the ​HCNode​ with less frequency, and if the frequency are
the same, the HCNode with symbol of smaller ASCII value should have
higher priority​. Now you need to go back to the inner class ​HCNode​ and
implement the ​compareTo​ method to satisfy the requirement above, as Java’s
built-in priority queue will use your ​compareTo​ method defined in ​HCNode​ to
determine the priority of different node.

Hint:

First, recall that the ​default behavior ​of ​compareTo​ method is: return positive
number if “this” is considered “larger” than the given object.

Then read the document about priority queue and find the information about
the ​default behavior​ of priority queue: is it a min heap or max heap by default?
Then think about the following questions:

a. What instance variables define the priority of ​HCNode​?
b. Do we want a min heap or max heap behavior from priority queue?
c. If you want the default behavior of priority queue, then should you keep
compareTo​ method to have its default behavior?
d. If you want the opposite of the default behavior of priority queue, then
should you keep ​compareTo​ method to have its default behavior?

3. Your next step is to build the ​HCTree​ using ​HCNode​ currently stored in the
priority queue. The algorithm has been discussed in class:

Iteratively, remove two nodes from the priority queue. Then use the first node to
be the ‘0’ child and the second node to be the ‘1’ child of a newly created
parent node. The frequency of this parent node is the sum of the frequencies of
its two children nodes. Make sure that the parent node takes a symbol from
one of its children (choose any one you want, but ​be consistent​). Then, add
this parent node back to the priority queue, so that it later becomes a “branch”
of your final tree.

You will need to think about when the ​HCTree​ is completely built: we are
essentially building the tree from the bottom up (from leaves to branches and
finally to the root).

The main reason why Huffman coding can compress data comes from this simple
method. From a high level perspective, since we are using a priority queue here to
help us build the tree bottom up, the ​HCNode​ with the most frequent symbol will hold
the shortest path from the root, while the ​HCNode​ with the least frequent symbol will
hold the longest path.

As a result, the most frequent symbol will correspond to the shortest sequence of
encoded bits. This is where the compression actually happens: We used much less
encoding bits to represent the most frequent symbol. Although the least frequent
symbol may have the longest number of encoded bits, but because this symbol
doesn’t appear so frequently, the overall encoding will be shorter in the end.
public void encode(byte symbol, BitOutputStream out) throws
IOException

For a given symbol, use the ​HCTree​ built before to find its encoding bits and write
those bits to the given ​BitOutputStream​.

In this method, to avoid inefficiently searching the whole tree to find the encoding bits
of the given symbol, you must take advantage of the leaf array that we created before:
it's much faster to start from the leaf node containing the given symbol, and then
traverse back to the root. You will then simply collect all the bits on that path and
reverse those bits at the end to get the encoding.

IMPORTANT: ​The following code will convert a byte c to its corresponding ascii value:
int ascii = c & 0xff;

Once you get the encoding bits, you should use ​out.writeBit(int i)​ that takes
in either 0 or 1 as a bit to write the encoding bits one by one to BitOutputStream.

public byte decode(BitInputStream in) throws IOException

Decodes the bits from ​BitInputStream​ and returns a byte that represents the
symbol that is encoded by a sequence of bits from ​BitInputStream​.






Testing HCTree:

Huffman Coding Tree can be hard to debug since most of the I/O is done by using bits,
but bits are hard to be visualized directly. To save you time from debugging later, we
enforce you to test the ​buildTree()​ to make sure the structure of your HCTree is
correct before you move on to the next part.

Now create a JUnit test file ​HCTreeTester.java​ to verify the correctness of your
buildTree()​ method. (You are not required to test methods other than
buildTree()​)

First, you should write an in-order traversal method to recursively traverse your HCTree,
and in-orderly print all the nodes in your HCTree out. (Note that toString() method for
HCNode was defined for you, so you can directly use it to print the node out)

public void inorder(HCNode root)

Then in the JUnit test method, create a freq array of size 256, and modify the array so
that it contains the correct information about the provided check1.txt file:

a: 17 b: 8 c: 7 d: 14 e: 9 f: 1 \n (newline char): 1

(You might refer to the ASCII table ​http://www.asciitable.com/​ for the ascii value of each
symbol above.)

Now from your own knowledge of Huffman coding and the description from the writeup
above, draw the resulting Huffman Coding Tree in a file ​HCT.pdf​. ​Make sure you
clearly indicate the symbol and freq of each HCNode, as well as what each edge
stands for in your HCTree drawing​. You will need to submit this as part of the
assignment.

Then you should pass this array to ​buildTree()​ and use your inorder method to print
out your HCTree and see if it matches your drawing. (You don’t need to use
assertEqual()​ here, and you may just print the HCTree out)


Part 3 - MyCompressor

Once you are done with building the HCTree, now we implement our compressor. For
this basic implementation, we will build the HCTree based on the character counts of a
large corpus. Use the corpus file, ​corpus.txt​, to build your HCTree.

public HCTree buildHuffmanTree(String corpusLocation) throws
IOException

This method will create the HCTree using the frequencies of the characters in the
corpus. In this method, you will populate the frequency array ​freq​ by counting the
occurrence of each character in the file ​corpusLocation​. The size of the array
should be 256, which is the size of extended ​ASCII​. (Since each byte is 8 bits, then
the number of all the possible bytes is simply 2^8 = 256). While creating the frequency
make sure to keep track of the ​indices of each character.​ For example, the element
at index 97 (which is the ASCII value of ‘a’) should hold the frequency of ‘a’ in the file.
Note: See provided tools below.

In short, his method takes in the corpus file (​corpusLocation​) and builds the
HCTree and stores it in the instance variable ​huffmanTree​.
public void compress(String inputFile, String compressedFile)
throws IOException

This method takes in two file names. ​inputFile​ is the name of the file that you want
to compress and a ​compressedFile​, the name of the new compressed file that your
compression algorithm should generate.
public void decompress(String compressedFile, String
outputFile) throws IOException

Similarly, this method takes in two file names. ​compressedFile​ is the name of the
compressed file that you want to decompress and ​outputFile​, the new
decompressed file that your algorithm should generate after decompressing.


Part 4 - Compress and Decompress

Overview

Now, we build our compression program.

The main method of ​MyCompressor.java​ takes in args in the following format:
First argument: corpus file
Second argument: signal command. Either “​compress”​ or “​decompress”.
Remaining arguments are the names of the file to compress or decompress.

Case “​compress​”: Compressed file should be names compressed_[original].txt

Case “​decompress​”: Decompressed file should be named decompressed_[original].txt

Eg.
1. src/corpus.txt compress src/f1.txt src/f2.txt
2. src/corpus.txt decompress src/compressed_f1.txt
src/compressed_f2.txt

In the first case the output should be two files: ​compressed_f1.txt
compressed_f2.txt
In the second case, the output should be two files:
decompressed_compressed_f1.txt decompressed_compressed_f2.txt


Provided Tools

Compression:

First you will need to scan through the corpus file to compute the frequencies of all 256
bytes. The following line of code will read through the given text file byte by byte, and
put all those bytes into a byte array.

byte[] input = Files.readAllBytes( Paths.get(/*file path*/) );

IMPORTANT: ​The following code will convert a byte c to its corresponding ascii value:
int ascii = c & 0xff;

Notice that these output stream initializations are given to you:

FileOutputStream file = new FileOutputStream(/*file path*/);
DataOutputStream out = new DataOutputStream(file);
BitOutputStream bitOut = new BitOutputStream(out);

We won’t go into details about how these output streams work, but you should know
how to write to the given file using these output stream.

For example, let’s say your third command line argument is a text file named
“compressed.txt”.​ ​Then to write an int 25 to “compressed.txt”, you will simply use
DataOutputStream​ by calling ​out.writeInt(25)​. (You should read the document
DataOutputStream​ for more information). And similarly, to write a single bit 0 to
“compressed.txt”, you will simply use ​BitOutputStream​ by calling
bitOut.writeBit(0);

Decompression:

Notice that these input stream initializations are given to you:

FileInputStream inFile = new FileInputStream(/*file path*/);
DataInputStream in = new DataInputStream(inFile);
BitInputStream bitIn = new BitInputStream(in);

You should also know how to read from the given file using these input stream. For
example, let’s say your third command line argument is a text file named
“compressed.txt”. Then to read an int from “compressed.txt”, you could simply use
DataInputStream​ by calling ​int byteCount = in.readInt()​ (You should read
the document ​DataInputStream​ for more information). And similarly, to read a single bit
from “compressed.txt”, you need to use ​BitInputStream​ by calling ​int bit =
bitOut.readBit()

FileOutputStream outFile = new FileOutputStream(/*file path*/);
DataOutputStream out = new DataOutputStream(outFile);

Also, to write to the output file byte by byte, you can simply call ​out.writeByte(byte
b)​.


Part 5 - Results
Overview

You are given 10 files (f1.txt - f10.txt), compress each file using your compression
algorithm and report the result in the form of the following table in a file
‘CompressionReport.txt’ or ‘CompressionReport.pdf’

File Original Size [KB] (OS) Compressed Size [KB] (CS) CS/OS
File1
...

Also, explain in a few lines the variation in the CS/OS values.

Critical Thinking​: ​Answer the following questions in 2-3 lines
Now, this method of compression using the Huffman Coding Tree might not be optimal.
1. What would happen if you used the file that you want to compress as the corpus?
Would you get better results? Why?
2. Assuming you only have a compressed version, can you directly decompress the file
that was compressed using HCTree built using itself as the corpus? [Yes/No]
3. If yes, explain how? If no, explain how would you modify your code to enable the
decompression?

Part 6 - Test Compress and Decompress

Once you have done implementing ​Compress​ and ​Decompress​, you need to perform
testing on your program.

We have provided 3 basic check files for you to test your Huffman Coding (check1.txt
and so on). You should use command line arguments to compress a check file to a
compressed file, and decompress that compressed file back to see if it matches the
original file.

Next, you should test your program on the larger 10 input files (f1.txt - f10.txt). You
should use command line arguments to compress a check file to a compressed file, and
decompress that compressed file back to see if it matches the original file.


Some Edge cases to fix:

1. Empty file

Compressing an empty file should generate an empty file. After decompressing, your
program should generate an empty file as well.

2. File with only single kind of char

We’ve provided singleChar.txt to test this case (A file with only newline char at each
line).

Submission

Due - November 26th (Tuesday, 11:59 PM)
Files to submit:

1. HCTree.java
2. HCTreeTester.java
3. MyCompressor.java
4. HCT.pdf
5. CompressionReport.txt

Checkpoint - November 24th (Sunday, 11:59 PM)
1. HCTree.java
2. HCTreeTester.java
3. HCT.pdf

After you submit your files to GradeScope, wait for the output of submission
script. Make sure you see this after your submission:

THIS IS A SUCCESSFUL SUBMISSION. YOUR SCORE WILL BE UPDATED ONCE 
GRADED. 
 
Otherwise, please fix the error and resubmit your files.



New to PA 8​:

For extra assurance on the code that you submit, we’ve included a basic script for you
to test the input files that came with your starter code. Under the output of a successful
submission, you should see the test output of input1.txt, input2.txt, and input3.txt.
Passing these submission tests is ​not​ a requirement for a successful submission; these
tests are there to help you ensure that you get identical files from compression followed
by uncompression.


The above is an example of a successful submission that passes the basic script.



The above is an example of a successful submission that does not pass the basic script.