霍夫曼编码.doc

重庆交通大学信息科学与工程学院综合性设计性实验报告专业 班级:通信工程2012级2班 学    号:  631206040217   姓    名:    雷勇     实验所属课程:  信息论与编码  实验室(中心): 软件与通信实验中心 指导教师:   黄大荣     2015年4月教师评阅意见:签名:      年  月  日实验成绩:霍夫曼编码的matlab实现一、实验目的和要求1回顾霍夫曼编码的原理。2用Matlab语言编程实现霍夫曼(Huffman)编码。二、实验原理1霍夫曼编码介绍霍夫曼编码(HuffmanCoding)是一种熵编码编码压缩方式,霍夫曼编码是可变字长编码(VLC)的一种。霍夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。霍夫曼编码是一种根据字母的使用频率而设计的变长码,能提高信息的传输效率,至今仍有广泛的应用。霍夫曼编码方法的具体过程是:首先把信源的各个输出符号序列按概率递降的顺序排列起来,求其中概率最小的两个序列的概率之和,并把这个概率之和看做是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)。然后,对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号序列。最后,按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字霍夫曼编码(HuffmanCoding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,,并发表于《一种构建极小多余编码的方法》(AMethodfortheConstructionofMinimum-RedundancyCodes)一文。在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。1951年,霍夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。,查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,霍夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。由于这个算法,学生终于青出于蓝,超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树,避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。2霍夫曼编码原理霍夫曼(Huffman)编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号,而将较短的编码码字分配给较大