我正在编写一种Huffman编/解码工具，希望找到一种有效的方法来存储创建的Huffman树以便储存在输出文件中。
目前我正在实现两个不同版本。
到目前为止，我在搜索中没有找到一种在尽可能少的空间中存储树结构的好方法，希望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;
}
}
}
以下是一个具体示例的输出：
输入：AAAAAABCCCCCCDDEEEEE
字符频率：
每个字符只占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个字节。
最终输出，包括树在内，如下所示。流中的每个字符（A-E）都编码为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个字节
由于原始数据是7个8比特（位）字符 = 56个比特（位），因此对于这样小的数据块会有太多的开销。
如果你已经熟悉霍夫曼编码，那么 DEFLATE 的 RFC 并不难理解：http://www.ietf.org/rfc/rfc1951.txt
2, 3, 2, 3, 2重新生成哈夫曼表？ - Aadit M Shahйцшщзъ，会怎样？ - Mikhail_Sam分支为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
更好的方法
树：
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]
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
first pattern (depth) first index
------------- ------- -----------
(000) (1) (0)
000 (2) 0
100 (3) 2
000 (4) 6
000 (5) 6
... ... ...
000 (32) 6
正如其他答案所述，存储哈夫曼编码LUTs有两种主要方法。您可以存储树的几何形状，0表示节点，1表示叶子，然后放入所有叶子值；或者您可以使用规范化哈夫曼编码，存储哈夫曼编码的长度。
问题在于，一种方法比另一种方法更好，这取决于具体情况。假设您希望压缩的数据中有n个唯一符号（例如aabbbcdddd，有4个唯一符号a、b、c、d）。
存储树的几何形状以及树中的符号所需的位数为10n-1。
假设您按符号顺序存储代码长度，并且代码长度为8位（256个符号字母的代码长度不会超过8位），则代码长度表的大小将是2048位。
当您有大量唯一符号时，比如256个，存储树的几何形状需要2559位。在这种情况下，代码长度表更加高效。确切地说，比存储树的几何形状节省了511位。
但是，如果您只有5个唯一的符号，则树形几何仅需要49位，在这种情况下，与存储代码长度表相比，存储树形几何要好近2000位。
对于 n < 205，树形几何最有效，而代码长度表对于 n >= 205 更有效。那么，为什么不兼顾两者，同时使用两者呢？在压缩数据的开头有1位表示接下来的多少位将以哈夫曼树的格式或代码长度表的格式进行存储。
实际上，为什么不添加两位，当它们都为0时，没有表格，数据未经压缩。因为有时候无法进行压缩！最好在文件开头有一个单独的字节为0x00，告诉解码器不用担心任何事情。通过不包括树的表格或几何形状来节省空间，并节省时间，不必不必要地压缩和解压缩数据。