三进制霍夫曼编码

1、题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。将霍夫曼编码推广至三进制编码设一个数据文件包含Q个字符：Al,A2,Aq,每个字符出现的频度对应为P：Pl,P2,，Pq。1将字符按频度从大到小顺序排列，记此时的排列为排列1。2用一个新的符号（设为S1）代替排列1中频度值最小的Q-2k（k为（Q-1）/2取整）个字符，并记其频度值为排列1中最小的Q-2k个频度值相加，再重新按频度从大到小顺序排列字符,记为排列2。（注：若Q-2k=0,则取其值为2,若Q-2k=1,则取其值为3.）3对排列2重复上述步骤2,直至最后剩下3个概率值。4从最后一个排列开始编码，根据3个概率大小，分别赋予与3

2、个字符对应的值：0、1、2,如此得到最后一个排列3个频度的一位编码。5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码,得到二位编码,其它不变。6如此一直往前，直到排列1所有的频度值都被编码为止。举例说明如下（假设Q=9）：字符A1A2A3A4A5A6A7A8A9频度0.220.180.150.130.100.070.070.050.03字符频度编码频度编码频度编码频度编码A10.2220.2220.3010.480A20.18000.18000.2220.301A30.15020.15010.18000.222A40.13100.1502

3、0.1501A50.10110.13100.1502A60.07120.1011A70.070100.0712A80.05011A90.03012频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1A9的码字依次为:2,00,02,10,11,12,010,011,012。构造三进制霍夫曼编码伪码程序如下：HUFFMAN(C)n-IC|Q-Cfori1ton-1doallocateanewnodesleftsxEXTRACT-MIN(Q)middlesyEXTRACT-MIN(Q)rightszEXTRACT-MIN(Q)fsfx+fy+fzINSERT(Q，z)returnEXTRA

4、CT-MIN(Q)霍夫曼编码(三进制)最优性证明在二进制霍夫曼编码中，文件的最优编码由一棵满二叉树表示，树中每个非叶子结点都有两个子结点。在此与之相对应，构造一棵满三叉树来表示三进制的霍夫曼编码，树中每个非叶子结点都有三个子结点。对文件中A中的每个字符a,设f(a)表示a在文件中出现的频度，dT(a)表示字符a的编码长度，亦即a的叶子在树中的深度。这样，编码一个文件所需的位数就是B(T)=Ef(a)dT(a)设A为一给定文件，其中每个字符都定义有频度fa。设x,y和z是A中具有最低频度的两个字符。并设A为文件A中移去x,y和z,再加上新的字符s后的文件，亦即A=A-x,y,zUs；如A一样为A

5、定义f,其中fs=fx+fy+fz。设T为文件A上最优前缀编码的任意一棵树，那么，将T中叶子节点s换成具有x,y和z孩子的内部节点所得到的树T,表示文件A上的一个最优前缀编码。证明：对每一个aA-x,y,z,有dT(a)=dT(a),故讹叫二讹叫。又小冃助冃琢冃珊)+1,从而有：fxdT(x)+fydT(y)+fzdT(z)=(fx+fy+fz)(dT(s)+1)=fsdT(s)+(fx+fy+fz)由此可得：B(T)=B(T)+fx+fy+fz假设T不表示A的最优前缀编码，那么存在一棵树T,有B(T)B(T)O设T是由T中将x,y和z的父亲结点替换为叶子结点s而得，其中频度fs=fx+fy+

6、fz。则有B(T)=B(T)-fx-fy-fzB(T)-fx-fy-fz=B(T)与之前假设的T表示A上的最优前缀编码矛盾，故T必定表示文件A上的最优前缀码，证毕。构造三进制霍夫曼编码程序代码及运行结果如下：程序源码：#include#include#includeintSorting(int*x,intn)/排序int*a,b,i,j,r=0;a=x;for(j=0;jn;j+)for(i=0;in-j-1;i+)if(*(a+i+1)=(*(a+i)b=*(a+i);*(a+i)=*(a+i+1);*(a+i+1)=b;if(i=r)r+;returnr;char*strcatzp(cha

7、r*str1,constchar*str2)/字符串拼接/ASSERT(str1!=NULL)&(str2!=NULL);char*addr=(char*)malloc(strlen(str1)+strlen(str2)+1)*sizeof(char);char*des=addr;/ASSERT(addr!=NULL);while(*str1)*addr=*str1;str1+;addr+;while(*str2)*addr=*str2;str2+;addr+;*addr=0;returndes;voidmain(void)charcharacter100=;char*code100=;cha

8、r*temp=NULL;charInputChar;floatInput_p;intp100100=0;intcount=6,i,j,m,tc=0;int*k;inti_charinput=0,i_pinput=1;/数据输入printf(”请输入字符，按Enter键结束输入:n);InputChar=getchar();while(InputChar!=n)/*约定一个结束符为-1*/if(InputChar!=)characteri_charinput+=InputChar;InputChar=getchar();printf(”请输入相应字符出现的频率，按O+Enter键结束输入:n);

9、scanf(%f,&Input_p);while(Input_p!=O)pOi_pinput+=(int)(Input_p*1OOO.O+1)/1O);scanf(%f,&Input_p);if(i_charinput!=(i_pinput-1)printf(输入字符与频率个数不相等，请确认后重新输入n);return;count=i_charinput;k=&p01;for(j=0;jcount;j+)for(i=0;icount-j-1;i+)if(*(k+i+1)=(*(k+i)m=*(k+i);*(k+i)=*(k+i+1);*(k+i+1)=m;InputChar=character

10、i;characteri=characteri+1;characteri+1=InputChar;/fortest/*for(i=1;i10;i+)printf(%d,p0i);*/Sorting(&p01,count);if(count%2!=0)tc=(count-3)/2;for(i=1;i=tc;i+)pi1=pi-11+pi-12+pi-13;for(j=2;j0;i-)temp=codepi0-1;for(j=count-2*i-1;j=0;j-)if(jpi0-1)codej+2=codej;elseif(jpi0-1)codej+3=codej;code0=strcatzp(t

11、emp,2);code1=strcatzp(temp,1);code2=strcatzp(temp,0);printf(字符编码为:n);for(i=0;i%sn,characteri,codei);printf(n);/fortest/*for(i=0;i(count-1)/2;i+)for(j=0;j1+count-2*i;j+)printf(%d,pij);printf(n);*/elsetc=(count+2)/2;for(i=1;i=tc;i+)pi1=pi-11+pi-12;for(j=2;j0;i-)temp=codepi0-1;for(j=count-i-1;j=0;j-)if(jpi0-1)codej+1=codej;elseif(jpi0-1)codej+2=codej;code0=strcatzp