霍夫曼树的有效存储方式

Question

我正在编写一种霍夫曼编码/解码工具，并且正在寻找一种有效的方法来存储霍夫曼树，该树是为了存储在输出文件中而创建的。

目前，我正在实现两个不同的版本。

1. 这一步将整个文件逐个字符地读取到内存中，并为整个文档建立一个频率表。这将只需要输出一次树，因此除了输入文件很小之外，效率不是什么大问题。

2. 我正在使用的另一种方法是读取大约64 KB的数据块，并对其进行频率分析，创建树并对其进行编码。但是，在这种情况下，在每个块之前，我都需要输出我的频率树，以便解码器能够重建其树并正确解码编码的文件。这是效率的体现，因为我想节省尽可能多的空间。

到目前为止，在我的搜索中，我还没有找到将树存储在尽可能小的空间中的好方法，我希望StackOverflow社区可以帮助我找到一个好的解决方案！

Answer 1

由于您已经必须实现代码以按字节组织的流/文件之上处理按位层，因此这是我的建议。不要存储实际频率，解码不需要它们。但是，您确实需要实际的树。因此，对于每个节点，从根目录开始：如果是叶节点：输出1位+ N位字符/字节如果不是叶节点，则输出0位。然后以相同的方式编码两个子节点（先左后右）要阅读，请执行以下操作：读取位。如果为1，则读取N位字符/字节，返回其周围没有子节点的新节点如果bit为0，则用相同的方式解码左右子节点，并用这些子节点返回周围的新节点，但没有值叶节点基本上是没有子节点的任何节点。使用这种方法，您可以在编写输出之前计算出确切的输出大小，以判断增益是否足以证明工作的合理性。假设您有一个键/值对字典，其中包含每个字符的出现频率，其中频率是实际出现的次数。用于计算的伪代码：Tree-size = 10 * NUMBER_OF_CHARACTERS - 1Encoded-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频率：答：6B：1C：6D：2E：5每个字符只有8位，因此树的大小将为10 * 5-1 = 49位。这棵树可能看起来像这样：      20  ----------  |        8  |     ------- 12     |     3-----   |   -----A   C   E   B   D6   6   5   1   2因此，每个字符的路径如下（左为0，右为1）：A：00乙：110C：01D：111E：10因此要计算输出大小：A：6次出现* 2位= 12位B：1次出现* 3位= 3位C：6次出现* 2位= 12位D：2次出现* 3位= 6位E：5次出现* 2位= 10位编码字节的总和是12 + 3 + 12 + 6 + 10 = 43位将其添加到树的49位中，输出将为92位或12个字节。将其与存储未经编码的原始20个字符所需的20 * 8个字节进行比较，您将节省8个字节。最终的输出（包括开始的树）如下。流（AE）中的每个字符都被编码为8位，而0和1只是一个位。流中的空间仅用于将树与编码数据分开，并且在最终输出中不占用任何空间。001A1C01E01B1D 0000000000001100101010101011111111010101010对于注释中包含的具体示例AABCDEF，您将获得以下信息：输入：AABCDEF频率：A2B：1C：1D：1E：1F：1树：        7  -------------  |           4  |       ---------  3       2       2-----   -----   -----A   B   C   D   E   F2   1   1   1   1   1路径：A：00B：01C：100D：101E：110传真：111树：001A1B001C1D01E1F = 59位数据：000001100101110111 = 18位总和：59 + 18 = 77位= 10字节由于原始字符是8个位的7个字符= 56，所以这样的小数据块会有太多开销。

Answer 2

树枝是0，树叶是1。首先遍历树的深度以获取其“形状”e.g. the shape for this tree0 - 0 - 1 (A)|    \- 1 (E)  \    0 - 1 (C)     \- 0 - 1 (B)         \- 1 (D)would be 001101011紧随其后的是具有相同深度一阶AECBD的字符的位（阅读时，您将知道从树的形状中期望有多少个字符）。然后输出该消息的代码。然后，您将获得一连串的比特，可以将其划分为多个字符以进行输出。如果要对其进行分块，则可以测试存储树以供下一个卡盘使用，就像重新使用前一个块的树一样有效，并且树形为“ 1”作为指示符可以重复使用前一个块的树。