huffman编码的matlab实现.doc

1、 Huffman编码的matlab实现 一、 Huffman编码霍夫曼编码方法的具体过程是：首先把信源的各个输出符号序列按概率递降的顺序排列起来，求其中概率最小的两个序列的概率之和，并把这个概率之和看作是一个符号序列的概率，再与其他序列依概率递降顺序排列（参与求概率之和的这两个序列不再出现在新的排列之中），然后，对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号序列。最后，按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组，就可分别得到各该符号序列的码字。二、 Huffman编码的Matlab源程序1、 Huffman源程序p=inpu

2、t(please input a number:) %提示输入界面n=length(p);for i=1:n if p(i)0 fprintf(n The sum of the probabilities in huffman can more than 1!n); p=input(please input a number:) %如果输入的概率数组总和大于1，则重新输入概率数组end q=p;a=zeros(n-1,n); %生成一个n-1行n列的数组for i=1:n-1 q,l=sort(q) %对概率数组q进行从小至大的排序，并且用l数组返回一个数组，该数组表示概率数组q排序前的顺序编

3、号 a(i,:)=l(1:n-i+1),zeros(1,i-1) %由数组l构建一个矩阵，该矩阵表明概率合并时的顺序，用于后面的编码 q=q(1)+q(2),q(3:n),1; %将排序后的概率数组q的前两项，即概率最小的两个数加和，得到新的一组概率序列end for i=1:n-1 c(i,1:n*n)=blanks(n*n); %生成一个n-1行n列，并且每个元素的的长度为n的空白数组，c矩阵用于进行huffman编码，并且在编码中与a矩阵有一定的对应关系end c(n-1,n)=0; %由于a矩阵的第n-1行的前两个元素为进行huffman编码加和运算时所得的最c(n-1,2*n)=1;

4、 后两个概率，因此其值为0或1，在编码时设第n-1行的第一个空白字符为0，第二个空白字符1。for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)=1)-(n-2):n*(find(a(n-i+1,:)=1) %矩阵c的第n-i的第一个元素的n-1的字符赋值为对应于a矩阵中第n-i+1行中值为1的位置在c矩阵中的编码值 c(n-i,n)=0 %根据之前的规则，在分支的第一个元素最后补0 c(n-i,n+1:2*n-1)=c(n-i,1:n-1) %矩阵c的第n-i的第二个元素的n-1的字符与第n-i行的第一个元素的前n-1个符号相同，因为其根节点

5、相同 c(n-i,2*n)=1 %根据之前的规则，在分支的第一个元素最后补1 for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)=j+1)-1)+1:n*find(a(n-i+1,:)=j+1) %矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值 end end %完成huffman码字的分配for i=1:n h(i,1:n)=c(1,n*(find(a(1,:)=i)-1)+1:find(a(1,:)=i)*n) %用h表示最后的huffman编码，

6、矩阵h的第i行的元素对应于矩阵c的第一行的第i个元素 ll(i)=length(find(abs(h(i,:)=32) %计算每一个huffman编码的长度end l=sum(p.*ll); %计算平均码长fprintf(n huffman code:n);hhh=sum(p.*(-log2(p); %计算信源熵 fprintf(n the huffman effciency:n); t=hh/l %计算编码效率2、程序运行结果三、结论Huffman编码的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的，就是说出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的。四、练习一、P47 3.1（1） 3.3 只算二进制huffman码二译码的实现二、可视化页面的生成