Huffman編碼實(shí)驗(yàn)報(bào)告

1二進(jìn)制哈夫曼編碼的原理及步驟（1）信源編碼的計(jì)算設(shè)有N個(gè)碼元組成的離散、無(wú)記憶符號(hào)集，其中每個(gè)符號(hào)由一個(gè)二進(jìn)制碼字表示，信源符號(hào)個(gè)數(shù)n、信源的概率分布P={p(si)},i=1,…..,n。且各符號(hào)xi的以li個(gè)碼元編碼，在變長(zhǎng)字編碼時(shí)每個(gè)符號(hào)的平均碼長(zhǎng)為；信源熵為：；唯一可譯碼的充要條件：；其中m為碼符號(hào)個(gè)數(shù)，n為信源符號(hào)個(gè)數(shù)，Ki為各碼字長(zhǎng)度。構(gòu)造哈夫曼數(shù)示例如下圖所示。1.000000001.000000000.400.600.400.600.300.300.300.3050.150.090.600.090.600.030.030.040.050.030.030.040.05（2）二元霍夫曼編碼規(guī)則（1）將信源符號(hào)依出現(xiàn)概率遞減順序排序。（2）給兩個(gè)概率最小的信源符號(hào)各分配一個(gè)碼位“0”和“1”，將兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含（n-1）個(gè)信源符號(hào)的新信源。稱(chēng)為信源的第一次縮減信源，用s1表示。（3）將縮減信源s1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟(2)，得到只含（n-2）個(gè)符號(hào)的縮減信源s2。（4）重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1，然后從最后一級(jí)縮減信源開(kāi)始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。2功能介紹輸入一段字符序列，通過(guò)本程序可得出該字符序列中各個(gè)字符出現(xiàn)的次數(shù)，以及每個(gè)字符出現(xiàn)的概率，并能計(jì)算出信源符號(hào)熵，每個(gè)字符的哈弗曼編碼，和相應(yīng)的平均碼長(zhǎng)，編碼效率，碼方差。3算法基本步驟描述得到信源序列得到信源序列輸出得出信源序列輸出得出信源序列個(gè)數(shù)得出信源序列的概率輸出計(jì)算信源符號(hào)熵輸出計(jì)算信源符號(hào)熵輸出信源符號(hào)的哈弗曼編碼輸出信源符號(hào)的哈弗曼編碼平均碼長(zhǎng)輸出平均碼長(zhǎng)輸出輸出編碼效率輸出編碼效率輸出碼方差輸出碼方差4C語(yǔ)言源代碼#include<stdio.h>#include<string.h>#include<math.h>#defineMAX100//定義全局變量h存放信息熵doubleh=0;//定義結(jié)構(gòu)體用于存放信源符號(hào)，數(shù)目及概率typedefstruct{//不同的字符 charSOURCECODE;//不同字符出現(xiàn)的次數(shù) intNUM;//不同字符出現(xiàn)的概率 doublePROBABILITY;//哈夫曼編碼符號(hào) intCode[MAX]; intstart;//哈夫曼樹(shù)的父結(jié)點(diǎn) intparent;//哈夫曼樹(shù)的左右子結(jié)點(diǎn) intlchild; intrchild;//哈夫曼編碼的長(zhǎng)度 intlengthofhuffmancode;}Hcode;HcodeINFORMATION[MAX];//該函數(shù)用來(lái)求信源所包含的符號(hào)，以及不同符號(hào)出現(xiàn)的次數(shù)和概率intPofeachsource(charinformationsource[MAX],inta){ inti,j=1,m,flag=0; chartemp;//預(yù)先存入第一個(gè)字符，便于與后面的字符進(jìn)行比較//統(tǒng)計(jì)不同的字符存入結(jié)構(gòu)體數(shù)組中//利用flag標(biāo)簽來(lái)標(biāo)記每個(gè)字符是否出現(xiàn)過(guò)，若出現(xiàn)過(guò)標(biāo)記為1，否則置為零 INFORMATION[0].SOURCECODE=informationsource[0]; for(i=1;i<a;i++){ for(m=0;m<i;m++){ flag=0; if(informationsource[m]==informationsource[i]){ flag=1; break; } } if(flag==1) continue; else INFORMATION[j++].SOURCECODE=informationsource[i]; } INFORMATION[j].SOURCECODE='\0'; printf("信源符號(hào)數(shù)為:%d\n",j);//統(tǒng)計(jì)相同的字符出現(xiàn)的次數(shù)//每做一個(gè)字符出現(xiàn)次數(shù)的統(tǒng)計(jì)都將結(jié)構(gòu)體數(shù)組里的NUM置為零 for(i=0;i<j;i++){ INFORMATION[i].NUM=0; for(m=0;m<a;m++) if(informationsource[m]==INFORMATION[i].SOURCECODE) INFORMATION[i].NUM++; }//統(tǒng)計(jì)每個(gè)字符出現(xiàn)的概率 for(i=0;i<j;i++) INFORMATION[i].PROBABILITY=(float)INFORMATION[i].NUM/a;//將每個(gè)不同字符出現(xiàn)的次數(shù)概率都顯示出來(lái) for(i=0;i<j;i++) printf("TheNUMandPROBABILITYofCode'%c'is%dand%.3f\n",INFORMATION[i].SOURCECODE,INFORMATION[i].NUM,INFORMATION[i].PROBABILITY); returnj;}//求信源符號(hào)的熵voidH(inta){ inti; for(i=0;i<a;i++){ h+=((-1)*(INFORMATION[i].PROBABILITY)*(log(INFORMATION[i].PROBABILITY)/log(2))); }}//哈夫曼編碼函數(shù)voidHuffman(inta){ Hcodecd; inti,j,m=0,lm=0,p,c; doublemin,lmin;//順序初始化每個(gè)信源父子結(jié)點(diǎn)為-1for(i=0;i<a;i++){INFORMATION[i].parent=-1;INFORMATION[i].lchild=-1;INFORMATION[i].lchild=-1;} //循環(huán)構(gòu)造Huffman樹(shù)for(i=0;i<a-1;i++){//min,lmin中存放兩個(gè)無(wú)父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán)值最小的兩個(gè)結(jié)點(diǎn)min=lmin=MAX;//找出所有結(jié)點(diǎn)中權(quán)值最小、無(wú)父結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)，并合并之為一顆二叉樹(shù)for(j=0;j<a+i;j++){if((INFORMATION[j].PROBABILITY<min)&&(INFORMATION[j].parent==-1)){lmin=min;lm=m;min=INFORMATION[j].PROBABILITY;m=j;}elseif((INFORMATION[j].PROBABILITY<lmin)&&(INFORMATION[j].parent==-1)){lmin=INFORMATION[j].PROBABILITY;lm=j;}}//設(shè)置找到的兩個(gè)子結(jié)點(diǎn)m、lm的父結(jié)點(diǎn)信息INFORMATION[m].parent=a+i;INFORMATION[lm].parent=a+i;INFORMATION[a+i].PROBABILITY=INFORMATION[m].PROBABILITY+INFORMATION[lm].PROBABILITY; INFORMATION[a+i].parent=-1;INFORMATION[a+i].lchild=m;INFORMATION[a+i].rchild=lm;} for(i=0;i<a;i++){cd.start=a-1;c=i;p=INFORMATION[c].parent;while(p!=-1)/*父結(jié)點(diǎn)存在*/{if(INFORMATION[p].lchild==c)cd.Code[cd.start]=1;elsecd.Code[cd.start]=0;cd.start--;/*求編碼的低一位*/c=p;p=INFORMATION[c].parent;/*設(shè)置下一循環(huán)條件*/}//保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位for(j=cd.start+1;j<m;j++){INFORMATION[i].Code[j]=cd.Code[j];}INFORMATION[i].start=cd.start; }}voidmain(){//定義存放信源符號(hào)的數(shù)組 charinformationsource[MAX]; inti,j,m; doubleaverageofhuffmancode=0.0,Eita,cV=0.0; printf("pleaseinputthesourceofinformation:"); for(i=0;;i++){ scanf("%c",&informationsource[i]); if(informationsource[i]=='\n') break; } informationsource[i]='\0'; printf("信源序列為:");//顯示已輸入的一串信源符號(hào) puts(informationsource);//返回不同信源符號(hào)的數(shù)目 m=Pofeachsource(informationsource,i);//求信源的符號(hào)熵 H(m); printf("信源的符號(hào)熵:H(X)=%.3f(比特/符號(hào))\n",h); Huffman(m);//輸出已保存好的所有存在編碼的哈夫曼編碼for(i=0;i<m;i++){printf("%c'sHuffmancodeis:",INFORMATION[i].SOURCECODE);for(j=INFORMATION[i].start+1;j<m;j++)printf("%d",INFORMATION[i].Code[j]); INFORMATION[i].lengthofhuffmancode=m-INFORMATION[i].start-1;printf("\n");}//求哈夫曼編碼的平均碼長(zhǎng)和編碼效率 for(i=0;i<m;i++) averageofhuffmancode+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode; printf("哈夫曼編碼的平均碼長(zhǎng)為:%lf(碼元/信源符號(hào))\n",averageofhuffmancode); Eita=h/averageofhuffmancode; printf("哈夫曼編碼的編碼效率為:%lf\n",Eita);//求哈弗曼編碼的碼方差 for(i=0;i<m;i++) cV+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode*INFORMATION[i].lengthofhuffmancode; cV-=averageofhuffmancode*averageofhuffmancode; printf("哈弗曼編碼的碼方差為：%lf\n",cV);}5運(yùn)行結(jié)果截圖:6實(shí)驗(yàn)分析（1）在哈弗曼編碼的過(guò)程中，對(duì)縮減信源符號(hào)按概率有大到小的順序重新排列，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。（2）哈弗曼編碼效率相當(dāng)高，對(duì)編碼器的要求也簡(jiǎn)單得多。（3）哈弗曼它保證了信源概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，每次縮減信源的最后兩個(gè)碼字總是最后一位碼元不同，前面的各位碼元都相同，每次縮減信源的最長(zhǎng)兩個(gè)碼字有相同的碼長(zhǎng)。（4）哈弗曼的編法并不一定是唯一的。