For this assignment, you will write a program to work with Huffman encoding. Huffman code is an optimal prefix code, which means no code is the prefix of another code. Most of the code is included. You will need to extend the code to complete three additional methods. In particular, code to actually build the Huffman tree is provided. It uses a data file containing the frequency of occurrence of characters. You will write the following three methods in the HuffmanTree class: public ArrayList getCodes(); public String encode(String str); public String decode(String huffString);

getCodes method: The getCodes method traverses the tree to generate a list of the characters and their corresponding codes. You will actually be asked to write this traverse method, which is directly called from getCodes it returns the Huffman code for each of the letters: private void traverse(ArrayList code, BinaryTreeNode node, String prefix) This private method requires that you recursively call it in order to traverse the tree. Once youve reached your base case, you have your Huffman Code for this letter so add it to your ArrayList!

encode method The encode method takes a text string (lowercase and spaces onlythe driver class provided replaces all non - lowercase letters & spaces with an empty string) and encodes it using the Huffman encoding from the tree. It returns a binary string representation of the encoding. Here we use a String, computing the length of the encode string and working with 0 and 1 characters. The encode method can use the getCodes method to produce a look up table, then step through the parameter string and simply look up the code for each character and append the code, made up of 0s & 1s, to the end of the encoded string. A sequential search through the ArrayList for each character is fine since there are only 27 elements in the list.

decode method: The decode method takes a string of "0"s and "1"s that has been encoded using the Huffman Tree, using the tree to decode it a back into the original ASCII string. Keep in mind that because Huffman code is a prefix code, you can start at the root of the Huffman tree and traverse left for 0 and right for a 1 until a leaf is reached. The character associated with that code (stored in the node) can be appended to the decoded string, then reset back to the root and continue stepping through the huffString parameter until the end of that string is reached

Letter.java:

public class Letter { char letter; double frequency; public Letter(char letter, double frequency) { super(); this.letter = letter; this.frequency = frequency; }

public char getLetter() { return letter; }

public void setLetter(char letter) { this.letter = letter; }

public double getFrequency() { return frequency; }

public void setFrequency(double frequency) { this.frequency = frequency; }

@Override public String toString() { return "Letter [letter=" + letter + ", frequency=" + frequency + "]" + " "; }

}

InvalidHuffmanCodeException.java: public class InvalidHuffmanCodeException extends RuntimeException{ /** * Sets up this exception with an appropriate message. * @param collection the name of the collection */ public InvalidHuffmanCodeException() { super("The Huffman Code could not be determined!"); }

}

HuffmanTreeTest.java

import static org.junit.Assert.*;

import java.util.ArrayList;

import org.junit.Test;

public class HuffmanTreeTest {

@Test public void testcode3() { HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt"); ArrayList codes = evaluator.getCodes(); assertEquals("Code [ch=s, code=11111]", codes.get(26).toString()); }

@Test public void encode3() { HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt"); ArrayList codes = evaluator.getCodes(); assertEquals("00", evaluator.encode(" ")); }

@Test public void encode5() { HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt"); ArrayList codes = evaluator.getCodes(); assertEquals("1111010011101110110001000110110011011110111100010", evaluator.encode("hotty toddy")); } @Test public void encode6() { HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt"); ArrayList codes = evaluator.getCodes(); assertEquals("110001100111100011101001111111100110011110101000101001101011100111110101100000010011000100010010101011101111110010101000111001", evaluator.encode("four score and seven years ago")); }

@Test(expected = InvalidHuffmanCodeException.class) public void encode9() { HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt"); ArrayList codes = evaluator.getCodes(); String result = evaluator.encode(""); fail("Did not catch invalid Huffman Code Exception"); }

@Test public void decode1() { HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt"); ArrayList codes = evaluator.getCodes(); assertEquals("q", evaluator.decode("1100001011")); } @Test public void decode2() { HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt"); ArrayList codes = evaluator.getCodes(); assertEquals("i", evaluator.decode("0111")); } @Test public void decode3() { HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt"); ArrayList codes = evaluator.getCodes(); assertEquals("work hard play harder", evaluator.decode("110010100111101110000110011110101011101101110010000110110101010001000111101010111011011101011101")); }

}

HuffmanTree.java:

/* This HuffmanTree class has been created from a scaled down version of * LinkedBinaryTree class from the textbook. * */ import java.io.File; import java.io.FileNotFoundException; import java.util.*;

public class HuffmanTree implements HuffmanADT { protected BinaryTreeNode root; protected int modCount; ArrayList list = new ArrayList(); /** * Creates a Huffman tree using the character set and frequency distribution * given in the file with name passed as a parameter. * */ public HuffmanTree(String filename) { root = null; // Read frequency data from file to create list of Letter objects try { Scanner letter_file = new Scanner (new File(filename)); while (letter_file.hasNext()) { String line = letter_file.nextLine(); list.add(new Letter(line.charAt(0), Double.parseDouble(line.substring(2)))); } // Construct the Huffman tree using the list of Letters build(); } catch (FileNotFoundException e) { System.out.println("Frequency file not found."); System.exit(0); }

} private void build() { // Make leaf nodes in the tree/forest for each character ArrayList> nodeList = new ArrayList>(); BinaryTreeNode temp = null; for (int i=0; i(new Letter(list.get(i).getLetter(), list.get(i).getFrequency())); nodeList.add(temp); } /* Use standard idea of Huffman encoding to build tree from leaf nodes. * Repeatedly, find the two subtrees with minimum weight and join them. * Internal nodes don't use the "letter" field, so just make them a constant * (#). The frequency used for the internal node is the sum of the frequency * of the two children. Stop when one node left in forest--it is a tree! */ BinaryTreeNode node1, node2; while (nodeList.size() > 1) { node1 = getMin(nodeList); node2 = getMin(nodeList); Letter internalElement = new Letter('#', node1.getElement().getFrequency() + node2.getElement().getFrequency()); BinaryTreeNode internal = new BinaryTreeNode(internalElement); internal.setLeft(node1); internal.setRight(node2); nodeList.add(internal); } // The one remaining node is the root root = nodeList.get(0); } private BinaryTreeNode getMin(ArrayList> nodes) { int min=0; // index of min // Find the node in the forest with the least frequency for (int i=1; i smallest = nodes.get(min); nodes.remove(min); return smallest; } public Letter getRootElement() throws EmptyCollectionException { if (root == null) throw new EmptyCollectionException("Huffman Tree"); else return root.getElement(); } protected BinaryTreeNode getRootNode() throws EmptyCollectionException { if (root == null) throw new EmptyCollectionException("Huffman Tree"); else return root; } public BinaryTreeNode getLeft() { return root.left; } public BinaryTreeNode getRight() { return root.right; } public boolean isEmpty() { return (root == null); }

/* This method returns an ArrayList of the codes in the Huffman Tree. * The Code class has a character and its corresponding encoding. In the * tree, left edges are designated as 0 and right edges as 1. * * DO NOT CHANGE THIS METHOD, but you need to write the traverse method. */ public ArrayList getCodes() { ArrayList code = new ArrayList(); if (root == null) return null; traverse(code, root.left, "0"); traverse(code, root.right, "1"); return code; }

/* Recursive method to traverse the Huffman tree, and for each leaf node, * add a Code record to the ArrayList. */ private void traverse(ArrayList code, BinaryTreeNode node, String prefix) { // TODO: Fill in this method }

/* The encode method can use the getCodes method above to produce a look up * table, then step through the parameter string and simply "look up" the code * for each character and append the code to the end of the encoded string. A * sequential search through the ArrayList for each character is fine since * there are only 27 elements in the list. */ @Override public String encode(String str) { // TODO: fill in this method return null; } /* * The decode method accepts a string of 0's and 1's and uses the Huffman * tree to determine the original string. Because it is a prefix code, you * can start at the root of the Huffman tree and traverse left for 0 and right * for a 1 until a leaf is reached. The character associated with that code * (stored in the node) can be appended to the decoded string, then * reset back to the root and continue stepping through the huffString * parameter until the end of that string is reached. * */ @Override public String decode(String huffString) { // TODO: Fill in this method return null; } }

HuffmanADT.java:

import java.util.ArrayList;

public interface HuffmanADT { public BinaryTreeNode getLeft(); public BinaryTreeNode getRight(); public boolean isEmpty(); public ArrayList getCodes(); public String encode(String str); public String decode(String huffString); }

EmptyCollectionException.java: /** * Represents the situation in which a collection is empty. * * @author Java Foundations * @version 4.0 */ public class EmptyCollectionException extends RuntimeException { /** * Sets up this exception with an appropriate message. * @param collection the name of the collection */ public EmptyCollectionException (String collection) { super ("The " + collection + " is empty."); } }

ElementNotFoundException.java: /** * ElementNotFoundException represents the situation in which a target element * is not present in a collection * * @author Java Foundations * @version 4.0 */

public class ElementNotFoundException extends RuntimeException { /** * Sets up this exception with an appropriate message. */ public ElementNotFoundException (String collection) { super ("The target element is not in this " + collection); } }

Driver.java:

import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Scanner;

public class Driver {

public static void main(String[] args) throws FileNotFoundException { System.out.println("Start"); // Instantiate LinkedBinaryTree and build Huffman tree from frequency file HuffmanTree huff = new HuffmanTree("letter_frequency.txt"); // Get the codes generated and print table ArrayList codes = huff.getCodes(); System.out.println("Size of codes is " + codes.size()); for (Code c: codes) { System.out.println(c); }

// Test the encoding Scanner in = new Scanner(System.in); boolean done = false; do { System.out.print("Enter a string (END to exit) --> "); String input = in.nextLine(); input = input.toLowerCase(); // Remove everything except lowercase letters: a-z & spaces: \s // ^ means any character but the following... input = input.replaceAll("[^a-z\\s]", ""); if (!input.equals("end")) { // Get and display encoding of string, with length String encoding = huff.encode(input); System.out.printf("Original string length is %d ", input.length()); System.out.printf("Encoded string (length %d), compressed %5.2f ", encoding.length(), encoding.length()/16.0); // Recall that characters are normally 2 bytes System.out.println(encoding); // Get and display decoding of encoded string System.out.println(); System.out.println("Now we try to reconstruct the original from the encoded string"); String original = huff.decode(encoding); if (original.equals(input)) { System.out.println("It worked! String is: " + original); } else { System.out.println("Oops. There was a problem. Decoded string is: " + original); } } else done = true; } while (!done); } }

Code.java: public class Code { Character ch; String code; public Code(Character ch, String hcode) { this.ch = ch; this.code = hcode; }

public Character getCh() { return ch; }

public void setCh(Character ch) { this.ch = ch; }

public String getCode() { return code; }

public void setCode(String hcode) { this.code = hcode; }

@Override public String toString() { return "Code [ch=" + ch + ", code=" + code + "]"; } }

BinaryTreeNode.java: /** * BinaryTreeNode represents a node in a binary tree with a left and * right child. * * @author Java Foundations * @version 4.0 */ public class BinaryTreeNode { protected T element; protected BinaryTreeNode left, right;

/** * Creates a new tree node with the specified data. * * @param obj the element that will become a part of the new tree node */ public BinaryTreeNode(T obj) { element = obj; left = null; right = null; } /** * Returns the number of non-null children of this node. * * @return the integer number of non-null children of this node */ public int numChildren() { int children = 0;

if (left != null) children = 1 + left.numChildren();

if (right != null) children = children + 1 + right.numChildren();

return children; } /** * Return the element at this node. * * @return the element stored at this node */ public T getElement() { return element; } /** * Return the right child of this node. * * @return the right child of this node */ public BinaryTreeNode getRight() { return right; } /** * Sets the right child of this node. * * @param node the right child of this node */ public void setRight(BinaryTreeNode node) { right = node; } /** * Return the left child of this node. * * @return the left child of the node */ public BinaryTreeNode getLeft() { return left; } /** * Sets the left child of this node. * * @param node the left child of this node */ public void setLeft(BinaryTreeNode node) { left = node; } }

letter_frequency.java:

20.152 a 6.5336 b 1.1936 c 2.2256 d 3.4024 e 10.1616 f 1.7824 g 1.612 h 4.8752 i 5.5728 j 0.01224 k 0.576 l 3.22 m 1.9248 n 5.3992 o 6.0056 p 1.5432 q 0.076 r 4.7896 s 5.0616 t 7.2448 u 2.2064 v 0.7824 w 1.888 x 0.12 y 1.5792 z 0.0592