哈夫曼编码在文件压缩中的应用.pptxVIP

南京邮电大学 毕 业 论 文;1;1;1;1;1;1;8;9;10;出的一种编码方法，该算法的核心部分为哈夫曼编码树（huffman coding tree） ;12;南京邮电大学 2009 届本科生毕业设计（论文） 压缩文件的文件结构如表1 在文件头部分可利用像素与文件头的偏移量距 离位置计算文件头和全表的长度, 从而得到哈夫曼编码树的起始位置。解码过 程: 指向哈夫曼树的树根。 根据当前一位编码为0或1从而指向左或右儿子节点。 判断该节点的左,右儿子是否是空(即为0)不是则向后扫描一个编码,执 行上一步,如是则完成一个解码,该叶子节点的数组下标即为像素值, 继续解下 一个。在解码过程中需要把按位存储的编码读取出来,这个过程就是按位读取。 (2)解压流程图 根据静态哈夫曼算法，解压缩过程为压缩的逆过程。先读取解压缩文件头， 获 得原文件的长度，字符的编码长度，字符的个数等信息，再构建解压缩树， 依次将编码恢复成原始数据。其总体流程图如图2-1所示： ;14;15;南京邮电大学 2009 届本科生毕业设计（论文）;南京邮电大学 2009 届本科生毕业设计（论文）;18;19;南京邮电大学 2009 届本科生毕业设计（论文） 曼树，用一个二维数组就可以模拟哈夫曼树的创建过程并得到各字符的编码。实 现思想如下： 先统计每个编码长度Ni (二叉树上的Ni 层) 上对应数据的数目，再分别对 Ni 层上的符号以递增顺序分配编码。最底层编码从0 开始， 第Ni 层第一个编码 为下一层最后一个编码的左边Ni 位数+ 1 。 例如，有一幅图片Picture.bmp，包含七种颜色，分别为A，B，C，D，E， F，G，其出现概率分别为0.25，0.20，0.18，0.13，0.10，0.09，0.05。按照哈 夫曼算法，所得哈夫曼树如图2-4所示：;21;22;南京邮电大学 2009 届本科生毕业设计（论文） 比较，找出相同的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建 的密码文件当中。 先打开密码文件，将之前编码后得到的密文内容存储到字符串中以便解码调 用。开始对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字 符是‘0’的时候，则索引走向左子节点；当是‘1’的时候，则走向右子节点。 以此类推，一直走到叶子节点为止，则当前叶子节点所代表的字符即为前一段密 文的解码结果，。再对下一个字符依次从根节点开始解码，如此循环对每一段密 文进行解码直到解码结束。将解码打印到屏幕，并将解码结果存入到新的解码文 件当中。 3.2 算法流程图 第一步：建立哈夫曼树;南京邮电大学 2009 届本科生毕业设计（论文） 第二步：构建哈夫曼编码表;南京邮电大学 2009 届本科生毕业设计（论文）;南京邮电大学 2009 届本科生毕业设计（论文）;27;28;29;南京邮电大学 2009 届本科生毕业设计（论文）;南京邮电大学 2009 届本科生毕业设计（论文） 图 4-2 (a) HT 初 始 状 态 图 4-2 (b) HT 终 止 状 态 根据生成的哈夫曼树对 HC 表中的字符进行编码，编码的方法：从该叶子到 根逆向求该字符的编码。例如图 4-2 中“把”的权值为 14，对应的编码为：“000”。 将得到的哈夫曼编码写入 HC[i].internal_code_address[j].code 指向的区域。 当字符编码完成之后，打开压缩文件，将哈夫曼树 HT 中除权重以外的数据（解 码无需权重信息）写入压缩文件中，作为下一次解压缩的解码表。再次打开要压 缩的文本文件，读取文件中的字符，根据编码的范围确定该字符是 ASCII 还是 GB2312，如果 ASCII 则调用折半查找函数，在编码表 HC 中进行纵向查找，查找 此 ASCII 出现的位置 p1，该字符的编码为 HC[p1].internal_code_address[1].code；如果字符是汉字，则调用折半查找先 纵向查找该汉字的第一字节机内码在 HC 中的位置 p1，然后从 HC[p1].internal_code_address 开始横向查找该汉字的第二字节机内码的位置 p2，这样就得到了该汉字的哈夫曼编码为 HC[p1].internal_code_address[p2].code 因为哈夫曼编码在 HC 表中是以字符 串形式存放（因为计算机的基本储单位是字节，如果以位存放，需要另设一个空 间来表示未编码的位空间大小）。所以需要将字符串“0101“转换为二进制 0101 写入文件。因为每个哈夫曼编码的长度是不一样的，假设某字符的哈夫曼长度为 4，则将该编码写入一个字节后，还剩余 4 个位，则下一次可以继续从第 5 个位 开始写入，当所有字符的编码都写入完毕