是否有可能有两种不同的霍夫曼编码方案产生不同的位数？

Question

我为霍夫曼编码做了一个解决方案，但我的代码没有产生预期的输出。

我不知道哪里出了问题。

感谢任何帮助。

abcdef
1 2 3 3 5 5

Your Output: 
00 01 10 110 1110 1111 

Expected Output: 
000 001 01 10 110 111

可以清楚地看到位数与预期的不同 16 我的是 17。不同的哈夫曼方案是否可以有不同的输出？

class Solution {

    class HuffmanNode {
        char c;
        int freq;
        HuffmanNode left;
        HuffmanNode right;

        public HuffmanNode(char c, int freq) {
            this.c = c;
            this.freq = freq;
            this.left = null;
            this.right = null;
        }
    }

    class HuffmanNodeComparator implements Comparator<HuffmanNode> {
        public int compare(HuffmanNode a, HuffmanNode b) {
            return a.freq - b.freq;
        }
    }

    ArrayList<String> res = new ArrayList<>();

    public ArrayList<String> huffmanCodes(String S, int f[], int N) {
        Queue<HuffmanNode> pq = new PriorityQueue<HuffmanNode>(new HuffmanNodeComparator());

        for (int i = 0; i < N; i++) {
            pq.offer(new HuffmanNode(S.charAt(i), f[i]));
        }

        while (pq.size() > 1) {
            HuffmanNode a = pq.poll();
            HuffmanNode b = pq.poll();
            HuffmanNode newNode = new HuffmanNode('-', a.freq + b.freq);

            newNode.left = a;
            newNode.right = b;

            pq.offer(newNode);
        }

        dfs(pq.poll(), "");

        return res;
    }

    public void dfs(HuffmanNode root, String HuffmanCode) {
        if (root == null) return;
        if (root.c != '-') {
            res.add(HuffmanCode);
            return;
        }

        dfs(root.left, HuffmanCode + "0");
        dfs(root.right, HuffmanCode + "1");
    }
}

Answer 1

两者都是有效的前缀代码，并且都是频率集 1、2、3、3、5、5 的有效霍夫曼代码。

然而，在这两种情况下，您的代码顺序似乎是任意的。如果它们应该对应于频率，那么两个输出都是错误的。较长的代码对应于较低的频率。一个非递减的频率序列将对应一个非递增的码长序列。

计算代码效率的方法不是通过添加长度。您将长度和相应频率的乘积相加。如果我适当地排序和关联长度和频率，那么第一个代码是 2x5 + 2x5 + 2x3 + 3x3 + 4x2 + 4x1 = 47。第二个代码是 2x5 + 2x5 + 3x3 + 3x3 + 3x2 + 3x1 = 47。两个代码是最优的，都用 47 位来表示消息。

您可以从霍夫曼算法中获取任一代码，因为在某一点上存在任意选择。在将 1 和 2 配对以获得频率为 3 的子树后，您现在有另外两个频率为 3 的叶子。所以现在你可以将子树和其中一个叶子组合起来，或者你可以将两个叶子组合起来。这些最终会导致不同的树。然而，两者都是最佳的。

是否有可能有两种不同的霍夫曼编码方案产生不同的位数？

Is it possible to have two different Huffman encoding scheme yielding different number of bits?

java

compression

priority-queue

lossless-compression

huffman-code