Grin Decompression

(Credit to Stuart Reges and Marty Stepp at the University of Washington and Stanford University whose Huffman Encoding assignment formed the basis for this homework!)

A Huffman Code is a scheme for lossless compression of data. Invented by David Huffman while he was a student at MIT, Huffman codes are a relatively simple and open compression technique used in a variety of commonly-used programs and file formats, e.g., various “zip” programs—gzip, pkzip, and bzip2—and image formats like jpegs and pngs. For us, they serve as a real-world example of trees in action! In this homework, we’ll write a program to encode and decode files in the .grin format, a simple compressed file format designed for this assignment. The core of a .grin file is an encoding of the file using Huffman’s algorithm.

Source Files

Add the following files to your lab repository for the week. You should add these source files to the src/main/java/edu/ttap/compression directory as they exist in the edu.ttap.compression package:

Background

Data Compression with Huffman Codes

The key insight behind compressing data whether it is text, music, images, or any other file on our system is that there are patterns in our data that we can discover and represent more concisely. For now, let’s constrain our view to text files to simplify the discussion, although our final program will work over any file type. Recall that all data in our program are ultimately represented in bits, sequences of zeros and ones. Characters are no different; as we know, we represent characters as a number indicating its character value as dictated by some standard, e.g., the ASCII standard which assigns a value in the range 0-255 (a byte or 8 bits) to each character.

Consider the following simple text file:

a ab bza

The character values and the binary encodings for each character of this file are:

Character	Value	Binary Rep.
`'a'`	97	01100001
`' '`	32	00100000
`'b'`	98	01100010
`'z'`	122	01111010

Note that the binary representation of the values is simply the character value in binary using 8 bits (as dictated by the ASCII standard). The binary representation of this file is the concatenation of all the binary representations of the characters in sequence:

01100001 00100000 01100001 01100010 00100000 01100010 01111010 01100001

There are actually no spaces in this bit-level representation of the file. I added them to make it clear where each character began and ended.

We dedicate 8 bits to each character to cover the complete range of possible character values, but clearly the above example does not benefit from this as it only uses four characters! Because of this, we could choose to represent the character much more concisely, e.g., using the following file-specific encoding of the characters in the file:

Character	Huffman Code
`'a'`	11
`' '`	00
`'b'`	10
`'z'`	010
`eof`	011

We introduce one extra special character, an end-of-file marker—eof—to tell us when the file ends. Shorter codes are assigned to more frequently used characters, e.g., 'a' and space, and longer codes are assigned to less frequently used characters (e.g., 'z'). With this representation of the characters, we obtain the following compressed binary file (spaces again inserted for readability):

11 00 11 10 00 10 010 11 011

Even with the additional eof character, note the savings in size. We went from a file of $8 \times 8 = 64$ bits to a compressed file containing a payload of only $20$ bits!

The choice of these codes is not arbitrary—these are precisely the codes that the Huffman tree produces for this particular text file! In particular, these codes have an important property: no code is a prefix of another code. Because of this, recovering the original data given the mapping from characters-to-Huffman codes is easy: we simply walk the compressed binary file from left-to-right and once we encounter a valid code, we replace it with its corresponding character.

Huffman Trees

The key data structures in storing these character codes is the Huffman tree. A Huffman tree is a binary tree consisting of:

Leaves that store a single character per leaf
Nodes that do not store data but always have two children.

Let’s look at an example of such a tree for our example above. For now, we’ll assume that we are given a valid Huffman tree to work with. We will show how to create such a tree later!

                  [*]
                 /   \
          -------     ------
         /                  \
       [*]                  [*]
      /   \                /   \
   [' ']  [*]           ['b'] ['a']
         /   \
      ['z'] [eof]

This Huffman tree encodes the Huffman codes for each of the characters present in the file. To derive these codes, we simply walk from root to leaf for each character and record the path as a binary number where going left corresponds to 0 and right corresponds to 1. The codes for our characters are therefore:

Character	Huffman Code
`'a'`	11
`' '`	00
`'b'`	10
`'z'`	010
`eof`	011

Note that this isn’t the only possible set of Huffman codes for this file. Depending on how the priority queue resolves ordering between nodes with the same frequencies, we may arrive at a different, yet equally-efficient encoding.

Decoding with Huffman Trees

With our Huffman tree we can decode a file that was compressed using the tree’s codes. To decode a file, we repeatedly walk the tree from root to leaf, using the bits found in the encoded file as a guide. Whenever we hit a leaf, we output its correspond character, terminating the process once we reach the end-of-file character.

Using the tree we derived above to decode this file (written in its binary representation):

11001110001001011011

We then read in 1 (right) and 1 (right) ending on a leaf that contains ‘a’; we output ‘a’. We reset our position back to the root of the tree and continue processing the binary file.
We read 0 (left) and 0 (left) and output a ’ ’.
We read 1 (right) and 1 (right) and output a ‘a’.
We read 1 (right) and 0 (left) and output a ‘b’.
We read 0 (left) and 0 (left) and output a ’ ’.
We read 1 (right) and 0 (left) and output a ‘b’.
We read 0 (left), 1 (right), and 0 (left) and output a ‘z’.
We read 1 (right) and 1 (right) and output a ‘a’.
We read 0 (left), 1 (right), and 1 (right) and terminate because we’ve encountered the end-of-file character.

The end result is the decoded string:

a ab bza

Which is what we started with!

Decoding Grins

An encoded file and its corresponding Huffman tree are stored in a particular file format we call a .grin file. A .grin file has the following binary file format

[magic Number (32 bits)][serialized tree][payload]
|                                       |
-----------------------------------------
                     |
                   header

The portion of the file corresponding to the magic number and the serialized tree is called the header of the file. The payload is the actual compressed binary data.

The magic number or file signature is an integer (recall that integers are 32 bits) that denotes the type of data that this file contains. There is no standard behind this—it is simply a quick and dirty way for a program to check to see if a given file is in the format of interest. A List of common file signatures can be found on Wikipedia. For the .grin file format, the magic number is a single integer, 0x736, which is the (hexadecimal) encoding of 1846, the year that Grinnell College was founded. The other part of the header is dedicated to a serialized version of the Huffman tree that we can use to decode the payload.

Serialized Huffman Trees

In order to decompress a payload, we store the Huffman tree used to compress the file within the .grin file itself. The tree is stored in a serialized, compact format. Recall that we can serialize a binary tree, i.e., write it to a sequential structure such as a file, by performing a pre-order traversal of the tree. When performing such a pre-order traversal, we serialize the tree as follows:

If the node is a leaf, we write a 0 bit and then 9 bits corresponding to the byte value stored at the leaf.
If the node is an interior node, we write a 1 bit and then recursively write the left and right children of this node.

For example, consider our Huffman tree from before. Here, we label the interior nodes for explanatory purposes, but these labels do not appear in the serialized tree!

                  [A]
                 /   \
          -------     ------
         /                  \
       [B]                  [D]
      /   \                /   \
   [' ']  [C]           ['b'] ['a']
         /   \
      ['z'] [eof]

A pre-order traversal of the tree yields:

The [A] interior node.
The [B] interior node.
The [' '] leaf.
The [C] interior node.
The ['z'] leaf.
The [eof, 1] leaf.
The [D] interior node.
The ['b'] leaf.
The ['a'] leaf.

Keeping in mind that each of our byte values are represented by the following series of 9-bit values:

'a': 001100001
' ': 000100000
'b': 001100010
'z': 001111010
eof: 100000000

Our serialization scheme yields the following compressed representation of our tree. Note that I’ve formatted the bit string so that it visually maps onto our pre-order traversal, but in reality, this would be a single sequence of 54 bits:

1
1
0 000100000
1
0 001111010
0 100000000
1
0 001100010
0 001100001

Deserialization of the tree from the .grin file simply reverses this process. We read and interpret the bits of the serialized tree and reconstruct the tree, emulating a pre-order traversal in the process.

Implementation

The HuffmanTree Class

Your first—and most important task—is to write a class called HuffmanTree that captures the above process. Your class should have the following constructor and methods:

HuffmanTree(BitInputStream in): constructs a HuffmanTree from the given file encoded in the serialized .grin format described above.
void decode(BitInputStream in, BitOutputStream out): Decodes a stream of Huffman codes from a file given as a stream of bits into their uncompressed form, saving the results to the given output stream. Note that the EOF character is not written to out because it is not a valid 8-bit chunk (it is 9 bits).

Bit-level input and output is quite finicky in Java. To help with this, we have provided two classes for you to use: BitInputStream and BitOuputStream

The relevant constructor and methods of the BitInputStream class are:

BitInputStream(String filename): constructs a new BitInputStream pointed at the given file.
int readBit(): reads a single bit of data from the stream, returning -1 if the stream is empty.
int readBits(int n): reads in n bits of data (from 0 to 32 bits), returning -1 if the stream runs out of bits in the process.

Note that the return types of readBit and readBits are integers even though an integer is much larger than a single bit or byte (8 bits). In particular, you should immediately cast the result of readBits to a primitive of the appropriate size.

The relevant constructor and methods of the BitOutputStream class are:

BitOutputStream(String filename): constructs a new BitOutputStream pointed at the given file.
int writeBit(int bit): writes a single bit of data from the stream (0 or 1).
int writeBits(int bits, int n): writes n bits of data to the stream (from 0 to 32 bits).

Both constructors of BitInputStream and BitOutputStream throw IOExceptions that you are free to handle using a try-catch block or a throws declaration on the relevant constructor and method signatures.

When designing the HuffmanTree, we identified two different types of nodes—leaf and (interior) nodes. Rather than representing them with two separate classes related by an interface, we will instead use a single class, Node, to represent them. In your Node class, add appropriate fields to support both a leaf and interior node. Depending on whether the Node is a leaf or an interior node, you’ll selectively ignore some of the fields, e.g., a leaf does not have children and an interior node does not have a byte value associated with it.

The Grin Program

We tie everything into a single program, Grin. Grin is a command-line program with the following syntax:

java Grin <infile> <outfile>

If grin is given invalid arguments, e.g., doesn’t provide exactly two arguments, then the program should report an error and exit.

Your main method should call out to the following static helper method of the Grin class that you should, in turn, implement:

void decode(String infile, String outfile): decodes the .grin file denoted by infile and writes the output to the file denoted by outfile.

Decode should perform the following operations in sequence:

Open a BitInputStream to the infile
Open a BitOutputStream to the outfile
Parse the header of the .grin file.
Constructs a HuffmanTree from the serialized version of the tree.
Decodes the payload using the Huffman Tree and the remainder of the stream, writing the results to the outfile

If the infile is not a valid .grin file (i.e., the magic number is not correct), then decode should throw an IllegalArgumentException.

While the process of decoding has many steps, most of them are implemented in your HuffmanTree class. On top of using the HuffmanTree class, you should write additional (static) helper functions within the Grin class to help factor out your code according to this outline.

Development

To exercise your Grin program, we have provided sample files as well as their encoded .grin files:

The worked example from the beginning of the assignment:
- huffman-example.txt
- huffman-example.grin
The Wikipedia article on Huffman Coding
- wikipedia-huffman-coding.txt
- wikipedia-huffman-coding.grin
The Six Elements of a Liberal Arts Education (from the Grinnell Catalog)
- elements.txt
- elements.grin
War and Peace by Leo Tolstoy (from Project Gutenberg):
- pg2600.txt
- pg2600.grin

You should place all eight of these test files in the files folder at the root of your repository. You should then test your implementation again all four samples and ensure that you get the output that you expect.

To check the results of decoding, employ the following utilities:

Use the Unix diff utility to check that the original file is identical to the file produced after decoding the encoded file (i.e., round-tripping works).
Use the Unix xxd utility with the -b flag to dump a file to its binary representation. This allows you to check that either a .grin file or a plaintext file is laid out exactly as you expect.

Here some additional notes to aid you in development:

You should not have to perform direct bit-level manipulation in this program (i.e., use the shift or logical bit operators). All your bit operations should be performed through BitInputStream and BitOutputStream.
Most of the work is building the Huffman Tree! Don’t move onto the decoding phase until you are certain that you can construct a Huffman Tree correctly and use it to encode and decode files.
Close your streams after you are done! In particular, make sure to explicitly close your BitOutputStream as you are done with it so that any remaining bits that have not yet been written to the file are indeed written.

Keyboard shortcuts

TTAP: Data Structures—Lab Manual