- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我的霍夫曼树代码有问题。在主要方法中,我输入一个符号字符串,还输入一个包含符号频率的整数数组。它应该打印出每个符号及其霍夫曼代码,但我认为它是错误的......
这是代码:
package huffman;
import java.util.*;
abstract class HuffmanTree implements Comparable<HuffmanTree> {
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<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
// initially, we have a forest of leaves
// one for each non-empty character
for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[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 的分配顺序是这样的话,那么符号 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 开始并递增的代码,随着长度的增加,在末尾添加位。
请注意,这是一个不寻常的示例,其中符号顺序也是频率顺序。通常情况并非如此。
关于java - Java 中的霍夫曼树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16658419/
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
我这样定义了一个二叉树: struct btree { int x; btree* left_child = nullptr; btree* right_child = nul
我有这个霍夫曼代码,旨在返回数组中每个字母的霍夫曼代码并按字母顺序打印它们。问题是它不生成任何输出,而是继续处理,直到我手动退出它。谁能帮我找出错误吗?我认为我的代码是正确的,但我不知道无限循环从何而
动机 想象一下一个哈夫曼压缩文件被部分下载,就像在p2p软件中一样,所以我们首先为整个文件分配磁盘空间,然后开始随机下载文件块。其中一个哈夫曼密码(但我们不知道是哪一个)是一个结束密码,所以如果这个密
以下 block 由霍夫曼 block 标记嵌套 -HUFF---------------------------------------------------------------------0
我是一名优秀的程序员,十分优秀!