CPS 100, Fall 2000, Huffman Coding

You will implement two programs:

• huff: compresses a given file

• unhuff: uncompresses a file compressed by huff

So applying unhuff to a file compressed by huff must exactly reproduce the original file. This involves implementing both programs based on the greedy Huffman algorithm discussed in class and in this online explanation.

The resulting program will be a complete and useful compression program although not, perhaps, as powerful as standard programs like compress or zip which use slightly different algorithms permitting a higher degree of compression than Huffman coding.

Because the compression scheme involves reading and writing in a bits-at-a-time manner as opposed to a char-at-a-time manner, the program can be hard to debug. In order to facilitate the design/code/debug cycle, you should take care to develop the program in an incremental fashion. If you try to write the whole program at once, you probably will not get a completely working program! Design, develop, and test so that you have a working program at each step.

Build a program by adding working and tested pieces.

Getting Started

• Makefile (site specific)
• globals.h
• bitread.cpp
• showargs.cpp
• tpqtest.cpp
• usemap.cpp

huff: The Compression Program

• To compress a file, count how many times every character occurs in a file. These counts are used to build weighted nodes that will be leaves in the Huffman tree.
The word character is used, but we mean 8-bit chunk and this chunk-size could change. Do not use any variables of type char in your program. Use only ints.
• From these counts, build the Huffman tree. To do this, first create one node per character, weighted with the number of times the character occurs, insert each node into a priority queue. Then choose two minimal nodes, join these nodes together as children of a newly created node, and insert the newly created node into the priority queue. The new node is weighted with the sum of the two minimal nodes taken from the priority queue. Continue this process until only one node is left in the priority queue. This is the root of the Huffman tree.
• Create a table or map of characters (8-bit chunks) to codings. The table of encodings is formed by traversing the path from the root of the Huffman tree to each leaf, each root-to-leaf path creates an encoding for the value stored in the leaf. When going left in the tree append a zero to the path; when going right append a one. All characters/encoding bit pairs may be stored in some kind of table or map to facilitate easy retrieval later.
• Finally, read the input file a second time. For each character/8-bit chunk read, write the encoding of the character (obtained from the map of encodings) to the compressed file.

To uncompress the file later, you must recreate the same Huffman tree that was used to compress (so the codes you send will match). This tree might be stored directly in the compressed file, or it might be created from character counts stored in the compressed file. In either case, this information must be coded and transmitted along with the compressed data (the tree/count data will be stored first in the compressed file, to be read by unhuff.

unhuff: The Decompression Program

The first thing unhuff should do is verify that the file being uncompressed was originally compressed by your huff program. In particular, your program should not crash if it is given a program to uncompress that was not compressed using the corresponding Huffman compression program. The robustness of the program will be an important criterion in grading the program.

One easy way to ensure that both programs work in tandem is to write a "magic number" at the beginning of a compressed file. This could be any number of bits that are specifically written as the first N bits of a huffman-compressed file (for some N). The corresponding decompression program first reads N bits, if the bits do not represent the "magic number" then the compressed file is not properly formed. You can read/write bits using the classes declared in bitops.h. A sample program which uses bitops.cpp is given in bitread.cpp.

Storing the Huffman Tree

For decompression to work with Huffman coding, information must be stored in the compressed file which allows the Huffman tree to be re-created so that decompression can take place. There are many options here. You can store all codes and lengths as normal (32 bit) C/C++ ints or you can try to be inventive and save space. For example, its possible to store just character counts and recreate the codes from the counts. Its also possible to store code-lengths and codes using bit-at-a-time operations. Any solution to storing information in the compressed file is acceptable, but full credit requires some attempt to save space/storage. Space-saving techniques are defined as those using less space than simply storing 257 counts as 32 bit ints. One useful technique is to write the tree to the file using a preorder traversal. You can use a 0 or 1 bit to differentiate between internal nodes and leaves, for example. The leaves must store character values (in the general case using 9-bits because of the pseudo-eof character).

For example, the sequence of 0's and 1's below represents the tree on the right (if you write the 0's and 1's the spaces wouldn't appear, the spaces are only to make the bits more readable to humans.)

0 0 1 001100001 1 000100000 1 001110100

The first 0 indicates a non-leaf, the second 0 is the left child of the root, a non-leaf. The next 1 is a leaf, it is followed by 9 bits that are represent 97, the ASCII code for 'a'. Then there's a 1 for the right child of the left child of the root, it stores 32, the ASCII value of a space. Then next 1 indicates the right child of the root is a leaf, it stores the ASCII value for a 't' which is 116.

Your program can write these bits using a standard pre-order traversal. You can then read them by reading a bit, then recursively reading left/right subtrees if the bit is a zero.

Program Interface

The huff program should write its compressed output to a file generated from the original file name by adding the suffix .hf to the file name. For example, the command below should compress the file foo storing the result in foo.hf.

    huff foo

Forcing Compression

The user should have the option of invoking huff with an argument -f which forces compression even when the compressed file is bigger. For example:

      prompt< huff foo
      no compression yielded, no output file foo.hf written
      prompt< huff -f foo

Finally, if the user specifies the -h option, your program should output the options that it supports and then exit. This allows the user to see how you expect the program to be used.

Determining If Compression Happens

Coding and Algorithmic Details

Note, do not use any variables of type char! You should use int variables when you think you might need a char everywhere in your program. The only time you might want to use a char variable is to print for debugging purposes -- you can cast an int to a printable char as shown in the code fragment below.

     int k = 'A';
     cout << char(k);

Command line arguments

The program showargs.cpp shows how command line arguments can be read and processed by your program. Do not spend time worrying how to process command-line arguments until you are sure the program works, this is not the most important part of the program. You can add command-line parameters after everything works.

Pseudo-EOF character

(for more details, see the complete huffman coding discussion.)

The operating system will buffer output, i.e., output to disk actually occurs when some internal buffer is full. In particular, it is not possible to write just one single bit to a file, all output is actually done in "chunks", e.g., it might be done in eight-bit chunks. In any case, when you write 3 bits, then 2 bits, then 10 bits, all the bits are eventually written, but you can not be sure precisely when they're written during the execution of your program. Also, because of buffering, if all output is done in eight-bit chunks and your program writes exactly 61 bits explicitly, then 3 extra bits will be written so that the number of bits written is a multiple of eight. Because of the potential for the existence of these "extra" bits when reading one bit at a time, you cannot simply read bits until there are no more left since your program might then read the extra bits written due to buffering. This means that when reading a compressed file, you CANNOT use code like this.

In Huffman trees/tables you use in your programs, the pseudo-EOF character/chunk always has a count of one --- this should be done explicitly in the code that determines frequency counts. In other words, a pseudo-char EOF with number of occurrences (count) of 1 must be explicitly created.

In the file globals.h the number of characters counted is specified by HUFF_ALPH_SIZE which has value 257. Although only 256 values can be represented by 8 bits, one character is used as the pseudo-EOF character [the value of PSEUDO-EOF could be 256, but it's set for 257 for historical reasons]. Your program should be able to work with n-bit chunks, not just 8-bit chunks.

Priority Queues

A heap-based, templated priority queue class tpqueue is provided (in the standard location with libtapestry files, see tpq.h. and tpq.cpp.). The program tpqtest.cpp shows how to use the class with pointers.

Creating a Table from a Huffman-tree

(for more details, see the complete huffman coding discussion.)

To create a table or map of coded bit values for each character you'll need to traverse the Huffman tree (e.g., inorder, preorder, etc.) making an entry in the table each time you reach a leaf. For example, if you reach a leaf that stores the character 'C', following a path left-left-right-right-left, then an entry in the 'C'-th location of the map should be set to 00110. You'll need to make a decision about how to store the bit patterns in the map. At least two methods are possible for implementing what could be a class/struct BitPattern:

• Use a string. This makes it easy to add a character (using +) to a string during tree traversal and makes it possible to use string as BitPattern. Your program may be slow because appending characters to a string (in creating the bit pattern) and accessing characters in a string (in writing 0's or 1's when compressing) is slower than the next approach.

• Alternatively you can store an integer for the bitwise coding of a character. You need to store the length of the code too to differentiate between 01001 and 00101. However, using an int restricts root-to-leaf paths to be at most 32 edges long since an int holds 32 bits. In a pathological file, a Huffman tree could have a root-to-leaf path of over 100. Because of this problem, you should use strings to store paths rather than ints. A slow correct program is better than a fast incorrect program.

Implementing and Debugging

Some ideas for classes are given below. You may decide to combine some of these into one class, or you may decide to implement more classes. These are a start and some suggestions, not requirements.

• A class could be responsible for creating the initial counts of how many times each character occurs. You could design, implement, and test the class in isolation from the rest of the huff program. Doing this for each of several classes will help both in developing huff and in re-using code in writing the uncompress program unhuff.

  For example, one possibility for a character counting class is shown below:

  #include "globals.h" #include "charcounter.h" CharCounter cc; cc.readFile("data/poe.txt"); // count chars in file int k; for (k = 0; k < ALPH_SIZE; k++) { int occs = cc.count(k); if (occs > 0) { cout << char(k) << " " << occs << endl; } } cout << "pseudo-eof count: " << cc.count(PSEUDO_EOF) << endl; Here the member function CharCounter::readFile reads and counts all the characters in a file. The function CharCounter::count returns the number of occurrences of a given character. You might also use CharCounter to read compressed-file headers too in unhuff.

  You'll need at least ALPH_SIZE counters (typically this is 256, see globals.h). There are more than 256 possible characters if you include the pseudo-EOF character

• A class to create the Huffman tree used in compression and decompression. The tree is created from character counts, so a Huffman-tree creating class might use a CharCounter object in creating the Huffman tree.

• A class that represents the map of character and encoding bit pattern pairs. You can use one of the templated map classes in tmap.h (see tmap.h and a demo program usemap.cpp) or write your own map-like class.

  Since the values stored in the map are constrained to be between 0 and 257, you can simpley store bitpattern/strings in a vector and index them directly. There's nothing at all inferior about this approach compared to using a map.

Similarly, you may want to implement a function to print the Huffman tree to help you determine if the tree you've built is correct.

Designing debugging functions as part of the original program will make the program development go more quickly since you will be able to verify that pieces of the program, or certain classes, work properly. Building in the debugging scaffolding from the start will make it much easier to test and develop your program. When testing, use small examples of test files maybe even as simple as "go go gophers" that help you verify that your program and classes are functioning as intended.

You might want to write encoding bits out first as strings or printable int values rather than as raw bits of zeros and ones which won't be readable except to other computer programs. A Compress class, for example, could support printAscii functions and printBits to print in human readable or machine readable formats.

We cannot stress enough how important it is to develop your program a few steps at a time. At each step, you should have a functioning program, although it may not do everything the first time it's run. By developing in stages, you may find it easier to isolate bugs and you will be more likely to get a program working faster. In other words, do not write hundreds of lines of code before compiling and testing

Using bitops.cpp

Bit read/write subprograms

this code is similar to the loop shown below which uses the standard get function to read a char from a stream.

When using writebits to write a specified number of bits, some bits may not be written immediately because of some buffering that takes place. To ensure that all bits are written, the last bits must be explicitly flushed. The function flushbits is called automatically if your program exits properly when the obstream destructor is called. You should not need to call it explicitly. If, for some reason you create an obstream object referenced by a pointer, make sure to delete the object so that its destructor is called.

Although readbits can be called to read a single bit at a time (by setting the first parameter to 1), the second parameter to the function is an int. You'll need to be able to access just one bit of this int (inbits in code above). In order to access just the right-most bit a bitwise and & can be used:

An example program using the bitreading classes is provided for you to study, it is called bitread.cpp. Because Huffman coding requires two passes over the input file you will need to use the method rewind that works with object variables of type ibstream.

The effect of ib.rewind() is to allow the input bit stream ib to be ''read again'', i.e., a loop that reads until no more bits are available (checking the return-value of readbits) will be able to read the entire file again.

Command-line Arguments

 
      g++ -g -o foo foo.cpp

prompt> showargs

program showargs has no command-line args

prompt> showargs -o fish -b fowl

showargs has 5 command-line args:
1-th arg is: -o
2-th arg is: fish
3-th arg is: -b
4-th arg is: fowl

Grading

Grading

Extra Credit

When this single file is unhuffed, all the files originally compressed should be uncompressed/unhuffed.

You'll need to store information about file names in the huffed file to know what to use for names when unhuffing. The original names must be used when uncompressing.

This extra credit is worth 10 points.

Submit

 submit_cps100 huff README *.h *.cpp Makefile