CSE100
Project #1
Due: 2008-10-14  11:59:00PM PDT.


File Compression

In this project, you will build utilities for compressing and uncompressing data files, similar to ZIP, RAR, BZ2, etc.  Specifically, you will use Huffman coding to create a more efficient dictionary to represent an input file; see Lewis & Denenberg, p145 for an overview of Huffman coding.

The compressor is invoked as:
    java Compress infile outfile

When run, this program reads infile, builds the Huffman coding tree from the contents of infile, and uses the code to write the compressed version to outfile in the specified format (see below).  The input file is not necessarily text, so you should treat it as a binary file (the "alphabet" for this assignment is all possible values of 1 byte, i.e., 0x00 through 0xFF).


The uncompressor is invoked as:
    java Uncompress infile outfile

When run, this program reads infile, which is a compressed file created by Compress, and uses its contents to reconstruct the original data in outfile.


Design

Your Compress program should go through the following steps:
  1. open the input file for reading,
  2. scan the input file and build a frequency counter for each symbol* encountered,
  3. use the frequency counter to construct a Huffman coding tree,
  4. open the output file for writing,
  5. write the header information (length, alphabet size, codebook) to the output file,
  6. re-read the input file, and for each byte, translate it to its corresponding codeword, and write it to the output file,
  7. close all files and exit.

* A symbol is one byte. 

Note: Writing the compressed data one bit at a time can be tricky.  You might want to pre-process the stream into bytes before writing to disk.


Your Uncompress program should go through the following steps:
  1. open the input file for reading,
  2. load in the header information,
  3. build a data structure which maps codewords to symbols (e.g. '01' -> X, '1101' -> Q),
  4. open the output file for writing,
  5. scan the body of the compressed file, translating codewords into symbols, and writing each symbol to the output file.
     
Note: Huffman coding is prefix-free, meaning that no codeword is a prefix of another codeword.  This means that you can read the bits one at a time until it matches a known codeword.  Again, reading one bit at a time can be tricky, so it might be helpful to translate the file's byte stream into a stream of bits (Booleans) before completing step 5.


Guidelines



Data Format

Your compressed files must adhere to the following format:


Example:

If the input file consists of:

    ABB

Then the compressed file, represented in hexadecimal, looks like:

    00 00 00 03         Length of the file
    00 00 00 02         Size of the alphabet
    41 01 00            Coding information for the first symbol (A) 
    42 01 80            Coding information for the second symbol (B)
    60                  The data stream 

Note that even though both symbols have a one-bit codeword (A -> 0, B -> 1), they are padded up to the nearest byte in the compressed file. (note that 8 = 1000 in binary, so a 1 padded with 0's) These extra 0-bits should not be interpreted as data.


There are three example compressed files available under /home/linux/ieng6/cs100f/public/p1data/.  For one of them, the original file is also provided.  You can use this to test whether your uncompress program is operating correctly by running the following commands:

    java Uncompress test.txt.p1z test.txt.new
    diff -q test.txt test.txt.new

If  there is no output from the diff command, then your uncompressed file is correct.  (See man diff for more information on this utility.)


Another utility that may be useful is hexdump, which displays the contents of a file in hexadecimal.  This will come in handy when testing your compress program.  For example, the command:

    hexdump -C test.txt.p1z

outputs:

    00000000  00 00 01 2b 00 00 00 18  44 04 10 45 04 30 46 04  |...+....D..E.0F.|
    00000010  40 47 04 50 41 05 a8 42  05 f8 43 04 00 4c 04 c0  |@G.PA..B..C..L..|
    00000020  4d 04 e0 0a 04 d0 48 04  60 49 04 80 4a 04 90 4b  |M.....H.`I..J..K|
    ...

The first column is the (32-bit) address of the first byte in the line, and each remaining column is a byte in the file, displayed in hex.  The contents of the file are displayed in ASCII in the far right column.


Turning in

When your program is finished, create a tar file including your source code and class files by running:

    tar czvf LASTNAME.tar.gz *.java *.class README

Then, submit your tar file by running:

    turnin -c cs100f -p p1 LASTNAME.tar.gz