三進(jìn)制霍夫曼編碼

1、題目：將霍夫曼編碼推廣至三進(jìn)制編碼，并證明它能產(chǎn)生最優(yōu)編碼。將霍夫曼編碼推廣至三進(jìn)制編碼設(shè)一個(gè)數(shù)據(jù)文件包含Q個(gè)字符：Al,A2,Aq,每個(gè)字符出現(xiàn)的頻度對(duì)應(yīng)為P：Pl,P2,，Pq。1將字符按頻度從大到小順序排列，記此時(shí)的排列為排列1。2用一個(gè)新的符號(hào)（設(shè)為S1）代替排列1中頻度值最小的Q-2k（k為（Q-1）/2取整）個(gè)字符，并記其頻度值為排列1中最小的Q-2k個(gè)頻度值相加，再重新按頻度從大到小順序排列字符,記為排列2。（注：若Q-2k=0,則取其值為2,若Q-2k=1,則取其值為3.）3對(duì)排列2重復(fù)上述步驟2,直至最后剩下3個(gè)概率值。4從最后一個(gè)排列開始編碼，根據(jù)3個(gè)概率大小，分別賦予與3

2、個(gè)字符對(duì)應(yīng)的值：0、1、2,如此得到最后一個(gè)排列3個(gè)頻度的一位編碼。5.此時(shí)的3個(gè)頻度中有一個(gè)頻度是由前一個(gè)排列的3個(gè)相加而來，這3個(gè)頻度就取它的一位編碼后面再延長(zhǎng)一位編碼,得到二位編碼,其它不變。6如此一直往前，直到排列1所有的頻度值都被編碼為止。舉例說明如下（假設(shè)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。構(gòu)造三進(jìn)制霍夫曼編碼偽碼程序如下：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)霍夫曼編碼(三進(jìn)制)最優(yōu)性證明在二進(jìn)制霍夫曼編碼中，文件的最優(yōu)編碼由一棵滿二叉樹表示，樹中每個(gè)非葉子結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。在此與之相對(duì)應(yīng)，構(gòu)造一棵滿三叉樹來表示三進(jìn)制的霍夫曼編碼，樹中每個(gè)非葉子結(jié)點(diǎn)都有三個(gè)子結(jié)點(diǎn)。對(duì)文件中A中的每個(gè)字符a,設(shè)f(a)表示a在文件中出現(xiàn)的頻度，dT(a)表示字符a的編碼長(zhǎng)度，亦即a的葉子在樹中的深度。這樣，編碼一個(gè)文件所需的位數(shù)就是B(T)=Ef(a)dT(a)設(shè)A為一給定文件，其中每個(gè)字符都定義有頻度fa。設(shè)x,y和z是A中具有最低頻度的兩個(gè)字符。并設(shè)A為文件A中移去x,y和z,再加上新的字符s后的文件，亦即A=A-x,y,zUs；如A一樣為A

5、定義f,其中fs=fx+fy+fz。設(shè)T為文件A上最優(yōu)前綴編碼的任意一棵樹，那么，將T中葉子節(jié)點(diǎn)s換成具有x,y和z孩子的內(nèi)部節(jié)點(diǎn)所得到的樹T,表示文件A上的一個(gè)最優(yōu)前綴編碼。證明：對(duì)每一個(gè)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假設(shè)T不表示A的最優(yōu)前綴編碼，那么存在一棵樹T,有B(T)B(T)O設(shè)T是由T中將x,y和z的父親結(jié)點(diǎn)替換為葉子結(jié)點(diǎn)s而得，其中頻度fs=fx+fy+

6、fz。則有B(T)=B(T)-fx-fy-fzB(T)-fx-fy-fz=B(T)與之前假設(shè)的T表示A上的最優(yōu)前綴編碼矛盾，故T必定表示文件A上的最優(yōu)前綴碼，證畢。構(gòu)造三進(jìn)制霍夫曼編碼程序代碼及運(yùn)行結(jié)果如下：程序源碼：#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;/數(shù)據(jù)輸入printf(”請(qǐng)輸入字符，按Enter鍵結(jié)束輸入:n);InputChar=getchar();while(InputChar!=n)/*約定一個(gè)結(jié)束符為-1*/if(InputChar!=)characteri_charinput+=InputChar;InputChar=getchar();printf(”請(qǐng)輸入相應(yīng)字符出現(xiàn)的頻率，按O+Enter鍵結(jié)束輸入: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(輸入字符與頻率個(gè)數(shù)不相等，請(qǐng)確認(rèn)后重新輸入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