哈弗曼编码

《哈弗曼编码》由会员分享，可在线阅读，更多相关《哈弗曼编码（30页珍藏版）》请在金锄头文库上搜索。

1、重庆科技学院课程设计报告院（系）:_电气与信息工程学院_ 专业班级: 计科普 0902 学生姓名: 付作辉 学 号: 2009441644 设计地点（单位）_计算机基础自主学习中心 I306 _ _设计题目:_哈夫曼编码解码器的实现 _ _ 完成日期： 2011 年 1 月 13 日 指导教师评语: _ _ _ 成绩（五级记分制）:_ _ 指导教师（签字）:_ _ 重庆科技学院课程设计任务书设计题目：哈夫曼编码解码器的实现学生姓名 付作辉课程名称 数据结构课程设计 专 业 班 级 计科 2009-02地 点 计算机基础自主学习中心 起止时间 2011.01.4-2011.01.14设计内容及要

2、求功能：利用哈夫曼编码对数据进行无损压缩，实现 Huffman压缩的编码器和译码器。1. 首先读入待压缩源文件。2. 然后建立并分析字母表，对每种字符的出现频度进行统计，以频度作为建立 Huffman树的权值。3.频度表建好后，就可以根据算法建立 Huffman树，对出现的每种字符进行 Huffman编码。4. 此时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件，并且计算压缩率。5. 译码过程先读入被压缩的文件，将其解释为比特流，根据 Huffman树，对比特流逐位译码，将译码结果逐次写入到磁盘文件。要求：完成编码译码功能。设计参数测试数据要求：自行设计。输出数据要求：输出每个字符

3、（或是词）的使用频率，及编码规则。进度要求2011.1.4 星期二（上午教师指导，下午学生独立完成） 、完成任务的讲解、并接受课程设计任务，选定课程设计的题目2011.1.5 星期三（上午教师指导，下午学生独立完成） 、了解任务的算法、并画出算法的程序流程图2011.1.6 星期四（上午教师指导，下午学生独立完成） 、对任务的关键技术进行验证、并确定解决办法2011.1.7 星期五（上午教师指导，下午学生独立完成） 、编制任务的程序2011.1.10 星期一（上午教师指导，下午学生独立完成） 、编制任务的程序2011.1.11 星期二（上午教师指导，下午学生独立完成） 、对程序的调试，并试运行

4、。2011.1.12 星期三（上午教师指导，下午学生独立完成） 、整理课程设计过程中的各个参数、并进行总结，提出改进意见2011.1.13 星期四（上午教师指导，下午学生独立完成） 、编写课程设计报告、准备答辨2011.1.14 星期五（上午答辨） 、进行答辨验收工作。参考资料1严蔚敏 吴伟民 著， 数据结构（C 语言版） ，清华大学出版社，2007.42Richard F.Gilberg Behrouz A.Forouzan, Data Structures A Pseudocode Approach with C，second edition, Thomson, 2005.13. 李春葆

5、著，数据结构教程，清华大学出版社，2005.1其它说明.本表应在每次实施前一周由负责教师填写二份，院系审批后交院系办备案，一份由负责教师留用。.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任： 向毅 指导教师：向毅、陈刘奎、熊茜 2010年 12 月 20日重庆科技学院本科生课程设计 摘要I摘要哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。哈夫曼编码算法使用字符在文件中出现的频率，并用哈夫曼树来建立一个用 01 串表示各字符的最优表示方式。通过 0，1 串替换字符，并压缩为 bit 流写入文件，从而实现文件的压缩，解压则通过读取文件

6、头和文件尾的解码规则，实现文件的解压。本程序就是基于以上原理设计了压缩、解压和打印哈夫曼编码的功能。本程序经过测试后，功能均能实现，运行稳定。关键词：哈夫曼编码 压缩 01 串 bit 流 二叉树 重庆科技学院本科生课程设计 目录目录摘要 .I1需求分析 .12系统分析与设计 .12.1算法设计 .12.2程序流程图 .12.2.1程序模块图 .12.2.3 Compress()函数流程图 .22.2.4 Uncompress()函数流程图 .32.2.4 文本存储示意图 .42.3 关键代码分析 .42.3.1结构体定义 .52.3.2数组的初始化 .52.3.3 生成 Huffman树 .

7、62.3.4 生成 Huffmancode .73软件测试 .93.1测试压缩功能 .93.2测试解压功能 .93.2测试 Huffmancode打印功能 .104总结 .115软件使用说明书 .13致谢 .14参考文献 .15附录 .16重庆科技学院本科生课程设计 需求分析11 需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码，是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二

8、叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈夫曼译码输

9、入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的 0，1 相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。本程序具有对文本压缩和解压的功能，并能打印出哈夫曼编码。重庆科技学院本科生课程设计 需求分析22 系统分析与设计2.1 算法设计Huffman编码是一种可变长编码方式，是

10、二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman 算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。权值统计：因为是处理文本文件，本程序定义了 512个结构体数组，因为一个字节存储的范围是 0255，及 256个字符（包括汉字的半个编码） ，根据定义 Huffman树的节点个数 m=2*n-1,所以 512个数组刚好能把所有字符统计出来。在逐个读取文本字符的时候，根据字符的 ASCII码做为数组下标，同时初始化512个数组，并将文件中存在的字符的 ASCII码存入对应的结构体中。生成 Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root) 注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表。生成 Huffmancode：根据 Huffman 树中个节点的关系生成 Huffmancode，规则