java - 我应该存储哈夫曼结果的什么类型的文件？

Question

我有树，每个字节的编码值，编码和解码表，以及编码文件的二进制文件中的编码文件，我有两个问题，我应该存储什么，只有解码表和编码文件应该足够了吗？我应该在什么类型的文件中存储解码表和编码文件？我正在使用 Java。

Answer 1

如果生成规范树，则只需存储每个字节的编码长度，按未编码值排序。由于霍夫曼代码的最大长度是不同的未编码值的数量，而最小长度是 1，因此每个长度都适合一个字节。 (gzip 库还对长度进行霍夫曼编码以进一步减少开销。)

假设代码是规范的，有一个简单的算法可以从长度列表生成完整的树。

实际上，至少有两种可能的规范编码风格。在这两种情况下，给定长度的代码与原始未编码字节的顺序相同。在 Wikipedia 中描述的规范代码中，较短的代码在较长的代码之前(即最短代码全为零。但是更常见的规范形式将较长的代码放在开头，因此最长代码全为zeros。维基百科文章包含用于生成规范编码形式的算法；另一种形式同样简单。

最长代码优先形式的优点是您可以证明只有最后一个 ceil(log<sub>2</sub>n)任何代码的位都可以是非零的( n 是字母表的大小)；换句话说，每个代码都包含一定数量的零位，后跟最多一个“字节”的混合零和一。此属性有助于加快解码速度。