哈夫曼编码课程设计报告

哈夫曼编码课程设计报告

ID:12962209

大小:162.50 KB

页数:23页

时间:2018-07-19

哈夫曼编码课程设计报告_第1页
哈夫曼编码课程设计报告_第2页
哈夫曼编码课程设计报告_第3页
哈夫曼编码课程设计报告_第4页
哈夫曼编码课程设计报告_第5页
资源描述:

《哈夫曼编码课程设计报告》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、数据结构课程设计报告基于哈夫曼树的文件压缩/解压程序专业班级:信科(2)班姓名:徐爱娟谢静学号:20101614310051201016143100502012-12_3123一需求分析1.课题要求(实现文件的压缩与解压并计算压缩率)A.描述压缩基本符号的选择方法B.运行时压缩原文件的规模应不小于5K2.设计目标A软件名称:基于哈夫曼编码的文件压缩实用程序系统B软件组成:huffman.exeC制作平台及相关调试工具:WindowsXPsp3MicrosoftVisualC++6.0D运行环境:dos/win2K/win2003/winxp/E性能特点:1.软件由一个可执行文件组成hu

2、ffman.exe为dos系统应用程序,体积小,高效快捷,适用范围广。2.对单字节(256叶子)进行哈夫曼编码,压缩率良好3.使用二级缓冲压缩/解压技术,速度比一般算法高4.可压缩最大体积为4G的文件,达到Fat32文件系统极限5.文件索引体积比常规算法小50%二 概要设计 1.相关函数介绍1.boolInitFromFile(stringfileadd)从文件中初始化哈夫曼树函数2.voidHTCreat(HTNodeht[],intn)构造哈夫曼树函数3.voidHCCreat(HTNodeht[],HCodehcd[],intn)构造哈夫曼编码函数4.voidConvertFil

3、e(HCodehcd[],stringfileadd,stringfileadd2)压缩and写入文件函数235.voidDecompressionFile(stringfileadd2,stringfileadd3)文件解压函数6.stringCompression(stringfileadd)压缩函数7.stringDecompression(stringfileadd2)解压函数Clock()三详细设计1压缩算法部分A核心算法:Huffman编码是一种可变长编码方式,是由美国数学家DavidHuffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长

4、度较短的代码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。Huffman算法的最根本的原则是:累计的(字符的统计数字*字符的编码长度)为最小,也就是权值(字符的统计数字*字符的编码长度)的和最小。B哈夫曼树构造算法:Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子:比如有以下数据,ABFACGCAHGBBAACECDFGFAAEABBB先进行统计A(8)B(6)C(4)D(1)E(2)F(3)G(3)H(1)括号里面的是统计次数生成Huffman树:每次取最小的那两个节点(node)合并成一个节点(node),并且将累计数值相加作为新的接点的

5、累计数值,最顶层的是根节点(root)注:列表中最小节点的是指包括合并了的节点在内的所有节点,已经合并的节点不在列表中运算的过程如下:1:D+H(2)2:DE+H(4)233:F+G(6)4:C+DEH(8)5:B+FG(12)6:A+CDEH(16)7:ACDEH+BFG(28)那么转化为Huffman树就是Huffman树层数Root┌┴┐ACDEHBFG1┌┴┐┌┴┐CDEHABFG2┌┴┐┌┴┐DEHCFG3┌┴┐DHE4┌┴┐DH5取左面是1右面是0则有。注:层数就是位数或者说是代码长度,权值=代码长度*该字的统计次数。代码位数权值A=1021623B=01212C=1103

6、12D=1111155E=111048F=00139G=00026H=1111055可以看出Huffman代码是唯一可解的(uniquelydecodable),如果你读到110就一定是C,不会有任何一个编码是以110开始的。如果不使用Huffman算法,而使用普通的编码,结果是什么呢?Huffman树层数Root┌┴┐ABCDEFGH1┌┴┐┌┴┐ABCDEFGH2┌┴┐┌┴┐┌┴┐┌┴┐ABCDEFGH3取左面是1右面是0则有代码位数权值A=11132423B=110318C=101312D=10033E=01136F=01039G=00139H=00033利用Huffman编码得

7、到的权值累计是73,如果利用普通定长编码的话,则要用84字符长度。从这个比较,可以看出,Huffman是怎么进行压缩的。C哈夫曼编码结构及算法编码:将ABCDEFGH用Huffman树产生的编码对应着写到文件中,并且保留原始的Huffman树,主要是编码段的信息。一般要编码256个元素的话需要511个单位来储存Huffman树,每个Huffman树都必须有以下的结构:code,char,left,right,probability(出现次数),

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。