Construct a Huffman tree based on the given frequencies of 26 English alphabets
ID: 3694294 • Letter: C
Question
Construct a Huffman tree based on the given frequencies of 26 English alphabets in upper case plus the space character. You should design your own HuffmanTree class and put it in myUtil package. You may use an inner class in HuffmanTree for the tree node that contains necessary information.
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. Note: You are not going to build a random Huffman tree. Instead, you will build a rightheavy tree, which means, whenever you try to combine two sub-Huffman trees to form a new tree, the left-child of the new root always points to the node with higher frequency. In such a way, the right-child intends to have more nodes. As the result, this strategy will build a tree with the right side heavier than the left side.
2. public void printCodeWords() This method prints out all codewords in the Huffman tree. The order of printing the codewords doesn’t matter, but they are required to be printed in the following format: Huffman Codes: 000:E[69](127) 0010:H[72](61) 0011:S[82](63) ..... The list 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 and S.
3. public String encodeToStr(String text) This method will return a 0-1 String using the Huffman code. For example, if the argument is "EHS" and we are using the same codes for this assignment to code it, the method should return "00000100011".
4. public String decodeFromStr(String codeString) The reverse of the function above. Using the same tree with the argument "00000100011", the method will return "EHS".
/**
* 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();
}
}
This is the driver class Asg7, but I need help constructing a huffman tree and using those four methods described above. Thank you.
Explanation / Answer
Hello there ,
Please find below code and its O/P.
Let me know if you have any queries.
Thanks.
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