一种哈夫曼树保存方法及系统

技术领域

本发明涉及数据压缩技术领域，尤其涉及一种哈夫曼树保存方法及系 统。

背景技术

哈夫曼树经常用于数据压缩算法，实际压缩中，不仅要保存压缩编码， 同时，为了解压缩，还需要保存哈夫曼树的树结构和节点总数等，目前， 用来存储哈夫曼树的方法有以下三种：

1、直接记录编码表方法

2、存储原始统计信息方式代替存储哈夫曼编码表；

3、利用链表存储完整哈夫曼树的方法；

以上三种方法中，直接记录编码表方法需要N-1位存储每个节点， 其中N为节点总数；存储原始统计信息方式代替存储哈夫曼编码表采用最 大数所占位数或者数据综合决定存储代码的位数；利用链表存储完整哈夫 曼树的方法一共需记录2N-1个固定长度的结构数据，其中，N为哈夫曼 树的节点数。

这三种方式为防止存在树形极端的情况，均需要考虑溢出问题，所以， 需要按照最多的存储位数存储哈夫曼树，这样，在哈夫曼树不满时，会造 成严重浪费，且存储极不稳定，此外，利用链表存储完整哈夫曼树的方法 还要存储链表指针，浪费更加严重。

发明内容

本发明所要解决的技术问题是，提供一种哈夫曼树保存方法及系统， 以解决哈夫曼树存储冗余、浪费严重且存储不稳定的问题。

本发明解决上述技术问题所采用的技术方案是提供一种哈夫曼树保 存方法，该方法包括步骤：

S1、根据树结构按层遍历每个节点，存储所述节点的总数N；

S2、判断所述节点总数N；

S3、若所述节点总数N≤2，不记录所述树结构；

S4、若所述节点总数N＞2，判断每个节点是否有子树，用1位存储。

优选地，步骤S4中，若有所述子树，该位存储为1；若无所述子树， 该位存储为0。

优选地，步骤S4中，还可以根据冗余需要增加到2-N位来存储对所 述节点的子树状态。

优选地，根据所述树结构，对所述记录进行优化，除去根节点和最后 两个叶节点，得到新的记录，所述新的记录含有一半叶节点，可根据之前 的节点推断最后一个节点，除去所述最后一个节点，并存储为最终记录。

优选地，所述哈夫曼树或与所述哈夫曼树特点相同的树还可以通过前 序遍历、中序遍历和后续遍历等方式进行遍历。

另一方面，本发明提供一种哈夫曼树保存系统，该系统包括：

遍历单元，用于根据树结构按层遍历每个节点，得到所述节点的总数 N；

第一判断单元，用于判断所述节点总数N，若N≤2，则不记录所述树 结构，若N＞2，则将遍历结构传递到第二判断单元；

第二判断单元，用于判断每个所述节点是否有子树；

记录单元，用1位，或根据冗余需要，增加到2-N位，记录所述第二 判断单元的判断结果；

存储单元，用于存储所述记录单元的记录和所述遍历单元的总数N。

优选地，根据所述第二判断单元的判断，若所述节点有所述子树，则 记录为1，若所述节点没有所述子树，则记录为0。

优选地，所述记录单元还包括优化单元，用来优化所述记录，除去所 述记录中代表所述树结构根节点的第一个记录、代表最后两个叶节点的最 后两个记录以及根据之前节点可以推导出的倒数第三个节点的记录。

优选地，所述遍历单元还可以通过前序遍历、中序遍历和后序遍历等 遍历方法对所述树结构进行遍历。

优选地，所述系统还可以保存与所述哈夫曼树树结构相似的结构。

附图说明

图1是本发明的一个优选实施例中哈夫曼树保存方法的流程图；

图2是本发明的一个优选实施例中哈夫曼树保存系统的结构图。

具体实施方式

以下实施例仅用于更加清楚地说明本发明的技术方案，而不能以此来 限制本发明的保护范围。说明书后续描述为实施本发明的较佳实施方式， 然所述描述乃以说明本发明的一般原则为目的，并非用以限定本发明的范 围。本发明的保护范围当视所附权利要求所界定者为准。

下面结合附图和具体实施例对本发明做进一步详细说明。

如图1所示，为本发明的一个优选实施例，公开了一种哈夫曼树保存 方法，该方法包含步骤：

S1、根据树结构按层遍历每个节点，存储节点的总数N；

S2、判断节点总数N；

S3、若节点总数N≤2，不记录树结构；

S4、若节点总数N＞2，判断每个节点是否有子树，用1位存储。

进一步地，步骤S4中，若有子树，该位存储为1；若无子树，该位 存储为0。

进一步地，步骤S4中，还可以根据冗余需要增加到2-N位来存储对 节点的子树状态。

本实施例中，通过按层遍历哈夫曼树节点的方法，仅需要2N-1位即 可存储整个树结构，并且在节点总数不大于2时，不需记录树结构，这种 方法能够节省存储哈夫曼树的空间，防止存储空间的浪费，并且不会造成 存储长度不固定的问题，能够达到稳定高效进行压缩的目的；即使需要增 加到2-N位来存储所述节点，对比其他存储方式仍旧更有优势。

进一步地，根据树结构，对记录进行优化，除去根节点和最后两个叶 节点，得到新的记录，新的记录含有一半叶节点，可根据之前的节点推断 最后一个节点，除去最后一个节点，并存储为最终记录。

本实施例中还可以对哈夫曼树的存储进行优化，哈夫曼树的根节点必 定有子树，记录为1，可以除去；哈夫曼树的最后两个节点必定是叶节点， 无子树，记录为0，可以除去；剩余节点中有一半是叶节点，因此，根据 之前的节点可以推断出倒数第三个节点是否有子树，不需要存储，整个哈 夫曼树的存储仅需要2N-5位即可，极大的节省了存储空间，杜绝了存储 空间浪费等问题。

进一步地，哈夫曼树或与哈夫曼树特点相同的树还可以通过前序遍历、 中序遍历和后续遍历等方式进行遍历。

本实施例中，哈夫曼树的存储方法还可用于特点相同的树上，节省存 储空间，同时，遍历方法出按层遍历外还可以通过前序遍历、中序遍历和 后续遍历等常用遍历方法，此外，除压缩外，本方法还可用于其他需存储 哈夫曼树的领域。

本领域普通技术人员可以理解，实现上述实施例方法中的全部或部分 步骤是可以通过程序来指令相关的硬件来完成，所述的程序可以存储于计 算机可读取存储介质中，该程序在执行时，包括上述实施例方法的各步骤， 而所述的存储介质可以是：ROM/RAM、磁碟、光盘、存储卡等。因此，本 领域相关技术人员应能理解，与本发明的方法相对应的，本发明还同时包 括一种跨平台接口自动化测试系统，参见图2，与上述方法步骤一一对应 地，该装置包括：

遍历单元，用于根据树结构按层遍历每个节点，得到节点的总数N；

第一判断单元，用于判断节点总数N，若N≤2，则不记录树结构，若 N＞2，则将遍历结构传递到第二判断单元；

第二判断单元，用于判断每个节点是否有子树；

记录单元，用1位，或根据冗余需要，增加到2-N位，记录所述第二 判断单元的判断结果；

存储单元，用于存储记录单元的记录和遍历单元的总数N。

本实施例中，本系统通过遍历单元按层遍历哈夫曼树的每个节点，通 过第一、第二判断单元用来判断哈夫曼树的结构，得到记录，并进行存储， 使得哈夫曼树能够高效快速进行存储，同时，占用存储空间小，存储长度 稳定性高。

进一步地，根据第二判断单元的判断，若节点有子树，则记录为1， 若节点没有子树，则记录为0。

进一步地，记录单元还包括优化单元，用来优化记录，除去记录中代 表树结构根节点的第一个记录、代表最后两个叶节点的最后两个记录以及 根据之前节点可以推导出的倒数第三个节点的记录。

本实施例中，第二判断单元判断每个节点的子树情况，记录单元进行 记录，存储哈夫曼树的树结构，记录单元可以通过优化单元对记录存储进 行优化，优化后，存储空间由之前的2N-1位缩小到2N-5位，极大的节省 了存储空间，达到了稳定高效压缩的目的。

进一步地，遍历单元还可以通过前序遍历、中序遍历和后序遍历等遍 历方法对树结构进行遍历。

进一步地，系统还可以保存与哈夫曼树树结构相似的结构。

本实施例中，系统可以对与哈夫曼树结构相似的数进行存储，也可通 过不同的遍历方法对其进行遍历，并按照遍历顺序记录和存储，每个节点 可以用1位进行存储，即使每个节点需2位存储，也可以节省存储空间， 此外，本系统除用于压缩数据外，也可以做其它用途。

与现有技术相比，本发明提供了一种一种哈夫曼树保存方法和系统， 通过遍历树的每个节点，根据每个节点是否有子树，对树结构进行记录， 若有子树，记为1，若无子树，记为0，用2N-1位(N为节点总数)记录 整个树结构，进一步，可以对记录进行优化，将根节点、最后两个叶节点 以及可通过之前节点推导出的倒数第三个节点除去，仅用2N-5位记录， 极大的减少了存储空间的浪费和冗余，用最小的空间存储整个树结构，且 达到稳定高效压缩的目的，同时，能够对其余特征相同的树进行同样的处 理，并应用到多个领域。

值得注意的是，以上所述仅为本发明的较佳实施例，并非因此限定 本发明的专利保护范围，本发明还可以对上述各种零部件的构造进行材 料和结构的改进，或者是采用技术等同物进行替换。故凡运用本发明的 说明书及图示内容所作的等效结构变化，或直接或间接运用于其他相关 技术领域均同理皆包含于本发明所涵盖的范围内。