java - 如何从 jpeg 文件中的 FFC4 (DHT) header 创建霍夫曼树？

Question

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

好的，背景:

我需要根据 jpg 文件中的 FFC4、DHT(定义霍夫曼表) header 提供的信息创建霍夫曼代码树。 DHT 头以这种方式定义霍夫曼表:

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
3 位的 05 代码:所以从列表中取出接下来的 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 header 中提供的信息中找到一种干净高效的方法来执行此操作。
我能想到的唯一方法是首先计算出上面的霍夫曼代码，然后实现一些根据需要创建节点并将符号保存在适当位置的方法，使用这些代码作为各种地址。然而，这似乎是一种迂回的方式，同时也在复制我需要的信息，我相信一定有更好、更简单的方法。

8) 因此，如果有人理解我的胡言乱语，我将非常感谢您提出一些建议。我意识到这是一个非常具体的问题，但如果不出意外，上面的信息可能对某人有帮助。我在这方面还很陌生，所以请原谅我的无知，特别欢迎易于理解的代码!

Answer 1

至于如何直接实现这个我不太确定，因为处理信息需要一段时间，但如果你知道 tries，算法应该非常简单.从第 7 点看来你没有？

我再举个例子:

         °
        / \
       /   \
      °     °
     / \   / \
    a   b  c  d 

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

     °
    / \
   a   °
      / \
     b   °
        / \
       c   d

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