我以为我可以自己解决这个问题,但我似乎根本没有进展。
好的,背景:
我需要根据 jpg 文件中的 FFC4、DHT(定义霍夫曼表)标头提供的信息创建霍夫曼代码树。 DHT 标头以这种方式定义 Huffman 表:
1)一系列16字节。每个字节定义有多少个符号具有 n 位的霍夫曼码,其中 n 是字节在序列中的位置。 (这有什么意义吗?!!)例如,十六进制的原始数据是:
00 01 05 01 01 01 ... 00
这意味着:
Num of bits: 1 2 3 4 5 6 7 ... 16
Num of codes: 00 01 05 01 01 01 01 ... 00
2) 在 16 个字节的列表之后是实际的符号本身。例如:
00 01 02 03 04 05 06 07 08 09 0A 0B
3)结合这两部分我们可以看到它们是:
1 位 00 代码。
01 代码有 2 位:因此从列表中取出第一个符号:00
05 代码具有 3 位:因此从列表中取出接下来的 5 个符号:01 02 03 04 05
.. 等等
4)最后我们必须根据上面的信息计算出实际的霍夫曼编码。如果您是数学天才,您可能已经发现,只需为每个新代码以特定位长度增加适当位数的二进制数即可计算出这些代码。当位长度增加时,只需增加二进制数,然后将其加倍并继续。当您手动绘制出许多这样的二叉树时,其他人就会变得显而易见......
5)所以这是我用来计算霍夫曼代码并将它们存储在数组中的代码:(首先我读取1处的数据)并将其放入数组中:dhtBitnum)
int binaryCode = 0;
count = 0;
StringBuffer codeString = new StringBuffer();
//populate array with code strings
for (int numBits=1; numBits<=16; numBits++) {
//dhtBitnum contains the number of codes that have a certain number of bits
for (int i=1; i<=dhtBitnum[(numBits-1)]; i++) {
//turn the binary number into a string
codeString.append(Integer.toBinaryString(binaryCode));
//prepend 0s until the code string is the right length
for(int n=codeString.length(); n<numBits; n++) {
codeString.insert(0, "0");
}
//put the created Huffman code in an array
dhtCodes[count]=codeString.toString();
binaryCode++;
count ++;
codeString.delete(0, codeString.length());
}
binaryCode = binaryCode << 1;
}
一旦我生成了霍夫曼代码并按顺序存储它们,我就可以按照它们在 2) 中出现的顺序添加它们引用的符号。这可能不是非常优雅,但它似乎至少可以工作并创建正确的表格。
6)如果有人仍在关注此内容,您应该获得一枚奖章。
7)现在的问题是我想将这些信息存储在二叉树中,以便稍后可以有效地解码jpg图像数据,而不是每次都搜索数组。不幸的是,我无法从上面的 jpg 标题中提供的信息中找出一种干净有效的方法来直接执行此操作。
我能想到的唯一方法是首先计算出上面的霍夫曼代码,然后实现一些根据需要创建节点并将符号保存在适当位置的方法,使用代码作为某种地址。然而,这似乎是一种迂回的方式,也重复了我需要的信息,我确信一定有更好、更简单的方法。
8)因此,如果有人理解我的胡言乱语,我将非常感谢您提出一些建议。我意识到这是一个非常具体的问题,但如果没有其他问题,上面的信息可能对某人有帮助。我对此还很陌生,所以请原谅我的无知,特别欢迎易于理解的代码!