COS 226 Programming Assignment Checklist: Burrows-Wheeler Data Compression

Frequently Asked Questions

What program should I use for reading and writing the data? You must use BinaryStdIn.java and BinaryStdOut.java. These read and write sequences of bytes, whereas StdIn.java and StdOut.java (as do System.out.print() and Scanner) read and write sequences of Unicode characters. These are in the updated stdlib.jar.

My programs don't work properly with binary data. Why not? Be absolutely sure that you are only using BinaryStdIn.java and BinaryStdOut.java for input and output.

Why does BinaryStdIn return the 8-bits as a (16-bit unsigned) char instead of as (an unsigned 8-bit) byte? The primitive type byte is a bit annoying in Java. When you operate on a byte, it is typically promoted to an int. E.g., to convert a byte b to a char ch, you must write ch = (char) (b & 0xff) instead of ch = (char) b. By using char, we avoid the hassle.

How can I compare the contents of two files (to check that the decoded version equals the original)? On OS X and Linux, use the command diff file1 file2; on Windows use the command fc file1 file2.

How can I view the contents of a binary file? You can use HexDump.java, as in the assignment. Alternatively, on OS X and Linux, you can use the hexdump or od utilities:

% hexdump < file
% od -t x1 < file

How do I determine the sizes of the original and compressed files? One way is to use your operating system's file manager and inspect the file size. You can also use HexDump.java, as in the assignment. Alternatively, on OS X and Linux, you can use the wc utility:

% wc -c < file
% java BurrowsWheeler - < file | java MoveToFront - | java Huffman - | wc -c

The program RadixQuicksort.java doesn't work with some inputs. Why not? It assumes that the strings are '\0'-terminated. Feel free to use Arrays.sort() or modify RadixQuicksort so that it sorts arbitrary strings. Note that RadixQuicksort implements the partition algorithm differently than described in the lecture slides and the packet this semester.

How much memory can my program consume? The Burrows-Wheeler encoder may use quite a bit, so you may need to use the -Xmx option when executing. You must use space linear in the input size N. (Industrial strength Burrows-Wheeler compression algorithms typically use a fixed block size, and encode the message in these smaller chunks. This reduces the memory requirements, at the expense of some loss in compression ratio.)

How do I use gzip and bzip2 on Windows? It's fine to use pkzip or 7-zip instead.

I'm curious. What compression algorithm is used in PKZIP? In gzip? In bzip2? PKZIP uses LZW compression followed by the Shannon-Fano trees algorithm (an entropy encoder similar to Huffman). The Unix utility gzip combines a variation of LZ77 (similar to LZW) and Huffman coding. The program bzip2 combines the Burrows-Wheeler transform, Huffman coding, and a (fancier) move-to-front style rule.

Input, Output, and Testing

Input. Here are some sample input files. To fully test your program, you should also try to compress and uncompress binary files (e.g., .class or .jpg files).

Reference solutions. For reference, we have provided the output of compressing aesop.txt and us.gif. We have also provided the results of applying each of the three encoding algorithms in isolation. Note that the GIF file is a binary file and is already compressed.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

Optional Optimization

Implement an efficient and elegant version of RadixQuicksort.java that works for arbitrary strings (even those that contain the character '\0'). Compare the performance of your implementation against the system sort when suffix sorting typical text files.