哈夫曼編碼實驗報告

1、實驗一哈夫曼編碼一、實驗?zāi)康?、掌握哈夫曼編碼原理；2、熟練掌握哈夫曼樹的生成方法；3、理解數(shù)據(jù)編碼壓縮和譯碼輸出編碼的實現(xiàn)。二、實驗要求實現(xiàn)哈夫曼編碼和譯碼的生成算法。三、實驗內(nèi)容先統(tǒng)計要壓縮編碼的文件中的字符字母出現(xiàn)的次數(shù)，按字符字母和空格出現(xiàn)的概率對其進行哈夫曼編碼，然后讀入要編碼的文件，編碼后存入另一個文件；接著再調(diào)出編碼后的文 件，并對其進行譯碼輸出，最后存入另一個文件中。五、實驗原理1、哈夫曼樹的定義：假設(shè)有 n個權(quán)值，試構(gòu)造一顆有 n個葉子節(jié)點的二叉樹，每個葉子帶 權(quán)值為wi,其中樹帶權(quán)路徑最小的二叉樹成為哈夫曼樹或者最優(yōu)二叉樹；2、哈夫曼樹的構(gòu)造：weight為輸入的頻率數(shù)組，

2、把其中的值賦給依次建立的HT Node對象中的data屬性,即每一個HT Node對應(yīng)一個輸入的頻率。然后根據(jù)data屬性按從小到大順序排序，每次從data取出兩個最小和此次小的HT Node ,將他們的data相加，構(gòu)造出新的 HTNode作為他們的父節(jié)點，指針parent , leftchild , rightchild賦相應(yīng)值。在把這個新的節(jié)點插入最小堆。 按此步驟可以構(gòu)造構(gòu)造出一棵哈夫曼樹。通過已經(jīng)構(gòu)造出的哈夫曼樹，自底向上，由頻率節(jié)點開始向上尋找parent,直到parent為樹的頂點為止。這樣， 根據(jù)每次向上搜索后，原節(jié)點為父節(jié)點的左孩子還是右孩子，來記錄1或0,這樣，每個頻率都會

3、有一個01編碼與之唯一對應(yīng)，并且任何編碼沒有前部分是同其他完整編碼一樣的。六、實驗流程 初始化，統(tǒng)計文本文件中各字符的個數(shù)作為權(quán)值，生成哈夫曼樹； 根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M行排序；把概率最小的兩個符號組成一個節(jié)點； 重復(fù)步驟(2) (3),直到概率和為1; 從根節(jié)點開始到相應(yīng)于每個符號的樹葉”，概率大的標(biāo)概率小的標(biāo) “1;” 從根節(jié)點開始，對符號進行編碼；譯碼時流程逆向進行，從文件中讀出哈夫曼樹，并利用哈夫曼樹將編碼序列解碼。七、實驗程序#include<iostream>#include<fstream> #include<iomanip>

4、#include<vector>using namespace std; typedef struct/ 節(jié)點結(jié)構(gòu)char data;記錄字符值long int weight;記錄字符權(quán)重unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;動態(tài)分配數(shù)組存儲哈夫曼樹typedef char * *HuffmanCode;/動態(tài)分配數(shù)組存儲哈夫曼編碼表void Select(HuffmanTree &HT,int i,int &s1,int &s2)/ 在 HT1t中選擇 parent 不為 0且權(quán)值最小的

5、兩個結(jié)點，其序號分別為si和s2s1=0;s2=0;int n1=30000,n2=30000;for(int k=1;k<=i;k+) if(HTk.parent=0)if(HTk.weight<n1) n2=n1; n1=HTk.weight;s2=s1; s1=k; elseif(HTk.weight<n2) n2=HTk.weight; s2=k; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)/將要編碼的字符串存入空樹中ifstream fin1("zifu.txt&quo

6、t;);ifstream fin2("weight.txt");if(n<=1)return;int m=2*n-1; int i;HT=new HTNodem+1;char *zifu;int *weight;zifu= new charn+1;weight=new intn+1;for(i=1;i<=n;i+)/將待編碼的字符放在 zifu數(shù)組中 char ch;ch=fin1.get(); zifui=ch; for(i=1;i<=n;i+)將帶編碼字符對應(yīng)的權(quán)值放在weight數(shù)組中fin2>>weighti; for( i=1;i&l

7、t;=n;i+) HTi.data=zifui;HTi.weight=weighti; for(i=n+1;i<=m;i+) HTi.data='' for(i=1;i<=m;i+) HTi.parent=HTi.lchild=HTi.rchild=0; for(i=n+1;i<=m;+i) int s1,s2;Select(HT,i-1,s1,s2);HTs1.parent=i; HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight; HC=(Huffman

8、Code)malloc(n+1)*sizeof(char*);開辟一個求編碼的工作空間char *cd; cd=(char *)malloc(n*sizeof(char); / 開辟空間存放權(quán)值 cdn-1='0' for(i=1;i<=n;i+) int start=n-1; int c,f;for( c=i, f=HTi.parent;f!=0;c=f,f=HTf.parent) / 從葉子到根逆向求編碼 if(HTf.lchild=c) cd-start='0' /若是左孩子編為0' elsecd-start='1' 若是右孩

9、子編為1HCi=(char *)malloc(n-start)*sizeof(char); / 為第 i 個編碼分配空間 strcpy(HCi,&cdstart);delete 口cd;/釋放工作空間/顯示有n個葉子結(jié)點的哈夫曼樹的編碼表將對應(yīng)字符的的哈弗曼樹存入"<<"weight"<<""<<"parent"<<"void printHuffmanTree(HuffmanTree HT,int n) ofstream fout("hfmtree.

10、txt");cout<<"NUM"<<""<<"data"<<""<<"lchild"<<" "<<"rchlid"<<endl;for(int i=1;i<=2*n-1;i+) fout<<HTi.weight<<setw(3)<<HTi.parent<<setw(3)<<HTi.lc

11、hild<<setw(3)<<HTi. rchild<<endl;cout<<i<<setw(5)<<HTi.data<<setw(3)<<HTi.weight<<setw(3)<<HTi.parent<<set w(3)<<HTi.lchild<<setw(3)<<HTi.rchild<<endl;void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n

12、)輸出字符的對應(yīng)哈弗 曼編碼并存入code.txt文件cout<<"Huffman code is:"<<endl;ofstream fout("code.txt");for(int i=1;i<=n;i+)cout<<HTi.data<<"-> "cout<<(HCi)<<endl;fout<<(HCi)<<endl;void code_file(HuffmanTree HT,HuffmanCode HC,int n)對文件

13、tobetran.txt 進行編碼，并將編碼存入codefile文件中ifstream fin("tobetran.txt");ofstream fout("codefile.txt");vector<char> a;char ch;while(ch=fin.get()!='*')a.push_back(ch);cout<<"待編碼的字符串為："for(int k=0;k<a.size();k+)cout<<ak;cout<<endl;cout<<&qu

14、ot;n 編碼結(jié)果："<<endl;for(int i=0;i<a.size();i+)for(int j=1;j<=n;j+)if(ai=HTj.data)fout<<HCj;break;fin.close();fout.close();打開codefile文件并對文件內(nèi)容void Decoding(HuffmanTree HT,HuffmanCode HC,int n)進行譯碼int const m=2*n-1;ifstream fin("codefile.txt");ofstream fout("texfile.

15、txt");vector<char> a;for(char c;fin>>c;) a.push_back(c);int count=0;for(int k=0;k<a.size();k+)cout<<ak;count+;if(count%50=0) cout<<endl;int i=0;int p;用p來記住m的值cout<<endl;cout<<"n 譯碼結(jié)果："<<endl; while(i<a.size()p=m;從哈弗曼數(shù)的根開始遍歷while(HTp.lchi

16、ld)if(ai='1') p=HTp.rchild; elsep=HTp.lchild; i+;fout<<HTp.data;cout<<HTp.data;void main()int n;cout<<"輸入權(quán)值個數(shù)：cin>>n;printf("n");HuffmanTree HT;HuffmanCode HC;HuffmanCoding(HT,HC,n);II.設(shè)置權(quán)值數(shù)值/哈夫曼樹HT/printHuffmanCoding(HT,HC,n);哈夫曼編碼表 HC 進行哈夫曼編碼 顯示編碼的字符7

17、顯不'要編碼的字符串，并把編碼值顯不'出來 譯碼并顯示譯碼后的字符串printf("n"); code_file(HT,HC,n); Decoding(HT,HC,n); printf("nn'n"); system("pause");T:Use riVAdmir istrjtorDeskto 野建文件夾De b Ligl.exthHuffman code Is：> 111A 一1010B > 100000C -> S00S0D 10110E > 010 F > 110011G &

18、gt; 1皿。血H > 0001I > 0110J > 1100001000K > 11060011L > 10111Cl > 11001F)I > Bill0 一> 1001P > 10S010 q > 1106001601R > 0010S > 0011I > 1101U > 00901U > 11QSQ&QW > 11001K 1100001010V > 100S11E > 1100001011待編碼的字符串為：1 LQUE ¥OU編碼結(jié)果:Bii0iiii0iiiie0iiiea000Bi0iiii0B0ina0i0BQ0i譯碼結(jié)果：I LOUE you請按任意鍵繼續(xù) . .八、結(jié)果分析哈夫曼編碼是動態(tài)變長編碼，臨時建立概率統(tǒng)計表和編碼樹。概率小的碼比較長，概率小的碼比較長。概率大的碼短，這樣把一篇文件編碼后，就會壓縮許多。從樹的角度看，哈 夫曼編碼方式是盡量把短碼都利用上。首先，把一階節(jié)點全都用上， 如果碼字不夠時，然后，再從某個節(jié)點伸出若干枝，