三进制霍夫曼编码

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个概率大小，分别

2、赋予与3个字符对应的值：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

3、.15020.1501A50.10110.13100.1502A60.07120.1011A70.070100.0712A80.05011A90.03012频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1A9的码字依次为:2,00,02,10,11,12,010,011,012。构造三进制霍夫曼编码伪码程序如下:HUFFMAN(C)1 n IC I2 Q C3 for i 1 to n-14 do allocate a new node s5 lefts x EXTRACT-MIN(Q)6 middles y EXTRACT-MIN(Q)7 rights z EXTRACT-MIN

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

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

6、yd T'(y)+fzd T'(z)=(fx+fy+fz)(d T“(s)+1)=fsd T''(s)+(fx+fy+fz) 由此可得：B(T)=B(T')+fx+fy+fz假设T不表示A的最优前缀编码，那么存在一棵树 T'',有B(T”)<B(T)。设T'''是由T“中将x, y和z的父亲结点替换为叶子结点s而得，其中频度fs=fx+fy+fz。则有B(T''')=B(T'')-fx-fy-fz<B(T)-fx-fy-fz=B(T')与之前假设的T

7、9;表示A'上的最优前缀编码矛盾，故T必定表示文件 A上的最优前缀码，证毕。构造三进制霍夫曼编码程序代码及运行结果如下: 程序源码：#i nclude <stdio.h>#in elude <stri ng.h>#in elude <stdlib.h> int Sorting( int *x, int n)排序int *a,b,i,j,r=0;a=x;for(j=0;j< n;j+)for(i=0;i< n-j_1;i+)if(*(a+i+1)<=(*(a+i) b=*(a+i); *(a+i)=*(a+i+1); *(a+i+1)

8、=b; if(i=r) r+;return r; char *strcatzp( char *str1, const char *str2)/字符串拼接sizeof(char);ASSERT(str1!=NULL )&&( str2!=NULL);char *addr=( char *)malloc(strle n(str1)+strle n( str2)+1)* char *des=addr;ASSERT(addr!=NULL);while (*str1)*addr=*str1;str1+; addr+; while (*str2)*addr=*str2; str2+; ad

9、dr+;*addr= '0'return des;void mai n( void)char character100= ""char *code100= ""char *temp=NULL;char In putChar;float In put_p;int p100100=0;int coun t=6,i,j,m,tc=0;int *k;int i_chari nput=0,i_p in put=1;数据输入printf("请输入字符，按 Enter键结束输入：n”)；In putChar = getchar();while

10、 (InputChar!= 'n')/* 约定一个结束符为 -1*/if (In putChar!='')characteri_chari nput+=ln putChar;In putChar = getchar();printf("请输入相应字符出现的频率，按0+Enter键结束输入:n");scanf("%f" , &lnput_p);while (Input_p!=0)pOi_pinput+= ( int)(Input_p* 1000.0+1)/10);scanf("%f" , &

11、;lnput_p);if(i_chari nput!=(i_p in put-1)printf（"输入字符与频率个数不相等，请确认后重新输入n"）;return;count = i_chari nput;k=&p01;for(j=0;j<co un t;j+)for(i=0;i<co un t-j-1;i+)if(*(k+i+1)<=(*(k+i)m=*(k+i);*(k+i)=*(k+i+1);*(k+i+1)=m;In putChar=characteri; characteri=characteri+1; characteri+1=ln pu

12、tChar;/for test/*for(i=1;i<10;i+)prin tf("%d ”,p0i);*/Sorti ng(&p01,cou nt);if (count%2 != 0)tc=(cou nt-3)/2;for(i=1;i<=tc;i+) pi1=pi-11+pi-12+pi-13; for(j=2;j<cou nt-2*i+1;j+)pij=pi-1j+2; pi0=1+Sorti ng(&pi1,cou nt-2*i);code0= "2"code1= "1"code2= "0&qu

13、ot;for(i=tc;i>0;i-)temp=codepi0-1;for(j=cou nt-2*i-1;j>=0;j-) if(j>pi0-1)codej+2=codej;else if(j<pi0-1)codej+3=codej;code0=strcatzp(temp, "2");code1=strcatzp(temp, "1");code2=strcatzp(temp, "0");printf("字符编码为:n");for(i=0;i<co un t;i+)printf( &qu

14、ot;%c->%sn" ,characteri,codei);printf( "n");/for test/* for(i=0;i<(cou nt-1)/2;i+)for(j=0;j<1+cou nt-2*i;j+)prin tf("%d ",pij);prin tf("n");*/elsetc=(cou nt+2)/2;for(i=1;i<=tc;i+) pi1=pi-11+pi-12;for(j=2;j<co un t-i+1;j+) pij=pi-1j+1;pi0=1+Sorti ng(&

15、amp;pi1,cou nt-i);code0= "2" code1="1" code2= "0"for(i=tc;i>0;i-)temp=codepi0-1;for(j=co un t_i_1;j>=0;j_)if(j>pi0-1) codej+1=codej;else if(j<pi0-1) codej+2=codej;code0=strcatzp(temp, "1");code1=strcatzp(temp, "0");printf("字符编码为:n");for(i=0;i<co un t;i+)printf( "%c->%sn" ,characteri,codei);printf( "n");/for test/*for(i=0;i<tc;i+)for(j=0;j<co un t+1;