CSCI 230 -- Data Structures and Algorithms
Project 2 -- File Compression, Inc.

 

October 16, 1999

Submission Deadline: Wednesday, Nov. 10 at 11:59:59 pm

Your successful completion of the ``Object Oriented Airlines'' project has resulted in union strike and a referral to File Compression, Inc., a company specializing in software for compressing the size of files. Mr. Zvi Lepmel, Chief Technical Officer of FCI, has brought you in as a consultant to help with the implementation of a new product that performs a type of compression known as Huffman coding. (You can find some background information on this technique in your textbook in Section 10.1.2.)

Huffman coding requires the ability to manipulate binary trees, so the main deliverable for this project will be the implementation of a binary tree class, similar to the generic container classes found in the C++ Standard Library. You have already met with the FCI team and sketched out the following interface for the class:

template <class T>
class binary_tree
{
public:
  binary_tree();
  ~binary_tree();
  binary_tree(const T &);
  binary_tree(const binary_tree &);
  binary_tree & operator=(const binary_tree &);

  friend class iterator;
  class iterator
  {
  public:
    friend class binary_tree;
    iterator();
    ~iterator();
    T & operator*() const;
    bool operator!=(const iterator &) const;
    bool operator==(const iterator &) const;

    iterator left() const;            // go to left child node
    iterator right() const;           // go to right child node
    iterator parent() const;          // go to parent node
    bool is_root() const;             // true if at root
    bool is_leaf() const;             // true if at a leaf
  };

  iterator begin() const;
  iterator end() const;
  T & root();

  void combine(binary_tree & t1, binary_tree & t2);
};

In addition to the usual constructors and destructors, the binary tree class also contains an iterator class for traversing over the nodes in the tree. Binary tree iterators support some of the normal iterator operations, plus some special functions for traversing binary trees. Additional member functions of the binary tree class provide iterators to the "begin" (root) node and a special "end" node not in the tree, and fetch the value stored in the root node of the tree.

Here is an example of how the binary tree class and its iterator class is intended to be used:

// Print out contents of tree using an ``in-order'' traversal.
void inorder_traversal(const binary_tree<int>::iterator & i)
{
  if (i.is_leaf())
  {
    std::cout << *i << " ";
  }
  else
  {
    inorder_traversal(i.left());
    std::cout << *i << " ";
    inorder_traversal(i.right());
  }
}

void main()
{
   binary_tree<int> tree;

    ...   // put some stuff into the tree

   inorder_traversal(tree.begin());
}

One member function deserves special mention. Since a binary tree container will be made up of dynamically allocated nodes, it is possible to "combine" two binary trees as the children of the root node of a third binary tree in constant time (this is similar to how STL lists can be spliced together). A special function is provided in the header and should be implemented by you to do exactly this. The nodes in t1 become the left subtree, and the nodes in t2 become the right subtree of the third tree (represented by *this). The "root" tree must consist of only a single node, and both t1 and t2 are empty afterwards. This sounds complicated, but remember it will be done in constant time!

With the help of this binary tree class (and some useful standard library components), a class for performing Huffman encoding and decoding can be implemented. The interface for this class is quite simple it provides two member functions, one to encode and one to decode. Both use standard library streams for their input and output.

class huffman_codec
{
public:
  void encode(std::istream &, std::ostream &);
  void decode(std::istream &, std::ostream &);
};

Encoding Algorithm

The Huffman encoding algorithm is as follows:

  1. Construct the encoding tree:
    1. Count the frequency of each byte value in the input (note that there are 28 = 256 possible byte values).
    2. Construct an initial binary tree for each byte value, weighted by its frequency.
    3. Repeat until there is only a single tree remaining: combine the two trees with the smallest weights into a new tree, with weight equal to the sum of that of the two combined trees.
  2. Construct the encoding table: for each byte value in the input, determine its code by tracing from the leaf node representing that value to the root of the tree. (Note that this will give you the code backwards, and you will need to reverse it.)
  3. Write out the compressed data:
    1. Write out the encoding tree (it is necessary to decode the file later). See below for a technique to do this.
    2. Write out the count of characters in the input.
    3. Write out the compressed data.

Decoding Algorithm

To decode a file:

  1. Read in and reconstruct the encoding tree (see below).
  2. Read in the character count.
  3. While there are characters left to decode:
    1. Start at the root of the encoding tree.
    2. While not at a leaf node, read a bit from the input and go to the left or right child as appropriate.
    3. Output the character in the leaf node.

Encoding Tree Output

Writing out the encoding tree is fairly straightforward. First, we can ignore the weight information, since it is only used in the initial construction of the tree from the frequency data. Also, we can take advantage of the fact that every node in the tree is either a leaf or has exactly two children.

The algorithm to write out the tree is recursive:

  1. If the root node of the tree is itself a leaf:
    1. Write out the byte value stored in the leaf, preceded by the character "." (period).
    2. Return.
  2. Otherwise:
    1. Recursively write out the left subtree, surrounded by parentheses.
    2. Recursively write out the right subtree, surrounded by parentheses.

Encoding Tree Input

Reading in and reconstructing the tree is also recursive:

  1. Read a character byte.
  2. If the character is "." (period), then we have a leaf:
    1. Read the next byte, and create a new tree with that value in its node.
    2. Return the new tree.
  3. Otherwise, the character must be a left parentheses, indicating we have two subtrees:
    1. Recursively read in the left subtree.
    2. Read in and skip the closing right parentheses and the next left parentheses.
    3. Recursively read in the right subtree.
    4. Read in and skip the closing right parentheses.
    5. Create a new tree combining the left and right subtrees, and return it.

Program synopsis and input format

The program will be run twice with the command-lines

    huffman encode input-file compressed-file
    huffman decode compressed-file output
The decoded output will be compared to (and should be identical with) the input file. You can use any file for sample input (even binary files).

Notes, hints, and assumptions

Implementation environment

Your program must compile and run using the Visual C++ developement environment.

Submission dates and guidelines

The final submission deadline is November 10 at 11:59:59 pm. Projects submitted later than this will NOT be accepted for credit.

Detailed project submission guidelines will be posted on the course web site.

Grading criteria

The program will be graded 25% for a clean compilation, 40% for correctness of the program, and 35% for program structure. Criteria for program correctness may be discerned from the foregoing description and will solely be based on the output from your program. Program structure includes class organization, member function design, code readability (indentation, variable names, etc.), and commentary. There should be comments describing the purpose of each class and the member functions and member variables. The comments about each class must also include a discussion of the flexibility of the class design and how well it will support future changes. Keep other comments, especially within the body of each function, short and concise. Avoid comments that just state in English what is obvious from the code. One bad example is

   i ++;   //  increment i

Academic integrity

Students may discuss the class and algorithm design. All code must be implemented by the student alone. Sharing of code among students is expressly forbidden and will be detected by code comparison tools. Projects from all six sections will be graded together by the TAs.