Question

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 you’ve 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 only–the 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 0’s & 1’s, 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 + "]" + "\n";
   }

}

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<Code> 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<Code> codes = evaluator.getCodes();
       assertEquals("00", evaluator.encode(" "));
   }

   @Test
   public void encode5() {
       HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt");
       ArrayList<Code> codes = evaluator.getCodes();
       assertEquals("1111010011101110110001000110110011011110111100010", evaluator.encode("hotty toddy"));
   }
   @Test
   public void encode6() {
       HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt");
       ArrayList<Code> 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<Code> 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<Code> codes = evaluator.getCodes();
       assertEquals("q", evaluator.decode("1100001011"));
   }
   @Test
   public void decode2() {
       HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt");
       ArrayList<Code> codes = evaluator.getCodes();
       assertEquals("i", evaluator.decode("0111"));
   }
   @Test
   public void decode3() {
       HuffmanTree evaluator = new HuffmanTree("letter_frequency.txt");
       ArrayList<Code> 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<Letter> root;
    protected int modCount;
   ArrayList<Letter> list = new ArrayList<Letter>();
  
    /**
     * 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<BinaryTreeNode<Letter>> nodeList = new ArrayList<BinaryTreeNode<Letter>>();
           BinaryTreeNode<Letter> temp = null;
           for (int i=0; i<list.size(); i++) {
               temp = new BinaryTreeNode<Letter>(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<Letter> node1, node2;
           while (nodeList.size() > 1) {
               node1 = getMin(nodeList);
               node2 = getMin(nodeList);
               Letter internalElement = new Letter('#', node1.getElement().getFrequency() +
                        node2.getElement().getFrequency());
               BinaryTreeNode<Letter> internal = new
                       BinaryTreeNode<Letter>(internalElement);
               internal.setLeft(node1);
               internal.setRight(node2);
               nodeList.add(internal);
           }
           // The one remaining node is the root
           root = nodeList.get(0);
    }
  
    private BinaryTreeNode<Letter> getMin(ArrayList<BinaryTreeNode<Letter>> nodes) {
             int min=0;   // index of min
             // Find the node in the forest with the least frequency
             for (int i=1; i<nodes.size(); i++) {
                      if (nodes.get(i).getElement().getFrequency() <
                              nodes.get(min).getElement().getFrequency()) {
                               min = i;
                      }
             }
             // Save, remove, then return the smallest node
             BinaryTreeNode<Letter> 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<Letter> getRootNode() throws EmptyCollectionException
    {
        if (root == null)
               throw new EmptyCollectionException("Huffman Tree");
        else return root;
    }
  
    public BinaryTreeNode<Letter> getLeft()
    {
        return root.left;
    }
  
    public BinaryTreeNode<Letter> 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<Code> getCodes() {
           ArrayList<Code> code = new ArrayList<Code>();
           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> code, BinaryTreeNode<Letter> 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<Letter> getLeft();
   public BinaryTreeNode<Letter> getRight();
   public boolean isEmpty();
   public ArrayList<Code> 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<Code> 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\n", input.length());
                System.out.printf("Encoded string (length %d), compressed %5.2f\n",
                       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<T>
{
    protected T element;
    protected BinaryTreeNode<T> 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<T> getRight()
    {
        return right;
    }
  
    /**
     * Sets the right child of this node.
     *
     * @param node the right child of this node
     */
    public void setRight(BinaryTreeNode<T> node)
    {
        right = node;
    }
  
    /**
     * Return the left child of this node.
     *
     * @return the left child of the node
     */
    public BinaryTreeNode<T> getLeft()
    {
        return left;
    }
  
    /**
     * Sets the left child of this node.
     *
     * @param node the left child of this node
     */
    public void setLeft(BinaryTreeNode<T> 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

Answer 1

Traverse, Decode and Encode methods are implemented below-

/* Recursive method to traverse the Huffman tree, and for each leaf node,
* add a Code record to the ArrayList.
*/
  
private void traverse(ArrayList<Code> code, BinaryTreeNode<Letter> node,
String prefix) {
// TODO: Fill in this method
if(node.left==null && node.right==null) {
Code c= new Code(node.getElement().getLetter(),prefix);
code.add(c);
}
else{

traverse(code,node.left,prefix+"0");
traverse(code,node.right,prefix+"1");


}

}
/* 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
String encoded="";
HuffmanTree huff = new HuffmanTree("letter_frequency.txt");
ArrayList<Code> codes = huff.getCodes();

for(int i=0;i<str.length();i++){
for (Code c: codes) {
if(c.getCh()==str.charAt(i)){
encoded+=c.getCode();
break;
}
}


}
return encoded;
}
  
/*
* 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

BinaryTreeNode<Letter> node=root;
int count=0;
String decoded="";
int i=0;
while(count<huffString.length()){

for(i=count;i<=huffString.length();i++){
if(node.left==null && node.right==null) {decoded+=node.getElement().getLetter(); count=i;break;}
else{
if(huffString.charAt(i)=='0') node=node.left;
else node=node.right;
}
}

node=root;
}

return decoded;
}

Output-

Driver [Java Application] C:\Program FilesJavajre1.8.0_121\bin javaw.exe (01-Nov-2017, 12:49:56 AM) Start Size of codes is 26 Code [ch-v, code-000000] Code [ch-x, code-00000100] Code [ch-j, code-0000010100] Code [ch-z, code-0000010101] Code [ch-q, code-000001011] Code [ch-k, code-0000011] Code [ch-f, code-00001] Code [ch-w, code-00010] Code [ch-m, code-00011] Code [ch-t, code-001] Code [ch-u, code-01000] Code [ch-c, code-01001] Code [ch-r, code-0101] Code [ch-h, code-0110] Code [ch-s, code-0111] Code [ch-e, code-100] Code [ch-n, code 1010] Code [ch-i, code-1011] Code [ch-b, code-110000] Code [ch-p, code-110001] Code [ch-y, code-110010] Code [ch-g, code-110011] Code [ch-o, code-1101] Code [ch-a, code-1110] Code [ch-l, code-11110] Enter a string (END to exit) --> sushant Driginal string length is 7 Encoded string (length 28), compressed 1.75 0111010000111011011101010001 Now we try to reconstruct the original from the encoded string It worked! String is: sushant Enter a string (END to exit) -->