huffman無損壓縮編碼實驗報告

《huffman無損壓縮編碼實驗報告》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、無損壓縮編碼（huffman編碼）實驗報告作者:計一飛學號：1004210228學院(系):電子工程與光電技術學院專業(yè):電子信息工程題目:無損壓縮編碼指導老師：康其桔摘要本文介紹了無損壓縮編碼中的霍夫曼（huffman）編碼。Huffman編碼是可變字長編碼的一種，該方法完全依據(jù)字符出現(xiàn)概率來構造最優(yōu)二叉樹（huffman樹），故有時又稱為最佳編碼。在文中，我們使用C++語言進行編碼，從下到上進行了熵編碼。關鍵詞：huffman、最優(yōu)二叉樹、熵編碼、C++AbstractThehuffman(Huffman)codingofLosslessc

2、odingwereintroducedinthispaper.Huffmancodingisakindofvariable-word-lengthcoding.Themethodiscompletelybasedonthecharactersappearprobabilitytoconstructtheoptimalbinarytree(Huffmantree),soitissometimesreferredtoastheoptimalcoding.Inthispaper,weusec++languagetocode,frombottomto

3、topintheentropycoding.Keywords:huffman、optimalbinarytree、entropycoding、C++一、實驗目的1、理解無損壓縮編碼的優(yōu)點和意義。2、理解樹、二叉樹、huffman樹的概念。3、學會二叉樹的C++編程，進行熵編碼。二、實驗步驟步驟①：按照符號出現(xiàn)概率大小的順序?qū)Ψ栠M行排序。步驟②：把概率最小的兩個符號組成一個節(jié)點P1。步驟③：重復步驟②，得到節(jié)點P2，P3，P4，……，PN，形成一棵樹，其中的PN稱為根節(jié)點。步驟④：從根節(jié)點PN開始到每個符號的樹葉，從上到下標上0(上枝)和1(

4、下枝)，至于哪個為1哪個為0則無關緊要，但通常把概率大的標成1，概率小的標成0。步驟⑤：從根節(jié)點PN開始順著樹枝到每個葉子分別寫出每個符號的代碼。三、實驗程序設計1、輸入字符，定義三個字符串，輸入字符串到words數(shù)組，并且求得其長度length。charwords[500],wds[500],wd[500];//定義三個字符串，長度都不超過500cin>>words;//輸入字符串intlength,len,m;length=strlen(words);//計算words字符串長度2、對words字符串進行從小到大冒泡排序，并且將words

5、中的元素全部賦給wds字符串。voidmaopao(charwd[],intlen)//函數(shù)冒泡排序{inti,j;chart;for(j=0;j<=len-1-1;j++)for(i=0;iwd[i+1]){t=wd[i];wd[i]=wd[i+1];wd[i+1]=t;}}}主函數(shù)：maopao(words,length);//定義冒泡函數(shù)cout<

6、1、將已經(jīng)排序好的字符串中同種字符刪除，使該字符在字符串中只剩下一個。得到wds的字符串長度len。voidtypedelete(char*a1,intlen)//刪除字符串中的同類字符使該字符只剩一個{while(*a1){if(*a1==*(a1+1)){strcpy(a1,a1+1);continue;}a1++;}}主函數(shù)：typedelete(wds,length);//定義同類刪除函數(shù)cout<

7、1、entr2，分別用于存放輸入字符串words中出現(xiàn)每個字符的頻率與頻數(shù)。定義log2函數(shù)用于計算熵。doublelog2(doublex)//定義log2函數(shù)計算熵值{doubley;y=log10(x)/log10(2);returny;}主函數(shù)：doubleentr1[500]={0,0,0};//定義一個數(shù)組，存放每個字母出現(xiàn)的頻率intentr2[500]={0,0,0};//定義一個數(shù)組，存放每個字母出現(xiàn)的頻數(shù)，即為權值doubleentropy=0;//定義熵，即平均碼長intj;for(i=0;i

8、=0;j