c++ - 存储霍夫曼树的有效方法

Question

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

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

1. 这一步将整个文件逐个字符读入内存，并为整个文档建立一个频率表。这只需要输出一次树，因此效率不是什么大问题，除非输入文件很小。
2. 我使用的另一种方法是读取一 block 大小约为 64 KB 的数据，然后对其进行频率分析，创建一棵树并对其进行编码。但是，在这种情况下，在每个 block 之前，我需要输出我的频率树，以便解码器能够重新构建其树并正确解码编码文件。这就是效率发挥作用的地方，因为我想尽可能多地节省空间。

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

Answer 1

由于您已经必须实现代码以在按字节组织的流/文件之上处理逐位层，因此这是我的建议。

不要存储实际频率，解码不需要它们。但是，您确实需要实际的树。

所以对于每个节点，从根开始:

1. 如果叶节点:输出 1 位 + N 位字符/字节
2. 如果不是叶节点，则输出 0 位。然后以相同的方式对两个子节点(先左后右)进行编码

要阅读，请执行以下操作:

1. 读取位。如果为 1，则读取 N 位字符/字节，返回没有子节点的新节点
2. 如果位为 0，则以相同的方式解码左右子节点，并返回带有这些子节点的新节点，但没有值

叶节点基本上是任何没有子节点的节点。

使用这种方法，您可以在编写输出之前计算输出的确切大小，以确定 yield 是否足以证明努力的合理性。这假设您有一个键/值对字典，其中包含每个字符的频率，其中频率是实际出现的次数。

计算伪代码:

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

频率:

• 答:6
• B:1
• C:6
• D:2
• E:5

每个字符只有 8 位，因此树的大小将是 10 * 5 - 1 = 49 位。

树可能如下所示:

      20
  ----------
  |        8
  |     -------
 12     |     3
-----   |   -----
A   C   E   B   D
6   6   5   1   2

所以每个字符的路径如下(0为左，1为右):

• 答:00
• 乙:110
• C: 01
• 电话:111
• E: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 个字节。

最终输出，包括开始的树，如下所示。流 (A-E) 中的每个字符都被编码为 8 位，而 0 和 1 只是一个位。流中的空间只是将树与编码数据分开，在最终输出中不占用任何空间。

001A1C01E01B1D 0000000000001100101010101011111111010101010

---

对于您在评论中的具体示例 AABCDEF，您将得到:

输入:AABCDEF

频率:

• 答:2
• B:1
• C:1
• D:1
• E:1
• F: 1

树:

        7
  -------------
  |           4
  |       ---------
  3       2       2
-----   -----   -----
A   B   C   D   E   F
2   1   1   1   1   1

路径:

• 答:00
• 乙:01
• C:100
• D:101
• 电子:110
• F: 111

树:001A1B001C1D01E1F = 59 位
数据:000001100101110111 = 18位
总和:59 + 18 = 77 位 = 10 个字节

由于原来是 8 位的 7 个字符 = 56，所以对于这么小的数据，你会有太多的开销。