三进制霍夫曼编码 Prepared on 22 November 2020题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。

※将霍夫曼编码推广至三进制编码设一个数据文件包含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个字符对应的值：0、1、2，如此得到最后一个排列3个频度的一位编码。

5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码，得到二位编码，其它不变。

6.如此一直往前，直到排列1所有的频度值都被编码为止。

举例说明如下（假设Q=9）：频度中的黑体为前一频度列表中斜体频度相加而得。

编码后字符A1~A9的码字依次为：2,00,02,10,11,12,010,011,012。

构造三进制霍夫曼编码伪码程序如下：HUFFMAN(C)1 n ←∣C ∣2 Q ← C3 for i ← 1 to n-14 do allocate a new node s5 left[s] ← x ← EXTRACT-MIN(Q)6 middle[s] ← y ← EXTRACT-MIN(Q)7 right[s] ← z ← EXTRACT-MIN(Q)8 f[s] ← f[x]+f[y]+f[z]9 INSERT(Q，z)10 return EXTRACT-MIN(Q)※霍夫曼编码（三进制）最优性证明在二进制霍夫曼编码中，文件的最优编码由一棵满二叉树表示，树中每个非叶子结点都有两个子结点。

在此与之相对应，构造一棵满三叉树来表示三进制的霍夫曼编码，树中每个非叶子结点都有三个子结点。

对文件中A中的每个字符a，设f(a)表示a在文件中出现的频度，d T(a)表示字符a的编码长度，亦即a 的叶子在树中的深度。

这样，编码一个文件所需的位数就是B(T)=∑f(a)d T(a)设A为一给定文件，其中每个字符都定义有频度f[a]。

设x，y和z是A中具有最低频度的两个字符。

并设A'为文件A中移去x，y和z，再加上新的字符s后的文件，亦即A'=A-{x,y,z}∪{s}；如A一样为A'定义f，其中f[s]=f[x]+f[y]+f[z]。

设T'为文件A'上最优前缀编码的任意一棵树，那么，将T'中叶子节点s换成具有x，y和z孩子的内部节点所得到的树T，表示文件A上的一个最优前缀编码。

证明：对每一个a∈A-{x,y,z}，有d T(a)=d T'(a)，故f[a]d T(a)=f[a]d T'(a)。

又d T'(x)=d T'(y)=d T'(z)=d T''(s)+1，从而有：f[x]d T'(x)+f[y]d T'(y)+f[z]d T'(z)=(f[x]+f[y]+f[z])(d T''(s)+1)=f[s]d T''(s)+(f[x]+f[y]+f[z])由此可得：B(T)=B(T')+f[x]+f[y]+f[z]假设T不表示A的最优前缀编码，那么存在一棵树T''，有B(T'')<B(T)。

设T'''是由T''中将x，y和z的父亲结点替换为叶子结点s而得，其中频度f[s]=f[x]+f[y]+f[z]。

则有B(T''')=B(T'')-f[x]-f[y]-f[z]<B(T)-f[x]-f[y]-f[z]=B(T')与之前假设的T'表示A'上的最优前缀编码矛盾，故T必定表示文件A上的最优前缀码，证毕。

构造三进制霍夫曼编码程序代码及运行结果如下：程序源码：#include <>#include <>#include <>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)=b;if(i==r) r++;}}}return r;}char *strcatzp(char *str1,const char *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';return des;}void main(void){char character[100]={""};char *code[100]={""};char *temp=NULL;char InputChar;float Input_p;int p[100][100]={0};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!=' '){character[i_charinput++]=InputChar;}InputChar = getchar();}printf("请输入相应字符出现的频率，按0+Enter键结束输入:\n");scanf("%f", &Input_p);while(Input_p!=0){p[0][i_pinput++]= (int)((Input_p* +1)/10);scanf("%f", &Input_p);}if(i_charinput!=(i_pinput-1)){printf("输入字符与频率个数不相等，请确认后重新输入\n");return;}count = i_charinput;k=&p[0][1];for(j=0;j<count;j++){for(i=0;i<count-j-1;i++){if((*(k+i+1))<=(*(k+i))){m=*(k+i);*(k+i)=*(k+i+1);*(k+i+1)=m;InputChar=character[i];character[i]=character[i+1];character[i+1]=InputChar;}}}//for test/* for(i=1;i<10;i++){printf("%d ",p[0][i]);}*/Sorting(&p[0][1],count);if(count%2 != 0){tc=(count-3)/2;for(i=1;i<=tc;i++){p[i][1]=p[i-1][1]+p[i-1][2]+p[i-1][3];for(j=2;j<count-2*i+1;j++){}p[i][0]=1+Sorting(&p[i][1],count-2*i);}code[0]="2";code[1]="1";code[2]="0";for(i=tc;i>0;i--){temp=code[p[i][0]-1];for(j=count-2*i-1;j>=0;j--){if(j>p[i][0]-1)code[j+2]=code[j];else if(j<p[i][0]-1)code[j+3]=code[j];}code[0]=strcatzp(temp,"2");code[1]=strcatzp(temp,"1");code[2]=strcatzp(temp,"0");}printf("字符编码为:\n");for(i=0;i<count;i++){printf("%c->%s\n",character[i],code[i]);}printf("\n");//for test/* for(i=0;i<(count-1)/2;i++){for(j=0;j<1+count-2*i;j++){printf("%d ",p[i][j]);}printf("\n");}*/}else{tc=(count+2)/2;for(i=1;i<=tc;i++){for(j=2;j<count-i+1;j++){p[i][j]=p[i-1][j+1];}p[i][0]=1+Sorting(&p[i][1],count-i);}code[0]="2";code[1]="1";code[2]="0";for(i=tc;i>0;i--){temp=code[p[i][0]-1];for(j=count-i-1;j>=0;j--){if(j>p[i][0]-1)code[j+1]=code[j];else if(j<p[i][0]-1)code[j+2]=code[j];}code[0]=strcatzp(temp,"1");code[1]=strcatzp(temp,"0");}printf("字符编码为:\n");for(i=0;i<count;i++){printf("%c->%s\n",character[i],code[i]);}printf("\n");//for test/* for(i=0;i<tc;i++){for(j=0;j<count+1;j++){printf("%d ",p[i][j]);}printf("\n");}*/}}。