So I have this question: Consider a DMS with seven possible symbols Xi, i = 1, 2, … , 7 and the
corresponding probabilities p1 = 0.37, p2 = 0.33, p3 = 0.16, p4 = 0.07, p5 = 0.04, p6 = 0.02,
and p7 = 0.01?
We first arrange the probabilities in the decreasing order and then construct the Huffman tree
as in Fig. 3.3.table answer
and I’m supposed to write it java. I have this solution for it.
however it’s not giving me the same answer as the table in the question. the output is
1 0.37 1.4344 0
2 0.33 1.5995 11
3 0.16 2.6439 101
4 0.07 3.8365 1000
5 0.04 4.6439 10011
6 0.02 5.6439 100101
7 0.01 6.6439 100100
but it should be like this
1 0.37 1.4344 0
2 0.33 1.5995 10
3 0.16 2.6439 110
4 0.07 3.8365 1110
5 0.04 4.6439 11110
6 0.02 5.6439 111110
7 0.01 6.6439 111111
why is it doing this? and how can i fix it?
this is the code that i tried:
import java.util.*;
class HuffmanNode {
double probability;
int symbol;
HuffmanNode left, right;
HuffmanNode(double prob, int sym) {
this.probability = prob;
this.symbol = sym;
left = right = null;
}
}
class HuffmanCoding {
public static void main(String[] args) {
double[] probabilities = { 0.37, 0.33, 0.16, 0.07, 0.04, 0.02, 0.01 };
int[] symbols = { 1, 2, 3, 4, 5, 6, 7 };
HuffmanNode root = buildHuffmanTree(probabilities, symbols);
Map<Integer, String> huffmanCodes = new HashMap<>();
generateHuffmanCodes(root, "", huffmanCodes);
printTable(huffmanCodes, probabilities);
}
private static HuffmanNode buildHuffmanTree(double[] probs, int[] syms) {
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(Comparator.comparingDouble(node -> node.probability));
for (int i = 0; i < probs.length; i++) {
pq.offer(new HuffmanNode(probs[i], syms[i]));
}
while (pq.size() > 1) {
HuffmanNode left = pq.poll();
HuffmanNode right = pq.poll();
HuffmanNode newNode = new HuffmanNode(left.probability + right.probability, -1);
newNode.left = left;
newNode.right = right;
pq.offer(newNode);
}
return pq.poll();
}
private static void generateHuffmanCodes(HuffmanNode node, String code, Map<Integer, String> codes) {
if (node.left == null && node.right == null) {
codes.put(node.symbol, code);
return;
}
if (node.left != null) {
generateHuffmanCodes(node.left, code + "0", codes);
}
if (node.right != null) {
generateHuffmanCodes(node.right, code + "1", codes);
}
}
private static void printTable(Map<Integer, String> codes, double[] probabilities) {
System.out.printf("%-10s %-12s %-15s %-10s%n", "Symbol", "Probability", "Self-information", "Codeword");
System.out.println("-".repeat(55));
for (int i = 0; i < probabilities.length; i++) {
double selfInfo = -Math.log(probabilities[i]) / Math.log(2);
System.out.printf("%-10d %-12.2f %-15.4f %-10s%n", i + 1, probabilities[i], selfInfo, codes.get(i + 1));
}
}
}
You need to sign in to view this answers