在 C++ 中紧凑地保存霍夫曼树
Saving a Huffman Tree compactly in C++
假设我已经用压缩文件编码了我的霍夫曼树。所以我有一个示例文件输出：
001A1C01E01B1D
我在将此字符串逐位保存到文件时遇到问题。我知道 C++ 一次只能输出一个字节到文件，所以我在以字节为单位存储这个字符串时遇到了问题。是否可以将前三位转换为 char 而无需程序填充为字节？如果它为遍历代码填充一个字节，那么我的树（和代码）将完全混乱。如果我一次将其切一个字节，那么如果树不正好是 8 的倍数会怎样？如果压缩文件的位长不是 8 的倍数会怎样？
希望我说得够清楚了。
简单地将n字节的序列视为8n位的序列。使用 >> 或 <<、| 和 & 运算符从可变长度位代码序列中提取 assemble 个字节。
流的结尾对于正确处理很重要。您需要流代码的结尾，以便解码器知道停止而不是尝试解码完成最后一个字节的最终填充位。
这个问题的标准解决方案是填充。有许多可能的填充方案。填充方案最多填充偶数个字节（即 8 位的倍数）。此外，它们对消息的长度（以位为单位）或填充位的数量进行编码（可以通过减法从中确定以位为单位的消息长度）。后一种解决方案显然会导致填充效率更高。
最简单的方法是，您可以在最后一个字节中附加 "unused" 位数作为附加字节值。
更上一层楼，首先假设填充位数为 3 位。定义编码文件的最后 3 位以对填充位数进行编码。现在，如果消息使用的最后一个字节不超过 5 位，则填充可以很好地适合同一字节。如果需要添加一个字节来包含填充，则最大间隙为 5+2=7（5 来自额外字节未使用的高位，而 2 是最后一个字节中最大可能 space free ，否则 3 位填充值将适合那里）。由于 0-7 可以用 3 位表示，所以这有效（它不适用于 2 位，因为最大间隙更大并且可表示值的范围更小）。
顺便说一句，将填充信息放在文件末尾（而不是 header 放在文件开头）的主要优点之一是压缩函数可以运行在流上，而不必事先知道它的长度。解压也可以stream-based，小心处理EOF信号。
假设我已经用压缩文件编码了我的霍夫曼树。所以我有一个示例文件输出：
001A1C01E01B1D
我在将此字符串逐位保存到文件时遇到问题。我知道 C++ 一次只能输出一个字节到文件，所以我在以字节为单位存储这个字符串时遇到了问题。是否可以将前三位转换为 char 而无需程序填充为字节？如果它为遍历代码填充一个字节，那么我的树（和代码）将完全混乱。如果我一次将其切一个字节，那么如果树不正好是 8 的倍数会怎样？如果压缩文件的位长不是 8 的倍数会怎样？
希望我说得够清楚了。
简单地将n字节的序列视为8n位的序列。使用 >> 或 <<、| 和 & 运算符从可变长度位代码序列中提取 assemble 个字节。
流的结尾对于正确处理很重要。您需要流代码的结尾，以便解码器知道停止而不是尝试解码完成最后一个字节的最终填充位。
这个问题的标准解决方案是填充。有许多可能的填充方案。填充方案最多填充偶数个字节（即 8 位的倍数）。此外，它们对消息的长度（以位为单位）或填充位的数量进行编码（可以通过减法从中确定以位为单位的消息长度）。后一种解决方案显然会导致填充效率更高。
最简单的方法是，您可以在最后一个字节中附加 "unused" 位数作为附加字节值。
更上一层楼，首先假设填充位数为 3 位。定义编码文件的最后 3 位以对填充位数进行编码。现在，如果消息使用的最后一个字节不超过 5 位，则填充可以很好地适合同一字节。如果需要添加一个字节来包含填充，则最大间隙为 5+2=7（5 来自额外字节未使用的高位，而 2 是最后一个字节中最大可能 space free ，否则 3 位填充值将适合那里）。由于 0-7 可以用 3 位表示，所以这有效（它不适用于 2 位，因为最大间隙更大并且可表示值的范围更小）。
顺便说一句，将填充信息放在文件末尾（而不是 header 放在文件开头）的主要优点之一是压缩函数可以运行在流上，而不必事先知道它的长度。解压也可以stream-based，小心处理EOF信号。