保存范式哈夫曼树的方法及装置的制造方法
保存范式哈夫曼树的方法及装置的制造方法
【技术领域】
[0001] 本发明设及编码存储技术，尤其设及保存范式哈夫曼树的方法及装置。
【背景技术】
[0002] 在进行数据压缩时常用到范式哈夫曼树，如:GZIB、化IB、PNG、JPEG、MPEG。实际压 缩中，除了保存压缩编码，还需要保存范式哈夫曼树及原始数据总量等，运样才能够解压 缩。本发明方案针对的是如何保存范式哈夫曼树。
[0003] 首先介绍范式哈夫曼编码的原理，范式哈夫曼编码过程大概分为4步：
[0004] 1)对压缩单元进行计数或概率统计，并按照从大到小进行排序，假定对字节数据 统计结果如下述表1所示：
[0005]
[0006] 表1对压缩单元进行计数或概率统计后的排序
[0007] 其中，符号用于对压缩单元进行标识，计数表示相应压缩单元的个数，概率表示相 应压缩单元占总压缩单元的比例。
[0008] 2)按照统计结果创建范式哈夫曼树，具体地:总是找到两个出现概率或次数最少 的合并二叉树，直到合并到一个根节点为止。假定按照上述结果分a，b，. .e共5步（e为结 果），创建流程如图1所示。
[0009] 3)按照左节点编码为0,右节点为1对数据单元进行编码，产生范式哈夫曼编码表， 如表2所示。
[0010] _
[0011] 表2范式哈夫曼编码表
[0012] 4)按照编码进行数据替换即压缩，也就是原来需要8位存储的数据A，B，. .E，最后 可W用1，3,3,3,3位数据代替，顺序存储，最终实现了压缩的目的。若要解压缩还需要记录 编码表，也即{A，0}，{B，100}，{C，101}，{D，110}，巧，111}。由于主要讨论如何存储编码表， 编码压缩的详细过程及解码过程就不再详细介绍了。
[0013] 目前存储范式哈夫曼编码表多采用如下方案：
[0014] 1)记录码长方式：
[0015]
[0016] 表3记录哈夫曼编码的码长表格
[0017] 如上表所示，码表需要保存的是1，3,3,3,3,因为范式哈夫曼树的特点，由运几个 数字就可W还原出原来的树。用码长代替编码的好处是存储位数的宽度是比较有限的，就 拿全部的单字节码表来看，最长也不会超过255位，也就是最长为1个字节。
[0018] 2)记录码长基础上对码表进行二次压缩的方式：
[0019] 将上述码表的数据1，3，3，3，3再次进行压缩，如使用化E压缩，则压缩后变为：1，0， 3，3(代表0+1 = 1个1和3+1 = 4个3)，也有别的方式的压缩的，当有大量重复数据时，例如长 度全为別寸，可能记录的就是8，255。
[0020] 现有保存范式哈夫曼树的方案存在W下缺陷：
[0021] 不压缩情况下：最大码长较长时每个码长保存位数需要加大，极端情况下字符 (8bit)压缩，码表长度将达到256字节。
[0022] 压缩情况下：多数压缩算法，面对重复字节压缩率都会提高，但面对几乎每个码长 都很少时(也即重复性较少时)就较难W发挥作用了。
[0023] 综上，现有保存范式哈夫曼树的方案都存在码表过大的问题，极端情况下达到甚 至超过直接存码表。
【发明内容】
[0024] 本发明提供了一种保存范式哈夫曼树的方法，该方法能够采用尽量少的数据来保 存范式哈夫曼树，提高存储效率。
[0025] 本发明提供了一种保存范式哈夫曼树的装置，该装置能够采用尽量少的数据来保 存范式哈夫曼树，提高存储效率。
[0026] 本发明提供了另一种保存范式哈夫曼树的方法，该方法能够采用尽量少的数据来 保存范式哈夫曼树，提高存储效率。
[0027] 本发明提供了另一种保存范式哈夫曼树的装置，该装置能够采用尽量少的数据来 保存范式哈夫曼树，提高存储效率。
[0028] -种保存范式哈夫曼树的方法，该方法包括：
[0029] 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用饰示记节点无子树；
[0030] 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从左至右 的顺序，从第一个节点开始记录，只记录到第一个不为Ν的节点；
[0031] 将记录的节点标记作为最终记录结果，保存最终记录结果。
[0032] -种保存范式哈夫曼树的装置，该装置包括节点标记记录模块和保存模块；
[0033] 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树， 用Ν标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采 用从左至右的顺序，从第一个节点开始记录，只记录到第一个不为Ν的节点；将记录的节点 标记发送给所述保存模块；
[0034] 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。
[0035] -种保存范式哈夫曼树的方法，该方法包括：
[0036] 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用饰示记节点无子树；
[0037] 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从右至左 的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；
[003引将记录的节点标记作为最终记录结果，保存最终记录结果。
[0039] -种保存范式哈夫曼树的装置，该装置包括节点标记记录模块和保存模块；
[0040] 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树， 用Ν标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采 用从右至左的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；将记录的节点 标记发送给所述保存模块；
[0041] 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。
[0042] 从上述方案可W看出，本发明中，对范式哈夫曼树的节点进行标记，再对每层节点 的标记进行记录，而后，将记录的节点标记作为最终记录结果，保存最终记录结果。本发明 采用从左至右或从右至左的顺序对每层节点的标记进行记录，从第一个节点开始记录，记 录到第一个不为Ν或不为Μ的节点。具体地，采用从左至右对每层节点的标记进行记录时，从 第一个节点开始记录，只记录到第一个不为Ν的节点，后续节点不再进行记录;类似地，采用 从右至左对每层节点的标记进行记录时，从第一个节点开始记录，只记录到第一个不为Μ的 节点，后续节点不再记录;另外，在此基础上不对每层最右侧节点和最后一层的所有节点进 行记录。本申请一改惯有的记录码长方式和二次压缩方式，提供了更加简便的记录方式，也 减少了存储数据，从而提高了存储效率。
【附图说明】
[0043] 图1为现有范式哈夫曼树的创建流程图；
[0044] 图2为本发明保存范式哈夫曼树的方法示意性流程图；
[0045] 图3为本发明对范式哈夫曼树各层进行记录的示意图实例；
[0046] 图4为本发明保存范式哈夫曼树的装置结构示意图。
【具体实施方式】
[0047] 为使本发明的目的、技术方案和优点更 加清楚明白，下面结合实施例和附图，对本 发明进一步详细说明。
[0048] 参见图2,为本发明保存范式哈夫曼树的方法示意性流程图，其包括W下步骤：
[0049] 步骤201，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用Ν标记节点无 子树;对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从左至右的顺序，从第 一个节点开始记录，只记录到第一个不为Ν的节点。
[0050] 其中，Μ和Ν可根据需要选取，可W是1位，也可W是2位或更多位。运里位为例，Μ 取值为1，Ν取值为0。需要保存的范式哈夫曼树仍W图1所示的实例进行说明，对各节点进行 标记后为图3所示:第一层:1，第二层:01，第Ξ层11，第四层:0000。
[0051] 为了减少存储数据，本申请中，对每层节点的标记进行记录时，从第一个节点开始 记录，只记录到第一个不为Ν的节点，后续不再记录。
[0052] 针对图3的实例，对各层进行记录：
[005；3]第一层山
[0054] 第二层：01;
[0055] 第Ξ层:1(因每层只记录到第一个不为0的节点）；
[0化6] 第四层:〇〇〇〇;
[0057] 最终记录结果：10110000。
[005引步骤202,将记录的节点标记作为最终记录结果，保存最终记录结果。
[0059] 可选地，还可W对范式哈夫曼树中的叶节点数目进行统计，得到叶节点总数，将叶 节点总数添加到最终记录结果中。
[0060] 图3的实例中，叶节点总数为5。本发明采用从左至右或从右至左的顺序对每层节 点的标记进行记录，从第一个节点开始记录，记录到第一个不为N或不为Μ的节点。具体地， 采用从左至右对每层节点的标记进行记录时，从第一个节点开始记录，只记录到第一个不 为Ν的节点，后续节点不再进行记录;类似地，采用从右至左对每层节点的标记进行记录时， 从第一个节点开始记录，只记录到第一个不为Μ的节点，后续节点不再记录。本申请一改惯 有的记录码长方式和二次压缩方式，提供了更加简便的记录方式，也减少了存储数据，从而 提高了存储效率。
[0061] 保存最终记录结果后，需要时，可对其进行解码，W获知范式哈夫曼树的结构。解 码具体过程包括：
[0062] 从上至下对各层依次进行解码：
[0063] 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2,将得到的乘 积值作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;
[0064] 从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ 个时停止，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后的标记作为当 前层的标记结果。下面结合图3的实例进行说明，其解码过程巧个叶节点，记录为10110000) 为：
[0065] 对各层采用前述流程进行解码，具体地：
[0066] 第一层:1;解码:1。
[0067] 此时，Ρ为1;从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记 位数目达到Ρ个时停止，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后 的标记作为当前层的标记结果，则得到的第一层的标记结果为1。
[006引第二层:01，解码:01;
[0069] 此时，Ρ为2;从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记 位数目达到Ρ个时停止，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后 的标记作为当前层的标记结果，则得到的第二层的标记结果为01。
[0070] 第；层：1，解码：11;
[0071] 此时，Ρ为2;从最终记录结果中依次读取标记位(前面已经读到10110000中的第3 位，运里从第四位开始读取），直至遇到标记为Μ或读取的标记位数目达到Ρ个时停止(运里， 读取一位，即1 )，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后的标记 作为当前层的标记结果，则得到的第Ξ层的标记结果为11。
[0072] 第四层:0000,解码为:0000。
[0073] 此时，Ρ为4;从最终记录结果中依次读取标记位(前面已经读到10110000中的第4 位，运里从第5位开始读取），直至遇到标记为Μ或读取的标记位数目达到Ρ个时停止(运里， 读取4位，即0000)，则得到的第四层的标记结果为0000。
[0074] 解码结束。
[0075] 此时，P = 0;解码结束。
[0076] 为了采用尽量少的数据来保存范式哈夫曼树，在编码保存时，因最后一层各节点 都标记为0,可W不对最后一层进行记录。进一步地，在编码保存时，还可W不对每层的最后 一个节点进行记录。
[0077] 对应地，解码将相应进行调整。举例说明，如果编码保存时，采用从左至右的顺序， 从第一个节点开始记录，只记录到第一个不为N的节点，并且，不对最后一层进行记录，也不 对每层的最后一个节点进行记录;解码具体为：
[0078] 将第一层节点的标记设置为M;
[0079] 从上至下对后续各层依次进行解码：
[0080] 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2,将得到的乘 积值作为当前层的节点数Ρ;
[0081] 从最终记录结果中读取叶节点总数，统计出当前层之前所有层标记为Ν的叶节点 数，计算出剩余叶节点数Q;
[0082] 判断Ρ是否等于Q，如果是，则当前层为最后一层，Ρ个节点全部为叶节点，标记为Ν; 否则，从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ-1 个时停止，为读取的标记填充后续标记Μ，直到标记位数达到Ρ位，将填充后的标记作为当前 层的标记结果。
[0083] 下面针对图3的实例进行详细说明。对各层进行记录：
[0084] 第一层:不记录(因每层的最后一个节点不记录）；
[0085] 第二层:0(因每层的最后一个节点不记录）；
[0086] 第Ξ层：1(因每层的最后一个节点不记录且仅记录到第一个不为0的节点）；
[0087] 第四层:不记录(因为最后一层不记录）；
[0088] 最终记录结果:01。
[0089] 运样，一共用2位便可存储上面例子中的范式哈弗曼树的结构，其效率显而易见， 比现有记录码长方式及进行二次压缩方式的效率提高很多。
[0090] 图3的实例中，叶节点总数为5。
[0091] 下面结合图3的实例进行说明，其解码过程(5个叶节点，记录为01)为：
[0092] 第一层:不记录，解码：1(因每层的最后一个节点不记录，一定为1)。
[0093] 对第二层W后的各层采用如下方式进行解码：当前层节点数(Ρ)=上一层为1的节 点数*2;当剩余叶节点数=Q时，当前层全部节点全部为叶节点，也即全部为0;按位读取压 缩位，直至遇到压缩位为1(假定第T位，读取至第T位)或个数达到P-1个停止;当读取的压缩 位为加寸，叶节点计数+1;从T+1至P位全部填充为1。
[0094] 本实例中，后续各层解码后依次为：
[00M]第二层:0，解码:01 (共2个节点，最 后一个不记录）；
[0096] 第Ξ层：1，解码：11(共2个节点，不记录最后一个节点，记录到第一个不为0的节 点）；
[0097] 第四层:不记录，解码为:0000(共4个叶节点，前面已出现1个叶节点，还剩4个叶节 点，因此确定本层为最后一层）。本发明中，为了采用尽量少的数据来保存范式哈夫曼树，首 先对范式哈夫曼树的特点进行深刻了解及分析：
[0098] 每个节点要么只有两个分支，要么是叶节点，运样的二叉树也被称为正则二叉树；
[0099] 所有非叶节点都靠一边(一般为右侧），一层中从某个节点开始的右侧都有子节点 直至本层结束；
[0100] 当范式哈夫曼树叶节点个数〉=2时，从上往下看，根节点总是有两个节点，最后一 层节点也一定是叶节点。基于W上的分析，本发明给出了下述存储解范式哈夫曼树的方案：
[0101] 存储叶节点的总数、树结构及树叶节点的值即可；
[0102] 树结构按层序遍历每个节点用1位表示有无子树(1:有，0:无）；
[0103] 每层的最后一个节点（包含根节点）不记录（因为除最后一层外，该节点一定有子 树)；
[0104] 每层仅记录到第一个不为0的节点（因为后全为1);
[0105] 最后一层不记录(因为最后一层一定是上一层有子树节点数的2倍且全为0)。
[0106] 本发明根据范式哈夫曼树(也称正则二叉树)的特点，按位存储一部分节点是否有 子树的方式，达到相对稳定且高效的压缩目的，最极端的情况下能够将全部256字符(8bit) 构成的范式哈夫曼树保存至到l〇g2(N)-l至N-2位中。
[0107] 因为按照范式哈夫曼编码压缩原始数据后的数据总位数都相同，因此只需考虑记 录范式哈夫曼树的不同。即便不考虑记录总叶节点数、叶节点代码最大位数、总字节数等额 外数据，针对上面的例子进行存储，粗略计算：
[0108] 直接记录编码表方法:5x3 = 15位；
[0109] 传统方式存储范式哈夫曼编码长度的码表:5x2 = 10位；
[0110] 传统方式存储范式哈夫曼编码长度的码表后进行二次压缩:4x2 = 8位或其它未知 情况；
[0111] 本发明的按位精简存储的方法:2位。
[0112] 极端的例子一:除根节点和最后一层外每层都有2个子节点，叶节点总数为256。
[0113] 直接记录编码表方法:255巧56 = 65280位；
[0114] 传统方式存储范式哈夫曼编码长度的码表:8巧56 = 2048位；
[0115] 传统方式存储范式哈夫曼编码长度的码表后进行二次压缩:糾256+256巧或其它
[0116] 本发明的按位精简存储的方法:254位。
[0117] 极端的例子二:叶节点总数为256的满二叉树。
[0118] 直接记录编码表方法:8巧56 = 2048位；
[0119] 传统方式存储范式哈夫曼编码长度的码表:8巧56 = 2048位；
[0120] 传统方式存储范式哈夫曼编码长度的码表后进行二次压缩:糾2或其它 [0121 ]本发明的按位精简存储的方法:7位。
[0122] 从上面数据可W看出：无论是极端情况还是普通情况下，本发明的存储方法都有 极高的效率。
[0123] 本发明技术方案可W用固定的1位存储树结构中一个节点的是否有子树，即便增 加冗余到2位甚至更多位也可能比其它方式有优势;还可W采用不同的捜索顺序，或用可区 分的不同值表示有无子树。并且，对于范式哈夫曼树同时包含左子树和右子树的情况，还可 W左右子树分开按位保存，也就是，从上到下将范式哈夫曼树划分为左子树和右子树，然后 分别进行保存。范式哈夫曼树的变体(例如:全部靠左)也可w按照此方法保存。本技术方案 除了应用于压缩数据外，也可W做其它用途。可W按照链表的逻辑，只是左右节点按位存储 有无节点来替代本发明方案。
[0124]前述是采用从左至右的顺序对各层节点进行记录，也可W，采用从右至左顺序对 各层节点进行记录，不同的是，从左至右记录每层节点时是记录到第一个不为N的节点，而 从右至左记录每层节点时时记录到第一个不为Μ的节点；两种顺序的编码保存方式W及解 码方式都类似，运里不再重复寶述，下面只做简要说明。
[01巧]对于从右至左的方式：
[01%]编码保存具体包括：
[0127] 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用饰示记节点无子树；
[0128] 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从右至左 的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；
[0129] 将记录的节点标记作为最终记录结果，保存最终记录结果。
[0130] 相应地，解码过程包括：
[0131 ]从上至下对各层依次进行解码：
[0132] 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2,将得到的乘 积值作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;
[0133] 从最终记录结果中依次读取标记位，直至遇到标记为Ν或读取的标记位数目达到Ρ 个时停止，为读取的标记填充后续标记Ν，直到标记总位数达到Ρ位，将填充后的标记作为当 前层的标记结果。
[0134] 当然地，为了采用尽量少的数据来保存范式哈夫曼树，在编码保存时，类似地，也 可W不对最后一层进行记录，还可W进一步不对每层最右侧的一个节点进行记录。
[0135] 参见图4,为本发明保存范式哈夫曼树的装置结构示意图，该装置包括节点标记记 录模块和保存模块；
[0136] 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树， 用Ν标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采 用从左至右的顺序，从第一个节点开始记录，只记录到第一个不为Ν的节点；将记录的节点 标记发送给所述保存模块；
[0137] 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。
[0138] 进一步地，该装置还包括叶节点总数统计模块，对范式哈夫曼树中的叶节点数目 进行统计，得到叶节点总数，发送给所述保存模块；
[0139] 所述保存模块，将叶节点总数添加到最终记录结果中，进行保存。
[0140] 较佳地，该装置还包括第一解码模块，对范式哈夫曼树的解码，具体地:从上至下 对各层依次进行解码:统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2， 将得到的乘积值作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;从最终记录结果中依 次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ个时停止，为读取的标记填充 后续标记Μ，直到标记位总数达到Ρ位，将填充后的标记作为当前层的标记结果。
[0141] 进一步地，本申请还提供了另一种保存范式哈夫曼树的装置，该装置包括节点标 记记录模块和保存模块；
[0142] 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树， 用Ν标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采 用从右至左 的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；将记录的节点 标记发送给所述保存模块；
[0143] 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。
[0144] 进一步地，该装置还包括叶节点总数统计模块，对范式哈夫曼树中的叶节点数目 进行统计，得到叶节点总数，发送给所述保存模块；
[0145] 所述保存模块，将叶节点总数添加到最终记录结果中，进行保存。
[0146] 较佳地，该装置还包括第二解码模块，对范式哈夫曼树的解码，具体地:从上至下 对各层依次进行解码：
[0147] 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2,将得到的乘 积值作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;
[0148] 从最终记录结果中依次读取标记位，直至遇到标记为Ν或读取的标记位数目达到Ρ 个时停止，为读取的标记填充后续标记Ν，直到标记总位数达到Ρ位，将填充后的标记作为当 前层的标记结果。
[0149] W上所述仅为本发明的较佳实施例而已，并不用W限制本发明，凡在本发明的精 神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明保护的范围之内。
【主权项】
1. 一种保存范式哈夫曼树的方法，其特征在于，该方法包括： 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用N标记节点无子树； 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从左至右的顺 序，从第一个节点开始记录，只记录到第一个不为Ν的节点； 将记录的节点标记作为最终记录结果，保存最终记录结果。2. 如权利要求1所述的方法，其特征在于，该方法还包括对范式哈夫曼树的解码，具体 地： 从上至下对各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1; 从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ个时 停止，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后的标记作为当前层 的标记结果。3. 如权利要求1所述的方法，其特征在于，对范式哈夫曼树每层节点的标记依次进行记 录时，不对最后一层的节点进行记录;该方法还包括： 对范式哈夫曼树中的叶节点数目进行统计，得到叶节点总数，将叶节点总数添加到最 终记录结果中。4. 如权利要求1所述的方法，其特征在于，对范式哈夫曼树每层节点的标记依次进行记 录时，每层的最后一个节点不记录;该方法还包括： 对范式哈夫曼树中的叶节点数目进行统计，得到叶节点总数，将叶节点总数添加到最 终记录结果中。5. 如权利要求4所述的方法，其特征在于，对范式哈夫曼树每层节点的标记依次进行记 录时，不对最后一层的节点进行记录。6. 如权利要求5所述的方法，其特征在于，该方法还包括对范式哈夫曼树的解码，具体 地： 将第一层节点的标记设置为Μ; 从上至下对后续各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ; 从最终记录结果中读取叶节点总数，统计出当前层之前所有层标记为Ν的叶节点数，计 算出剩余叶节点数Q; 判断Ρ是否等于Q，如果是，则当前层为最后一层，Ρ个节点全部为叶节点，标记为Ν;否 贝1J，从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ-1个 时停止，为读取的标记填充后续标记Μ，直到标记位数达到Ρ位，将填充后的标记作为当前层 的标记结果。7. -种保存范式哈夫曼树的装置，其特征在于，该装置包括节点标记记录模块和保存 丰旲块； 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用Ν标 记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从左 至右的顺序，从第一个节点开始记录，只记录到第一个不为N的节点；将记录的节点标记发 送给所述保存模块； 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。8. 如权利要求7所述的装置，其特征在于，该装置还包括第一解码模块，对范式哈夫曼 树的解码，具体地:从上至下对各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;从最终记录结果中依次读取标记位，直 至遇到标记为Μ或读取的标记位数目达到Ρ个时停止，为读取的标记填充后续标记Μ，直到标 记位总数达到Ρ位，将填充后的标记作为当前层的标记结果。9. 一种保存范式哈夫曼树的方法，其特征在于，该方法包括： 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用Ν标记节点无子树； 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从右至左的顺 序，从第一个节点开始记录，只记录到第一个不为Μ的节点； 将记录的节点标记作为最终记录结果，保存最终记录结果。10. 如权利要求9所述的方法，其特征在于，该方法还包括对范式哈夫曼树的解码，具体 地： 从上至下对各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1; 从最终记录结果中依次读取标记位，直至遇到标记为Ν或读取的标记位数目达到Ρ个时 停止，为读取的标记填充后续标记Ν，直到标记总位数达到Ρ位，将填充后的标记作为当前层 的标记结果。11. 一种保存范式哈夫曼树的装置，其特征在于，该装置包括节点标记记录模块和保存 丰旲块； 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用Ν标 记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从右 至左的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；将记录的节点标记发 送给所述保存模块； 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。12. 如权利要求11所述的装置，其特征在于，该装置还包括第二解码模块，对范式哈夫 曼树的解码，具体地:从上至下对各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;从最终记录结果中依次读取标记位，直 至遇到标记为Ν或读取的标记位数目达到Ρ个时停止，为读取的标记填充后续标记Ν，直到标 记总位数达到Ρ位，将填充后的标记作为当前层的标记结果。
【专利摘要】本发明公开了保存范式哈夫曼树的方法及装置，其中，该方法包括：对范式哈夫曼树的节点进行标记，用M标记节点有子树，用N标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地：采用从左至右的顺序，从第一个节点开始记录，只记录到第一个不为N的节点；将记录的节点标记作为最终记录结果，保存最终记录结果。本发明方案能够实现采用尽量少的数据来保存范式哈夫曼树，提高存储效率。
【IPC分类】H03M7/40, H03M7/42
【公开号】CN105490683
【申请号】CN201510836102
【发明人】王志强, 郭军
【申请人】东方网力科技股份有限公司
【公开日】2016年4月13日
【申请日】2015年11月26日
【技术领域】
[0001] 本发明设及编码存储技术，尤其设及保存范式哈夫曼树的方法及装置。
【背景技术】
[0002] 在进行数据压缩时常用到范式哈夫曼树，如:GZIB、化IB、PNG、JPEG、MPEG。实际压 缩中，除了保存压缩编码，还需要保存范式哈夫曼树及原始数据总量等，运样才能够解压 缩。本发明方案针对的是如何保存范式哈夫曼树。
[0003] 首先介绍范式哈夫曼编码的原理，范式哈夫曼编码过程大概分为4步：
[0004] 1)对压缩单元进行计数或概率统计，并按照从大到小进行排序，假定对字节数据 统计结果如下述表1所示：
[0005]
[0006] 表1对压缩单元进行计数或概率统计后的排序
[0007] 其中，符号用于对压缩单元进行标识，计数表示相应压缩单元的个数，概率表示相 应压缩单元占总压缩单元的比例。
[0008] 2)按照统计结果创建范式哈夫曼树，具体地:总是找到两个出现概率或次数最少 的合并二叉树，直到合并到一个根节点为止。假定按照上述结果分a，b，. .e共5步（e为结 果），创建流程如图1所示。
[0009] 3)按照左节点编码为0,右节点为1对数据单元进行编码，产生范式哈夫曼编码表， 如表2所示。
[0010] _
[0011] 表2范式哈夫曼编码表
[0012] 4)按照编码进行数据替换即压缩，也就是原来需要8位存储的数据A，B，. .E，最后 可W用1，3,3,3,3位数据代替，顺序存储，最终实现了压缩的目的。若要解压缩还需要记录 编码表，也即{A，0}，{B，100}，{C，101}，{D，110}，巧，111}。由于主要讨论如何存储编码表， 编码压缩的详细过程及解码过程就不再详细介绍了。
[0013] 目前存储范式哈夫曼编码表多采用如下方案：
[0014] 1)记录码长方式：
[0015]
[0016] 表3记录哈夫曼编码的码长表格
[0017] 如上表所示，码表需要保存的是1，3,3,3,3,因为范式哈夫曼树的特点，由运几个 数字就可W还原出原来的树。用码长代替编码的好处是存储位数的宽度是比较有限的，就 拿全部的单字节码表来看，最长也不会超过255位，也就是最长为1个字节。
[0018] 2)记录码长基础上对码表进行二次压缩的方式：
[0019] 将上述码表的数据1，3，3，3，3再次进行压缩，如使用化E压缩，则压缩后变为：1，0， 3，3(代表0+1 = 1个1和3+1 = 4个3)，也有别的方式的压缩的，当有大量重复数据时，例如长 度全为別寸，可能记录的就是8，255。
[0020] 现有保存范式哈夫曼树的方案存在W下缺陷：
[0021] 不压缩情况下：最大码长较长时每个码长保存位数需要加大，极端情况下字符 (8bit)压缩，码表长度将达到256字节。
[0022] 压缩情况下：多数压缩算法，面对重复字节压缩率都会提高，但面对几乎每个码长 都很少时(也即重复性较少时)就较难W发挥作用了。
[0023] 综上，现有保存范式哈夫曼树的方案都存在码表过大的问题，极端情况下达到甚 至超过直接存码表。
【发明内容】
[0024] 本发明提供了一种保存范式哈夫曼树的方法，该方法能够采用尽量少的数据来保 存范式哈夫曼树，提高存储效率。
[0025] 本发明提供了一种保存范式哈夫曼树的装置，该装置能够采用尽量少的数据来保 存范式哈夫曼树，提高存储效率。
[0026] 本发明提供了另一种保存范式哈夫曼树的方法，该方法能够采用尽量少的数据来 保存范式哈夫曼树，提高存储效率。
[0027] 本发明提供了另一种保存范式哈夫曼树的装置，该装置能够采用尽量少的数据来 保存范式哈夫曼树，提高存储效率。
[0028] -种保存范式哈夫曼树的方法，该方法包括：
[0029] 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用饰示记节点无子树；
[0030] 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从左至右 的顺序，从第一个节点开始记录，只记录到第一个不为Ν的节点；
[0031] 将记录的节点标记作为最终记录结果，保存最终记录结果。
[0032] -种保存范式哈夫曼树的装置，该装置包括节点标记记录模块和保存模块；
[0033] 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树， 用Ν标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采 用从左至右的顺序，从第一个节点开始记录，只记录到第一个不为Ν的节点；将记录的节点 标记发送给所述保存模块；
[0034] 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。
[0035] -种保存范式哈夫曼树的方法，该方法包括：
[0036] 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用饰示记节点无子树；
[0037] 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从右至左 的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；
[003引将记录的节点标记作为最终记录结果，保存最终记录结果。
[0039] -种保存范式哈夫曼树的装置，该装置包括节点标记记录模块和保存模块；
[0040] 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树， 用Ν标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采 用从右至左的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；将记录的节点 标记发送给所述保存模块；
[0041] 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。
[0042] 从上述方案可W看出，本发明中，对范式哈夫曼树的节点进行标记，再对每层节点 的标记进行记录，而后，将记录的节点标记作为最终记录结果，保存最终记录结果。本发明 采用从左至右或从右至左的顺序对每层节点的标记进行记录，从第一个节点开始记录，记 录到第一个不为Ν或不为Μ的节点。具体地，采用从左至右对每层节点的标记进行记录时，从 第一个节点开始记录，只记录到第一个不为Ν的节点，后续节点不再进行记录;类似地，采用 从右至左对每层节点的标记进行记录时，从第一个节点开始记录，只记录到第一个不为Μ的 节点，后续节点不再记录;另外，在此基础上不对每层最右侧节点和最后一层的所有节点进 行记录。本申请一改惯有的记录码长方式和二次压缩方式，提供了更加简便的记录方式，也 减少了存储数据，从而提高了存储效率。
【附图说明】
[0043] 图1为现有范式哈夫曼树的创建流程图；
[0044] 图2为本发明保存范式哈夫曼树的方法示意性流程图；
[0045] 图3为本发明对范式哈夫曼树各层进行记录的示意图实例；
[0046] 图4为本发明保存范式哈夫曼树的装置结构示意图。
【具体实施方式】
[0047] 为使本发明的目的、技术方案和优点更 加清楚明白，下面结合实施例和附图，对本 发明进一步详细说明。
[0048] 参见图2,为本发明保存范式哈夫曼树的方法示意性流程图，其包括W下步骤：
[0049] 步骤201，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用Ν标记节点无 子树;对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从左至右的顺序，从第 一个节点开始记录，只记录到第一个不为Ν的节点。
[0050] 其中，Μ和Ν可根据需要选取，可W是1位，也可W是2位或更多位。运里位为例，Μ 取值为1，Ν取值为0。需要保存的范式哈夫曼树仍W图1所示的实例进行说明，对各节点进行 标记后为图3所示:第一层:1，第二层:01，第Ξ层11，第四层:0000。
[0051] 为了减少存储数据，本申请中，对每层节点的标记进行记录时，从第一个节点开始 记录，只记录到第一个不为Ν的节点，后续不再记录。
[0052] 针对图3的实例，对各层进行记录：
[005；3]第一层山
[0054] 第二层：01;
[0055] 第Ξ层:1(因每层只记录到第一个不为0的节点）；
[0化6] 第四层:〇〇〇〇;
[0057] 最终记录结果：10110000。
[005引步骤202,将记录的节点标记作为最终记录结果，保存最终记录结果。
[0059] 可选地，还可W对范式哈夫曼树中的叶节点数目进行统计，得到叶节点总数，将叶 节点总数添加到最终记录结果中。
[0060] 图3的实例中，叶节点总数为5。本发明采用从左至右或从右至左的顺序对每层节 点的标记进行记录，从第一个节点开始记录，记录到第一个不为N或不为Μ的节点。具体地， 采用从左至右对每层节点的标记进行记录时，从第一个节点开始记录，只记录到第一个不 为Ν的节点，后续节点不再进行记录;类似地，采用从右至左对每层节点的标记进行记录时， 从第一个节点开始记录，只记录到第一个不为Μ的节点，后续节点不再记录。本申请一改惯 有的记录码长方式和二次压缩方式，提供了更加简便的记录方式，也减少了存储数据，从而 提高了存储效率。
[0061] 保存最终记录结果后，需要时，可对其进行解码，W获知范式哈夫曼树的结构。解 码具体过程包括：
[0062] 从上至下对各层依次进行解码：
[0063] 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2,将得到的乘 积值作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;
[0064] 从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ 个时停止，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后的标记作为当 前层的标记结果。下面结合图3的实例进行说明，其解码过程巧个叶节点，记录为10110000) 为：
[0065] 对各层采用前述流程进行解码，具体地：
[0066] 第一层:1;解码:1。
[0067] 此时，Ρ为1;从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记 位数目达到Ρ个时停止，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后 的标记作为当前层的标记结果，则得到的第一层的标记结果为1。
[006引第二层:01，解码:01;
[0069] 此时，Ρ为2;从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记 位数目达到Ρ个时停止，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后 的标记作为当前层的标记结果，则得到的第二层的标记结果为01。
[0070] 第；层：1，解码：11;
[0071] 此时，Ρ为2;从最终记录结果中依次读取标记位(前面已经读到10110000中的第3 位，运里从第四位开始读取），直至遇到标记为Μ或读取的标记位数目达到Ρ个时停止(运里， 读取一位，即1 )，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后的标记 作为当前层的标记结果，则得到的第Ξ层的标记结果为11。
[0072] 第四层:0000,解码为:0000。
[0073] 此时，Ρ为4;从最终记录结果中依次读取标记位(前面已经读到10110000中的第4 位，运里从第5位开始读取），直至遇到标记为Μ或读取的标记位数目达到Ρ个时停止(运里， 读取4位，即0000)，则得到的第四层的标记结果为0000。
[0074] 解码结束。
[0075] 此时，P = 0;解码结束。
[0076] 为了采用尽量少的数据来保存范式哈夫曼树，在编码保存时，因最后一层各节点 都标记为0,可W不对最后一层进行记录。进一步地，在编码保存时，还可W不对每层的最后 一个节点进行记录。
[0077] 对应地，解码将相应进行调整。举例说明，如果编码保存时，采用从左至右的顺序， 从第一个节点开始记录，只记录到第一个不为N的节点，并且，不对最后一层进行记录，也不 对每层的最后一个节点进行记录;解码具体为：
[0078] 将第一层节点的标记设置为M;
[0079] 从上至下对后续各层依次进行解码：
[0080] 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2,将得到的乘 积值作为当前层的节点数Ρ;
[0081] 从最终记录结果中读取叶节点总数，统计出当前层之前所有层标记为Ν的叶节点 数，计算出剩余叶节点数Q;
[0082] 判断Ρ是否等于Q，如果是，则当前层为最后一层，Ρ个节点全部为叶节点，标记为Ν; 否则，从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ-1 个时停止，为读取的标记填充后续标记Μ，直到标记位数达到Ρ位，将填充后的标记作为当前 层的标记结果。
[0083] 下面针对图3的实例进行详细说明。对各层进行记录：
[0084] 第一层:不记录(因每层的最后一个节点不记录）；
[0085] 第二层:0(因每层的最后一个节点不记录）；
[0086] 第Ξ层：1(因每层的最后一个节点不记录且仅记录到第一个不为0的节点）；
[0087] 第四层:不记录(因为最后一层不记录）；
[0088] 最终记录结果:01。
[0089] 运样，一共用2位便可存储上面例子中的范式哈弗曼树的结构，其效率显而易见， 比现有记录码长方式及进行二次压缩方式的效率提高很多。
[0090] 图3的实例中，叶节点总数为5。
[0091] 下面结合图3的实例进行说明，其解码过程(5个叶节点，记录为01)为：
[0092] 第一层:不记录，解码：1(因每层的最后一个节点不记录，一定为1)。
[0093] 对第二层W后的各层采用如下方式进行解码：当前层节点数(Ρ)=上一层为1的节 点数*2;当剩余叶节点数=Q时，当前层全部节点全部为叶节点，也即全部为0;按位读取压 缩位，直至遇到压缩位为1(假定第T位，读取至第T位)或个数达到P-1个停止;当读取的压缩 位为加寸，叶节点计数+1;从T+1至P位全部填充为1。
[0094] 本实例中，后续各层解码后依次为：
[00M]第二层:0，解码:01 (共2个节点，最 后一个不记录）；
[0096] 第Ξ层：1，解码：11(共2个节点，不记录最后一个节点，记录到第一个不为0的节 点）；
[0097] 第四层:不记录，解码为:0000(共4个叶节点，前面已出现1个叶节点，还剩4个叶节 点，因此确定本层为最后一层）。本发明中，为了采用尽量少的数据来保存范式哈夫曼树，首 先对范式哈夫曼树的特点进行深刻了解及分析：
[0098] 每个节点要么只有两个分支，要么是叶节点，运样的二叉树也被称为正则二叉树；
[0099] 所有非叶节点都靠一边(一般为右侧），一层中从某个节点开始的右侧都有子节点 直至本层结束；
[0100] 当范式哈夫曼树叶节点个数〉=2时，从上往下看，根节点总是有两个节点，最后一 层节点也一定是叶节点。基于W上的分析，本发明给出了下述存储解范式哈夫曼树的方案：
[0101] 存储叶节点的总数、树结构及树叶节点的值即可；
[0102] 树结构按层序遍历每个节点用1位表示有无子树(1:有，0:无）；
[0103] 每层的最后一个节点（包含根节点）不记录（因为除最后一层外，该节点一定有子 树)；
[0104] 每层仅记录到第一个不为0的节点（因为后全为1);
[0105] 最后一层不记录(因为最后一层一定是上一层有子树节点数的2倍且全为0)。
[0106] 本发明根据范式哈夫曼树(也称正则二叉树)的特点，按位存储一部分节点是否有 子树的方式，达到相对稳定且高效的压缩目的，最极端的情况下能够将全部256字符(8bit) 构成的范式哈夫曼树保存至到l〇g2(N)-l至N-2位中。
[0107] 因为按照范式哈夫曼编码压缩原始数据后的数据总位数都相同，因此只需考虑记 录范式哈夫曼树的不同。即便不考虑记录总叶节点数、叶节点代码最大位数、总字节数等额 外数据，针对上面的例子进行存储，粗略计算：
[0108] 直接记录编码表方法:5x3 = 15位；
[0109] 传统方式存储范式哈夫曼编码长度的码表:5x2 = 10位；
[0110] 传统方式存储范式哈夫曼编码长度的码表后进行二次压缩:4x2 = 8位或其它未知 情况；
[0111] 本发明的按位精简存储的方法:2位。
[0112] 极端的例子一:除根节点和最后一层外每层都有2个子节点，叶节点总数为256。
[0113] 直接记录编码表方法:255巧56 = 65280位；
[0114] 传统方式存储范式哈夫曼编码长度的码表:8巧56 = 2048位；
[0115] 传统方式存储范式哈夫曼编码长度的码表后进行二次压缩:糾256+256巧或其它
[0116] 本发明的按位精简存储的方法:254位。
[0117] 极端的例子二:叶节点总数为256的满二叉树。
[0118] 直接记录编码表方法:8巧56 = 2048位；
[0119] 传统方式存储范式哈夫曼编码长度的码表:8巧56 = 2048位；
[0120] 传统方式存储范式哈夫曼编码长度的码表后进行二次压缩:糾2或其它 [0121 ]本发明的按位精简存储的方法:7位。
[0122] 从上面数据可W看出：无论是极端情况还是普通情况下，本发明的存储方法都有 极高的效率。
[0123] 本发明技术方案可W用固定的1位存储树结构中一个节点的是否有子树，即便增 加冗余到2位甚至更多位也可能比其它方式有优势;还可W采用不同的捜索顺序，或用可区 分的不同值表示有无子树。并且，对于范式哈夫曼树同时包含左子树和右子树的情况，还可 W左右子树分开按位保存，也就是，从上到下将范式哈夫曼树划分为左子树和右子树，然后 分别进行保存。范式哈夫曼树的变体(例如:全部靠左)也可w按照此方法保存。本技术方案 除了应用于压缩数据外，也可W做其它用途。可W按照链表的逻辑，只是左右节点按位存储 有无节点来替代本发明方案。
[0124]前述是采用从左至右的顺序对各层节点进行记录，也可W，采用从右至左顺序对 各层节点进行记录，不同的是，从左至右记录每层节点时是记录到第一个不为N的节点，而 从右至左记录每层节点时时记录到第一个不为Μ的节点；两种顺序的编码保存方式W及解 码方式都类似，运里不再重复寶述，下面只做简要说明。
[01巧]对于从右至左的方式：
[01%]编码保存具体包括：
[0127] 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用饰示记节点无子树；
[0128] 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从右至左 的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；
[0129] 将记录的节点标记作为最终记录结果，保存最终记录结果。
[0130] 相应地，解码过程包括：
[0131 ]从上至下对各层依次进行解码：
[0132] 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2,将得到的乘 积值作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;
[0133] 从最终记录结果中依次读取标记位，直至遇到标记为Ν或读取的标记位数目达到Ρ 个时停止，为读取的标记填充后续标记Ν，直到标记总位数达到Ρ位，将填充后的标记作为当 前层的标记结果。
[0134] 当然地，为了采用尽量少的数据来保存范式哈夫曼树，在编码保存时，类似地，也 可W不对最后一层进行记录，还可W进一步不对每层最右侧的一个节点进行记录。
[0135] 参见图4,为本发明保存范式哈夫曼树的装置结构示意图，该装置包括节点标记记 录模块和保存模块；
[0136] 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树， 用Ν标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采 用从左至右的顺序，从第一个节点开始记录，只记录到第一个不为Ν的节点；将记录的节点 标记发送给所述保存模块；
[0137] 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。
[0138] 进一步地，该装置还包括叶节点总数统计模块，对范式哈夫曼树中的叶节点数目 进行统计，得到叶节点总数，发送给所述保存模块；
[0139] 所述保存模块，将叶节点总数添加到最终记录结果中，进行保存。
[0140] 较佳地，该装置还包括第一解码模块，对范式哈夫曼树的解码，具体地:从上至下 对各层依次进行解码:统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2， 将得到的乘积值作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;从最终记录结果中依 次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ个时停止，为读取的标记填充 后续标记Μ，直到标记位总数达到Ρ位，将填充后的标记作为当前层的标记结果。
[0141] 进一步地，本申请还提供了另一种保存范式哈夫曼树的装置，该装置包括节点标 记记录模块和保存模块；
[0142] 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树， 用Ν标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采 用从右至左 的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；将记录的节点 标记发送给所述保存模块；
[0143] 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。
[0144] 进一步地，该装置还包括叶节点总数统计模块，对范式哈夫曼树中的叶节点数目 进行统计，得到叶节点总数，发送给所述保存模块；
[0145] 所述保存模块，将叶节点总数添加到最终记录结果中，进行保存。
[0146] 较佳地，该装置还包括第二解码模块，对范式哈夫曼树的解码，具体地:从上至下 对各层依次进行解码：
[0147] 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘W2,将得到的乘 积值作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;
[0148] 从最终记录结果中依次读取标记位，直至遇到标记为Ν或读取的标记位数目达到Ρ 个时停止，为读取的标记填充后续标记Ν，直到标记总位数达到Ρ位，将填充后的标记作为当 前层的标记结果。
[0149] W上所述仅为本发明的较佳实施例而已，并不用W限制本发明，凡在本发明的精 神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明保护的范围之内。
【主权项】
1. 一种保存范式哈夫曼树的方法，其特征在于，该方法包括： 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用N标记节点无子树； 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从左至右的顺 序，从第一个节点开始记录，只记录到第一个不为Ν的节点； 将记录的节点标记作为最终记录结果，保存最终记录结果。2. 如权利要求1所述的方法，其特征在于，该方法还包括对范式哈夫曼树的解码，具体 地： 从上至下对各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1; 从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ个时 停止，为读取的标记填充后续标记Μ，直到标记位总数达到Ρ位，将填充后的标记作为当前层 的标记结果。3. 如权利要求1所述的方法，其特征在于，对范式哈夫曼树每层节点的标记依次进行记 录时，不对最后一层的节点进行记录;该方法还包括： 对范式哈夫曼树中的叶节点数目进行统计，得到叶节点总数，将叶节点总数添加到最 终记录结果中。4. 如权利要求1所述的方法，其特征在于，对范式哈夫曼树每层节点的标记依次进行记 录时，每层的最后一个节点不记录;该方法还包括： 对范式哈夫曼树中的叶节点数目进行统计，得到叶节点总数，将叶节点总数添加到最 终记录结果中。5. 如权利要求4所述的方法，其特征在于，对范式哈夫曼树每层节点的标记依次进行记 录时，不对最后一层的节点进行记录。6. 如权利要求5所述的方法，其特征在于，该方法还包括对范式哈夫曼树的解码，具体 地： 将第一层节点的标记设置为Μ; 从上至下对后续各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ; 从最终记录结果中读取叶节点总数，统计出当前层之前所有层标记为Ν的叶节点数，计 算出剩余叶节点数Q; 判断Ρ是否等于Q，如果是，则当前层为最后一层，Ρ个节点全部为叶节点，标记为Ν;否 贝1J，从最终记录结果中依次读取标记位，直至遇到标记为Μ或读取的标记位数目达到Ρ-1个 时停止，为读取的标记填充后续标记Μ，直到标记位数达到Ρ位，将填充后的标记作为当前层 的标记结果。7. -种保存范式哈夫曼树的装置，其特征在于，该装置包括节点标记记录模块和保存 丰旲块； 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用Ν标 记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从左 至右的顺序，从第一个节点开始记录，只记录到第一个不为N的节点；将记录的节点标记发 送给所述保存模块； 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。8. 如权利要求7所述的装置，其特征在于，该装置还包括第一解码模块，对范式哈夫曼 树的解码，具体地:从上至下对各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;从最终记录结果中依次读取标记位，直 至遇到标记为Μ或读取的标记位数目达到Ρ个时停止，为读取的标记填充后续标记Μ，直到标 记位总数达到Ρ位，将填充后的标记作为当前层的标记结果。9. 一种保存范式哈夫曼树的方法，其特征在于，该方法包括： 对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用Ν标记节点无子树； 由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从右至左的顺 序，从第一个节点开始记录，只记录到第一个不为Μ的节点； 将记录的节点标记作为最终记录结果，保存最终记录结果。10. 如权利要求9所述的方法，其特征在于，该方法还包括对范式哈夫曼树的解码，具体 地： 从上至下对各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1; 从最终记录结果中依次读取标记位，直至遇到标记为Ν或读取的标记位数目达到Ρ个时 停止，为读取的标记填充后续标记Ν，直到标记总位数达到Ρ位，将填充后的标记作为当前层 的标记结果。11. 一种保存范式哈夫曼树的装置，其特征在于，该装置包括节点标记记录模块和保存 丰旲块； 所述节点标记记录模块，对范式哈夫曼树的节点进行标记，用Μ标记节点有子树，用Ν标 记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地:采用从右 至左的顺序，从第一个节点开始记录，只记录到第一个不为Μ的节点；将记录的节点标记发 送给所述保存模块； 所述保存模块，将记录的节点标记作为最终记录结果，保存最终记录结果。12. 如权利要求11所述的装置，其特征在于，该装置还包括第二解码模块，对范式哈夫 曼树的解码，具体地:从上至下对各层依次进行解码： 统计当前层的上一层中标记为Μ的节点数，将统计出的节点数乘以2,将得到的乘积值 作为当前层的节点数Ρ;若当前层为第一层时，Ρ为1;从最终记录结果中依次读取标记位，直 至遇到标记为Ν或读取的标记位数目达到Ρ个时停止，为读取的标记填充后续标记Ν，直到标 记总位数达到Ρ位，将填充后的标记作为当前层的标记结果。
【专利摘要】本发明公开了保存范式哈夫曼树的方法及装置，其中，该方法包括：对范式哈夫曼树的节点进行标记，用M标记节点有子树，用N标记节点无子树；由上至下对范式哈夫曼树每层节点的标记依次进行记录，具体地：采用从左至右的顺序，从第一个节点开始记录，只记录到第一个不为N的节点；将记录的节点标记作为最终记录结果，保存最终记录结果。本发明方案能够实现采用尽量少的数据来保存范式哈夫曼树，提高存储效率。
【IPC分类】H03M7/40, H03M7/42
【公开号】CN105490683
【申请号】CN201510836102
【发明人】王志强, 郭军
【申请人】东方网力科技股份有限公司
【公开日】2016年4月13日
【申请日】2015年11月26日
最新回复(0)