三进制霍夫曼编码

1、题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。将霍夫曼编码推广至三进制编码设一个数据文件包含Q个字符：A1，A2，Aq，每个字符出现的频度对应为P：P1，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(C1 n C 2 Q C 3 for i 1 to n-14 do allocate a new node s5 lefts x EXTRACT-MIN(Q6 middles y EXTRACT-MIN(Q7 rights z EXTRACT-MIN(Q8 fs fx

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

5、上新的字符s后的文件，亦即A'=A-x,y,zs；如A一样为A'定义f，其中fs=fx+fy+fz。设T'为文件A'上最优前缀编码的任意一棵树，那么，将T'中叶子节点s换成具有x，y和z孩子的内部节点所得到的树T，表示文件A上的一个最优前缀编码。证明：对每一个aA-x,y,z，有dT(a=dT'(a，故fadT(a=fadT'(a。又dT'(x=dT'(y=dT'(z=dT''(s+1，从而有：fxdT'(x+fydT'(y+fzdT'(z=(fx+fy+fz(dT'

6、'(s+1=fsdT''(s+(fx+fy+fz由此可得：B(T=B(T'+fx+fy+fz假设T不表示A的最优前缀编码，那么存在一棵树T''，有B(T'' 。设 T''' 是由 T'' 中将 x ， y 和 z 的父亲结点替换为叶子结点 s 而得，其中频度 fs=fx+fy+fz 。则有 B(T'''=B(T''-fx-fy-fz 与之前假设的T'表示A'上的最优前缀编码矛盾，故T必定表示文件A上的最优前缀码，证毕。构造三进制霍夫曼编

7、码程序代码及运行结果如下：程序源码：#include #include #include int Sorting(int *x,int n/排序int *a,b,i,j,r=0;a=x; for(j=0;j for(i=0;i if(*(a+i+1<=(*(a+ib=*(a+i;*(a+i=*(a+i+1;*(a+i+1=b;if(i=r r+;return r;char *strcatzp(char *str1,const char *str2/字符串拼接 /ASSERT(str1!=NULL&&(str2!=NULL;char *addr=(char *malloc(

8、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'return des;void main(voidchar character100=""char *code100=""char *temp=NULL;char InputChar;float Input_p;int p100100=0;

9、int count=6,i,j,m,tc=0;int *k;int i_charinput=0,i_pinput=1;/数据输入printf("请输入字符，按Enter键结束输入:n"InputChar = getchar(; while(InputChar!='n'/*约定一个结束符为-1*/ if (InputChar!=' 'characteri_charinput+=InputChar; InputChar = getchar(; printf("请输入相应字符出现的频率，按0+Enter键结束输入:n"scanf

10、("%f", &Input_p;while(Input_p!=0 p0i_pinput+= (int(Input_p* 1000.0+1/10; scanf("%f", &Input_p; if(i_charinput!=(i_pinput-1printf("输入字符与频率个数不相等，请确认后重新输入n"return;count = i_charinput;k=&p01;for(j=0;j for(i=0;i if(*(k+i+1<=(*(k+im=*(k+i;*(k+i=*(k+i+1;*(k+i+1=

11、m;InputChar=characteri;characteri=characteri+1;characteri+1=InputChar;/for test/* for(i=1;i<10;i+printf("%d ",p0i;*/ Sorting(&p01,count;if(count%2 != 0tc=(count-3/2; for(i=1;i<=tc;i+pi1=pi-11+pi-12+pi-13;for(j=2;j pij=pi-1j+2;pi0=1+Sorting(&pi1,count-2*i;code0="2"co

12、de1="1"code2="0"for(i=tc;i>0;i-temp=codepi0-1;for(j=count-2*i-1;j>=0;j-if(j>pi0-1codej+2=codej;else if(j codej+3=codej;code0=strcatzp(temp,"2"code1=strcatzp(temp,"1"code2=strcatzp(temp,"0"printf("字符编码为:n"for(i=0;i printf("%c-&

13、gt;%sn",characteri,codei;printf("n"/for test/* for(i=0;i<(count-1/2;i+for(j=0;j<1+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;j pij=pi-1j+1;pi0=1+Sorting(&pi1,count-i;code0="2"code1="1"code2="0"for(i=tc;i>0;i-temp=codepi0-1;for(j=count-i-1;j>=0;j-if(j>pi0-1codej+1=codej;else if(j codej+2=codej;code0=strcatzp(temp,"1"cod