I need help with programming in Java. Below is the question I have to answer (in
ID: 3809281 • Letter: I
Question
I need help with programming in Java. Below is the question I have to answer (including both parts A and B). I am having a lot of trouble with the coding but I think I understand the concept. Underneath the question is the work I have done on the problem and my code so far. If anything is wrong or if you need to change anything in my code please feel free to do so.
Q1) Write a program in Java to construct a Huffman tree for encoding with the above data. Your output have to generate an optimal binary prefix code for each letter. Please Include the image of your output.
A) Decode each bit string using the Huffman code.
011000101010100 - (I determined it should be ECTTC)
1000100001010100 - (I determined it should be ICICTX)
111001001111110 - (I determined it should be RCIERI)
1000010011100 - (I determined it should be ICXRC)
B) Encode each word using the Huffman code in 1.
RISE - (I determined it should be 11110110011)
EXIT - (I determined it should be 0110100100101)
TEXT - (I determined it should be 010101101000101)
EXERCISE - (I determined it should be 01101000111110010110011)
MY WORK SO FAR:
MY CODE SO FAR:
import java.util.*;
abstract class HuffmanTree implements Comparable<HuffmanTree> {
public final int frequency; // the frequency of this tree
public HuffmanTree(int freq) { frequency = freq; }
// compares on the frequency
public int compareTo(HuffmanTree tree) {
return frequency - tree.frequency;
}
}
class HuffmanLeaf extends HuffmanTree {
public final char value; // the character this leaf represents
public HuffmanLeaf(int freq, char val) {
super(freq);
value = val;
}
}
class HuffmanNode extends HuffmanTree {
public final HuffmanTree left, right; // subtrees
public HuffmanNode(HuffmanTree l, HuffmanTree r) {
super(l.frequency + r.frequency);
left = l;
right = r;
}
}
2 2 x 5 T 18 l I IS II IS -p 15 2 x 5; T 37* 27 37 I 2? 9: S 10: R a: s to: R 21 X ST E -b 011 37 27 12 C IS:* I 19 ais lo R 2 x 5 T
Explanation / Answer
import java.util.*;
abstract class HuffmanTree implements Comparable<HuffmanTree> {
public final int frequency; // the frequency of this tree
public HuffmanTree(int freq) { frequency = freq; }
// compares on the frequency
public int compareTo(HuffmanTree tree) {
return frequency - tree.frequency;
}
}
class HuffmanLeaf extends HuffmanTree {
public final char value; // the character this leaf represents
public HuffmanLeaf(int freq, char val) {
super(freq);
value = val;
}
}
class HuffmanNode extends HuffmanTree {
public final HuffmanTree left, right; // subtrees
public HuffmanNode(HuffmanTree l, HuffmanTree r) {
super(l.frequency + r.frequency);
left = l;
right = r;
}
}
public class HuffmanCode {
// input is an array of frequencies, indexed by character code
public static HuffmanTree buildTree(int[] charFreqs) {
PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
// initially, we have a forest of leaves
// one for each non-empty character
for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[i] > 0)
trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));
assert trees.size() > 0;
// loop until there is only one tree left
while (trees.size() > 1) {
// two trees with least frequency
HuffmanTree a = trees.poll();
HuffmanTree b = trees.poll();
// put into new node and re-insert into queue
trees.offer(new HuffmanNode(a, b));
}
return trees.poll();
}
public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
assert tree != null;
if (tree instanceof HuffmanLeaf) {
HuffmanLeaf leaf = (HuffmanLeaf)tree;
// print out character, frequency, and code for this leaf (which is just the prefix)
System.out.println(leaf.value + " " + leaf.frequency + " " + prefix);
} else if (tree instanceof HuffmanNode) {
HuffmanNode node = (HuffmanNode)tree;
// traverse left
prefix.append('0');
printCodes(node.left, prefix);
prefix.deleteCharAt(prefix.length()-1);
// traverse right
prefix.append('1');
printCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}
public static void main(String[] args) {
// we will assume that all our characters will have
// code less than 256, for simplicity
int[] charFreqs = new int[256];
charFreqs['C'] = 12;
charFreqs['E'] = 8;
charFreqs['I'] = 18;
charFreqs['R'] = 10;
charFreqs['S'] = 9;
charFreqs['T'] = 5;
charFreqs['X'] = 2;
// build tree
HuffmanTree tree = buildTree(charFreqs);
// print out results
System.out.println("SYMBOL WEIGHT HUFFMAN CODE");
printCodes(tree, new StringBuffer());
}
}
This code will generate a table for every symbol and corresponding huffmancode for that symbol.