Хаффман Кодирование Java [закрыто] ⇐ JAVA

[Anonymous]

Итак, у меня есть вопрос: рассмотрим DMS с семью возможными символами Xi, i = 1, 2, ... , 7 и
соответствующими вероятностями p1 = 0,37, p2 = 0,33, p3 = 0,16, p4 = 0,07, p5 = 0,04, p6 = 0,02,
и p7 = 0,01?
Сначала расположим вероятности в порядке убывания, а затем построим дерево Хаффмана
как на рис. 3.3.таблица ответь
и я должен написать это на Java. У меня есть это решение.
однако оно не дает мне того же ответа, что и таблица в вопросе. результат
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

но должно быть так
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

почему он это делает? и как я могу это исправить?
это код, который я пробовал:
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 huffmanCodes = new HashMap();
generateHuffmanCodes(root, "", huffmanCodes);
printTable(huffmanCodes, probabilities);
}

private static HuffmanNode buildHuffmanTree(double[] probs, int[] syms) {
PriorityQueue pq = new PriorityQueue(Comparator.comparingDouble(node -> node.probability));

for (int i = 0; i < probs.length; i++) {
pq.offer(new HuffmanNode(probs, syms));
}

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 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 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) / Math.log(2);
System.out.printf("%-10d %-12.2f %-15.4f %-10s%n", i + 1, probabilities, selfInfo, codes.get(i + 1));
}
}
}


Подробнее здесь: https://stackoverflow.com/questions/791 ... oding-java