霍夫曼编码Java

Question

我有这个问题：

考虑一个具有七个可能符号 Xi, i = 1, 2, ... , 7 的 DMS 相应的概率 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<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));
    }
  }
}

Answer 1

您的答案没有任何问题。向每个左分支或右分支分配 0 或 1 位的选择是任意的。您的输出和问题中的表格都是正确的，并且都是所提供概率的最佳前缀代码。

虽然没有必要，但可以通过将

while (pq.size() > 1) {

之后的前两行代码替换为以下内容来生成表格图像中的代码：

    HuffmanNode right = pq.poll();
    HuffmanNode left = pq.poll();
    if (left.symbol == -1 && right.symbol != -1) {
        HuffmanNode temp = left;
        left = right;
        right = temp;
    }

这迫使叶子到正确的分支。