c# - 如何有效地将霍夫曼树和编码二进制字符串存储到文件中？

我可以轻松地将字符串转换为 Huffman-Tree，然后编码为二进制序列。

我应该如何保存这些才能真正压缩原始数据然后恢复？

我在网上搜索，但我只能找到指南和答案，直到我已经做过。如何进一步使用霍夫曼算法来实际实现无损压缩？

我在这个项目中使用 C#。

编辑：到目前为止，我已经实现了这些，可能需要重新考虑。

我正在尝试压缩文本文件。我使用霍夫曼算法，但有一些我无法弄清楚的关键点：

压缩时的“aaaabbbccdef”给出这种编码

Key = a, Value = 11
Key = b, Value = 01
Key = c, Value = 101
Key = d, Value = 000
Key = e, Value = 001
Key = f, Value = 100

11111111010101101101000001100是编码版本。它通常需要 12*8 位，但我们已将其压缩为 29 位。对于这么小的文件，这个例子可能有点不必要，但让我解释一下我试图做什么。

我们这里有 29 位，但我们需要 8*n 位，所以我用零填充编码字符串，直到它变成 8 的倍数。由于我可以添加 1 到 7 个零，因此使用 1 字节来表示这一点已经绰绰有余。这种情况下，我添加了 3 个零

11111111010101101101000001100000 然后将我添加到前面的额外位数添加为二进制，然后拆分为 8 位片段

00000011-11111111-01010110-11010000-01100000

将这些转换为 ASCII 字符

ÿVÐ`

现在，如果我有编码表，我可以查看前 8 位将其转换为整数 ignoreBits 并通过忽略最后一个 ignoreBits 将其转回原始形式。

问题是我还想在此文件中包含未压缩版本的编码表，以获得功能齐全的 ZIP/UNZIP prpgram，但我无法确定我的 ignoreBits 何时结束、我的 encodingTable 开始/结束、编码位开始/结束。

我考虑过使用空字符，但不能保证 Values 不能产生空字符。“ddd”在这种情况下产生00000000-0.....

标签： c#compressionhuffman-codelossless-compression

您的代码表示需要自动终止。然后你知道下一位是霍夫曼码的开始。一种方法是遍历 Huffman 代码产生的树，为每个分支写入一个 0 位，或者在一个 1 位后跟叶符号。遍历完成后，您知道下一位必须是代码。

您还需要使您的数据自行终止。请注意，在您给出的示例中，添加的三个零位将被解码为另一个“d”。所以你会错误地得到 'aaaabbbccdefd' 作为结果。您需要在编码数据之前加上预期的符号计数，或者您需要在编码集中添加一个符号，频率为 1，这标志着数据的结束。