哈夫曼编码c实现

1、 中南大学信息论编码实验报告 专业班级:电子信息1002指导老师：赵颖姓名:付永军学号:0909100707 目录一.实验目的3二、实验内容3三、实验原理41.1使用matlab 实现香农码编码。41.2、使用matlab 实现huffman 编码.72.1、使用c+实现香农码编码101）香农编码原理102）编码步骤102.2、使用c+实现huffman 编码14四实验结果17一.实验目的 1. 掌握香农码和 huffman 编码原理和过程。2. 熟悉 matlab 软件的基本操作，练习使用matlab 实现香农码和huffman编码。3. 熟悉 c/c+语言，练习使用c/c+实现香农码和hu

2、ffman 编码。4. 应用 huffman 编码实现文件的压缩和解压缩。二、实验内容1、使用matlab 实现香农码和huffman 编码，并自己设计测试案例。2、使用cc+实现香农码和huffman 编码，并自己设计测试案例。3、可以用任何开发工具和开发语言，尝试实现huffman 编码应用在数据文件的压缩和解压缩中，并自己设计测试案例。三、实验原理1.1使用matlab 实现香农码编码。 编程方法：据课本上的介绍编码香农码的方法。首先，给定信源符号概率，要先判断信源符号概率是否满足概率分布，即各概率之和是否为1，如果不为1就没有继续进行编码的必要，虽然任可以正常编码，但编码失去了意义。其

3、次，对信源符号概率进行从小到大的排序，以便进行下一步。从第一步就知道信源符号的个数n，于是构造一个nx4的零矩阵d，以便储存接下来运算的结果。把排好序的信源符号概率以列的形式赋给d的第一列。再次，做编码的第二步，求信源符号概率的累加概率（方法见程序），用来编写码字。接着求各信源符号概率对应的自信息量，用于求解码长k。然后，我们对刚求的自信息量对无穷方向取最小正整数，得到的最小正整数就是该信源符号所对应编码的码长k，有了码长，接下来就可以求解码字。最后，对所求到的累加概率求其二进制，取其小数点后的数，所取位数由该信源符号对应的码长决定，所用的步骤结束，依次得到各信源符号的香农编码。程序展现：cl

4、c;clear;a=0.4,0.3,0.1,0.09,0.07,0.04;a=fliplr(sort(a);%降序排列m,n=size(a);for i=1:n b(i,1)=a(i);%生成b的第1列end%生成b第2列的元素a=sum(b(:,1)/2;for k=1:n-1 if abs(sum(b(1:k,1)-a)=abs(sum(b(1:k+1,1)-a) break; endendfor i=1:n%生成b第2列的元素 if i=k b(i,2)=0; else b(i,2)=1; endend%生成第一次编码的结果end=b(:,2);end=sym(end);%生成第3列及以

5、后几列的各元素j=3;while (j=0) p=1; while(p=n) x=b(p,j-1); for q=p:n if x=-1 break; else if b(q,j-1)=x y=1; continue; else y=0; break; end end end if y=1 q=q+1; end if q=p|q-p=1 b(p,j)=-1; else if q-p=2 b(p,j)=0; end(p)=char(end(p),0; b(q-1,j)=1; end(q-1)=char(end(q-1),1; else a=sum(b(p:q-1,1)/2; for k=p:q-

6、2 if abs(sum(b(p:k,1)-a)=abs(sum(b(p:k+1,1)-a); break; end end for i=p:q-1 if i在输入的概率矩阵p正确的前提条件下,对p进行排序，并用矩阵l记录p排序之前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小的两个数加和，得到新的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵p以及每次排序之前概率顺序的矩阵a。2新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行huffman编码： 将c矩阵的第n-1行的第一和第二个元素分别令为0和1（表示在编码时，根节点之下的概率较小的元素后补

7、0，概率较大的元素后补1，后面的编码都遵守这个原则） 然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码（该编码即为第n-i-1行第一、二个元素的根节点），则矩阵c的第n-i行的第一、二个元素的n-1的字符为以上求得的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码， 最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成huffman编码。3计

8、算信源熵和平均码长，其比值即为编码密码效率。程序展现p=input(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进行从小至大的排

9、序，并且用l数组返回一个数组，该数组表示概率数组q排序前的顺序编号 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行的前两个元素为进

10、行huffman编码加和运算时所得的最c(n-1,2*n)=1; 后两个概率，因此其值为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

11、的字符与第n-i行的第一个元素的前n-1个符号相同，因为其根节点相同 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

12、(a(1,:)=i)*n) %用h表示最后的huffman编码，矩阵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.1、使用c+实现香农码编码1）香农编码原理 香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平

13、均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度ki满足下式 i(xi)ki(xi)+1, 就可以得到这种码。这种编码方法就是香农编码。2）编码步骤 香农编码法冗余度稍大，实用性不大，但有重要的理论意义。编码步骤如下：（1） 将信源消息符号按其出现的概率大小依次排列 p（x1）p（x2）p（xn）（2） 确定满足下列不等式整数码长ki： -log2p(xi)ki-log2p(xi)+1（3） 为了编成唯一可译码，计算第i个消息的累加概率 pi=p(xk)（4） 将累加概率pi变成二进制数。取pi二进制数的小数点后ki位即为该消息符号的二进制码字程

14、序实现#include #include #include #define max_cl 10 /*maxsize of length of code*/#define max_pn 6 /*输入序列的个数*/typedef float datatype;typedef struct shnode datatype pb; /*第i个消息符号出现的概率*/ datatype p_sum; /*第i个消息符号累加概率*/ int kl; /*第i个消息符号对应的码长*/ int codemax_cl; /*第i个消息符号的码字*/ struct shnode *next; shnolist;da

15、tatype sym_arrymax_pn; /*序列的概率*/void pb_scan(); /*得到序列概率*/void pb_sort(); /*序列概率排序*/void valuelist(shnolist *l); /*计算累加概率，码长，码字*/void codedisp(shnolist *l); void pb_scan() int i; datatype sum=0; printf(input %d possible!n,max_pn); for(i=0;i); scanf(%f,&sym_arryi); sum=sum+sym_arryi; /*判断序列的概率之和是否等于1

16、，在实现这块模块时，scanf()对float数的缺陷，故只要满足0.99sum1.0001|sum0.99) printf(sum=%f,sum must (0.999sum1.0001),sum); pb_scan(); /*选择法排序*/void pb_sort() int i,j,pos; datatype max; for(i=0;imax_pn-1;i+) max=sym_arryi; pos=i; for(j=i+1;jmax) max=sym_arryj; pos=j; sym_arrypos=sym_arryi; sym_arryi=max; void codedisp(sh

17、nolist *l) int i,j; shnolist *p; datatype hx=0,kl=0; /*hx存放序列的熵的结果，kl存放序列编码后的平均码字的结果*/ p=l-next; printf(numtgailvtsumt-lb(p(ai)tlenthtcoden); printf(n); for(i=0;ipb,p-p_sum,-3.332*log10(p-pb),p-kl); j=0; for(j=0;jkl;j+) printf(%d,p-codej); printf(n); hx=hx-p-pb*3.332*log10(p-pb); /*计算消息序列的熵*/ kl=kl+

18、p-kl*p-pb; /*计算平均码字*/ p=p-next; printf(h(x)=%ftkl=%fnr=%fbit/code,hx,kl,hx/kl); /*计算编码效率*/shnolist *setnull() shnolist *head; head=(shnolist *)malloc(sizeof(shnolist); head-next=null; return(head);shnolist *my_creat(datatype a,int n) shnolist *head,*p,*r; int i; head=setnull(); r=head; for(i=0;ipb=a

19、i; p-next=null; r-next=p; r=p; return(head);void valuelist(shnolist *l) shnolist *head,*p; int j=0; int i; datatype temp,s; head=l; p=head-next; temp=0; while(jp_sum=temp; temp=temp+p-pb; p-kl=-3.322*log10(p-pb)+1;/*编码，*/ s=p-p_sum; for(i=0;ikl;i+) p-codei=0; for(i=0;ikl;i+) p-codei=2*s; if(2*s=1) s

20、=2*s-1; else if(2*s=0) break; else s=2*s; j+; p=p-next; int main(void) shnolist *head; pb_scan(); pb_sort(); head=my_creat(sym_arry,max_pn); valuelist(head); codedisp(head); 2.2、使用c+实现huffman 编码算法 1、从键盘输入组成信源c的字符个数n； 2、从键盘输入信源c和组成信源的字符所对应的概率数组p； 3、用函数来对信源进行二进制编码；先对p按从大到小进行排序，与此同时要把c中相应的字符的位置做相应的调换；用

21、数组来记录编码：在进行记录编码时是从数组的最后一个开始存储的，而且，每进行一次编码所记录下来的两个编码是按从数组的最后一个元素开始服从countm-k-j、countm-k-j-1，其中k表示编码所进行的次数，j表示每次编码都只有;最后用函数来输出编码。程序实现#include #include #include #include #define n 100 typedef struct double probobility; int lnode; int rnode; node;node treen; int p = 0, total = 0; char stkn, q = 0; int u

22、sedn,node_lenn;void print_code() int i = 0; for (i = 0; i q; i+) printf(%c, stki); void print_avg_len() int i; double avg_len=0; for(i=0;itotal;i+) avg_len+=bobility * (double)node_leni; printf(the average length is %fn,avg_len); int find_min() int i_min = 0, i; while (usedi_min & i_min p)

23、i_min+; for (i = 0; i p; i+) if (!usedi & bobility = treei_bobility) i_min = i; return i_min; void create_tree() int n1, n2; node newnode; while (1) if (treep - 1.probobility = 1) break; n1 = find_min(); usedn1 = 1; n2 = find_min(); usedn2 = 1; bobility = bobility + bobility; newnode.lnode = n1; newnode.rnode = n2; treep+ = newnode; void traverse_tree(int i) if (treei.lnode = -1 & treei.rnode = -1) printf(%-ftt|, bobility); print_code(); printf(tt|%-dn,q);