Huffman编码软件实现

信息与编码实验报告姓名：学号：专业班级：学院：联系方式:实验二：Huffman编码软件实现一、实验目的1.进一步熟悉Huffman编码过程；2.掌握Matlab程序的设计和调试技术。二、实验要求1.输入：信源符号个数r、信源的概率分布P；2.输出：每个信源符号对应的Huffman编码的码字。三、实验内容1)从键盘输入组成信源S的字符个数N；2)从键盘输入信源S和组成信源的字符所对应的概率数组P；3)对信源进行二进制Huffman编码。四、实验报告1.简要总结Huffman编码的原理与特点霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。霍夫曼编码，有如下特征：a．它是一种分组码：各个信源符号都被映射成一组固定次序的码符号。b．它是一种唯一可解的码：任何码符号序列只能以一种方式译码。c．它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即霍夫曼编码所得的码字为即时码。所以，一串码符号中的每个码字都可不考虑其后的码符号直接解码出来。2.写出Huffman编码的基本步骤，画出实现Huffman编码的程序流程图。设信源s={s1,s2,…sq},其对应的概率分布为p(si)={p1,p2,…,pq},霍夫曼编码的编码步骤如下：a.将q个信源符号按概率递减的方式排列。b.用0、1码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，其概率为两符号概率之和，从而得到只包含q-1个符号的新信源，称为s信源的缩减信源s1.c.将缩减信源s1中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0、1码符号表示，这样又形成了由q-2个符号构成的缩减信源s2.d.依次继续下去，直到缩减信源只剩下两个符号为止，将最后两个字符分别用0、1码符号表示，从右向左读取相应的码字，即为对应信源符号的码字。霍夫曼编码程序流程图：开始输入信源符号对应的概率p(si)={p1,p2,…,pq}将x1.x2合并成一个新的符号，其概率为两符号概率之和，s信源的缩减信源s1.将缩减信源将剩下的最后两个字符分别用0、1码符号表示把以上概率按递减的方式排列用0、1码符号分别表示概率最小的两个信源符号x1.x2将缩减信源s1中的符号仍按概率大小以递减次序排列进行q-2次循环从右向左读取相应的码字，输出码字结束3.给出Huffman编码的源程序，并给出实验过程中的测试结果例：使用matlab语言对以下信源进行Huffman编码，并使用该程序求每个信源符号对应的Huffman编码的码字。123456780.40.180.10.10.070.060.050.04sssssssssp程序如下所示：%哈夫曼编码的MATLAB实现（基于0、1编码）：clc;clear;A=[0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04];%信源消息的概率序列A=fliplr(sort(A));%按降序排列T=A;[m,n]=size(A);B=zeros(n,n-1);%空的编码表（矩阵）fori=1:nB(i,1)=T(i);%生成编码表的第一列endr=B(i,1)+B(i-1,1);%最后两个元素相加T(n-1)=r;T(n)=0;T=fliplr(sort(T));t=n-1;forj=2:n-1%生成编码表的其他各列fori=1:tB(i,j)=T(i);endK=find(T==r);B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在该列的位置r=(B(t-1,j)+B(t,j));%最后两个元素相加T(t-1)=r;T(t)=0;T=fliplr(sort(T));t=t-1;endB;%输出编码表END1=sym('[0,1]');%给最后一列的元素编码END=END1;t=3;d=1;forj=n-2:-1:1%从倒数第二列开始依次对各列元素编码fori=1:t-2ifi1&B(i,j)==B(i-1,j)d=d+1;elsed=1;endB(B(n,j+1),j+1)=-1;temp=B(:,j+1);x=find(temp==B(i,j));END(i)=END1(x(d));endy=B(n,j+1);END(t-1)=[char(END1(y)),'0'];END(t)=[char(END1(y)),'1'];t=t+1;END1=END;endA%排序后的原概率序列END%编码结果fori=1:n[a,b]=size(char(END(i)));L(i)=b;endavlen=sum(L.*A)%平均码长H1=log2(A);H=-A*(H1')%熵P=H/avlen%编码效率结果输出如下：A为排序后的原概率序列A=0.40000.18000.10000.10000.07000.06000.05000.0400每个信源符号对应的Huffman编码的码字为：END=[1,001,011,0000,0100,0101,00010,00011]平均码长为avlen=2.6100熵H=2.5524编码效率P=0.97794.总结实验过程遇到的问题及解决方法在一开始编程时，不要忘记对原始概率先进行降序排列，并把最小的两个概率相加求和。循环结束后，对最后的两个字符分别用0、1表示。然后按照从左到右的方式进行编码，输出码字。注意matlab编程中的一些细节问题，不要出错。5.实验收获及总结通过本次实验，加深了对Huffman编码的原理的认识，对Huffman编码的步骤有了更加深刻的了解。知道了如何利用Huffman编码求信源的码字。并学会了使用matlab编写Huffman编码的程序，利用该程序，使得对信源符号求解Huffman编码的题型变得更加容易。