一种高效的霍夫曼树存储方法

不要存储实际频率,解码时不需要它们。然而,你确实需要一棵真正的树。

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

2. 如果bit为0,则以相同的方式解码左右子节点,并返回它们周围的新节点和这些子节点,但没有值

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

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

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;
        }
    }
}

这是一个特定示例的输出示例。

频率:

• B: 1
• C: 6

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

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

因此,每个字符的路径如下(0为左,1为右):

• A: 00
• B: 110
• C: 01

因此,要计算输出大小:

• 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

频率:

• A: 2
• B: 1
• E: 1

树:

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

路径:

• A: 00
• B: 01
• C: 100
• D: 101
• F: 111

树:001A1B001C1D01E1F=59位

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

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

• A: 00
• B: 110
• C: 01

然后,您可以将它们存储为: 2, 3, 2, 3, 2

如果你想得到 真的

如果你已经熟悉哈夫曼编码,DEFLATE的RFC还不错: http://www.ietf.org/rfc/rfc1951.txt

e.g. the shape for this tree

0 - 0 - 1 (A)
|    \- 1 (E)
  \
    0 - 1 (C)
     \- 0 - 1 (B)
         \- 1 (D)

would be 001101011

如果你正在对其进行分块,你可以测试为下一个卡盘存储树与为上一个块重用树一样有效,并将树的形状设置为“1”作为只重用前一个块中的树的指标。

更新 This page 描述了从频率表构建树的方式。作为奖励,它还通过提到一种保存树的方法来避免删除此答案:

输出哈夫曼树本身最简单的方法是,从根开始,先转储左侧,然后转储右侧。对于每个节点,您输出一个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]

您不需要使用相同的二叉树,只需保持计算出的树深度,即编码比特数。因此,只需将未压缩值的向量[A B 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

所有这些表都适合小的固定长度(对于长度不超过32位的霍夫曼码,LUT最多只需要31行,上面的另外两列最多可以填充32行)。

    first pattern (depth) first index
    ------------- ------- -----------
    (000)          (1)    (0)
     000           (2)     0
     100           (3)     2
     000           (4)     6
     000           (5)     6
     ...           ...     ...
     000           (32)    6

一旦你在查找表中找到一个位置(在第一列中搜索),你就可以立即从输入中获取比特数,然后获取向量的起始索引。通过在减去第一个索引后进行基本位掩码,您获得的位深度可用于直接导出调整后的索引位置。

总之:永远不要存储链接的二叉树,也不需要任何循环来执行查找,只需要在31个模式的表中的固定位置比较5个嵌套的if模式,以及一个包含解码值向量内起始偏移的31个int的表(在嵌套的if/then/else测试的第一个分支中,向量的起始偏移是隐含的,它总是零;它也是最频繁的分支,因为它与最频繁解码值的最短代码相匹配)。