Modify HuffmanTree.java and HuffmanNode.java to allow the user to select the val

Question

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)

Explanation / Answer

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 1) { final HuffmanNode node1 = nodeQueue.remove(); final HuffmanNode node2 = nodeQueue.remove(); HuffmanNode node = new HuffmanNode('', 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

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.