c++ - 将霍夫曼编码输出到文件

Question

我有一个程序可以读取文件并保存每个字符的出现频率。然后它根据每个字符的频率构造一个霍夫曼树，然后将树的霍夫曼代码输出到一个文件。

所以像“Hello World”这样的输入会将这个序列输出到一个文件中:

01010101 0010 010 010 01010 0101010 000 01010 00101 010 0001

这是有道理的，因为最常见的字符具有最短的代码。问题是，这会使文件大小增加十倍。我意识到原因是因为每个 1 和 0 在内存中都表示为它自己的字符，所以它们每个都扩展为一个字节的数据。

我在想我能做的是将每个代码(例如“010”)转换为一个字符并将其保存到文件中——但这仍然会将代码填充为一个字节长(如果代码是长于一个字节)。

我该怎么做？如果需要，我可以提供代码片段——我基本上是将每个代码保存到一个字符串中，所以这就是文件变得如此大的原因(它将每个“位”输出为一个字节)。例如，如果我要将代码转换为 long，那么像 00010 这样的代码将表示为 2，而像 010 这样的代码也将表示为 2。

Answer 1

您基本上必须一次处理一个字节(或一个字)。维护一个用位填充的字节，并记录到目前为止已填充了多少位。当你到达 8 时，写入字节并从一个空字节重新开始。