Spring 2009
Due: WED 11:59pm APR 15
the 2nd midterm will be MON APR 20.
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 #2, however, we use a min-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. Note that this draft hould be done with non-static methods.
Draft #2
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. Here is the skeleton of the class you will be using:
public class Hw3b //solves draft #2 for project #3 { int last; //the # of nodes in heap. This decreases as succesive pairs of //minimum nodes are extracted final int MAX = 11;//there are 11 pairs of letter-frequency entries TreeNode x = new TreeNode[MAX + 1]//one more element for shift up class Huffman//defines the data frequency record { public String letter; public int freq; } class TreeNode implements Comparable < TreeNode> //defines the treelets comprising the list. { public Huffman data; public TreeNode left, right; //you must write the compareTo method } }
where Huffman 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 #1:
. Note we don't decrement last because we will be placing the treelet with p1 and p2 as children at the bottom of the heap.
The data for this program is the same as for draft #1.
Your main method should: