如何在jpeg文件中从FFC4(DHT)头创建霍夫曼树？

Question

我以为我可以自己解决这个问题,但我似乎根本没有前进.

好的,背景:

我需要根据jpg文件中FFC4,DHT(Define Huffman Table)标头提供的信息创建一个Huffman代码树.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)结合这两部分,我们看到它们是:
00代码,1位.
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)所以,如果有人理解我的谣言,我会非常感谢一些建议.我意识到这是一个非常具体的问题,但如果没有别的,上面的信息可能会对某人有所帮助.我仍然很新,所以借口我的无知,易于理解的代码特别受欢迎!

Answer 1

至于如何直接实现这一点，我并不完全确定，因为处理信息需要一段时间，但如果您了解attempts ，该算法应该非常简单。从第7点看来，你不这么认为？

\n\n

我将添加一个示例：

\n\n

         \xc2\xb0\n        / \\\n       /   \\\n      \xc2\xb0     \xc2\xb0\n     / \\   / \\\n    a   b  c  d \n

\n\n

在这个简单的 trie 中，如果我们向左走，我们会假设左边是 0，右边是 1。因此，如果遇到模式“00”，则它对应于 a。模式“10”对应于 c。通常对于哈夫曼树，特里树会不平衡，即

\n\n

     \xc2\xb0\n    / \\\n   a   \xc2\xb0\n      / \\\n     b   \xc2\xb0\n        / \\\n       c   d\n

\n\n

在这种情况下，前缀代码“0”对应于a。代码 111 为“d”。

\n