哈夫曼編碼實(shí)驗(yàn)報(bào)告

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

2、造：weight 為輸入的頻率數(shù)組，把其中的值賦給依次建立的 HT Node 對(duì)象中的 data 屬性 , 即每一個(gè) HT Node 對(duì)應(yīng)一個(gè)輸入的頻率。然后根據(jù)data 屬性按從小到大順序排序， 每次從data 取出兩個(gè)最小和此次小的 HT Node ，將他們的 data 相加，構(gòu)造出新的 HTNode 作為 他們的父節(jié)點(diǎn)，指針pare nt ， leftchild ， rightchild 賦相應(yīng)值。在把這個(gè)新的節(jié)點(diǎn)插入最小堆。 按此步驟可以構(gòu)造構(gòu)造出一棵哈夫曼樹。通過已經(jīng)構(gòu)造出的哈夫曼樹，自底向上，由頻率節(jié)點(diǎn)開始向上尋找pare nt, 直到 pare nt為樹的頂點(diǎn)為止。這樣， 根據(jù)每

3、次向上搜索后，原節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子還是右孩子， 來記 錄 1 或 0, 這樣，每個(gè)頻率都會(huì)有一個(gè)01 編碼與之唯一對(duì)應(yīng)，并且任何編碼沒有前部分是同其他完整編碼一樣的。6、 實(shí)驗(yàn)流程 初始化，統(tǒng)計(jì)文本文件中各字符的個(gè)數(shù)作為權(quán)值， 生成哈夫曼樹； 根據(jù)符號(hào)概率的大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序； 把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)； 重復(fù)步驟（ 2 ）（3 ），直到概率和為1 ； 從根節(jié)點(diǎn)開始到相應(yīng)于每個(gè)符號(hào)的 樹葉”概率大的標(biāo)“0”概率小的標(biāo)“1 ； 從根節(jié)點(diǎn)開始，對(duì)符號(hào)進(jìn)行編碼； 譯碼時(shí)流程逆向進(jìn)行，從文件中讀出哈夫曼樹， 并利用哈夫曼樹將編碼序列解碼。七、 實(shí)驗(yàn)程序#in clude #in

4、 clude #in clude #in clude using n amespace std;typedef struct / 節(jié)點(diǎn)結(jié)構(gòu)char data;/記錄字符值long int weight; 記錄字符權(quán)重un sig ned int pare nt,lchild,rchild;HTNode,*Huffma nTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedef char * *HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表中選擇 pare nt 不為 0void Select(HuffmanTree &HT,int i,int &s1,int &s2)/ 在 HT1.t且權(quán)值

5、最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為 si 和 s2s1=0;s2=0;int n1=30000, n2=30000;for(i nt k=1;k=i;k+)if(HTk.pare nt=O)if(HTk.weight n1)n2=n1; n 仁 HTk.weight;s2=s1; s1=k;elseif(HTk.weight n2)n 2=HTk.weight;s2=k;將要編碼的字符串存入void Huffma nCodi ng(Huffma nTree &H T,Huffma nCode & HC,i nt n)/ 空樹中ifstream fin 1(zifu.txt);ifstream fin

6、 2(weight.txt);if(n=1)return;int m=2* n-1;int i;HT=new HTNodem+1;char *zifu;int *weight;zifu= new char n+1;weight =new intn+1;for(i=1;i=n;i+) 將待編碼的字符放在 zifu 數(shù)組中char ch;ch=fi n1.get();zifui=ch;for(i=1;iweigh ti;for( i=1;i=n ;i+)HTi.data=zifui;HTi.weight=weighti;for(i=n+1;i=m;i+)HTi.data=;for(i=1;i=m;

7、i+)HTi.pare nt=HTi.lchild=HTi.rchild=O;for(i=n+1;i=m;+i)int s1,s2;Select(HT,i-1,s1,s2);HTs1.pare nt=i;HTs2.pare nt=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(Huffma nCode)malloc( n+1)*sizeof(char*); 開辟一個(gè)求編碼的工作空間char *cd;cd=(char *)malloc(n*sizeof(char); / 開辟空間存放權(quán)值cdn-1=0;fo

8、r(i=1;i=n ;i+)int start =n-1;int c,f;for( c=i, f=HTi.parent;f!=O;c=f,f=HTf.parent) / 從葉子到根逆向求編碼if(HTf.lchild=c)cd-start=0; / 若是左孩子編為 Oelsecd-start=1 ：/若是右孩子編為1HCi=(char *)malloc(n-start)*sizeof(char);/ 為第 i 個(gè)編碼分配空間strcpy(HCi,&cdstart); delete cd;/釋放工作空間void prin tHuffma nTree(Huffma nTree HT,i nt n)

9、 ofstream fout(hfmtree.txt);coutNUMdatalchild rchlide ndl;for(i nt i=1;i=2* n-1;i+)/ 顯示有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的編碼表將對(duì)應(yīng)字符的的哈弗曼樹存入weightparentfoutHTi.weightsetw(3)HTi.pare ntsetw (3) HTi.lchildsetw(3)HTi. rchilde ndl;coutisetw(5)HTi.datasetw(3)HTi.weightsetw (3) HTi.pare ntset w(3)HTi.lchildsetw (3) HTi.rchilde

10、 ndl;void printHuffmanCoding(HuffmanTreeHT,HuffmanCode HC,int n) 輸出字符的對(duì)應(yīng)哈弗曼編碼并存入code.txt 文件coutHuffma n code is:e ndl;ofstream fout(code.txt);for(i nt i=1;i=n ;i+)coutHTi.data ;cout(HCi)e ndl;fout(HCi)e ndl;void code_file(HuffmanTree HT,HuffmanCode HC,int n)/ 對(duì)文件 tobetran.txt 進(jìn)行編碼，并將編碼存入 codefile 文件

11、中ifstream fin (tobetra n. txt);ofstream fout(codefile.txt);vector a;char ch;while(ch=fi n.get()!=*)a.push_back(ch);cout 待編碼的字符串為： for(i nt k=O;ka.size();k+) coutak;coute ndl;coutn 編碼結(jié)果 :endl;for(i nt i=0;ia.size();i+)for(i nt j=1;j=n ;j+)if(ai=HTj.data) foutHCj; break;fin. close();fout.close();void

12、Decodi ng(Huffma nTree HT,Huffma nCode HC,i nt n) 進(jìn) 打開 codefile 文件并對(duì)文件內(nèi)容 行譯碼int const m=2* n-1;ifstream fin (codefile.txt);ofstream fout(textfile.txt); vector a;for(char c;fi n c;)a.push_back(c);int coun t=0;for(i nt k=0;ka.size();k+)coutak;coun t+;if(cou nt%50=0) coute ndl;int i=0;int p;/用 p 來記住 m

13、的值coute ndl;coutn 譯碼結(jié)果： endl;while(ia.size()p=m;/從哈弗曼數(shù)的根開始遍歷while(HTp.lchild)11if(ai=1) p=HTp.rchild; else p=HTp.lchild; i+;foutHTp.data;coutHTp.data; void mai n()int n;cout?但夾DebugLexeI：一IIill 1010 IHHH00 萌HHS 1011 10 110011100601 naai 0110 1100801MB 11000011 10111 until n Bill ieai1H0glM 110000108

14、1 00ie 00111101 00001 1100800 110001 iiaeeeieia 1000111100001011待編鳴的字符串為:I LOVE VOU編碼結(jié)果：B1101111011iLKU11100e0(ai011110eB1110HL00t)Hl譯碼培果:I LOUE YOU請(qǐng)按任意鍵繼續(xù).八、結(jié)果分析哈夫曼編碼是動(dòng)態(tài)變長編碼，臨時(shí)建立概率統(tǒng)計(jì)表和編碼樹。概率小的碼比較長，概率小的碼比較長。概率大的碼短，這樣把一篇文件編碼后，就會(huì)壓縮許多。從樹的角度看，哈 夫曼編碼方式是盡量把短碼都利用上。首先，把一階節(jié)點(diǎn)全都用上，如果碼字不夠時(shí)，然后，再從某個(gè)節(jié)點(diǎn)伸出若干枝，引出二階節(jié)點(diǎn)作為碼字，以此類推，顯然所得碼長最短，再根據(jù) 建立的概 率統(tǒng)計(jì)表合理分布和放置，使其平均碼長最短就可以得到最佳碼。九、實(shí)驗(yàn)總結(jié)