In this assignment, you will be implementing the Huffman coding algorithm to compress and decompress a file. This will be accomplished using some of the new data structures that have been introduced in lecture and readings. For example, you will use the priority queue container class of the C++ STL. In addition, you will also implement binary file IO, which essentially means reading from and writing to a file in binary as opposed to ASCII.
In order to keep Piazza response times fast, please fully read this write-up. Any questions asked on Piazza that have been answered here will not be answered again.
For those who feel comfortable working in C++ and avoiding the pitfalls and common mistakes covered throughout this write-up, here is a general overview of what this assignment entails.
compress
uncompress
Note: This section is not required reading, just some history behind Huffman coding.
Even though disk space and bandwidth are cheaper now than ever before in history, there is also more data than ever before. So the ability to compress data is still very useful. Compression comes in two flavors, lossless and lossy. It is often possible to make a file significantly smaller without any loss of information whatsoever (lossless compression). One such method, known as Huffman coding, was invented by David Huffman in 1952. Huffman code compression is used today as part of JPEG image compression, the MP3 audio compression standards, the Unix file compression command pack, and many other applications. In contrast, many audio and video file formats use a different type of compression known as lossy. With this compression type, some information is lost.
You must follow these steps to acquire the starter code and prepare for the assignment. Copy the files from /home/linux/ieng6/cs100f/public/handout/PA3_handout.tar (cp /home/linux/ieng6/cs100f/public/handout/PA3_handout.tar . to copy into current directory) and uncompress (tar -xf PA3_handout.tar) in the appropriate location. As a review of linux command line, you can change directories using "cd" and to build the code, you can type "make" in the appropriate directory.
The skeleton code provided to you in Git contains the following files:
HCNode.hpp, HCTree.hpp, BitInputStream.hpp, BitOutputStream.hpp
Solution files for final submission:
compress.cpp, uncompress.cpp, HCNode.hpp, HCNode.cpp, HCTree.hpp, HCTree.cpp, BitInputStream.cpp/hpp, BitOutputStream.cpp/hpp
Read below to find out what you are expected to implement in each of these files.
Note: See the Important Notes section of the writeup for the differences between the .hpp and .cpp files.
The compress.cpp file will contain the code needed for the compression portion of this assignment. When run, this program will read the contents of the file named by its first command line argument, construct a Huffman tree for the contents of that file, and use the Huffman tree to encode the data into binary. The encoded data is essentially the compressed version of the contents of the input file and should be written to a output file named by the second command line argument. The binary executable, which will be named compress, can be run as follows:
./compress infile outfile
infile is the file to be compressed. outfile will be the compressed version of the file.
Refer to the section on Error Handling in Important Notes for what types of input validation are needed.
The uncompress.cpp file will contain the code needed for the decompression portion of this assignment. When run, this program will read the contents of the file named by its first command line argument. This file should be one that has been created by your compress program. It will use the contents of that file to reconstruct the original, uncompressed version, which is written to a file named by the second command line argument. The binary executable, which will be named uncompress, can be run as follows:
./uncompress infile outfile
infile is the file to be decompressed. outfile will be the decompressed version of the file.
Refer to the section on Error Handling in Important Notes for what types of input validation are needed.
Similar to the BST, your implementation of the Huffman tree will contain nodes, each holding pointers to the left and right children of that node as well as a pointer to the parent node. What's new in the nodes of your Huffman tree are the members count and symbol, which hold the frequency of a particular symbol and its symbol ID, respectively.
In addition the HCNode class will overload the < operator. Remember, to construct the Huffman tree correctly, nodes must be placed into a priority queue, and removed according to the priority rule. Since an HCNode is not a primitive type, the priority queue can not determine which node to give higher priority to without your help. Overriding the < operator will be used to help the priority queue compare two nodes and subsequently assign the correct priorities. Do not forget that you must define a consistent way of dealing with ties. So, if two nodes have the same count, you should have a deterministic way of giving one of the nodes higher priority. Think about why this is necessary. We will discuss more on this during lecture.
One crucial data structure you will need to implement is a binary tree that represents the Huffman tree and further provides the encoding and decoding functionalities. The HCTree.hpp header file provided to you specifies possible interfaces for this structure. You may modify this file in any way you wish. Additionally, you will need to write a companion HCTree.cpp file that implements the interfaces specified in HCTree.hpp. You will need your implementation of the Huffman tree in your compress and uncompress programs.
From the source code comments, the functionality of the remaining methods should be clear. Encoding is the process of determining the bit stream for the compression part of the project, and the decoding is used for decompressing the data.
Note: See the Important Notes section of the writeup for the correct method of handling file reads and writes.
The BitInputStream will be used for the decompression part of the assignment. Remember, when reading the compressed file from disk, you are going to start at the root of the tree, then reading a single bit at a time traverse the tree until you reach a leaf node. The leaf will be the original symbol that was encoded from the source file. Since the smallest chunk of data that can be read from a file is a byte (8 bits), you must implement a buffer to hold the chunk of data read from the file and implemenent additional functionality to assist with bit level reads.
The initial contents of the compressed file will be some type of header with the necessary information to decompress your input file. Some of this information can be extracted at the byte level and/or the four-byte level. This is where readByte() and readInt() will prove useful. Pay special attention to the comments in the source file. Both readByte() and readInt() should not touch the bit buffer used for readBit().
Note: See the Important Notes section of the writeup for the correct method of handling file reads and writes.
The BitOutputStream will be used for the compression part of the assignment. Remember, when writing the compressed file to disk, you are going to be encoding bits. You will be starting at the leaf of the tree, and traversing towards the root keeping track of whether to encode a 0 or a 1. However, since you most likely will have a bit string with a length not divisible by eight (the length of a byte), you will have to store these bits in a buffer and write them to disk only when the buffer is full.
The writeByte() and writeInt() methods will not touch the buffer, but will write either one byte or four bytes to the file stream directly. The flush() method should empty any remaining bits in the buffer whenever appropriate -- especially at the end of the compression phase.
In implementing Huffman's algorithm, you will find it convenient to use multiple data structures. For example, a priority queue will assist building the Huffman tree. Feel free to utilize other beneficial data structures. However, you should use good object-oriented design in your solution. For example, since a Huffman code tree will be used by both your compress and uncompress programs, it makes sense to encapsulate its functionality inside a single class accessible by both programs. With a good design, the main methods in the compress and uncompress programs will be quite simple; they will create objects of other classes and call their methods to do the necessary work.
One important design detail for this assignment is: how to represent information about the Huffman code in the compressed file so the file can be correctly decompressed. Probably the easiest way to do it is to save the frequency counts of the bytes in the original uncompressed file as a sequence of 256 integers at the beginning of the compressed file. You have to think about the question of how many bytes you will need to use to store each integer and how this relates to the maximum size of the files that you are required to encode. To help you with your header design, please note the following:
Your compress program must work for input files up to 10 megabytes in size, so a particular byte value may occur up to 10 million times in the file.
Storing the frequency counts in your header is not very efficient in terms of space: it uses 1024 bytes of disk for the header no matter what the statistics of the input file are. Alternative approaches may use arrays to represent the structure of the tree itself in the header. Other schemes also work. With some cleverness, it is possible to optimize the header size to about 10*M bits, where M is the number of distinct byte values that actually appear in the input file. However, do not attempt to reduce the size of the header until you’ve gotten your compress and uncompress to work correctly for the provided inputs.
You must ensure all file IO is handled in binary mode, otherwise your program will not be portable across different operating systems. Reading and writing in text mode (ASCII) causes the family of Microsoft Windows operating systems to perform translations on the ASCII character codes representing line endings. Note: On Unix and Linux operating system, this translation does not happen. ASCII mode exists as an option purely for compatibility purposes with other platforms and is completely ignored internally.
What does all this mean?
Let's start with an explanation of how your key strokes are recorded in an ASCII text file. A set of 256 unique 8-bit sequences representing character codes, known as the ASCII table, is used to map your key stroke to a unique entry in this table. Besides letters, numbers, and symbols, this set also contains bit sequences for the space, enter, tab, and other special characters.
For example, when you press the letter 'a' on your keyboard, the bit sequence mapped to 'a', 01100001 is stored in your file. Generally, we do not refer to these bit sequences in their binary form, but instead use their equivalent hexadecimal notation for brevity. For 'a', this value is 0x61. When you press the space bar on your keyboard, the value 0x20 is stored. Across all operating systems, this is generally handled in exactly the same manner.
Now that we have an understanding of how key strokes are mapped to byte-sized values, let's return to what happens when you press enter on your keyboard.
Just a couple notes in case you do some extra research online. At one time, Mac OS, Unix, and Windows all handled this process differently. Today, OSX and Unix handle this process exactly the same. Only Microsoft Windows, dating all the way back to MS-DOS, still handles this process differently. Thus, the point of this section.
When you press enter on your keyboard, this is just another value looked up in the ASCII table and stored in your file. On both OSX and Unix (including Linux) the bit value recorded is 0x0A -- this is known also as a line-feed character. However, on Windows, two values are used, 0x0D0A. This is referred to as a carriage return-line feed.
Now, to the point of the assignment.
Let's say you're writing a program that opens a text file, does some processing to it, and then saves the changes to a new file. On OSX and Unix, regardless of the file mode selected when opening the input and output files (even if one is binary mode and the other is ASCII mode), all is well in the world. The line-endings in both files will be exactly the same. Remember, ASCII mode only exists on those operating systems for legacy purposes.
Now, let's say you write/compile this same program on a Windows machine. If you open both files in ASCII mode, then each new-line character read from the input file will be translated to the Microsoft implementation. This means each occurrence of 0x0A will be translated to 0x0D0A in the output file.
For a text file, this might not be a problem. Many Unix and Mac text editors are capable of recognizing the Windows end of line (EOL) sequence, and behave as expected. However, in some text editors, you may actually end up seeing a ^M at the end of each line. If you've ever seen this before, now you know why!
Just because this might be OK for a text file, it is ABSOLUTELY NOT OK for any other type of file such as a JPEG or MP3. Why? Well, because in an MP3 file, an occurrence of 0x0A is not a new line character, it's just an 8-bit sequence that happens to match the line-feed sequence in the ASCII table. Thus, treating the input as a line-feed would be fatal to your programs correctness.
There's one thing I haven't mentioned yet. This is the heart of the problem. When Windows encounters 0x0D0A in a text file, it translates it 0x0A in memory. When writing to a file, 0x0A is translated back to 0x0D0A. This is the cause of our headache. The reason is, what if the input file actually contained 0x0A and when we wrote to the output file, we wrote 0x0D0A?
In your Huffman compression program, if you filled up your bit buffer with the bit sequence 00001010 and then wrote that byte of data to a file, you would end up writing 00001101 00001010. Now your file contains extra information that was never part of the original!
Long story short: Don't open your files in ASCII mode, use Binary mode instead
All file reads and writes must be done using the functions get() and read() for input file streams, and put() and write() for output file streams. DO NOT use the overloaded operators << or >>. Using them will result in a translation of the value to ASCII text (regardless of file open mode). For example, the following code:
some_output_file_stream << 10;
will not result in the integer value 10 being written to the file. Instead the ASCII value for the characters 1 and 0 will be written.
This is a huge part of this assignment and one that we will not be providing much help with. However, we understand this can seem like a daunting task. So, to provide you with some guidance, there are some questions you must ask, and to identify those questions, it is suggested that you pick a random word or sentence, and perform the compression on paper. Essentially, you should tally up the occurrences of each character, create the Huffman tree, encode your selected text, and hand the encoded (compressed) string of ones and zeros to your partner. Don't let them see the original string. Ask your partner to decompress the encoded file, restoring the original text. Obviously, they will be hopelessly lost without some additional knowledge. These questions will be your guide to understanding what else needs to be stored in the compressed file. Oops! That was a hint.
Once you've come up with a solution, it is strongly advised that your first implementation be the most naive and straightforward version possible. Later, you can work towards optimizing this process. Optimizing in this context means eliminating any unnecessary information from your file header, further reducing the compressed file size.
It is important to implement all the appropriate error handling to ensure the program runs correctly and does not crash if the user provides invalid arguments at the command-line. Some checks to perform: Does the input file exist? Can it be opened and read from? Does the file contain any data? Can the output file be written?
A useful Linux tool for comparing two files is called cmp (see the manual page for cmp by typing 'man cmp' in an open terminal). Essentially, you should compress a file with the compress utility, followed by decompressing it with the uncompress utility, and then comparing the compressed/decompressed version with the original file. If you did everything correctly, they will be 100% identical.
Another useful tool for performing sanity checks is hexdump (see the manual page for hexdump by typing 'man hexdump' in an open terminal). Note, x86 architecture is little endian, so you must include the -C flag when using hexdump.
One difference from the assignment (BST) is the introduction of an .hpp file. Unlike other languages, such as Java, that allow for interfaces to be created, C++ does not. Therefore, the closest option a programmer has for decoupling the interface from the actual implementation is the use of header files. The header files contain just the prototypes for the functions and the class. No actual definitions for functions exist in the header files. The actual implementation is placed inside the cpp files. In general, this is the convention used by many C++ programmers. C++ templates are sometimes an exception and this has to do with compiler challenges.
The files refcompress and refuncompress are "reference" implementations that satisfy the functional requirement of this assignment. You can use them to verify your results. Note that the reference binaries were compiled to run on ieng6, so if you attempt to run it on a different architecture they will most likely not work.
Note: Your compress is not expected to work with refuncompress, and your uncompress is not expected to work with refcompress. The provided reference executable files are a matched pair.
When you have completed the assignment, you must submit it. One thing you must add to identify yourself and who you worked with, you must have a file called student_numbers.txt that contains student numbers one per line with UNIX style endings. Now you will do this in two steps. We have created a turnin prep script that checks to make sure your code builds with our makefiles and passes some sanity checks.
Some points to keep in mind:
There are 20 possible points on the assignment. If your solution files do not compile and link error-free, you will receive 0 points for this assignment. We will compile your files using the Makefile distributed with the assignment, on ieng6.
Points for Final Submission:
20 points for your compress and uncompress programs that use Huffman coding to correctly compress and decompress files. We define acceptable compression to be within 25% of the supplied reference compress program. So if the reference compresses a given file to 100KB, you will not lose credit if your correctly compressed files are not larger than 125KB. You will not be required to demonstrate compression for files smaller than 10KB, but you must compress them correctly. We define "correctly" in the sense that you can recover the original file from the compressed version. If your implementation beats the reference implementation in compression on a subset of test cases, then you will receive 2 points extra credit.