無損壓縮編碼（huffman編碼）實(shí)驗(yàn)報(bào)告

無損壓縮編碼（huffman編碼）實(shí)驗(yàn)報(bào)告作者:學(xué)號：學(xué)院(系):電子工程與光電技術(shù)學(xué)院專業(yè):電子信息工程題目:無損壓縮編碼指導(dǎo)老師：摘要本文介紹了無損壓縮編碼中的霍夫曼（huffman）編碼。Huffman編碼是可變字長編碼的一種，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造最優(yōu)二叉樹（huffman樹），故有時(shí)又稱為最佳編碼。在文中，我們使用C++語言進(jìn)行編碼，從下到上進(jìn)行了熵編碼。關(guān)鍵詞：huffman、最優(yōu)二叉樹、熵編碼、C++AbstractThehuffman(Huffman)codingofLosslesscodingwereintroducedinthispaper.Huffmancodingisakindofvariable-word-lengthcoding.Themethodiscompletelybasedonthecharactersappearprobabilitytoconstructtheoptimalbinarytree(Huffmantree),soitissometimesreferredtoastheoptimalcoding.Inthispaper,weusec++languagetocode,frombottomtotopintheentropycoding.Keywords:huffman、optimalbinarytree、entropycoding、C++實(shí)驗(yàn)?zāi)康睦斫鉄o損壓縮編碼的優(yōu)點(diǎn)和意義。理解樹、二叉樹、huffman樹的概念。學(xué)會二叉樹的C++編程，進(jìn)行熵編碼。實(shí)驗(yàn)步驟步驟①：按照符號出現(xiàn)概率大小的順序?qū)Ψ栠M(jìn)行排序。步驟②：把概率最小的兩個(gè)符號組成一個(gè)節(jié)點(diǎn)P1。步驟③：重復(fù)步驟②，得到節(jié)點(diǎn)P2，P3，P4，……，PN，形成一棵樹，其中的PN稱為根節(jié)點(diǎn)。步驟④：從根節(jié)點(diǎn)PN開始到每個(gè)符號的樹葉，從上到下標(biāo)上0(上枝)和1(下枝)，至于哪個(gè)為1哪個(gè)為0則無關(guān)緊要，但通常把概率大的標(biāo)成1，概率小的標(biāo)成0。步驟⑤：從根節(jié)點(diǎn)PN開始順著樹枝到每個(gè)葉子分別寫出每個(gè)符號的代碼。實(shí)驗(yàn)程序設(shè)計(jì)輸入字符，定義三個(gè)字符串，輸入字符串到words數(shù)組，并且求得其長度length。charwords[500],wds[500],wd[500];//定義三個(gè)字符串，長度都不超過500cin>>words;//輸入字符串intlength,len,m;length=strlen(words);//計(jì)算words字符串長度對words字符串進(jìn)行從小到大冒泡排序，并且將words中的元素全部賦給wds字符串。voidmaopao(charwd[],intlen)//函數(shù)冒泡排序{inti,j;chart;for(j=0;j<=len-1-1;j++) for(i=0;i<len-j-1;i++) {if(wd[i]>wd[i+1]){t=wd[i];wd[i]=wd[i+1];wd[i+1]=t;} }}主函數(shù)：maopao(words,length);//定義冒泡函數(shù)cout<<words<<'\n';for(inti=0;i<=length;i++)//將words中的內(nèi)容賦給wds{wds[i]=words[i];}將已經(jīng)排序好的字符串中同種字符刪除，使該字符在字符串中只剩下一個(gè)。得到wds的字符串長度len。voidtypedelete(char*a1,intlen)//刪除字符串中的同類字符使該字符只剩一個(gè){while(*a1){ if(*a1==*(a1+1)) {strcpy(a1,a1+1); continue; } a1++;}}主函數(shù)：typedelete(wds,length);//定義同類刪除函數(shù)cout<<wds<<'\n';//輸出排序好且一組相異的字符串wdslen=strlen(wds);//字符串wds的長度4、定義兩個(gè)數(shù)組entr1、entr2，分別用于存放輸入字符串words中出現(xiàn)每個(gè)字符的頻率與頻數(shù)。定義log2函數(shù)用于計(jì)算熵。doublelog2(doublex)//定義log2函數(shù)計(jì)算熵值{doubley;y=log10(x)/log10(2);returny;}主函數(shù)：doubleentr1[500]={0,0,0};//定義一個(gè)數(shù)組，存放每個(gè)字母出現(xiàn)的頻率intentr2[500]={0,0,0};//定義一個(gè)數(shù)組，存放每個(gè)字母出現(xiàn)的頻數(shù)，即為權(quán)值doubleentropy=0;//定義熵，即平均碼長intj;for(i=0;i<len;i++)for(j=0;j<length;j++){if(wds[i]==words[j]){entr2[i]++;}//將每個(gè)字母出現(xiàn)地頻數(shù)存放在entr2[]中}for(i=0;i<len;i++){entr1[i]=(double)entr2[i]/length;}//計(jì)算頻率i=0;while(i<len){entropy+=entr1[i]*(log2(1/entr1[i]));//利用定義的log2函數(shù)計(jì)算熵i++;}for(i=0;i<len;i++){cout<<entr1[i]<<'\t';}cout<<'\n';for(i=0;i<len;i++){cout<<entr2[i]<<'\t';}cout<<'\n';cout<<"平均碼長,即熵為entropy="<<entropy<<'\n';//到此主要是為了計(jì)算熵的值，也為霍夫曼編碼做鋪墊。定義一個(gè)二叉樹（huffman）結(jié)構(gòu)體，包含了權(quán)值、父節(jié)點(diǎn)、左右子節(jié)點(diǎn)、狀態(tài)值、編碼。structhuffmantree{intwei;//權(quán)值intprt;//父節(jié)點(diǎn)intlch;//左子節(jié)點(diǎn)intrch;//右子節(jié)點(diǎn)inttmp;//中間變量，tmp=0還未進(jìn)行遍歷tmp=1已近進(jìn)行過向左遍歷tmp=2已經(jīng)進(jìn)行過左右遍歷向上找到節(jié)點(diǎn)charcode[N];charcode[N];};定義2*len個(gè)huffman樹，調(diào)用huffman函數(shù)，利用結(jié)構(gòu)體中的父節(jié)點(diǎn)、左右節(jié)點(diǎn)，將整個(gè)huffman樹構(gòu)造出來。其次進(jìn)行huffman編碼，通過判斷tmp這個(gè)狀態(tài)值，二叉樹形成最優(yōu)二叉樹。最后進(jìn)行編碼的輸出。voidselect(huffmantree*HT,intn,int&i,int&j)//該函數(shù)用于找最小值和次小值的位置{intk;i=1;while(HT[i].prt!=0){i++;}for(k=i+1;k<=n;k++){if((HT[k].prt==0)&&(HT[k].wei<HT[i].wei))i=k;}j=1;while((j==i)||(HT[j].prt!=0)){j++;}for(k=j+1;k<=n;k++){if((HT[k].prt=0)&&k!=i&&HT[k].wei<HT[j].wei)j=k;}}voidhuffman(intw[],huffmantree*HT,intn)//w存放n個(gè)字符的權(quán)值{intm=2*n-1;inti,k,j;huffmantree*p=0;for(p=HT+1,i=1;i<=m;i++,p++){HT[i].prt=0;HT[i].lch=0;HT[i].rch=0;}for(p=HT+1,i=1;i<=n;i++,p++){HT[i].wei=w[i-1];}for(p=HT+n+1,i=n+1;i<=m;i++,p++){HT[i].wei=0;}for(k=n+1;k<=m;k++){select(HT,k-1,i,j);//找最小值和次小值的位置HT[i].prt=k,HT[j].prt=k;//找到ij的父節(jié)點(diǎn)付給kHT[k].lch=i,HT[k].rch=j;//父節(jié)點(diǎn)的左右指針分別指向i,jHT[k].wei=HT[i].wei+HT[j].wei;}}voidhuffmancoding(huffmantree*HT,intn)//n個(gè)葉子結(jié)點(diǎn)的huffman編碼從根節(jié)點(diǎn)開始編碼{intBT=2*n-1;intm=BT;intl,r,p;chars1[100]="0",s2[100]="1";for(inti=0;i<=m;i++)//中間變量賦初值{HT[i].tmp=0;}strcpy(HT[m].code,"");while(1){l=HT[BT].lch;r=HT[BT].rch;p=HT[BT].prt; if(p==0&&HT[BT].tmp==2) break; if(l==0||r==0) {HT[BT].tmp=2;}//如果是葉子結(jié)點(diǎn)則給中間變量賦值2向上返回一節(jié)結(jié)點(diǎn) if(HT[BT].tmp==0)//未進(jìn)行過遍歷，開始向左遍歷 {HT[BT].tmp=1;//已經(jīng)進(jìn)行過向左遍歷 l=HT[BT].lch; strcpy(HT[l].code,HT[BT].code); strcat(HT[l].code,s1); BT=l; } elseif(HT[BT].tmp==1) {HT[BT].tmp=2; r=HT[BT].rch; strcpy(HT[r].code,HT[BT].code); strcat(HT[r].code,s2); BT=r; } elseif(HT[BT].tmp==2) {p=HT[BT].prt;BT=p;}}}voidprint(huffmantreeHT[],intn)//總共n個(gè)葉子節(jié)點(diǎn){inti;cout<<"源碼："<<endl;for(i=1;i<=n;i++) cout<<HT[i].wei<<endl;cout<<"Huffman編碼："<<endl;for(i=1;i<=n;i++){cout<<HT[i].code<<endl;}}主函數(shù)：m=2*len-1;huffmantree*HT;HT=newhuffmantree[m+1];huffman(entr2,HT,len);huffmancoding(HT,len);print(HT,len);deleteHT;實(shí)驗(yàn)結(jié)果如圖，輸入字符串“ccaaZZAD.,”,之后的結(jié)果依次為words的長度、冒泡后的words、wds、刪除同類字符的wds、