Question

You will construct a Huffman tree based on the given frequencies of 26 English
alphabets in upper case plus the space character. An internal tree node class in
HuffmanTree with necessary information is required.

• You will not randomly switch left and right children when merger two trees. Instead, you will
build a right-heavy tree according to the following strategies to select the right child.

(1) The tree that is taller will be the right child, i.e., the height is greater;
(2) If the two tree of the same height, then the tree with more nodes will be the right child;
(3) If (1) and (2) fail to discriminate, then the sum of the ASCII values of the alphabets in
the tree is greater will be the right child.
Use the same criteria if frequency is not sufficient to decide which two trees should be merged.

(1) HuffmanTree(char[] a, int[] f)
This is a constructor that builds a Huffman tree based on a and f, where a is an array of
characters to be encoded and f is an array of frequencies corresponding to the characters
in a. For example, if a[3] = ’D’ and f[3] = 43, that means the frequency of ’D’ is 43.

(2) public void printCodeWords()
This method prints out all codewords in the Huffman tree from left leaves to right leaves
in the tree. Use the following format:
Huffman Codes:
E[69]:000 (127)
H[72]:0010 (61)
S[82]:0011 (63)
.....
Z[90]:1111111111 (1)
The 0-1 string indicates that 000 is the Huffman code
for E, [69] indicates the ASCII value of character E, and
(127) is the frequency; same to characters H, S and Z.

(3) public String encode(String text)
This method will return a 0-1 String using the Huffman codes. For example, encode("EHS")
should return "00000100011".

(4) public String decode(String codeString)
The reverse of the function above. For example, decode("00000100011") returns "EHS".
--------------------------------------------------------------------------------------------------------------------------
Here is the driver provided

This is my driver class, Asg7.java
/**
* You should not modify this program. You should develop your own
* HuffmanTree.java and put it in the package, myUtil.
*
* @author cli2
*
*/
import myUtil.HuffmanTree;

public class Asg7 {
// this example is extended from Corman's book
static public void CormanFrequency() {
int[] f = {82,15,29,43,127,22,20,61,70,5,8,40,24,67,75,19,4,60,63,91,28,10,23,2,21,1,123};
char[] a = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',' '};
HuffmanTree ht = new HuffmanTree(a, f); // Construct a Huffman Tree based on a and f
ht.printCodeWords();
System.out.printf("%nCode: %s%n", ht.encodeToStr("HUFFMAN ENCODING IS VERY USEFUL"));
System.out.printf("%nText: %s%n", ht.decodeFromStr("00100111011110011110011111011001000010000100001111101011010100110001101100101001001101010111110000110110111010011111010101010110"));
System.out.printf("%nText: %s%n", ht.decodeFromStr("0111101101101111011101110101011011001101100101110001011011101010010011010111100011101000"));
System.out.printf("%nText: %s%n", ht.decodeFromStr("11100010100100110101001001101011100010000010101101100001111100101100001100111001110110100011111000010001110"));
}
  
public static void main(String[] args) {   
CormanFrequency();
}

}

Answer 1

package myUtil;

import java.util.ArrayList;
import java.util.PriorityQueue;

class HuffNode implements Comparable<HuffNode> {
   // fields
   public int value;
   public int weight;
   public HuffNode leftTree;
   public HuffNode rightTree;
   public HuffNode parent;

   // constructors
   public HuffNode() {
       parent = null;
   }

   public HuffNode(int v, int w, HuffNode lTree, HuffNode rTree, HuffNode par) {
       value = v;
       weight = w;
       leftTree = lTree;
       rightTree = rTree;
       parent = par;
   }

   // setters/getters

   @Override
   public int compareTo(HuffNode rhs) {
       return weight - rhs.weight;
   }

   @Override
   public String toString() {
       String str = "";
       str += this.value;
       return str;
   }
}

// object representing a huffman tree
public class HuffmanTree {
   // fields
   private int size = 0;
   private HuffNode root = new HuffNode();
   private PriorityQueue<HuffNode> huffQueue = new PriorityQueue();
   public ArrayList<String> pathTable = new ArrayList();
   public ArrayList<Character> valueTable = new ArrayList();

   // constructor
   public HuffmanTree(char[] code, int[] freq) {
       // get the counts
       this.size = freq.length;

       // throw exception if arrays are different sizes
       if (freq.length != code.length) {
           throw new UnsupportedOperationException("Error: Character and code length mismatch.");
       }

       // build huffQueue from frequencies given
       for (int i = 0; i < this.size; i++) {
           huffQueue.offer(new HuffNode(code[i], freq[i], null, null, null));
       }

       // build huffman tree from queue
       createTree();

       // build code table from huffman tree
       createTable(this.root, "");
   }

   // setters/getters

   /**
   * creates Huffman Tree from frequencies and values
   *
   * @param null
   */
   private void createTree() {
       // while elements remain in huffQueue, add to tree
       while (huffQueue.size() > 1) {
           // pop off two minimum elements in huffQueue
           HuffNode tempL = huffQueue.poll();
           HuffNode tempR = huffQueue.poll();

           // create root for two minimum elements and build tree
           HuffNode parent = new HuffNode(0, tempL.weight + tempR.weight, tempL, tempR, null);
           tempL.parent = parent;
           tempR.parent = parent;

           // add new tree back in huffQueue
           huffQueue.offer(parent);
           this.size++;
       }

       // set HuffTree root to remaining element in huffQueue
       this.root = huffQueue.peek();
   }

   /**
   * creates code table for a huffman tree
   *
   * @param HuffNode
   * -- root for tree, string -- for building paths
   */
   private void createTable(HuffNode curr, String str) {
       // if iterator is null, return
       if (curr == null)
           return;

       // else if leaf, display path and value
       if (curr.leftTree == null&& curr.rightTree == null) {
           char tempChar;
           if (curr.value == 32)
               tempChar = ' ';

           if (curr.value == 10)
               tempChar = 'n';

           else
               tempChar = (char) curr.value;
           // add value and path to code tables
           this.valueTable.add(tempChar);
           this.pathTable.add(str);
       }

       // add 0 if before moving to left child
       str += "0";
       // recursively call in pre-order
       createTable(curr.leftTree, str);

       // adjust path and add 1 before moving to right child
       str = str.substring(0, str.length() - 1);
       str += "1";
       createTable(curr.rightTree, str);
   }

   /**
   * display given huffman tree using pre-order traversal
   *
   * @param HuffNode
   * -- root of tree to be displayed
   */
   // global variable used for representing 'levels' of tree
   String tacks = "";

   public void getTree(HuffNode curr) {
       // if iterator is null, return
       if (curr == null)
           return;

       // else if leaf, display level, weight, and value
       if (curr.leftTree == null&& curr.rightTree == null) {
           // case statements to handle displaying space and newline
           switch (curr.value) {
           case 32:
               System.out.println(tacks + curr.weight + ": sp");
               break;
           case 10:
               System.out.println(tacks + curr.weight + ": nl");
               break;
           default:
               System.out.println(tacks + curr.weight + ": " + (char) curr.value);
               break;
           }
       }

       // else display level and weight
       else
           System.out.println(tacks + curr.weight);

       // increment level marker
       tacks += "- ";
       // recursively call in pre-order
       getTree(curr.leftTree);
       getTree(curr.rightTree);
       // decrement level marker
       tacks = tacks.substring(0, tacks.length() - 2);
   }

   /**
   * returns size of a given huffman tree
   *
   * @param HuffTree
   * - to obtain size of
   * @return int -- size of tree
   */
   public int getSize() {
       return this.size;
   }

   /**
   * returns encoded bits for a given string
   *
   * @param String
   * -- to be encoded
   * @return String -- encoded version of original string
   */
   public String encodeToStr(String input) {
       // create empty string to hold code
       String str = "";

       // iterate through given string
       for (int x = 0; x < input.length(); x++) {
           // iterate through code tables
           for (int i = 0; i < valueTable.size(); i++) {
               // if char in string matches code in table, add path to string
               if (valueTable.get(i) == input.charAt(x))
                   str += pathTable.get(i);
           }
       }
       return str;
   }

   /**
   * returns decoded string for a given set of bits
   *
   * @param String
   * -- bits to be decoded
   * @return String -- decoded version of bits
   */
   public String decodeFromStr(String bits) {
       // create empty string to hold decoded message
       String decodedStr = "";

       // iterate through bits
       for (int i = 0; i < bits.length(); i++) {
           if (!getChar(bits.substring(0, i + 1)).equals("")) {
               decodedStr += getChar(bits.substring(0, i + 1));
               bits = bits.substring(i + 1);
               i = 0;
           }
       }
       return decodedStr;
   }

   /**
   * returns character for a given set of bits
   *
   * @param String
   * -- bits to be checked
   * @return String -- character associated with bits if any
   */
   private String getChar(String bits) {
       // create string to hold potential character
       String character = "";
       // traverse code table to seek match
       for (int i = 0; i < pathTable.size(); i++) {
           // add to string if match is found
           if (pathTable.get(i).equals(bits))
               character = valueTable.get(i).toString();
       }
       return character;
   }

   public void printCodeWords() {
       System.out.println("Display Tree:");
       HuffNode curr = this.root;
       this.getTree(curr);
       System.out.println("");

   }

}

=====O/P=====

Display Tree:
1133
- 491
- - 240
- - - 117
- - - - 57
- - - - - 28: U
- - - - - 29: C
- - - - 60: R
- - - 123: sp
- - 251
- - - 124
- - - - 61: H
- - - - 63: S
- - - 127: E
- 642
- - 289
- - - 137
- - - - 67: N
- - - - 70: I
- - - 152
- - - - 75: O
- - - - 77
- - - - - 37
- - - - - - 18
- - - - - - - 8: K
- - - - - - - 10: V
- - - - - - 19: P
- - - - - 40: L
- - 353
- - - 166
- - - - 82: A
- - - - 84
- - - - - 41
- - - - - - 20: G
- - - - - - 21: Y
- - - - - 43: D
- - - 187
- - - - 91: T
- - - - 96
- - - - - 45
- - - - - - 22: F
- - - - - - 23: W
- - - - - 51
- - - - - - 24: M
- - - - - - 27
- - - - - - - 12
- - - - - - - - 5: J
- - - - - - - - 7
- - - - - - - - - 3
- - - - - - - - - - 1: Z
- - - - - - - - - - 2: X
- - - - - - - - - 4: Q
- - - - - - - 15: B

Code: 010000000111100111100111110110010000010111000000011010110111001100011010000110010101001101100101100011101010010000001010111111000000010111

Text: DAFMANH CWES ND HIOLA PGMOO

Text: EDEEDLSEE VENPY OFEO

Text: T HIOI OT UODCFKE ATGETRR