Modify HuffmanTreejava and HuffmanNodejava to allow the user

Modify HuffmanTree.java and HuffmanNode.java to allow the user to select the value of n 9 to construct an n ary Huffman Tree. Once finished, verify the accuracy of your tree by running it for the English Alphabet for n = 3, 4, 5, 6, 7, 8, 9. For each value of n, compute the average codeword length. Write these in a table (n vs. ACW L(Cn)).

/ HuffmanTree.java

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

public class HuffmanTree {

public static void main(String[] args){
Scanner in = new Scanner(System.in);
System.out.print(\"Enter the file name: \");
String fileName = in.nextLine();
ArrayList<HuffmanNode> nodes = new ArrayList<>();
ArrayList<HuffmanNode> temp = new ArrayList<>();
try {
Scanner fin = new Scanner(new FileReader(fileName));
String symbol;
double prob;
while(fin.hasNext()){
symbol = fin.next();
prob = fin.nextDouble();
nodes.add(findInsertIndex(nodes, prob), new HuffmanNode(symbol, prob));
}
fin.close();
temp.addAll(nodes);
HuffmanNode root = createHuffmanTree(temp);
setCodeWords(root);
double avg = 0;
for (HuffmanNode node : nodes) {
System.out.println(node.getS() + \": \" + node.getC() + \": \" + node.getL());
avg += node.getL();
}
if(avg != 0)
avg /= nodes.size();
System.out.println(\"Average code length is: \" + avg);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}

private static HuffmanNode createHuffmanTree(ArrayList<HuffmanNode> nodes){
HuffmanNode root = null;
if(nodes.size() > 0) {
HuffmanNode node0, node1, node;
while (nodes.size() > 1) {
node0 = nodes.get(0);
node1 = nodes.get(1);
node = new HuffmanNode(null, node0.getP() + node1.getP());
node.setLeft(node0);
node.setRight(node1);
nodes.remove(0);
nodes.remove(0);
nodes.add(findInsertIndex(nodes, node.getP()), node);
}
root = nodes.get(0);
}
return root;
}

private static void setCodeWords(HuffmanNode root){
if(root != null){
setCodeWords(root, \"\");
}
}

private static void setCodeWords(HuffmanNode root, String codeWord){
if(root.getS() != null){
root.setC(codeWord);
root.setL(codeWord.length());
}
else{
setCodeWords(root.getLeft(), codeWord + \"0\");
setCodeWords(root.getRight(), codeWord + \"1\");
}
}

private static int findInsertIndex(ArrayList<HuffmanNode> nodes, double prob){
for(int i = 0; i < nodes.size(); ++i){
if(prob < nodes.get(i).getP()){
return i;
}
}
return nodes.size();
}

}

// HuffmanNode.java

public class HuffmanNode {

private String S;
private double P;
private String C;
private int L;
private HuffmanNode left, right;

public HuffmanNode(String s, double p) {
S = s;
P = p;
}

public String getS() {
return S;
}

public void setS(String s) {
S = s;
}

public double getP() {
return P;
}

public void setP(double p) {
P = p;
}

public String getC() {
return C;
}

public void setC(String c) {
C = c;
}

public int getL() {
return L;
}

public void setL(int l) {
L = l;
}

public HuffmanNode getLeft() {
return left;
}

public void setLeft(HuffmanNode left) {
this.left = left;
}

public HuffmanNode getRight() {
return right;
}

public void setRight(HuffmanNode right) {
this.right = right;
}
}

//EnglishAlphabet.txt (symbols with probability)

Solution

public final class Huffman { private Huffman() {}; private static class HuffmanNode { char ch; int frequency; HuffmanNode left; HuffmanNode right; HuffmanNode(char ch, int frequency, HuffmanNode left, HuffmanNode right) { this.ch = ch; this.frequency = frequency; this.left = left; this.right = right; } } private static class HuffManComparator implements Comparator { @Override public int compare(HuffmanNode node1, HuffmanNode node2) { return node1.frequency - node2.frequency; } } /** * Compresses the string using huffman algorithm. * The huffman tree and the huffman code are serialized to disk * * @param sentence The sentence to be serialized * @throws FileNotFoundException If file is not found * @throws IOException If IO exception occurs. */ public static void compress(String sentence) throws FileNotFoundException, IOException { if (sentence == null) { throw new NullPointerException(\"Input sentence cannot be null.\"); } if (sentence.length() == 0) { throw new IllegalArgumentException(\"The string should atleast have 1 character.\"); } final Map charFreq = getCharFrequency(sentence); final HuffmanNode root = buildTree(charFreq); final Map charCode = generateCodes(charFreq.keySet(), root); final String encodedMessage = encodeMessage(charCode, sentence); serializeTree(root); serializeMessage(encodedMessage); } private static Map getCharFrequency(String sentence) { final Map map = new HashMap(); for (int i = 0; i < sentence.length(); i++) { char ch = sentence.charAt(i); if (!map.containsKey(ch)) { map.put(ch, 1); } else { int val = map.get(ch); map.put(ch, ++val); } } return map; } /** * Map map * Some implementation of that treeSet is passed as parameter. * @param map */ private static HuffmanNode buildTree(Map map) { final Queue nodeQueue = createNodeQueue(map); while (nodeQueue.size() > 1) { final HuffmanNode node1 = nodeQueue.remove(); final HuffmanNode node2 = nodeQueue.remove(); HuffmanNode node = new HuffmanNode(\'\\0\', node1.frequency + node2.frequency, node1, node2); nodeQueue.add(node); } // remove it to prevent object leak. return nodeQueue.remove(); } private static Queue createNodeQueue(Map map) { final Queue pq = new PriorityQueue(11, new HuffManComparator()); for (Entry entry : map.entrySet()) { pq.add(new HuffmanNode(entry.getKey(), entry.getValue(), null, null)); } return pq; } private static Map generateCodes(Set chars, HuffmanNode node) { final Map map = new HashMap(); doGenerateCode(node, map, \"\"); return map; } private static void doGenerateCode(HuffmanNode node, Map map, String s) { if (node.left == null && node.right == null) { map.put(node.ch, s); return; } doGenerateCode(node.left, map, s + \'0\'); doGenerateCode(node.right, map, s + \'1\' ); } private static String encodeMessage(Map charCode, String sentence) { final StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < sentence.length(); i++) { stringBuilder.append(charCode.get(sentence.charAt(i))); } return stringBuilder.toString(); } private static void serializeTree(HuffmanNode node) throws FileNotFoundException, IOException { final BitSet bitSet = new BitSet(); try (ObjectOutputStream oosTree = new ObjectOutputStream(new FileOutputStream(\"/Users/ap/Desktop/tree\"))) { try (ObjectOutputStream oosChar = new ObjectOutputStream(new FileOutputStream(\"/Users/ap/Desktop/char\"))) { IntObject o = new IntObject(); preOrder(node, oosChar, bitSet, o); bitSet.set(o.bitPosition, true); // padded to mark end of bit set relevant for deserialization. oosTree.writeObject(bitSet); } } } private static class IntObject { int bitPosition; } /* * Algo: * 1. Access the node * 2. Register the value in bit set. * * * here true and false dont correspond to left branch and right branch. * there, * - true means \"a branch originates from leaf\" * - false mens \"a branch originates from non-left\". * * Also since branches originate from some node, the root node must be provided as source * or starting point of initial branches. * * Diagram and how an bit set would look as a result. * (source node) * / \\ * true true * / \\ * (leaf node) (leaf node) * | | * false false * | | * * So now a bit set looks like [false, true, false, true] * */ private static void preOrder(HuffmanNode node, ObjectOutputStream oosChar, BitSet bitSet, IntObject intObject) throws IOException { if (node.left == null && node.right == null) { bitSet.set(intObject.bitPosition++, false); // register branch in bitset oosChar.writeChar(node.ch); return; // DONT take the branch. } bitSet.set(intObject.bitPosition++, true); // register branch in bitset preOrder(node.left, oosChar, bitSet, intObject); // take the branch. bitSet.set(intObject.bitPosition++, true); // register branch in bitset preOrder(node.right, oosChar, bitSet, intObject); // take the branch. } private static void serializeMessage(String message) throws IOException { final BitSet bitSet = getBitSet(message); try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(\"/Users/ap/Desktop/encodedMessage\"))){ oos.writeObject(bitSet); } } private static BitSet getBitSet(String message) { final BitSet bitSet = new BitSet(); int i = 0; for (i = 0; i < message.length(); i++) { if (message.charAt(i) == \'0\') { bitSet.set(i, false); } else { bitSet.set(i, true); } } bitSet.set(i, true); // dummy bit set to know the length return bitSet; } /** * Retrieves back the original string. * * * @return The original uncompressed string * @throws FileNotFoundException If the file is not found * @throws ClassNotFoundException If class is not found * @throws IOException If IOException occurs */ public static String expand() throws FileNotFoundException, ClassNotFoundException, IOException { final HuffmanNode root = deserializeTree(); return decodeMessage(root); } private static HuffmanNode deserializeTree() throws FileNotFoundException, IOException, ClassNotFoundException { try (ObjectInputStream oisBranch = new ObjectInputStream(new FileInputStream(\"/Users/ap/Desktop/tree\"))) { try (ObjectInputStream oisChar = new ObjectInputStream(new FileInputStream(\"/Users/ap/Desktop/char\"))) { final BitSet bitSet = (BitSet) oisBranch.readObject(); return preOrder(bitSet, oisChar, new IntObject()); } } } /* * Construct a tree from: * input [false, true, false, true, (dummy true to mark the end of bit set)] * The input is constructed from preorder traversal * * Algo: * 1 Create the node. * 2. Read what is registered in bitset, and decide if created node is supposed to be a leaf or non-leaf * */ private static HuffmanNode preOrder(BitSet bitSet, ObjectInputStream oisChar, IntObject o) throws IOException { // created the node before reading whats registered. final HuffmanNode node = new HuffmanNode(\'\\0\', 0, null, null); // reading whats registered and determining if created node is the leaf or non-leaf. if (!bitSet.get(o.bitPosition)) { o.bitPosition++; // feed the next position to the next stack frame by doing computation before preOrder is called. node.ch = oisChar.readChar(); return node; } o.bitPosition = o.bitPosition + 1; // feed the next position to the next stack frame by doing computation before preOrder is called. node.left = preOrder(bitSet, oisChar, o); o.bitPosition = o.bitPosition + 1; // feed the next position to the next stack frame by doing computation before preOrder is called. node.right = preOrder(bitSet, oisChar, o); return node; } private static String decodeMessage(HuffmanNode node) throws FileNotFoundException, IOException, ClassNotFoundException { try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream(\"/Users/ameya.patil/Desktop/encodedMessage\"))) { final BitSet bitSet = (BitSet) ois.readObject(); final StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < (bitSet.length() - 1);) { HuffmanNode temp = node; // since huffman code generates full binary tree, temp.right is certainly null if temp.left is null. while (temp.left != null) { if (!bitSet.get(i)) { temp = temp.left; } else { temp = temp.right; } i = i + 1; } stringBuilder.append(temp.ch); } return stringBuilder.toString(); } } public static void main(String[] args) throws FileNotFoundException, IOException, ClassNotFoundException { // even number of characters Huffman.compress(\"some\"); Assert.assertEquals(\"some\", Huffman.expand()); // odd number of characters Huffman.compress(\"someday\"); Assert.assertEquals(\"someday\", Huffman.expand()); // repeating even number of characters + space + non-ascii Huffman.compress(\"some some#\"); Assert.assertEquals(\"some some#\", Huffman.expand()); // odd number of characters + space + non-ascii Huffman.compress(\"someday someday&\"); Assert.assertEquals(\"someday someday&\", Huffman.expand()); } }