数据结构课程设计报告Huffman编码与文件压缩.docx
《数据结构课程设计报告Huffman编码与文件压缩.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告Huffman编码与文件压缩.docx（14页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告Huffman编码与文件压缩
课程设计报告
题目：
题目三
哈夫曼编码与文件压缩
课程名称：
数据结构
专业班级：
计算机科学与技术1003班
学号：
姓名：
鲁辰
指导教师：
报告日期：
2012.09.26
计算机科学与技术学院
目录
1任务书3
2绪言4
2.1课题背景4
2.2课题研究的目的和意义4
2.3国内外概况4
2.4课题的主要研究工作4
3系统设计方案的研究5
3.1系统的控制特点与性能要求5
3.2系统实现的原理5
3.2.1Huffman算法5
3.2.2Huffman编码5
3.2.3压缩过程5
3.2.4解压过程6
3.3系统实现方案分析6
3.3.1实现Huffman编码及压缩所需的变量6
3.3.2文件名处理7
3.3.3实现Huffman编码及压缩过程所需要的函数7
3.3.4实现解压缩过程所需要的函数8
3.3.5输入输出8
4基于Huffman编码的文件压缩程序的设计9
4.1主模块功能介绍9
5系统的实现10
5.1目标程序运行截图10
5.2测试及测试数据分析10
5.2.1测试数据10
5.2.2测试数据分析11
6总结与展望12
参考文献13
附录英文缩写词14
1任务书
题目三哈夫曼编码与文件压缩
☐设计目的：
掌握二叉树、哈夫曼树的概念，性质与存储结构，能够利用哈夫曼算法实现哈夫曼编码，并应用于文件压缩，从而提高学生综合运用知识的技能与实践能力。
☐设计内容：
分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。
有兴趣的同学可以查阅资料实现Lempel-Zivslidingwindow压缩方法，并与之比较。
☐设计要求：
（1）要求界面友好，输入文本文件可带路径（如：
D:
\doc\original.txt），哈夫曼算法所得到的压缩文件名为*.cod，哈夫曼树也以文件形式保存，文件名为*.hfm。
（2）显示压缩比、压缩时间、解压时间与对应的编码表。
☐设计提示：
统计文本文件中各字符的频度并作为权值生成哈夫曼树，并利用哈夫曼树进行二进制编码。
☐参考文献：
[1]严蔚敏,吴伟民.数据结构（C语言版）.北京:
清华大学出版社,1997
[2]王晓东.计算机算法设计与分析.北京:
电子工业出版社,2007
[3]严蔚敏,吴伟民,米宁.数据结构题集（C语言版）.北京:
清华大学出版社,1999
2绪言
2.1课题背景
在计算机软件应用领域，文件压缩是一项重要的技术。
为了减少传输数据量或者减少存储空间，都需要将大型文件压缩成较小的文件。
2.2课题研究的目的和意义
Huffman编码具有速度快、简单等优点，是一种很好的压缩方法。
2.3国内外概况
1952年，DavidA.Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。
2.4课题的主要研究工作
（1）通过查阅书籍并在网上查看相关论文，对Huffman编码算法有一个清晰的认识。
（2）使用MicrosoftVisualStudio2010实现基于Huffman编码的文件压缩程序。
（3）通过使用各种不同的测试文件对该程序进行测试，记录并分析压缩算法的压缩比、压缩时间等数据。
（4）分析测试数据，并根据需要对代码进行优化。
3系统设计方案的研究
3.1系统的控制特点与性能要求
本系统是使用VS2010开发的MFC应用程序，对话框是使用MFC生成的，而对文件读写操作以及Huffman编码的算法部分是用C语言实现的。
本系统的特点是图形界面，使用简单，便于操控。
本系统不要求使用者安装VisualStudio或者MFC类库（？
）。
3.2系统实现的原理
3.2.1Huffman算法
（1）根据给定的n个权值{
}构成n棵二叉树的集合F={
}，其中每棵二叉树
中只有一个带权为
的根结点，其左右子树为空。
（2）在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
（3）在F中删除这两棵树，同时将新达到的二叉树加入F中。
（4）重复
（2）和（3），直到F只含一棵树为止。
3.2.2Huffman编码
假设每种字符在电文中出现的次数为
，其编码长度为
，电文中只有n种字符，则电文总长为
。
对应到二叉树上，若置
为叶子结点的权，
恰为从根到叶子结点的路径长度，则
恰为二叉树上的带权路径长度。
由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率做权，设计一棵Huffman树的问题，由此得到的二进制前缀编码即为Huffman编码。
3.2.3压缩过程
前提：
与输入的路径对应的文件为txt格式。
（1）构造Huffman树：
算法如3.2.1所示。
（2）将Huffman树编码：
初始化编码数组，并遍历Huffman树，得到各个字符的编码，并保存为.hfm文件。
（3）将.txt文件中的内容读取出来，找到对应的Huffman编码，并将相应的Huffman编码写入.cod文件中。
3.2.4解压过程
前提：
与输入的路径对应的文件为txt格式，且输入的路径对应的xxx.cod文件有对应的Huffman编码文件xxx.hfm存在。
（1）由.hfm文件载入Huffman编码的数组。
（2）读取.cod文件的内容，并找到其对应的字符写入新的.txt文件。
3.3系统实现方案分析
3.3.1实现Huffman编码及压缩所需的变量
表3.1实现Huffman编码所需变量列表（均为全局变量）
名称
声明语句or类型
功能
Huffman_Node
typedefstructHuffman_Node
{
unsignedcharchar_value;//字符的值
doublechar_weight;//权值
structHuffman_Node*leftchild,*rightchild,*parent;
}Huffman_Node;
Huffman树的结点
app_times[256]
int[]
存储每个字符在文本文件中出现的次数
*my_Huffman_Tree
Huffman_Node*my_Huffman_Tree=NULL;
指向生成的Huffman树
h_code
unsignedinth_code[256][MaxCodeLength]
用于存储生成的Huffman编码
temp_code
unsignedinttemp_code[MaxCodeLength];
当遍历Huffman树为求得一个新的Huffman编码时，作为临时存储Huffman编码用
3.3.2文件名处理
（1）输入文件名称的合法性
文件名称合法性的识别，即当选择待压缩文件时，只能选择txt格式的文本文件；当选择待解压文件时，只能选择符合3.2.4所述规定的cod格式的文件。
（2）文件路径的初始化
表3.3文件名
变量名
功能
aa=0（进行压缩）
aa=1（进行解压缩）
filename
用于存储输入的待压缩的文件的路径
无任何作用
filename1
将filename的最后四个字符被改为.cod后的文件名，以备写入压缩后的文件内容
用于存储输入的待解压的文件的路径
filename2
将filename的最后四个字符被改为.hfm后的文件名，以备写入Huffman树文件
将filename1的最后四个字符被改为.hfm后的文件名，以备读入Huffman树文件，修改的前提是该文件存在。
filename3
无任何作用
将filename1的最后五个字符被改为u.txt后的文件名，以备写入解压缩后的文件内容
3.3.3实现Huffman编码及压缩过程所需要的函数
表3.2实现压缩所需函数列表
调用顺序
函数声明
功能
（1）
voidcount_times（void）
打开txt文本文件，并对各字符的出现次数进行统计，写入app_times中
（2）
voidCreateHuffTree（void）
构造Huffman树，先将app_times中的内容，分别写入各个Huffman树结点权值和字符值，然后用Huffman算法构造Huffman树
（3）
voidInitCode（void）
初始化Huffman编码，将h_code的值均置为-1
（4）
voidFindCode（Huffman_Node*pNode）
通过遍历Huffman树求Huffman编码，并将单次循环求出的Huffman编码存放在temp_code中。
遍历结束后，调用函数CopyCode将temp_code赋值给h_code的相应位置。
voidCopyCode（intnum）
将temp_code赋值给h_code的num行
（5）
voidCompressionFile（void）
读入filename路径对应文件的字符，并将其转化为Huffman编码写入filename1路径对应的文件内。
将数组app_times的内容存入filename2路径对应的文件内，以便解压缩时构造Huffman树。
3.3.4实现解压缩过程所需要的函数
voidDeCompressionFile（void）
先从filename2路径对应的文件中读出，再调用CreateHuffTree函数，构造Huffman树，再根据filename1路径的.cod文件，读出编码，并根据编码遍历Huffman树，直到遇到叶子结点，将该叶子结点的字符的值写入对应路径filename3的txt文件中，再读入下一个Huffman编码，直到filename1的文件结尾。
3.3.5输入输出
输入：
（1）待压缩文件的路径
（2）待解压文件的路径
输出：
（1）错误信息
（2）在输入的文件的路径下建立的压缩后或解压缩后的文件
4基于Huffman编码的文件压缩程序的设计
4.1主模块功能介绍
当用户点击界面上的按钮后，会对当前情况作出判断。
如果输入不符合要求，则弹出错误信息要求重新输入。
当且仅当选择了符合要求的扩展名的文件后，才能够点击开始按钮进行压缩或者解压。
如图所示。
图4.1主程序程序框图
5系统的实现
5.1目标程序运行截图
图4.2程序运行截图
5.2测试及测试数据分析
5.2.1测试数据
表5.1测试数据
文件名
中文/非中文字数
txt大小/B
cod大小/B
压缩比
耗时/ms
压缩
解压
非中文
中文
test0.txt
518
28
3889
2468
0.63461
5
3
test1.txt
7294
53877
153430
127036
0.827974
44
33
test2.txt
11603
13
70163
42156
0.600829
20
14
test3.txt
582
35142
73377
57000
0.77681
23
16
test4.txt
728352
0
3937077
2244724
0.57015
963
641
test5.txt
75662
0
421735
240836
0.57106
133
72
test6.txt
63470
51
324237
182416
0.562601
106
55
test7.txt
405120
4075
828531
634508
0.765823
214
161
5.2.2测试数据分析
（1）中文字符对压缩比的影响：
当中文字符占总字符的比例增加时，压缩比也会增加。
说明Huffman编码在压缩中文字符时，效果不如英文字符明显。
如图所示。
中文字符所占比例
图5.1压缩比与中文字符所占比例的关系
（2）文件大小与压缩、解压时间的关系：
很明显，当被压缩、解压的文件越大，压缩、解压消耗的时间越长。
且文件大小与操作耗时基本成线性关系。
文件大小B
图5.2文件大小与压缩、解压时间的关系
6总结与展望
通过设计并编写基于Huffman的文本文件压缩程序，我获益良多。
首先，由于界面是使用VisualStudio2010制作MFC应用程序实现的，所以，我在编写代码的过程中对MFC编程和Windows程序设计加深了了解。
其次，通过实现Huffman编码及文件压缩，我对Huffman算法及Huffman编码都有了深入的理解，对二叉树也加深了认识。
还有，在调试的过程中，遇到了一些问题。
通过解决这些问题，提高了我发现并解决问题的能力。
虽然在本次的课设中我成功实现了Huffman编码与文件压缩，但是仍然觉得任务书中提到的Lempel-Ziv、SlidingWindow压缩算法实现起来较有难度。
尽管，对上述两种算法都查找了相关论文和例子程序，但是仍没能够成功将其实现。
不过，我一定会在以后的学习闲暇努力将上述两种算法实现。
另外，对于提交的Huffman压缩程序，也是有增加功能的空间的，只是时间有限，无法一一实现。
比如，可以增加对压缩比的分析功能，通过对多组不同文本文件的压缩，对比文件大小与压缩比、中文字符比例与压缩比的关系，并使用最小二乘法将曲线拟合出来。
还可以使用SHA1算法检查文件的完整性，以检验Huffman编码的压缩确实是无损压缩。
总之，我认为现在的提交的这个程序还有很多可以改进的地方，可以变得更加完善。
参考文献
[1]严蔚敏,吴伟民.数据结构（C语言版）.北京:
清华大学出版社,1997
[2]王晓东.计算机算法设计与分析.北京:
电子工业出版社,2007
[3]严蔚敏,吴伟民,米宁.数据结构题集（C语言版）.北京:
清华大学出版社,1999
[4]张静盛.Windows编程循序渐进.北京:
机械工业出版社,2008
附录英文缩写词
英文缩写
英文全名
中文译名
VS2010
VisualStudio2010
MFC
MicrosoftFoundationClasses
SHA1
SecureHashAlgorithm
安全哈希算法
升级会员 