保存范式哈夫曼树的方法及装置

技术领域

本发明涉及编码存储技术，尤其涉及保存范式哈夫曼树的方法及装置。

背景技术

在进行数据压缩时常用到范式哈夫曼树，如：GZIB、ZLIB、PNG、JPEG、MPEG。 实际压缩中，除了保存压缩编码，还需要保存范式哈夫曼树及原始数据总量等，这样 才能够解压缩。本发明方案针对的是如何保存范式哈夫曼树。

首先介绍范式哈夫曼编码的原理，范式哈夫曼编码过程大概分为4步：

1)对压缩单元进行计数或概率统计，并按照从大到小进行排序，假定对字节数据 统计结果如下述表1所示：

表1对压缩单元进行计数或概率统计后的排序

其中，符号用于对压缩单元进行标识，计数表示相应压缩单元的个数，概率表示 相应压缩单元占总压缩单元的比例。

2)按照统计结果创建范式哈夫曼树，具体地：总是找到两个出现概率或次数最少 的合并二叉树，直到合并到一个根节点为止。假定按照上述结果分a,b,..e共5步(e 为结果)，创建流程如图1所示。

3)按照左节点编码为0，右节点为1对数据单元进行编码，产生范式哈夫曼编码表， 如表2所示。

表2范式哈夫曼编码表

4)按照编码进行数据替换即压缩，也就是原来需要8位存储的数据A,B,..E，最后 可以用1,3,3,3,3位数据代替，顺序存储，最终实现了压缩的目的。若要解压缩还需要记 录编码表，也即{A,0}，{B,100}，{C,101}，{D,110}，{E,111}。由于主要讨论如何存 储编码表，编码压缩的详细过程及解码过程就不再详细介绍了。

目前存储范式哈夫曼编码表多采用如下方案：

1)记录码长方式：

表3记录哈夫曼编码的码长表格

如上表所示，码表需要保存的是1,3,3,3,3，因为范式哈夫曼树的特点，由这几个数 字就可以还原出原来的树。用码长代替编码的好处是存储位数的宽度是比较有限的， 就拿全部的单字节码表来看，最长也不会超过255位，也就是最长为1个字节。

2)记录码长基础上对码表进行二次压缩的方式：

将上述码表的数据1,3,3,3,3再次进行压缩，如使用RLE压缩，则压缩后变为：1,0,3,3 (代表0+1＝1个1和3+1＝4个3)，也有别的方式的压缩的，当有大量重复数据时，例如 长度全为8时，可能记录的就是8,255。

现有保存范式哈夫曼树的方案存在以下缺陷：

不压缩情况下：最大码长较长时每个码长保存位数需要加大，极端情况下字符(8bit) 压缩，码表长度将达到256字节。

压缩情况下：多数压缩算法，面对重复字节压缩率都会提高，但面对几乎每个码 长都很少时(也即重复性较少时)就较难以发挥作用了。

综上，现有保存范式哈夫曼树的方案都存在码表过大的问题，极端情况下达到甚 至超过直接存码表。

发明内容

本发明提供了一种保存范式哈夫曼树的方法，该方法能够采用尽量少的数据来保 存范式哈夫曼树，提高存储效率。

本发明提供了一种保存范式哈夫曼树的装置，该装置能够采用尽量少的数据来保 存范式哈夫曼树，提高存储效率。

本发明提供了另一种保存范式哈夫曼树的方法，该方法能够采用尽量少的数据来 保存范式哈夫曼树，提高存储效率。

本发明提供了另一种保存范式哈夫曼树的装置，该装置能够采用尽量少的数据来 保存范式哈夫曼树，提高存储效率。

一种保存范式哈夫曼树的方法，该方法包括：

对范式哈夫曼树的节点进行标记，用M标记节点有子树，用N标记节点无子树；

由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地：采用从左至右 的顺序，从第一个节点开始记录，只记录到第一个不为N的节点；

将记录的节点标记作为最终记录结果，保存最终记录结果。

一种保存范式哈夫曼树的装置，该装置包括节点标记记录模块和保存模块；

所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用M标记节点有子树， 用N标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体 地：采用从左至右的顺序，从第一个节点开始记录，只记录到第一个不为N的节点； 将记录的节点标记发送给所述保存模块；

所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。

一种保存范式哈夫曼树的方法，该方法包括：

对范式哈夫曼树的节点进行标记，用M标记节点有子树，用N标记节点无子树；

由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地：采用从右至左 的顺序，从第一个节点开始记录，只记录到第一个不为M的节点；

将记录的节点标记作为最终记录结果，保存最终记录结果。

一种保存范式哈夫曼树的装置，该装置包括节点标记记录模块和保存模块；

所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用M标记节点有子树， 用N标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体 地：采用从右至左的顺序，从第一个节点开始记录，只记录到第一个不为M的节点； 将记录的节点标记发送给所述保存模块；

所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。

从上述方案可以看出，本发明中，对范式哈夫曼树的节点进行标记，再对每层节 点的标记进行记录，而后，将记录的节点标记作为最终记录结果，保存最终记录结果。 本发明采用从左至右或从右至左的顺序对每层节点的标记进行记录，从第一个节点开 始记录，记录到第一个不为N或不为M的节点。具体地，采用从左至右对每层节点 的标记进行记录时，从第一个节点开始记录，只记录到第一个不为N的节点，后续节 点不再进行记录；类似地，采用从右至左对每层节点的标记进行记录时，从第一个节 点开始记录，只记录到第一个不为M的节点，后续节点不再记录；另外，在此基础上 不对每层最右侧节点和最后一层的所有节点进行记录。本申请一改惯有的记录码长方 式和二次压缩方式，提供了更加简便的记录方式，也减少了存储数据，从而提高了存 储效率。

附图说明

图1为现有范式哈夫曼树的创建流程图；

图2为本发明保存范式哈夫曼树的方法示意性流程图；

图3为本发明对范式哈夫曼树各层进行记录的示意图实例；

图4为本发明保存范式哈夫曼树的装置结构示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施例和附图， 对本发明进一步详细说明。

参见图2，为本发明保存范式哈夫曼树的方法示意性流程图，其包括以下步骤：

步骤201，对范式哈夫曼树的节点进行标记，用M标记节点有子树，用N标记节 点无子树；对范式哈夫曼树每层节点的标记依次进行记录，具体地：采用从左至右的 顺序，从第一个节点开始记录，只记录到第一个不为N的节点。

其中，M和N可根据需要选取，可以是1位，也可以是2位或更多位。这里以1 位为例，M取值为1，N取值为0。需要保存的范式哈夫曼树仍以图1所示的实例进 行说明，对各节点进行标记后为图3所示：第一层：1，第二层：01，第三层11，第 四层：0000。

为了减少存储数据，本申请中，对每层节点的标记进行记录时，从第一个节点开 始记录，只记录到第一个不为N的节点，后续不再记录。

针对图3的实例，对各层进行记录：

第一层：1；

第二层：01；

第三层：1(因每层只记录到第一个不为0的节点)；

第四层：0000；

最终记录结果：10110000。

步骤202，将记录的节点标记作为最终记录结果，保存最终记录结果。

可选地，还可以对范式哈夫曼树中的叶节点数目进行统计，得到叶节点总数，将 叶节点总数添加到最终记录结果中。

图3的实例中，叶节点总数为5。本发明采用从左至右或从右至左的顺序对每层 节点的标记进行记录，从第一个节点开始记录，记录到第一个不为N或不为M的节 点。具体地，采用从左至右对每层节点的标记进行记录时，从第一个节点开始记录， 只记录到第一个不为N的节点，后续节点不再进行记录；类似地，采用从右至左对每 层节点的标记进行记录时，从第一个节点开始记录，只记录到第一个不为M的节点， 后续节点不再记录。本申请一改惯有的记录码长方式和二次压缩方式，提供了更加简 便的记录方式，也减少了存储数据，从而提高了存储效率。

保存最终记录结果后，需要时，可对其进行解码，以获知范式哈夫曼树的结 构。解码具体过程包括：

从上至下对各层依次进行解码：

统计当前层的上一层中标记为M的节点数，将统计出的节点数乘以2，将得到的 乘积值作为当前层的节点数P；若当前层为第一层时，P为1；

从最终记录结果中依次读取标记位，直至遇到标记为M或读取的标记位数目达到 P个时停止，为读取的标记填充后续标记M，直到标记位总数达到P位，将填充后的 标记作为当前层的标记结果。下面结合图3的实例进行说明，其解码过程(5个叶节 点，记录为10110000)为：

对各层采用前述流程进行解码，具体地：

第一层：1；解码：1。

此时，P为1；从最终记录结果中依次读取标记位，直至遇到标记为M或读取的 标记位数目达到P个时停止，为读取的标记填充后续标记M，直到标记位总数达到P 位，将填充后的标记作为当前层的标记结果，则得到的第一层的标记结果为1。

第二层：01，解码：01；

此时，P为2；从最终记录结果中依次读取标记位，直至遇到标记为M或读取的 标记位数目达到P个时停止，为读取的标记填充后续标记M，直到标记位总数达到P 位，将填充后的标记作为当前层的标记结果，则得到的第二层的标记结果为01。

第三层：1，解码：11；

此时，P为2；从最终记录结果中依次读取标记位(前面已经读到10110000中的 第3位，这里从第四位开始读取)，直至遇到标记为M或读取的标记位数目达到P个 时停止(这里，读取一位，即1)，为读取的标记填充后续标记M，直到标记位总数达 到P位，将填充后的标记作为当前层的标记结果，则得到的第三层的标记结果为11。

第四层：0000，解码为：0000。

此时，P为4；从最终记录结果中依次读取标记位(前面已经读到10110000中的 第4位，这里从第5位开始读取)，直至遇到标记为M或读取的标记位数目达到P个 时停止(这里，读取4位，即0000)，则得到的第四层的标记结果为0000。

解码结束。

此时，P＝0；解码结束。

为了采用尽量少的数据来保存范式哈夫曼树，在编码保存时，因最后一层各节点 都标记为0，可以不对最后一层进行记录。进一步地，在编码保存时，还可以不对每 层的最后一个节点进行记录。

对应地，解码将相应进行调整。举例说明，如果编码保存时，采用从左至右的顺 序，从第一个节点开始记录，只记录到第一个不为N的节点，并且，不对最后一层进 行记录，也不对每层的最后一个节点进行记录；解码具体为：

将第一层节点的标记设置为M；

从上至下对后续各层依次进行解码：

统计当前层的上一层中标记为M的节点数，将统计出的节点数乘以2，将得到的 乘积值作为当前层的节点数P；

从最终记录结果中读取叶节点总数，统计出当前层之前所有层标记为N的叶节点 数，计算出剩余叶节点数Q；

判断P是否等于Q，如果是，则当前层为最后一层，P个节点全部为叶节点，标 记为N；否则，从最终记录结果中依次读取标记位，直至遇到标记为M或读取的标记 位数目达到P-1个时停止，为读取的标记填充后续标记M，直到标记位数达到P位， 将填充后的标记作为当前层的标记结果。

下面针对图3的实例进行详细说明。对各层进行记录：

第一层：不记录(因每层的最后一个节点不记录)；

第二层：0(因每层的最后一个节点不记录)；

第三层：1(因每层的最后一个节点不记录且仅记录到第一个不为0的节点)；

第四层：不记录(因为最后一层不记录)；

最终记录结果：01。

这样，一共用2位便可存储上面例子中的范式哈弗曼树的结构，其效率显而易见， 比现有记录码长方式及进行二次压缩方式的效率提高很多。

图3的实例中，叶节点总数为5。

下面结合图3的实例进行说明，其解码过程(5个叶节点，记录为01)为：

第一层：不记录，解码：1(因每层的最后一个节点不记录，一定为1)。

对第二层以后的各层采用如下方式进行解码：当前层节点数(P)＝上一层为1的节 点数*2；当剩余叶节点数＝Q时，当前层全部节点全部为叶节点，也即全部为0；按位 读取压缩位，直至遇到压缩位为1(假定第T位，读取至第T位)或个数达到P-1个 停止；当读取的压缩位为0时，叶节点计数+1；从T+1至P位全部填充为1。

本实例中，后续各层解码后依次为：

第二层：0，解码：01(共2个节点，最后一个不记录)；

第三层：1，解码：11(共2个节点，不记录最后一个节点，记录到第一个不为0 的节点)；

第四层：不记录，解码为：0000(共4个叶节点，前面已出现1个叶节点，还剩 4个叶节点，因此确定本层为最后一层)。本发明中，为了采用尽量少的数据来保存范 式哈夫曼树，首先对范式哈夫曼树的特点进行深刻了解及分析：

每个节点要么只有两个分支，要么是叶节点，这样的二叉树也被称为正则二叉树；

所有非叶节点都靠一边(一般为右侧)，一层中从某个节点开始的右侧都有子节点 直至本层结束；

当范式哈夫曼树叶节点个数>＝2时，从上往下看，根节点总是有两个节点，最后 一层节点也一定是叶节点。基于以上的分析，本发明给出了下述存储解范式哈夫曼树 的方案：

存储叶节点的总数、树结构及树叶节点的值即可；

树结构按层序遍历每个节点用1位表示有无子树(1:有，0:无)；

每层的最后一个节点(包含根节点)不记录(因为除最后一层外，该节点一定有 子树)；

每层仅记录到第一个不为0的节点(因为后全为1)；

最后一层不记录(因为最后一层一定是上一层有子树节点数的2倍且全为0)。

本发明根据范式哈夫曼树(也称正则二叉树)的特点，按位存储一部分节点是否 有子树的方式，达到相对稳定且高效的压缩目的，最极端的情况下能够将全部256字 符(8bit)构成的范式哈夫曼树保存至到log2(N)-1至N-2位中。

因为按照范式哈夫曼编码压缩原始数据后的数据总位数都相同，因此只需考虑记 录范式哈夫曼树的不同。即便不考虑记录总叶节点数、叶节点代码最大位数、总字节 数等额外数据，针对上面的例子进行存储，粗略计算：

直接记录编码表方法：5x3＝15位；

传统方式存储范式哈夫曼编码长度的码表：5x2＝10位；

传统方式存储范式哈夫曼编码长度的码表后进行二次压缩：4x2＝8位或其它未知 情况；

本发明的按位精简存储的方法：2位。

极端的例子一：除根节点和最后一层外每层都有2个子节点，叶节点总数为256。

直接记录编码表方法：255*256＝65280位；

传统方式存储范式哈夫曼编码长度的码表：8*256＝2048位；

传统方式存储范式哈夫曼编码长度的码表后进行二次压缩：8*256+256*2或其它

本发明的按位精简存储的方法：254位。

极端的例子二：叶节点总数为256的满二叉树。

直接记录编码表方法：8*256＝2048位；

传统方式存储范式哈夫曼编码长度的码表：8*256＝2048位；

传统方式存储范式哈夫曼编码长度的码表后进行二次压缩：8*2或其它

本发明的按位精简存储的方法：7位。

从上面数据可以看出：无论是极端情况还是普通情况下，本发明的存储方法都有 极高的效率。

本发明技术方案可以用固定的1位存储树结构中一个节点的是否有子树，即 便增加冗余到2位甚至更多位也可能比其它方式有优势；还可以采用不同的搜索 顺序，或用可区分的不同值表示有无子树。并且，对于范式哈夫曼树同时包含左 子树和右子树的情况，还可以左右子树分开按位保存，也就是，从上到下将范式 哈夫曼树划分为左子树和右子树，然后分别进行保存。范式哈夫曼树的变体(例 如：全部靠左)也可以按照此方法保存。本技术方案除了应用于压缩数据外，也 可以做其它用途。可以按照链表的逻辑，只是左右节点按位存储有无节点来替代 本发明方案。

前述是采用从左至右的顺序对各层节点进行记录，也可以，采用从右至左顺序对 各层节点进行记录，不同的是，从左至右记录每层节点时是记录到第一个不为N的节 点，而从右至左记录每层节点时时记录到第一个不为M的节点；两种顺序的编码保存 方式以及解码方式都类似，这里不再重复赘述，下面只做简要说明。

对于从右至左的方式：

编码保存具体包括：

对范式哈夫曼树的节点进行标记，用M标记节点有子树，用N标记节点无子树；

由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地：采用从右至左 的顺序，从第一个节点开始记录，只记录到第一个不为M的节点；

将记录的节点标记作为最终记录结果，保存最终记录结果。

相应地，解码过程包括：

从上至下对各层依次进行解码：

统计当前层的上一层中标记为M的节点数，将统计出的节点数乘以2，将得到的 乘积值作为当前层的节点数P；若当前层为第一层时，P为1；

从最终记录结果中依次读取标记位，直至遇到标记为N或读取的标记位数目达到 P个时停止，为读取的标记填充后续标记N，直到标记总位数达到P位，将填充后的 标记作为当前层的标记结果。

当然地，为了采用尽量少的数据来保存范式哈夫曼树，在编码保存时，类似地， 也可以不对最后一层进行记录，还可以进一步不对每层最右侧的一个节点进行记录。

参见图4，为本发明保存范式哈夫曼树的装置结构示意图，该装置包括节点标记 记录模块和保存模块；

所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用M标记节点有子树， 用N标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体 地：采用从左至右的顺序，从第一个节点开始记录，只记录到第一个不为N的节点； 将记录的节点标记发送给所述保存模块；

所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。

进一步地，该装置还包括叶节点总数统计模块，对范式哈夫曼树中的叶节点数目 进行统计，得到叶节点总数，发送给所述保存模块；

所述保存模块，将叶节点总数添加到最终记录结果中，进行保存。

较佳地，该装置还包括第一解码模块，对范式哈夫曼树的解码，具体地：从上至 下对各层依次进行解码：统计当前层的上一层中标记为M的节点数，将统计出的节点 数乘以2，将得到的乘积值作为当前层的节点数P；若当前层为第一层时，P为1；从 最终记录结果中依次读取标记位，直至遇到标记为M或读取的标记位数目达到P个时 停止，为读取的标记填充后续标记M，直到标记位总数达到P位，将填充后的标记作 为当前层的标记结果。

进一步地，本申请还提供了另一种保存范式哈夫曼树的装置，该装置包括节点标 记记录模块和保存模块；

所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用M标记节点有子树， 用N标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体 地：采用从右至左的顺序，从第一个节点开始记录，只记录到第一个不为M的节点； 将记录的节点标记发送给所述保存模块；

所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。

进一步地，该装置还包括叶节点总数统计模块，对范式哈夫曼树中的叶节点数目 进行统计，得到叶节点总数，发送给所述保存模块；

所述保存模块，将叶节点总数添加到最终记录结果中，进行保存。

较佳地，该装置还包括第二解码模块，对范式哈夫曼树的解码，具体地：从上至 下对各层依次进行解码：

统计当前层的上一层中标记为M的节点数，将统计出的节点数乘以2，将得到的 乘积值作为当前层的节点数P；若当前层为第一层时，P为1；

从最终记录结果中依次读取标记位，直至遇到标记为N或读取的标记位数目达到 P个时停止，为读取的标记填充后续标记N，直到标记总位数达到P位，将填充后的 标记作为当前层的标记结果。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精 神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明保护的范围 之内。