DOC《课程设计报告》

课程设计报告题目三: 哈弗曼编码与文件压缩 课程名称: 哈弗曼编码与文件压缩 专业班级: 计算机科学与技术1008班学号: 姓名: 指导教师: 报告日期: 计算机科学与技术学院 目录一序言 1.

1课题背景.2 1.2课设研究的目的就意义.3 1.3课设要求.3 1.4课设内容.3 1.5实验环境.3 1.6实验原理.4 1.7构造哈夫曼树和编码原理图及对应实现部分.4 二 界面介绍 2.1菜单栏及相应的函数.7 2.2相关控件及操作图示介绍.9 打开控件.9 哈夫曼控件.10 压缩机解压控件.12 三 源代码(附录) 3.1源代码(主要部分)16 四 小结.29 五 参考文献 一序言 1.1背景资料 哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种.uffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码 . 1951年,哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试.导师Robert M. Fano给他们的学期报告的题目是,寻找最有效的二进制编码.由于无法证明哪个已有编码是最有效的,哈夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的. 哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件.哈夫曼压缩属于可变代码长度算法一族.意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代.因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列. 以哈夫曼树即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩. 在计算机信息处理中, 哈夫曼编码 是一种一致性编码法(又称 熵编码法 ),用于数据的无损耗压缩.这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码.这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的).这种方法是由David.A.Huffman发展起来的. 例如,在英文中,e的出现概率很高,而z的出现概率则最低.当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位(bit)来表示,而z则可能花去25个位(不是26).用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位.二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多.倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例.(参见http://baike.baidu.com/view/4225236.htm百度百科). 1.2课设研究的目的就意义 : ⒈了解有关文件的基本概念 ⒉掌握哈夫曼树的概念及其构造方法 ⒊正确实现线性链表的插入,删除等运算 ⒋掌握遍历二叉树的方法 ⒌运用哈夫曼树及其编码 1.3课设要求: (1)要求界面友好,输入文本文件可带路径(如:D:\doc\original.txt),哈夫曼算法所得到的压缩文件名为*.cod,哈夫曼树也以文件形式保存,文件名为*.hfm. (2)显示压缩比、压缩时间、解压时间与对应的编码表. 1.4课设内容: 分析与设计哈夫曼树的存储结构,实现哈夫曼算法以及编码与译码基本功能,并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件,然后进行解压缩得到解压文件.有兴趣的同学可以查阅资料实现Lempel-Ziv sliding window压缩方法,并与之比较. 1.5实验环境: Windows7 vc++6.0 C语言编写,基于win32,利用了里面资源视图做的界面 1.6实验原理: 压缩部分: 1.构造哈夫曼树,对其进行前缀编码 (1)扫描待压缩文件,得出各字符出现频率. (2)根据给定的n个权值{W1,W2,...Wn}构成n棵二叉树的集合F={T1,T2,…,Tn},每棵二叉树Ti中只有一个带权为Wi的根节点,其左右子树均空. (3)在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树,且值新的二叉树的根节点的权值为其左右子树上根节点的全值之和. (4)在F中删除这两棵树.同时将新得到的二叉树加入F中. 重置(2)和(3),直到F只含一棵树为止.这棵树便是哈夫曼树. 2.由Huffman树得到各字符前缀编码. 3.根据前缀编码,对文件中各个字符进行编码,并按每八位一次写入压缩文件. 4.处理剩余不到八位部分,写入压缩文件. 5.将前缀编码及相关信息写入压缩文件. 6.关闭指针,完成压缩.计算压缩率. 解压部分: 读入压缩文件长度和源文件长度.读入前缀编码. 对文件中各字符解码,写入解压文件. 判断解压文件是否完好(对比压缩前文件长度),关闭指针,完成解压. 1.7构造哈夫曼树和编码原理图及对应实现部分: 在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树. 【例】给定4个叶子结点a,b,c和d,分别带权7,5,2和4.构造如下图所示的三棵二叉树(还有许多棵),它们的带权路径长度分别为: (a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4*3=35 其中(c)树的WPL最小,可以验证,它就是哈夫曼树. 注意: ① 叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树. ② 最优二叉树中,权越大的叶子离根越近. ③ 最优二叉树的形态不唯一,WPL最小 构造哈夫曼树: void createhfm(BiTree temp[],long n) { long i,j,min,pt1;