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.從最后一個排列開始

2、編碼，根據3個概率大小，分別賦予與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.1800

3、0.222A40.13100.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 C 2 Q C 3 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

4、z EXTRACT-MIN(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和z，再加上新的字符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)+f

6、ydT'(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)。設T'''是由T''中將x，y和z的父親結點替換為葉子結點s而得，其中頻度fs=fx+fy+fz。則有B(T''')=B(T'')-fx-fy-fz<B(T)-fx-fy-fz

7、=B(T')與之前假設的T'表示A'上的最優前綴編碼矛盾，故T必定表示文件A上的最優前綴碼，證畢。構造三進制霍夫曼編碼程序代碼及運行結果如下：程序源碼：#include <stdio.h>#include <string.h>#include <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);*

8、(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+;*add

9、r='0'return des;void main(void)char character100=""char *code100=""char *temp=NULL;char InputChar;float Input_p;int p100100=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!=&#

10、39;n')/*約定一個結束符為-1*/ if (InputChar!=' ')characteri_charinput+=InputChar; InputChar = getchar(); printf("請輸入相應字符出現的頻率，按0+Enter鍵結束輸入:n");scanf("%f", &Input_p);while(Input_p!=0) p0i_pinput+= (int)(Input_p* 1000.0+1)/10); scanf("%f", &Input_p); if(i_char

11、input!=(i_pinput-1)printf("輸入字符與頻率個數不相等，請確認后重新輸入n");return;count = i_charinput;k=&p01;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=characteri;characteri=characteri+1;characteri+1=InputChar;/for test/*for(i=1;i<1

12、0;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;j<count-2*i+1;j+)pij=pi-1j+2;pi0=1+Sorting(&pi1,count-2*i);code0="2"code1="1"code2="0"for(i=tc;i>0;i-)temp=codepi0-1;for

13、(j=count-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<count;i+)printf("%c->%sn",characteri,codei);printf(&qu

14、ot;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<count-i+1;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-1)codej+1=codej;else if(j<pi0-1)codej+2=codej;code0=strcatzp(temp,"1");code1=strcatzp(temp,"0");pri