霍夫曼编码

信息论与编码实验报告重庆交通大学信息科学与工程学院综合性设计性实验报告专业班级：通信工程2012级2班学号：631206040217姓名：雷勇实验所属课程：信息论与编码实验室(中心)：软件与通信实验中心指导教师：黄大荣2015年4月信息论与编码实验报告第2页共8页教师评阅意见：签名：年月日实验成绩：霍夫曼编码的matlab实现一、实验目的和要求1回顾霍夫曼编码的原理。2用Matlab语言编程实现霍夫曼（Huffman）编码。二、实验原理1霍夫曼编码介绍霍夫曼编码(HuffmanCoding)是一种熵编码编码压缩方式，霍夫曼编码是可变字长编码(VLC)的一种。霍夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。霍夫曼编码是一种根据字母的使用频率而设计的变长码,能提高信息的传输效率,至今仍有广泛的应用。霍夫曼编码方法的具体过程是：首先把信源的各个输出符号序列按概率递降的顺序排列起来,求其中概率最小的两个序列的概率之和,并把这个概率之和看做是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)。然后,对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号序列。最后,按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字霍夫曼编码(HuffmanCoding)是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，DavidA.Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一信息论与编码实验报告第3页共8页个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师RobertM.Fano给他们的学期报告的题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。2霍夫曼编码原理霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1和0分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。离散无记忆信源。例如：Uu1u2u3u4u5P(U)=0.40.20.20.10.1码字Wi信符si概率P(si)编码过程第一次第二次第三次信息论与编码实验报告第4页共8页W1=0W2=10W3=111W4=1101W5=1100S1S2S3S4S50.40.20.20.10.10.40.20.210.200.40.410.200.610.401A(1)0通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码。3霍夫曼树下面是字符串agdfaghdabsb的霍夫曼编码的霍夫曼树：出现的字符字符出现的次数a3g2d2f1h1b2s1合计12信息论与编码实验报告第5页共8页三、实验步骤分为两步，首先是码树形成过程：对信源概率进行合并形成编码码树。然后是码树回溯过程：在码树上分配编码码字并最终得到霍夫曼编码。1、码树形成过程将信源概率按照从小到大顺序排序并建立相应的位置索引。然后按上述规则进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束。在这一过程中每一次都把排序后的信源概率存入矩阵G中，位置索引存入矩阵Index中。这样，由排序之后的概率矩阵G以及索引矩阵Index就可以恢复原概率矩阵P了，从而保证了回溯过程能够进行下去。2、码树回溯过程在码树上分配编码码字并最终得到Huffman编码。从索引矩阵M的末行开始回溯：(1)在Index的末行2元素位置填入0和1。(2)根据该行索引1位置指示，将索引1位置的编码（‘1’）填入上一行的第一、第二元素位置，并在它们之后分别添加‘0’和‘1’。(3)将索引不为‘1’的位置的编码值（‘0’）填入上一行的相应位置（第3列）。(4)以Index的倒数第二行开始向上，重复步骤(1)～(3)，直到计算至Index的首行为止。四、程序代码%取得信源概率矩阵,并进行合法性判断clear;P=input('请输入信源概率向量P=');N=length(P);forcomponent=1:1:Nif(P(component)0)error('信源概率不能小于0');endendif((sum(P)-1)0.0001)error('信源概率之和必须为1');end%建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯,从而得出对应的编码Q=PIndex=zeros(N-1,N);%初始化Indexfori=1:N-1[Q,L]=sort(Q);Index(i,:)=[L(1:N-i+1),zeros(1,i-1)];G(i,:)=Q;Q=[Q(1)+Q(2),Q(3:N),1];%将Q中概率最小的两个元素合并，元素不足的地信息论与编码实验报告第6页共8页方补1end%根据以上建立的Index矩阵，进行回溯，获取信源编码fori=1:N-1Char(i,:)=blanks(N*N);%初始化一个由空格符组成的字符矩阵N*N,用于存放编码end%从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一行进行编码Char(N-1,N)='0';%G中的N-1行即最后一行第一个元素赋为0，存到Char中N-1行的N列位置Char(N-1,2*N)='1';%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置%以下从G的倒数第二行开始向前编码fori=2:N-1Char(N-i,1:N-1)=Char(N-i+1,N*(find(Index(N-i+1,:)==1))-(N-2):N*(find(Index(N-i+1,:)==1)));%将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置Char(N-i,N)='0';%然后在当前行的第一个编码位置末尾填入'0'Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1);%将G后一行中索引为1的编码码字填入到当前行的第二个编码位置Char(N-i,2*N)='1';%然后在当前行的第二个编码位置末尾填入'1'forj=1:i-1%内循环作用：%将Index后一行中索引不为1处的编码按照左右顺序填入当前行的第3个位置开始的地方,最后计算到Index的首行为止Char(N-i,(j+1)*N+1:(j+2)*N)=Char(N-i+1,N*(find(Index(N-i+1,:)==j+1)-1)+1:N*find(Index(N-i+1,:)==j+1));endend%Char中第一行的编码结果就是所需的Huffman编码输出，通过Index中第一行索引将编码对应到相应概率的信源符号上。fori=1:NResult(i,1:N)=Char(1,N*(find(Index(1,:)==i)-1)+1:find(Index(1,:)==i)*N);end%打印编码结果String='信源概率及其对应的Huffman编码如下';disp(String);disp(P);disp(Result);五、对比分析，通过给给定不同的信源，对结果进行分析对比验证，并得出相应分分析报告。信息论与编码实验报告第7页共8页以输入信源概率向量P=[0.40.30.20.1]，得到的霍夫曼编码为：图1霍夫曼编码1以输入信源概率向量P=[0.30.20.10.10.3]，得到的霍夫曼编码为：图2霍夫曼编码2分析：霍夫曼编码方法得到的码并非是唯一的，原因是：(1)每次对信源缩减时，赋予最后两个概率最小的信源符号的码符号“0”和“1”是可以互换的，所以可得到不同的霍夫曼码；(2)对信源进行缩减时，如果两个概率最小的信源符号合并后的概率与其他信源符号的概率相同，则在进行概率排序时的次序是任意的，因此会得到不同的霍夫曼码。信息论与编码实验报告第8页共8页六、提交实验报告通过本次实验，对霍夫曼编码有了更深刻的理解，霍夫曼码是用概率匹配的方法进行信源编码。霍夫曼码的编码方法保证了概率大的信源符号对应的码长小，概率小的信源符号对应的码长大，充分利用了短码；每次缩减信源的最长两个码字有相同的码长，并且仅仅只有最后一位码符号不同。因为老师给了相对简洁的代码，所以我的难点就是读懂每一句代码。虽然理论上的霍夫曼编码的实现步骤比较易懂，但是在实践中具体用matlab实现还是有一点困难，在一些关键点上会有些绕，好在最后看懂了。同时，我也认识了自己还有很多不足，需要进一步学习的地方，在接下来的学习中我会花更多时间，来认真加深知识理解与运用。