为了账号安全,请及时绑定邮箱和手机立即绑定

霍夫曼树的有效存储方式

霍夫曼树的有效存储方式

郎朗坤 2019-11-28 13:45:16
我正在编写一种霍夫曼编码/解码工具,并且正在寻找一种有效的方法来存储霍夫曼树,该树是为了存储在输出文件中而创建的。目前,我正在实现两个不同的版本。这一步将整个文件逐个字符地读取到内存中,并为整个文档建立一个频率表。这将只需要输出一次树,因此除了输入文件很小之外,效率不是什么大问题。我正在使用的另一种方法是读取大约64 KB的数据块,并对其进行频率分析,创建树并对其进行编码。但是,在这种情况下,在每个块之前,我都需要输出我的频率树,以便解码器能够重建其树并正确解码编码的文件。这是效率的体现,因为我想节省尽可能多的空间。到目前为止,在我的搜索中,我还没有找到将树存储在尽可能小的空间中的好方法,我希望StackOverflow社区可以帮助我找到一个好的解决方案!
查看完整描述

3 回答

?
炎炎设计

TA贡献1808条经验 获得超4个赞

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


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


因此,对于每个节点,从根目录开始:


如果是叶节点:输出1位+ N位字符/字节

如果不是叶节点,则输出0位。然后以相同的方式编码两个子节点(先左后右)

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


读取位。如果为1,则读取N位字符/字节,返回其周围没有子节点的新节点

如果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;

        }

    }

}

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


输入: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):


A:00

乙: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

路径:


A:00

B:01

C:100

D:101

E:110

传真:111

树:001A1B001C1D01E1F = 59位

数据:000001100101110111 = 18位

总和:59 + 18 = 77位= 10字节


由于原始字符是8个位的7个字符= 56,所以这样的小数据块会有太多开销。


查看完整回答
反对 回复 2019-11-28
?
慕莱坞森

TA贡献1810条经验 获得超4个赞

树枝是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”作为指示符可以重复使用前一个块的树。


查看完整回答
反对 回复 2019-11-28
  • 3 回答
  • 0 关注
  • 722 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信