我正在编写一个霍夫曼编码/解码工具，并且正在寻找一种有效的方法来存储为存储在输出文件内部而创建的霍夫曼树。
目前我正在实施两个不同的版本。
到目前为止，在我的搜索中，我还没有找到一种将树存储在尽可能小的空间中的好方法，我希望 StackOverflow 社区可以帮助我找到一个好的解决方案！
由于您已经必须实现代码以在字节组织的流/文件之上处理按位层，因此这是我的建议。
不要存储实际频率，解码不需要它们。但是，您确实需要实际的树。
所以对于每个节点，从根开始：
要阅读，请执行以下操作：
叶节点基本上是任何没有子节点的节点。
使用这种方法，您可以在编写输出之前计算输出的确切大小，以确定收益是否足以证明努力的合理性。这假设您有一个键/值对字典，其中包含每个字符的频率，其中频率是实际出现的次数。
计算伪代码：
Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))
树大小的计算考虑了叶节点和非叶节点，并且内联节点比字符数少一个。
SIZE_OF_ONE_CHARACTER 将是位数，这两个将为您提供我对树的方法 + 编码数据将占用的总位数。
PATH(c) 是一个函数/表，它将产生从根到树中该字符的位路径。
这是一个看起来像 C# 的伪代码，它假设一个字符只是一个简单的字节。
void EncodeNode(Node node, BitWriter writer)
{
if (node.IsLeafNode)
{
writer.WriteBit(1);
writer.WriteByte(node.Value);
}
else
{
writer.WriteBit(0);
EncodeNode(node.LeftChild, writer);
EncodeNode(node.Right, writer);
}
}
要读回它：
Node ReadNode(BitReader reader)
{
if (reader.ReadBit() == 1)
{
return new Node(reader.ReadByte(), null, null);
}
else
{
Node leftChild = ReadNode(reader);
Node rightChild = ReadNode(reader);
return new Node(0, leftChild, rightChild);
}
}
一个示例（简化、使用属性等）节点实现：
public class Node
{
public Byte Value;
public Node LeftChild;
public Node RightChild;
public Node(Byte value, Node leftChild, Node rightChild)
{
Value = value;
LeftChild = leftChild;
RightChild = rightChild;
}
public Boolean IsLeafNode
{
get
{
return LeftChild == null;
}
}
}
这是来自特定示例的示例输出。
输入： AAAAAAABCCCCCCDDEEEEE
频率：
每个字符只有 8 位，因此树的大小将是 10 * 5 - 1 = 49 位。
树可能如下所示：
20
----------
| 8
| -------
12 | 3
----- | -----
A C E B D
6 6 5 1 2
所以每个字符的路径如下（0为左，1为右）：
所以要计算输出大小：
编码字节的总和为 12+3+12+6+10 = 43 位
将其添加到树中的 49 位，输出将是 92 位或 12 个字节。与存储未编码的原始 20 个字符所需的 20 * 8 字节相比，您将节省 8 个字节。
最终输出，包括开始的树，如下所示。流 (AE) 中的每个字符都被编码为 8 位，而 0 和 1 只是一个位。流中的空间只是将树与编码数据分开，在最终输出中不占用任何空间。
001A1C01E01B1D 0000000000001100101010101011111111010101010
对于您在评论中的具体示例 AABCDEF，您将得到以下信息：
输入：AABCDEF
频率：
树：
7
-------------
| 4
| ---------
3 2 2
----- ----- -----
A B C D E F
2 1 1 1 1 1
路径：
树：001A1B001C1D01E1F = 59 位
数据：000001100101110111 = 18 位
总和：59 + 18 = 77 位 = 10 字节
由于原来是 8 位 = 56 的 7 个字符，因此您将有太多这样的小数据的开销。
如果您对树的生成有足够的控制权，则可以使其成为规范树（例如，与DEFLATE相同），这基本上意味着您创建规则来解决构建树时的任何模棱两可的情况。然后，就像 DEFLATE 一样，您实际需要存储的只是每个字符的代码长度。
也就是说，如果你有上面提到的树/代码 Lasse：
然后你可以将它们存储为：2、3、2、3、2
这实际上是足够的信息来重新生成霍夫曼表，假设您总是使用相同的字符集——比如 ASCII。（这意味着你不能跳过字母——你必须为每个字母列出一个代码长度，即使它是零。）
如果您还限制了位长度（例如 7 位），则可以使用短二进制字符串存储这些数字中的每一个。所以 2,3,2,3,2 变成 010 011 010 011 010 - 适合 2 个字节。
如果你想变得非常疯狂，你可以做 DEFLATE 所做的事情，并为这些代码的长度制作另一个霍夫曼表，并预先存储它的代码长度。特别是因为他们添加了“连续插入零 N 次”的额外代码以进一步缩短内容。
如果您已经熟悉霍夫曼编码，则 DEFLATE 的 RFC 还不错： http ://www.ietf.org/rfc/rfc1951.txt
分支是0叶子是1。首先遍历树深度以获得它的“形状”
e.g. the shape for this tree
0 - 0 - 1 (A)
| \- 1 (E)
\
0 - 1 (C)
\- 0 - 1 (B)
\- 1 (D)
would be 001101011
紧随其后的是相同深度一阶 AECBD 中的字符位（阅读时您会知道从树的形状中期望有多少字符）。然后输出消息的代码。然后，您将拥有一长串位，您可以将其划分为字符以进行输出。
如果您正在对其进行分块，您可以测试为下一个块存储树与为前一个块重用树一样有效，并且树形状为“1”作为仅重用来自前一个块的树的指示符.
树通常是从字节的频率表中创建的。因此，存储该表，或者仅存储按频率排序的字节本身，然后即时重新创建树。这当然假设您正在构建树以表示单个字节，而不是更大的块。
更新：正如 j_random_hacker 在评论中指出的那样，您实际上不能这样做：您需要频率值本身。当您构建树时，它们会组合并向上“冒泡”。本页描述了从频率表构建树的方式。作为奖励，它还通过提到一种保存树的方法来避免删除这个答案：
输出霍夫曼树本身的最简单方法是，从根开始，先转储左侧，然后转储右侧。对于每个节点，您输出一个 0，对于每个叶子，您输出一个 1，后跟 N 位表示该值。
更好的方法
树：
7
-------------
| 4
| ---------
3 2 2
----- ----- -----
A B C D E F
2 1 1 1 1 1 : frequencies
2 2 3 3 3 3 : tree depth (encoding bits)
现在只需导出此表：
depth number of codes
----- ---------------
2 2 [A B]
3 4 [C D E F]
您不需要使用相同的二叉树，只需保留计算出的树深度，即编码位数。所以只需保持未压缩值的向量 [ABCDEF] 按树深度排序，使用相对索引而不是这个单独的向量。现在为每个深度重新创建对齐的位模式：
depth number of codes
----- ---------------
2 2 [00x 01x]
3 4 [100 101 110 111]
您立即看到的是，只有每行中的第一位模式是重要的。您将获得以下查找表：
first pattern depth first index
------------- ----- -----------
000 2 0
100 3 2
这个 LUT 的尺寸非常小（即使你的 Huffman 代码可以是 32 位长，它也只会包含 32 行），实际上第一个模式始终为空，在执行模式的二分查找时可以完全忽略它在其中（这里只需要比较一个模式以了解位深度是 2 还是 3，并获得关联数据存储在向量中的第一个索引）。在我们的示例中，您需要在最多 31 个值的搜索空间中执行输入模式的快速二进制搜索，即最多 5 个整数比较。这 31 个比较例程可以在 31 个代码中进行优化，以避免所有循环，并且在浏览整数二叉查找树时必须管理状态。所有这个表都适合小的固定长度（对于不超过 32 位的 Huffman 代码，LUT 最多只需要 31 行，
换句话说，上面的 LUT 每个需要 31 个 32 位大小的整数，32 个字节来存储位深度值：但是您可以通过暗示深度列（以及深度 1 的第一行）来避免这种情况：
first pattern (depth) first index
------------- ------- -----------
(000) (1) (0)
000 (2) 0
100 (3) 2
000 (4) 6
000 (5) 6
... ... ...
000 (32) 6
所以你的 LUT 包含 [000, 100, 000(30times)]。要在其中搜索，您必须找到输入位模式在两个模式之间的位置：它必须低于此 LUT 中下一个位置的模式，但仍高于或等于当前位置的模式（如果两个位置包含相同的模式，当前行将不匹配，输入模式适合下面）。然后你将分而治之，最多使用 5 次测试（二分查找需要单个代码，其中嵌入了 5 个 if/then/else 嵌套级别，它有 32 个分支，达到的分支直接指示不存在的位深度需要存储；然后您对第二个表执行单个直接索引查找以返回第一个索引；您在解码值向量中附加地导出最终索引）。
一旦您在查找表中获得一个位置（在第一列中搜索），您就会立即获得从输入中获取的位数，然后是向量的起始索引。通过减去第一个索引后的基本位掩码，您获得的位深度可用于直接导出调整后的索引位置。
总之：永远不要存储链接的二叉树，并且您不需要任何循环来执行查找，它只需要 5 个嵌套的 if 比较 31 个模式表中固定位置的模式，以及一个包含起始偏移量的 31 个整数表解码值的向量（在嵌套 if/then/else 测试的第一个分支中，向量的起始偏移量是隐含的，它始终为零；它也是最频繁的分支，因为它匹配最短的代码这是最常见的解码值）。
有两种主要方法可以将霍夫曼代码 LUT 存储为其他答案状态。您可以存储树的几何形状，0 表示节点，1 表示叶子，然后放入所有叶子值，或者您可以使用规范的霍夫曼编码，存储霍夫曼代码的长度。
问题是，根据情况，一种方法比另一种方法更好。假设您要压缩的数据中唯一符号的数量（aabbbcdddd，有 4 个唯一符号，a, b, c, d）是n。
沿着树中的符号存储树的几何形状的位数是10n - 1。
假设您按照代码长度的符号顺序存储代码长度，并且代码长度为 8 位（256 个符号字母的代码长度不会超过 8 位），代码长度表的大小将是平坦的 2048 位。
当您有大量唯一符号（例如 256 个）时，将需要 2559 位来存储树的几何形状。在这种情况下，码长表的效率要高得多。准确地说，511 位更有效。
但是如果你只有 5 个唯一的符号，那么树几何结构只需要 49 位，在这种情况下，与存储代码长度表相比，存储树几何结构几乎要好 2000 位。
树几何对 最有效n < 205，而代码长度表对 更有效n >= 205。那么，为什么不两全其美，并使用两者呢？在压缩数据的开头有 1 位表示下一个无论多少位将采用代码长度表的格式，还是哈夫曼树的几何形状。
其实为什么不加两位呢，当都为0的时候，没有表，数据是未压缩的。因为有时，您无法获得压缩！最好在文件开头有一个 0x00 字节，告诉解码器不要担心做任何事情。通过不包括表或树的几何图形来节省空间，并节省时间，不必不必要地压缩和解压缩数据。