c++ - 在 C++ 中紧凑地保存霍夫曼树

Question

假设我已经用压缩文件编码了我的霍夫曼树。所以我有一个示例文件输出:

001A1C01E01B1D

我在将此字符串逐位保存到文件时遇到问题。我知道 C++ 一次只能输出一个字节到文件，所以我在以字节为单位存储这个字符串时遇到了问题。是否可以将前三位转换为 char 而无需程序填充为字节？如果它为遍历代码填充一个字节，那么我的树(和代码)将完全困惑。如果我一次将其切一个字节，那么如果树不正好是 8 的倍数会怎样？如果压缩文件的位长不是 8 的倍数会怎样？

希望我已经说得够清楚了。

Answer 1

这个问题的标准解决方案是填充。有许多可能的填充方案。填充方案最多填充偶数个字节(即 8 位的倍数)。此外，它们对消息的长度(以位为单位)或填充位的数量进行编码(可以通过减法从中确定以位为单位的消息长度)。后一种解决方案显然会导致填充效率稍微高一些。

最简单的是，您可以在最后一个字节中附加“未使用”的位数作为附加字节值。

更上一层楼，首先假设填充位数为 3 位。定义编码文件的最后 3 位以对填充位数进行编码。现在，如果消息使用的最后一个字节不超过 5 位，则填充可以很好地适契约(Contract)一字节。如果需要添加一个字节来包含填充，则最大间隙为 5+2=7(5 来自额外字节未使用的高位，2 是最后一个字节中可用的最大可能空间，否则 3 -位填充值会适合那里)。由于 0-7 可以用 3 位来表示，所以这是可行的(它不适用于 2 位，因为最大间隙更大并且可表示值的范围更小)。

顺便说一下，将填充信息放在文件末尾(而不是作为文件开头的 header )的主要优点之一是压缩函数可以在流上运行，而无需提前知道它的长度。解压缩也可以基于流，小心处理 EOF 信号。