用Huffman编码实现压缩程序(论文).pdf

风 吟 飞整理 用用 Huffman 编码实现压缩程序编码实现压缩程序 摘要摘要 本文是对 Huffman 算法进行的一次实践 根据 ascii 码文件中各 ascii 字符出现的频率情况创建 Huffman 树 再将各字符对应的哈夫曼编码写入文 件中 同时 亦可根据对应的哈夫曼树 将哈夫曼编码文件解压成字符文件 关键词 Huffman 算法 压缩 解压缩 Abstract This article is a practice of huffman algorithm First I create the huffman tree based on the appearance frequency of each ascii character in the files then I output each ascii character s corresponding huffman code to the zipped file And I also make the program could unzip the huffman zipped files into the ascii files Key Words Huffman Algorithm Zip unzip 前言前言 Huffman 算法是个简单而高效的贪心算法 主要用来创建最优二叉树 可以在通讯时 对于出现频率较高的字符 用较少的比特数便可以进行通讯 从而节省通讯线路的资源消耗 该算法在各类数据结构 算法 组合数学 离散数学 图论等主题的书籍中都有所涉及 故本文不再赘述 本文致力于用 Huffman 算法实现压缩与解 压缩 采用的语言为 C 语言 编译环境 VC 6 0 下面给出 1中实现的 Huffman 树的结构及创建算法 有两点说明 1 这里的 Huffman 树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式 这种空间上的消耗带来了算法实现 上的便捷 2 由于对于最后生成的 Huffman 树 其所有叶子结点均为从一个内部树扩充出去的 所以 当外部叶子结点数为 m 个时 内部结点数为 m 1 整个 Huffman 树的需要的结点数为 2m 1 Code1 Huffman Algorithm define MAXCHAR 30000 define MAXNODE 300 define MAXNUM 150 define InfoType char struct HtNode EBTreeType ww char info int parentIndex 风 吟 飞整理 int llinkIndex int rlinkIndex struct HtTree struct HtNode ht MAXNODE int rootIndex typedef struct HtTree PHtTree PHtTree huffmanAlgorithm int m EBTreeType w PHtTree pht int i j int firstMinIndex secondMinIndex int firstMinW secondMinW pht PHtTree malloc sizeof struct HtTree assertF pht NULL in huffman algorithm mem apply failure n Initialize the tree array for i 0 iht i llinkIndex 1 pht ht i rlinkIndex 1 pht ht i parentIndex 1 if iht i ww w i pht ht i info char i else pht ht i ww 1 for i 0 i m 1 i new Inner Node Num m 1 firstMinW MAXCHAR firstMinIndex 1 secondMinW MAXCHAR secondMinIndex 1 for j 0 jht j wwht j parentIndex 1 trans minFirst info to minSecond info secondMinIndex firstMinIndex secondMinW firstMinW 风 吟 飞整理 set new first min node firstMinIndex j firstMinW pht ht j ww else if pht ht j wwht j parentIndex 1 update second node info secondMinW pht ht j ww secondMinIndex j Construct a new node m i is current new node s index pht ht firstMinIndex parentIndex m i pht ht secondMinIndex parentIndex m i pht ht m i ww firstMinW secondMinW pht ht m i llinkIndex firstMinIndex pht ht m i rlinkIndex secondMinIndex pht rootIndex m i return pht 压缩过程的实现压缩过程的实现 压缩过程的流程是清晰而简单的 1 创建 Huffman 树 2 打开需压缩文件 3 将需压缩文件中的每个 ascii 码对应的 huffman 编码按 bit 单位输出 4 文件压缩结束 其中 步骤 1 和步骤 3 是压缩过程的关键 步骤 1 这里所要做工作是得到 Huffman 数中各叶子结点字符出现的频率并进行创建 统计字符出现的频率可以有很多方法 如每次创建前扫描被创建 的文件 实时 的生成各字符的出现频率 或者是创建前即做好统计 本文采用后一种的方案 统计了十篇不同的文章中字符出现的频率 当前 也可 以根据被压缩文件的特性有针对性的进行统计 如要压缩 C 语言的源文件 则可事先对多篇 C 语言源文件中出现的字符进行统计 这样 会创建出 高度相对较 矮 的 Huffman 树 从而提高压缩效果 创建 Huffman 树的算法前文已有陈述 这里就不再重复了 步骤 3 将需压缩文件中的每个 ascii 码对应的 huffman 编码按 bit 单位输出 这是本压缩程序中最关键的部分 这里涉及 转换 和 输出 两个关键步骤 风 吟 飞整理 转换 部分大可不必去通过遍历 Huffman 树来找到每个字符对应的哈夫曼编码 可以将每个 Huffman 码值及其对应的 ascii 码存放于如下所示的结 构体中 typedef struct char asciiCode unsigned long haffCode int haffCodeLen HaffCode 创建由该结构体结点所组成的 长度为 128 的一维数组 codeList128且 codeList 中的下标和 asciiCode 满足下面的顺序存放关系 codeList i asciiCode i 这样的话 查找某个字符 inChar 的 huffman 编码的工作便变得相当轻松了 如下 sHaffCode codeList inChar haffCode 数组 codeList128的创建可以采用某种遍历方式下的按找到的字符进行置数的方式 十分的方便 Code2 codeList 的创建算法 采用前序遍历的方式进行创建 void preHaffListMake PHtTree inTree int rootIndex unsigned long youBiao int sDepth HaffCode inList if inTree ht rootIndex llinkIndex 1 inList inTree ht rootIndex info haffCodeLen sDepth else preHaffListMake inTree inTree ht rootIndex llinkIndex youBiao ht rootIndex rlinkIndex youBiao 1 0 x01 sDepth 1 inList 风 吟 飞整理 输出 部分是最重要的部分 也是最易出错的部分 这里 涉及到 C 语言的位操作 要求这个算法能处理好以下几个问题 1 每个字符所对应的 haffCode 的比特位长度由 5 23 位不等长 不可少输 多输 输错任何一位 后一个字符的 haffCode 要紧跟在前 一个字符的 haffCode 后面 2 最后一个字符要能合理的结束 这主要是为解压缩考虑的 比如 在最后一个要输出的 haffCode 的最后一位 它恰好是位于最后一个 有效字符的第一位 剩下的七个比特位是要用无效的 haffCode 加以填充的 否则 如果填充的 haffCode 亦为某个 ascii 字符的 haffCode 时 那么在解压缩时 则该在原被压缩文件中不存在的字符便会无中生有的在解压后的文件中出现 这显然是不正确的 应在程序中 加以处理 编码部分的流程如图 1 利用 Huffman 算法实现对 ascii 字符文件的压缩 图一 Code3 压缩部分的核心代码 define REARPOS 80 curIndex curLen 0 rearCode haffList REARPOS haffCode rearCodeLen haffList REARPOS haffCodeLen while feof inputFile count 0 outputData 0 x01 while count 8 if curIndex curLen 1 get data if feof inputFile break inData fgetc inputFile printf c inData if inData 1 else the rear output adjust for i 0 i 8 count i outputData rearCodeLen 1 i break 2 search table Should be a ascii file curCode haffList inData haffCode curLen haffList inData haffCodeLen realLen getBinLen curCode i curLen realLen curIndex 0 if i 0 outputData curLen curIndex 1 outputData rootIndex while feof inputFile if count 8 1 get data inData fgetc inputFile get 8 len bin haff code if inData 1 count 0 if myHtTree ht nodeIndex llinkIndex 1 nodeIndex myHtTree rootIndex else tmpBinData inData 7 count if tmpBinData 0 x00 nodeIndex myHtTree ht nodeIndex llinkIndex else if tmpBinData 0 x01 nodeIndex myHtTree ht nodeIndex rlinkIndex else printf error happen in read bin n count 风 吟 飞整理 拓展成一个简易的加密软件拓展成一个简易的加密软件 由于 huffman 树的算法是公开的 而对于不同的字符频率序列 压缩和解压缩的结果将截然不同 因而 可以将字符频率序列从程序中剥离出来 形成一个密钥文件 这样 压缩和解压缩的过程都必需依赖于统一的密钥才能得以进行 具体程序 请参考附录 程序压缩效果测试程序压缩效果测试 经测试 本程序对文本的压缩效果与被压缩文件的大小成正比 即被压缩文件越大 则压缩效果越好 在测试中 可将 8 14KB的源代码压缩为6 40KB