Programming Assignment 3 Computer Science 102

Spring 2007

Due THURS 11:59pm APR 12

the 2nd midterm will bw MON APR 16.

Introduction

As discussed in draft#1, we are studying an efficient scheme for for compressing text files called Huffman coding. We again exploit the fact that not all characters appear with the same frequency in the text, by encoding rarely used characters with long codes and frequently used ones with short codes.

Given a set of characters and their corresponding frequencies, an optimal coding scheme is produced by Huffman coding. It uses a binary tree for encoding. In Draft #3, however, we use a heap as a priority queue instead of a linked list. The big Oh behavior for removing the smallest value (the root) from the heap is O(1) -- it's done in constant time -- and the behavior for reheaping is O(log(n)) since it only depends on the height; whereas, the big Oh behavior for removing the minimum values from a linked list and repositioning the combined treelet is O(n). The big Oh behavior for doing this for n nodes is O(n*log(n)) for the heap and O(n^2) for the linked list. Please use the command line to execute your program and read from it the two file names, namely, huff.txt (it contains the letters and frequencies) and huffcode.txt (the "compressed" binary file). The command line can be obtained from Run on the Start menu by typing cmd. The two file names should be used as global variables in your program. Note that this draft can be done with static methods.

Draft #3

We will use a heap implementation of a priority queue to this program. Note that here we use a min-heap in this project instead of the max-heap we used in class. Also, deleteMin() will replace the deleteMax() that is on the lecture links on the web. Here is the skeleton of the class you will be using:

```public class Hw3c
//solves draft #3 for project #3
{
static int last;
//the # of nodes in heap. This decreases as succesive pairs of
//minimum nodes are extracted
final static int MAX = 11;//there are 11 pairs of letter-frequency entries

static Comparable x = new Comparable[MAX + 1]//one more element for shift up

private static class HuffRecord//defines the data frequency record
{  public String letter;
public int freq;
}

private static class TreeNode implements Comparable
//defines the treelets comprising the list
{  public HuffRecord data;
public TreeNode left, right;
}
}
```

where HuffRecord and TreeNode are, as before, embedded classes. The keyword public is optional because it is the default. The class TreeNode must of course contain a compareTo method and should also contain a toString() method. Here are the methods to be altered or added to your class of draft #2:

1. public static void initialize() Here stream is an array of HuffRecord. This method assigns the two fields of stream[], i.e., freq and letter to the corresponding fields of an instance of TreeNode, let's say aux. It assigns this to an element of an array of Comparable, x[]. This array is an instance variable which represents the heap.

2. method shift(int m) shifts the elements if x one position, so that parent =child/2 has meaning.

3. Method build creates a heap by calling shiftUp(j) in a loop. To facilitate your understanding of the heap process let's call shiftUp(j) by the name insert instead.

4. Method reduceIt() calls reduce in a while loop while an instance variable last is greater than one. last represents the value of the highest subscript of the heap as the heap is shrunken,

5. private static void reduce() is similar to the method of the same name in draft #2. It
• calls DeleteMin twice to obtain the element of the heap with minimum frequency, i.e., the root. The first call should return a pointer op1 of type Comparable. The counter last is then decremented. The second call should return a pointer op2. These pointers should be cast to pointers p1 and p2 of type TreeNode.

• calls Combine with the above two pointers as parameters.
6. private static void combine(TreeNode p1, TreeNode p2) creates a new instance aux of TreeNode as in draft #2 whose frequency field is the sum of the frequencies in the objects pointed to by p1 and p2, and assigns aux to x[last]. Then places the element in its proper place in the heap by calling insert(last).

7. private static Comparable deleteMin(int n) saves the top of the heap (the first element in x[]) in temp, and replaces it with the last element in the array. It then reheapifies the heap by calling shiftDown(n-1). This method is defined in the heap sort done in class. Finally it returns temp.

Each procedure should contain preconditions and postconditions. The data for this program is the same as for draft #2.

Your main method should:

• Read the data from the file and form the heap.
• Print the elements of the heap.
• Reduce the heap to the final element.
• Print the Huffman code for each letter and decode the input string
The output for forming the heap is on the WEB. In the output, X is the character placed in the letter field for elements produced by combining two other elements.