数据结构课程设计报告Huffman编码与文件压缩.docx

课 程 设 计 报 告题目： 题目三 哈夫曼编码与文件压缩 课程名称： 数据结构 专业班级：计算机科学与技术1003班 学 号： 姓 名： 鲁辰 指导教师： 报告日期： 2012.09.26 计算机科学与技术学院目 录1任务书32 绪言42.1 课题背景42.2 课题研究的目的和意义42.3 国内外概况42.4 课题的主要研究工作43 系统设计方案的研究53.1 系统的控制特点与性能要求53.2 系统实现的原理53.2.1 Huffman算法53.2.2 Huffman编码53.2.3 压缩过程53.2.4 解压过程63.3 系统实现方案分析63.3.1 实现Huffman编码及压缩所需的变量63.3.2文件名处理73.3.3 实现Huffman编码及压缩过程所需要的函数73.3.4 实现解压缩过程所需要的函数83.3.5 输入输出84 基于Huffman编码的文件压缩程序的设计94.1 主模块功能介绍95 系统的实现105.1 目标程序运行截图105.2 测试及测试数据分析105.2.1 测试数据105.2.2 测试数据分析116 总结与展望12参考文献13附录 英文缩写词141 任务书题目三 哈夫曼编码与文件压缩p 设计目的：掌握二叉树、哈夫曼树的概念，性质与存储结构，能够利用哈夫曼算法实现哈夫曼编码，并应用于文件压缩，从而提高学生综合运用知识的技能与实践能力。p 设计内容：分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。有兴趣的同学可以查阅资料实现Lempel-Ziv sliding window压缩方法，并与之比较。p 设计要求：（1）要求界面友好，输入文本文件可带路径（如：D:docoriginal.txt），哈夫曼算法所得到的压缩文件名为*.cod，哈夫曼树也以文件形式保存，文件名为*.hfm。（2）显示压缩比、压缩时间、解压时间与对应的编码表。p 设计提示：统计文本文件中各字符的频度并作为权值生成哈夫曼树，并利用哈夫曼树进行二进制编码。 p 参考文献：1 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社,19972 王晓东. 计算机算法设计与分析. 北京: 电子工业出版社, 20073 严蔚敏, 吴伟民, 米宁. 数据结构题集（C语言版）. 北京: 清华大学出版社,19992 绪言2.1 课题背景在计算机软件应用领域，文件压缩是一项重要的技术。为了减少传输数据量或者减少存储空间，都需要将大型文件压缩成较小的文件。2.2 课题研究的目的和意义Huffman编码具有速度快、简单等优点，是一种很好的压缩方法。2.3 国内外概况1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于一种构建极小多余编码的方法（A Method for the Construction of Minimum-Redundancy Codes）一文。2.4 课题的主要研究工作（1）通过查阅书籍并在网上查看相关论文，对Huffman编码算法有一个清晰的认识。（2） 使用 Microsoft Visual Studio 2010 实现基于Huffman编码的文件压缩程序。（3）通过使用各种不同的测试文件对该程序进行测试，记录并分析压缩算法的压缩比、压缩时间等数据。（4）分析测试数据，并根据需要对代码进行优化。3 系统设计方案的研究3.1 系统的控制特点与性能要求本系统是使用VS2010开发的MFC应用程序，对话框是使用MFC生成的，而对文件读写操作以及Huffman编码的算法部分是用C语言实现的。本系统的特点是图形界面，使用简单，便于操控。本系统不要求使用者安装Visual Studio 或者 MFC类库（？）。3.2 系统实现的原理3.2.1 Huffman算法（1）根据给定的n个权值1,2,n构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为i的根结点，其左右子树为空。（2）在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。（3）在F中删除这两棵树，同时将新达到的二叉树加入F中。（4）重复（2）和（3），直到F只含一棵树为止。3.2.2 Huffman编码假设每种字符在电文中出现的次数为i，其编码长度为li，电文中只有n种字符，则电文总长为i=1nili。对应到二叉树上，若置i为叶子结点的权，li恰为从根到叶子结点的路径长度，则i=1nili恰为二叉树上的带权路径长度。由此可见，设计电文总长最短的二进制前缀编码即为以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_Nodetypedef struct Huffman_Nodeunsigned char char_value; /字符的值double char_weight;/权值struct Huffman_Node *leftchild,*rightchild,*parent;Huffman_Node;Huffman树的结点app_times256int存储每个字符在文本文件中出现的次数*my_Huffman_TreeHuffman_Node *my_Huffman_Tree=NULL;指向生成的Huffman树h_codeunsigned int h_code256MaxCodeLength用于存储生成的Huffman编码temp_codeunsigned int temp_codeMaxCodeLength;当遍历Huffman树为求得一个新的Huffman编码时，作为临时存储Huffman编码用3.3.2文件名处理（1）输入文件名称的合法性文件名称合法性的识别，即当选择待压缩文件时，只能选择txt格式的文本文件；当选择待解压文件时，只能选择符合3.2.4所述规定的cod格式的文件。（2）文件路径的初始化表3. 2 文件名变量名功能aa=0（进行压缩）aa=1（进行解压缩）filename用于存储输入的待压缩的文件的路径无任何作用filename1将filename的最后四个字符被改为.cod后的文件名，以备写入压缩后的文件内容用于存储输入的待解压的文件的路径filename2将filename的最后四个字符被改为.hfm后的文件名，以备写入Huffman树文件将filename1的最后四个字符被改为.hfm后的文件名，以备读入Huffman树文件，修改的前提是该文件存在。filename3无任何作用将filename1的最后五个字符被改为u.txt后的文件名，以备写入解压缩后的文件内容3.3.3 实现Huffman编码及压缩过程所需要的函数表3. 3 实现压缩所需函数列表调用顺序函数声明功能（1）void count_times(void)打开txt文本文件，并对各字符的出现次数进行统计，写入app_times中（2）void CreateHuffTree(void)构造Huffman树，先将app_times中的内容，分别写入各个Huffman树结点权值和字符值，然后用Huffman算法构造Huffman树（3）void InitCode(void)初始化Huffman编码，将h_code的值均置为-1（4）void FindCode(Huffman_Node *pNode)通过遍历Huffman树求Huffman编码，并将单次循环求出的Huffman编码存放在temp_code中。遍历结束后，调用函数CopyCode将temp_code赋值给h_code的相应位置。void CopyCode(int num)将temp_code赋值给h_code的num行（5）void CompressionFile(void)读入filename路径对应文件的字符，并将其转化为Huffman编码写入filename1路径对应的文件内。将数组app_times的内容存入filename2路径对应的文件内，以便解压缩时构造Huffman树。3.3.4 实现解压缩过程所需要的函数void DeCompressionFile(void)先从filename2路径对应的文件中读出，再调用CreateHuffTree函数，构造Huffman树，再根据filename1路径的.cod文件，读出编码，并根据编码遍历Huffman树，直到遇到叶子结点，将该叶子结点的字符的值写入对应路径filename3的txt文件中，再读入下一个Huffman编码，直到filename1的文件结尾。3.3.5 输入输出输入：（1） 待压缩文件的路径（2） 待解压文件的路径输出：（1） 错误信息（2） 在输入的文件的路径下建立的压缩后或解压缩后的文件4 基于Huffman编码的文件压缩程序的设计4.1 主模块功能介绍当用户点击界面上的按钮后，会对当前情况作出判断。如果输入不符合要求，则弹出错误信息要求重新输入。当且仅当选择了符合要求的扩展名的文件后，才能够点击开始按钮进行压缩或者解压。如图所示。弹出“打开”对话框等待用户选择弹出“打开”对话框等待用户选择aa=？“开始”单击按钮“选择待压缩文件”“选择待解压文件”开始初始化aa，app_times等10弹出错误信息“请选择文件”压缩解压路径合法？是aa=0弹出错误信息“请选择txt文本文件”否弹出错误信息“请选择cod文件”路径合法？是aa=1结束否图4. 1 主程序程序框图5 系统的实现5.1 目标程序运行截图 图4. 2 程序运行截图5.2 测试及测试数据分析5.2.1 测试数据表5. 1 测试数据 文件名直接使用打开按钮即可选取文件名中文/非中文字数txt大小/Bcod大小/B压缩比耗时/ms压缩解压非中文中文test0.txt51828388924680.6346153test1.txt7294538771534301270360.8279744433test2.txt116031370163421560.6008292014test3.txt5823514273377570000.776812316test4.txt7283520393707722447240.57015963641test5.txt7566204217352408360.5710613372test6.txt63470513242371824160.56260110655test7.txt40512040758285316345080.7658232141615.2.2 测试数据分析（1）中文字符对压缩比的影响：当中文字符占总字符的比例增加时，压缩比也会增加。说明Huffman编码在压缩中文字符时，效果不如英文字符明显。如图所示。中文字符所占比例 图5. 1 压缩比与中文字符所占比例的关系（2）文件大小与压缩、解压时间的关系：很明显，当被压缩、解压的文件越大，压缩、解压消耗的时间越长。且文件大小与操作耗时基本成线性关系。文件大小B图5. 2文件大小与压缩、解压时间的关系6 总结与展望通过设计并编写基于Huffman的文本文件压缩程序，我获益良多。首先，由于界面是使用Visual Studio 2010 制作MFC应用程序实现的，所以，我在编写代码的过程中对MFC编程和Windows程序设计加深了了解。其次，通过实现Huffman编码及文件压缩，我对Huffman算法及Huffman编码都有了深入的理解，对二叉树也加深了认识。还有，在调试的过程中，遇到了一些问题。通过解决这些问题，提高了我发现并解决问题的能力。虽然在本次的课设中我成功实现了Huffman编码与文件压缩，但是仍然觉得任务书中提到的Lempel-Ziv、Sliding Window 压缩算法实现起来较有难度。尽管，对上述两种算法都查找了相关论文和例子程序，但是仍没能够成功将其实现。不过，我一定会在以后的学习闲暇努力将上述两种算法实现。另外，对于提交的Huffman压缩程序，也是有增加功能的空间的，只是时间有限，无法一一实现。比如，可以增加对压缩比的分析功能，通过对多组不同文本文件的压缩，对比文件大小与压缩比、中文字符比例与压缩比的关系，并使用最小二乘法将曲线拟合出来。还可以使用SHA1算法检查文件的完整性，以检验Huffman编码的压缩确实是无损压缩。总之，我认为现在的提交的这个程序还有