Finish your Heap implementation from Lab 11.
In class we went through an example of constructing an optimal variable-length code for a set of symbols by building a Huffman tree. Using this as a guide, build a Huffman tree by hand for the following frequency table of four symbols:
A 8 B 3 C 1 D 1
Draw the intermediate trees at each step of the process on a piece of paper, starting from single-leaf Huffman trees and proceeding to the final tree. Make sure to clearly show which trees get merged at each step. What is the resulting binary code for each of the four symbols? Show the sequence of bits produced by encoding the message ABBAD.
Download the folder assign11.zip, which contains the starting code for the exercises below.
Implement the FrequencyTable method buildHuffmanTree(), which should build and return a Huffman tree from the frequency information stored in the table. As a reminder, a HuffmanTree object keeps track of the following information:
- A set of "symbols" stored at the root, represented as a TreeSet of Characters.
- An integer weight value stored at the root.
- References to the left and right subtrees, which are themselves HuffmanTrees.
Your buildHuffmanTree() method will need to maintain a priority queue of HuffmanTrees, repeatedly removing the two trees of lowest weight (highest priority) from the queue and merging them together into a new tree, which is then reinserted into the queue, until only one tree remains. The HuffmanTree class implements the parameterized interface Comparable<HuffmanTree>, so that trees can be compared based on their weight values, via the compareTo method. This method will be used implicitly by the priority queue when adding and removing trees.
If you got your Heap class from Lab 11 to work, you can use it to represent the priority queue. If you didn't get it to work, you may use Java's PriorityQueue<E> class instead (which is itself implemented internally as a heap). Notice also that HuffmanTree extends HuffmanViewer. This pre-compiled class (included in the assign11 folder) provides support for displaying your Huffman trees graphically, which may help in testing and debugging your code. The following methods are inherited by HuffmanTree from the HuffmanViewer class:
tree.draw() draws the tree in a 500 x 300 pixel window tree.draw(width, height) draws the tree in a window of size width x height tree.setFontSize(size) changes the font size used to draw the tree tree.close() closes the tree display window
TestHuffmanCoding is the main program. It asks the user for a filename, creates a FrequencyTable from the file, and constructs a HuffmanTree from the table. As a simple test, try your program on the file example1.txt (included in the assign11 folder), which is the example we went over in class. One possible tree is shown below. However, a different tree could be produced depending on the order in which trees of equal weight are removed from the priority queue for merging. In any case, the resulting variable-length code will still be optimal.
Complete the HuffmanTree method encodeSymbol(Character symbol), which should take a single Character symbol and return a String of 0's and 1's representing the bit sequence that encodes symbol. For example, calling the method with the symbol 'D' on the above tree should return the String "1011". If symbol is not found in the tree, an appropriate error message should be printed.
Complete the HuffmanTree method encodeString(String message), which should take a String of symbols and return a String of 0's and 1's representing the complete bit sequence that encodes the entire message. Hint: use your encodeSymbol method as a helper. For example, calling encodeString with "ABC" should return "01001010".