Homework 7 Challenge (optional)

No due date: submit on Gradescope here.

Goals:

• Practice building and traversing binary trees.
• Implement the Huffman compression algorithm.

This problem is completely optional, but a good challenge if you're looking for more practice. Create a file called HuffmanCoder.java to implement the Huffman Coding algorithm we used in Lab 6.

To represent the tree, we recommend using the BinaryTree class we used in Lecture 8M, but using the following class to represent the nodes:

class HuffmanNode implements Comparable<HuffmanNode> {
  public Character letter; // char from message (if leaf), '~' if internal
  public int value; // character frequency (if leaf), or sum of two child values (if internal)
  public HuffmanNode left; // left child node in binary tree
  public HuffmanNode right; // right child node in binary tree
  public String code; // resulting encoding of this node, e.g. "01101"

  // Implement a constructor, toString, etc.

  public int compareTo(HuffmanNode otherNode) {
    if (value < otherNode.value) return -1;
    if (value > otherNode.value) return 1;
    return letter.compareTo(otherNode.letter);
  }
}

The compareTo method will prioritize checking the values of the two HuffmanNode objects, and then use (if the values are equal) the Character compareTo method to determine which nodes should be prioritized in the PriorityQueue. When you create internal nodes, you can set the letter to ~ (tilde), which will mean these internal nodes will be placed after the regular alphabet letters in the queue when there is a tie in the value.

Your public HuffmanCoder class should provide the following public methods:

• String encode(String message): encodes a message by (1) counting the frequency of each character, (2) creating a priority queue, (3) building and saving the Huffman Coding Tree, (4) computing the encoding of each character and then (5) building a bit String which encodes the input message.
• String decode(String bits): given a character sequence of bits, decodes the bits by traversing the Huffman Coding Tree (which needs to be built in the encode method).

For example, the encode method could take in the message from Lab 6 and return:

"111011000100101010010111100101001000111010100100011101100111111111101010010001110110011111111110101001000111000"

The decode method would then take this bit String and use the tree to obtain the original message.

Use Java's built-in PriorityQueue for this problem, specifically as PriorityQueue<HuffmanNode>. To set up the initial priority queue, you might want to use a Map to calculate character frequencies (recall the example in Lecture 3W).

Upload the HuffmanCoder.java file to the Homework 7 Challenge (Optional) assignment on Gradescope. A few tests will check the methods above.