我有树,每个字节的编码值,编码和解码表,以及编码文件的二进制文件中的编码文件,我有两个问题,我应该存储什么,只有解码表和编码文件应该足够了吗?我应该在什么类型的文件中存储解码表和编码文件?我正在使用 Java。
最佳答案
如果生成规范树,则只需存储每个字节的编码长度,按未编码值排序。由于霍夫曼代码的最大长度是不同的未编码值的数量,而最小长度是 1,因此每个长度都适合一个字节。 (gzip 库还对长度进行霍夫曼编码以进一步减少开销。)
假设代码是规范的,有一个简单的算法可以从长度列表生成完整的树。
实际上,至少有两种可能的规范编码风格。在这两种情况下,给定长度的代码与原始未编码字节的顺序相同。在 Wikipedia 中描述的规范代码中,较短的代码在较长的代码之前(即最短代码全为零。但是更常见的规范形式将较长的代码放在开头,因此最长代码全为zeros。维基百科文章包含用于生成规范编码形式的算法;另一种形式同样简单。
最长代码优先形式的优点是您可以证明只有最后一个 ceil(log<sub>2</sub>n)
任何代码的位都可以是非零的( n
是字母表的大小);换句话说,每个代码都包含一定数量的零位,后跟最多一个“字节”的混合零和一。此属性有助于加快解码速度。
关于java - 我应该存储哈夫曼结果的什么类型的文件?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16002656/