Java的哈夫曼树

我的哈夫曼树代码有问题。 在main方法中,我输入了一个符号字符串,我还输入了一个包含符号频率的整数数组。 它应该打印出每个Symbol及其Huffman代码,但我认为它错了……

这是代码:

package huffman; import java.util.*; abstract class HuffmanTree implements Comparable { public final int frequency; // the frequency of this tree public HuffmanTree(int freq) { frequency = freq; } // compares on the frequency public int compareTo(HuffmanTree tree) { return frequency - tree.frequency; } } class HuffmanLeaf extends HuffmanTree { public final char value; // the character this leaf represents public HuffmanLeaf(int freq, char val) { super(freq); value = val; } } class HuffmanNode extends HuffmanTree { public final HuffmanTree left, right; // subtrees public HuffmanNode(HuffmanTree l, HuffmanTree r) { super(l.frequency + r.frequency); left = l; right = r; } } public class Huffman { // input is an array of frequencies, indexed by character code public static HuffmanTree buildTree(int[] charFreqs, char[] test2) { PriorityQueue trees = new PriorityQueue(); // initially, we have a forest of leaves // one for each non-empty character for (int i = 0; i  0) trees.offer(new HuffmanLeaf(charFreqs[i], test2[i])); assert trees.size() > 0; // loop until there is only one tree left while (trees.size() > 1) { // two trees with least frequency HuffmanTree a = trees.poll(); HuffmanTree b = trees.poll(); // put into new node and re-insert into queue trees.offer(new HuffmanNode(a, b)); } return trees.poll(); } public static void printCodes(HuffmanTree tree, StringBuffer prefix) { assert tree != null; if (tree instanceof HuffmanLeaf) { HuffmanLeaf leaf = (HuffmanLeaf)tree; // print out character, frequency, and code for this leaf (which is just the prefix) System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix); } else if (tree instanceof HuffmanNode) { HuffmanNode node = (HuffmanNode)tree; // traverse left prefix.append('0'); printCodes(node.left, prefix); prefix.deleteCharAt(prefix.length()-1); // traverse right prefix.append('1'); printCodes(node.right, prefix); prefix.deleteCharAt(prefix.length()-1); } } public static void main(String[] args) { //Symbols: String str = "12345678"; char[] test2 = str.toCharArray(); //Frequency (of the symbols above): int[] charFreqs = {36,18,12,9,7,6,5,4}; // build tree HuffmanTree tree = buildTree(charFreqs,test2); // print out results System.out.println("SYMBOL\tFREQ\tHUFFMAN CODE"); printCodes(tree, new StringBuffer()); } } 

我得到的输出是:

 SYMBOL FREQ HUFFMAN CODE 1 36 0 3 12 100 6 6 1010 5 7 1011 2 18 110 4 9 1110 8 4 11110 7 5 11111 

这很奇怪,例如符号7应该是:11110和符号8应该是:11111

你能帮我吗?

位模式的分配与代码的最优性无关。 你的任务将工作得很好。 没有什么奇怪的。 你本可以对2:110,3:100或4:1110,5:1011表示担忧,但这些也很好。

对代码强加命令的唯一原因是减少将代码从压缩器传送到解压缩器所需的位数。 您可以发送每个符号的代码长度,而不是发送代码,只要代码的构造在两侧都是相同的长度。

在这种情况下,该方法通常是将数字顺序的代码分配给排序的符号列表。 那么你确实会让符号7的代码“值”低于符号8,如果这是它们的分配顺序。

对于您的示例,这样的规范代码将是:

 1: 1 - 0 2: 3 - 100 3: 3 - 101 4: 4 - 1100 5: 4 - 1101 6: 4 - 1110 7: 5 - 11110 8: 5 - 11111 

您只需获取长度并在相同长度内对符号进行排序。 然后分配以0开头并递增的代码,在您逐步增加长度时将位添加到末尾。

请注意,这是一个不常见的示例,其中符号顺序也是频率顺序。 通常情况并非如此。

只需添加一个0来理解完成位。 (超过3位读数)

1 36 0 3 12 100 6 6 1010 5 7 1011’0 2 18 110 4 9 1110 8 4 11110 7 5 11111’0

从答案的评论中回答这个问题:

嘿马克,谢谢你的帮助,但我真的不明白你是如何得到这些代码的? 我是否需要在代码中进行大量更改?<

Mark简单地指代霍夫曼编码的目标,以找到每个符号的最有效深度(比特数),使得所有符号的整体编码(所有符号的频率[符号] * codeLenght [符号])被最小化。

因此,实际上您需要做的就是确定每个符号的叶子深度(级别)。 现在按每个符号的深度对其进行排序,然后开始计算它们。

现在你只需要计算模式了。 就那么简单:

 Example: 2x2: 00, 01 (next is 10) 4x3: 10 + (00, 01, 10) = 1000, 1001, 1010 (next is 1011) 5x3: 1011 + (0, 1, 0 + 10) = 10110, 10111, 10110 + 10 = 11000 (next would be 11001)... 

最后一部分显示了如果元素数量大于两个组之间的可用比特差异会发生什么。 它只是添加到前缀。

这样就创建了一个使用最少空间的霍夫曼代码。 由于这只是一棵树,你也可以从11111开始并删除1并获得另一个在位数方面同样有效的代码系统。

可以添加的一件事是,有一些修改可以将比较中的1(或0)的数量增加到0(或1),因此您有另一种机会压缩用于压缩消息的位模式。


摘要:按频率树中的深度对符号进行排序。 通过添加(减去)一个来构造代码。 下一个免费代码是下一组的开始前缀。 对于每个新成员,只需添加(减去)。 然后从代码中填充0(1)开始。

为了存储这样的树,记住通过对相同的symbole组使用相同的算法,您只需要存储以下信息:

组数n,n * {+ bitDepth,符号数i,s1,s2 … si}。 由于存储n,+ bitDepth,符号数本身就是压缩主题,你可以使用可变位格式甚至发出一个霍夫曼树,因为你会发现几乎不均匀的分布,这是你看到压缩发生的主要原因与霍夫曼树。