存储霍夫曼树的有效方法

Question

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

目前我正在实施两种不同的版本.

1. 这个文件逐个字符地将整个文件读入内存,并为整个文档构建频率表.这只需要输出一次树,因此除了输入文件很小之外,效率不是很大的问题.
2. 我正在使用的另一种方法是读取一块大小为64千字节的数据,并对其进行频率分析,创建一个树并对其进行编码.但是,在这种情况下,在每个块之前,我将需要输出我的频率树,以便解码器能够重新构建其树并正确解码编码文件.这是效率确实到位的地方,因为我想节省尽可能多的空间.

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

Answer 1

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

不存储实际频率,解码时不需要它们.但是,您确实需要实际的树.

所以对于每个节点,从root开始:

1. 如果叶节点:输出1位+ N位字符/字节
2. 如果不是叶节点,则输出0位.然后以相同的方式编码两个子节点(左起第一个)

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

1. 读位.如果为1,则读取N位字符/字节,返回其周围没有子节点的新节点
2. 如果位为0,则以相同的方式解码左右子节点,并使用这些子节点返回它们周围的新节点,但没有值

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

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

用于计算的伪代码:

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

频率:

• 答: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
• B:110
• C:01
• D: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个字节.

最终输出,包括开始的树,如下所示.流(AE)中的每个字符编码为8位,而0和1只是一位.流中的空间只是将树与编码数据分开,并且不占用最终输出中的任何空间.

001A1C01E01B1D 0000000000001100101010101011111111010101010

对于你在评论AABCDEF中的具体例子,你会得到这个:

输入:AABCDEF

频率:

• A2
• 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
• B:01
• C:100
• D:101
• E:110
• F:111

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

由于原始版本是8位= 56的7个字符,因此这些小块数据的开销过大.

Answer 2

如果你对树的生成有足够的控制,你可以让它做一个规范的树(例如,与DEFLATE一样),这基本上意味着你创建规则来解决构建树时的任何模糊情况.然后,像DEFLATE一样,您实际需要存储的是每个字符的代码长度.

也就是说,如果你有上面提到的树/代码Lasse:

• 答:00
• B:110
• C:01
• D:111
• E:10

然后你可以将它们存储为: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

Answer 3

分支是 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”作为仅重用前一个块中的树的指示符.