什么类型的文件我应该存储霍夫曼的结果



我有树,每个字节的编码值,编码和解码表,以及我的编码文件在二进制文件中用于编码文件,我有两个问题,我应该存储什么,只有解码表和编码文件应该足够?我应该在什么类型的文件中存储解码表和我的编码文件?

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

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

实际上,至少有两种可能的规范编码样式。在这两种情况下,给定长度的代码与原始未编码字节的顺序相同。在维基百科中描述的规范代码中,较短的代码位于较长的代码之前(即最短的代码都是零)。但是更常见的规范形式将较长的代码放在开头,因此最长的代码都是零。维基百科条目包括用于生成其规范化编码形式的算法;另一种形式也同样简单。

最长码优先形式的优点是,你可以证明,只有最后的ceil(log2n)位可以是非零的任何代码(n是字母表的大小);换句话说,每个代码由一定数量的0位组成,后面跟着最多一个"字节"的混合0和1。

最新更新