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

1、算法分析與設(shè)計(jì)課程設(shè)計(jì)報(bào)告題 目：利用哈夫曼編碼算法實(shí)現(xiàn)字串最優(yōu)前綴碼的生成工作 專(zhuān) 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)： 姓 名： 指導(dǎo)教師： 2016年 5 月 25日6 / 8文檔可自由編輯打印一、問(wèn)題分析。哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。 哈夫曼樹(shù)注意事項(xiàng)： 初始森林中的n棵二叉樹(shù)，每棵樹(shù)有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，又是葉子 n個(gè)葉子的哈夫曼樹(shù)要經(jīng)過(guò)n-1次合并，產(chǎn)生n-1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹(shù)中共有2n-1個(gè)結(jié)點(diǎn)。 哈夫曼樹(shù)是嚴(yán)格的二叉樹(shù)，沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)。前綴碼：對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。

2、這種編碼稱(chēng)為前綴碼。表示最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)，即樹(shù)中任意節(jié)點(diǎn)都有2個(gè)兒子。帶權(quán)值的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。權(quán)值越小的結(jié)點(diǎn)，其到根結(jié)點(diǎn)的路徑越長(zhǎng)。所謂前綴碼是指，對(duì)字符集進(jìn)行編碼時(shí)，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，比如常見(jiàn)的等長(zhǎng)編碼就是前綴碼。所謂最優(yōu)前綴碼是指，平均碼長(zhǎng)或文件總長(zhǎng)最小的前綴編碼稱(chēng)為最優(yōu)的前綴碼（這里的平均碼長(zhǎng)相當(dāng)于碼長(zhǎng)的期望值）。哈夫曼編碼算法實(shí)現(xiàn)字串最優(yōu)前綴碼的生成，這是壓縮的一種方式，在實(shí)際生活中應(yīng)用廣泛，一般采用貪心算法，二、問(wèn)題的解決方案/算法選擇/設(shè)計(jì)思路。(1)哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹(shù)T。 (2)算法以|C

3、|個(gè)葉結(jié)點(diǎn)開(kāi)始，執(zhí)行|C|1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹(shù)T。 (3)假設(shè)編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹(shù)。一旦2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一棵新的樹(shù)，其頻率為合并的2棵樹(shù)的頻率之和，并將新樹(shù)插入優(yōu)先隊(duì)列Q。經(jīng)過(guò)n1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹(shù)，即所要求的樹(shù)T。生成哈夫曼樹(shù)（1）根據(jù)給定的n個(gè)權(quán)值w1,w2,.,wn構(gòu)造n棵二叉樹(shù)的集合F=T1,T2,.,Tn，其中Ti中只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，左右子樹(shù)為空； （2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值為最小的數(shù)作為左、右子樹(shù)以構(gòu)造一棵新的二叉樹(shù)

4、，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。 （3）將新的二叉樹(shù)加入到F中，刪除原兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)；（4）重復(fù)（2）和（3）直到F中只含一棵樹(shù)為止，這棵樹(shù)就是哈夫曼樹(shù)。圖1在隊(duì)列中取最小的兩個(gè)數(shù)，根的權(quán)值是這兩個(gè)數(shù)的和，在將根的值帶回隊(duì)列中，在取最小的兩個(gè)數(shù)，重復(fù)進(jìn)行，得到哈夫曼樹(shù)。記左子樹(shù)為0，右子樹(shù)為1，得到最優(yōu)前綴數(shù)。三、算法設(shè)計(jì)/問(wèn)題求解中所遇到的問(wèn)題及分析解決方案。 生成樹(shù)/*功能用于生成哈夫曼樹(shù)*/ huffman ctrHuffmanTree(int n) int m=2*n-1;/1n存儲(chǔ)葉子結(jié)點(diǎn)n+1m存儲(chǔ)樹(shù)的n-1個(gè)內(nèi)部結(jié)點(diǎn) huffman tree

5、=(huffman)malloc(sizeof(huffmanNode)*(m+1);/用于存儲(chǔ)哈夫曼樹(shù)各結(jié)點(diǎn) priorityqueue h;/用于存儲(chǔ)優(yōu)先隊(duì)列首地址 int i; if(tree=NULL) printf("out of space"); exit(-1); /*生成葉子結(jié)點(diǎn)*/ for(i=1;i<=n;i+) printf("輸入 %d 字母和權(quán)重:",i); scanf("%c%f",&treei.c,&treei.f); treei.i=i; treei.parent=treei.lc

6、hild=treei.rchild=-1; treei.code=NULL; getchar();/吸收回車(chē) /*初始化優(yōu)先隊(duì)列*/ h=initializePrioQueue(n,tree); /*生成n-1個(gè)內(nèi)部結(jié)點(diǎn)*/ for(i=n+1;i<=m;i+) huffmanNode x,y,z; x=popPrioQueue(h); y=popPrioQueue(h); z.f=x.f+y.f; z.lchild=x.i; z.rchild=y.i; z.parent=-1; z.i=i; treex.i.parent=i; treey.i.parent=i; treei=z; pu

7、shPrioQueue(h,z); /*前綴碼生成*/ for(i=1;i<=n;i+) char *c=(char *)malloc(sizeof(n); int start=n-1; int j=i; if(c=NULL) printf("out of space"); exit(-1); cn-1='0' while(treej.parent!=-1) if(treetreej.parent.lchild=j)c-start='0' else c-start='1' j=treej.parent; /*給編碼申請(qǐng)空

8、間*/ treei.code=(char *)malloc(sizeof(char)*(n-start); strcpy(treei.code,c+start); /*釋放優(yōu)先隊(duì)列空間*/ free(h->element); free(h); return tree; 四、算法設(shè)計(jì)/問(wèn)題求解特色及關(guān)鍵技術(shù)。 特點(diǎn)：隨機(jī)生成權(quán)重。 貪心算法：二叉樹(shù)T表示字符集C的一個(gè)最優(yōu)前綴碼，證明可以對(duì)T作適當(dāng)修改后得到一棵新的二叉樹(shù)T”，在T”中x和y是最深葉子且為兄弟，同時(shí)T”表示的前綴碼也是C的最優(yōu)前綴碼。設(shè)b和c是二叉樹(shù)T的最深葉子，且為兄弟。設(shè)f(b)<=f(c)，f(x)<=f(

9、y)。由于x和y是C中具有最小頻率的兩個(gè)字符，有f(x)<=f(b)，f(y)<=f(c)。首先，在樹(shù)T中交換葉子b和x的位置得到T'，然后再樹(shù)T'中交換葉子c和y的位置，得到樹(shù)T''。圖2將原問(wèn)題變?yōu)橐粋€(gè)相似的、但規(guī)模更小的子問(wèn)題、而后的每一步都是當(dāng)前看似最佳的選擇。這種選擇依賴(lài)于已做出的選擇，但不依賴(lài)于未做出的選擇。/優(yōu)先隊(duì)列初始化 void pushPrioQueue(priorityqueue h,huffmanNode x) int i; if(isFull(h) printf("隊(duì)列已滿(mǎn)n"); return; for

10、(i=+h->size;h->elementi/2.f>x.f;i/=2) h->elementi=h->elementi/2;/父結(jié)點(diǎn)向下移 h->elementi=x; 五、算法測(cè)試。圖3六、結(jié)論。根據(jù)各個(gè)字符的權(quán)值建立一顆哈夫曼樹(shù)制作哈夫曼編碼表，對(duì)數(shù)據(jù)文件的編碼過(guò)程是：依次讀人文件中的字符，在哈夫曼編碼表中找到此字符，將字符轉(zhuǎn)換為對(duì)應(yīng)的哈夫曼編碼。對(duì)壓縮后的數(shù)據(jù)文件進(jìn)行解碼則必須借助于哈夫曼樹(shù)，其過(guò)程是：依次讀人文件的二進(jìn)制碼，從哈夫曼樹(shù)的根結(jié)點(diǎn)出發(fā)，若當(dāng)前讀入0，則走向左孩子，否則走向右孩子。一旦到達(dá)某一葉子時(shí)便譯出相應(yīng)的字符。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。哈夫曼編碼是動(dòng)態(tài)變長(zhǎng)編碼，臨時(shí)建立概率統(tǒng)計(jì)表和編碼樹(shù)。概率小的碼比較長(zhǎng)，概率小的碼比較長(zhǎng)。概率大的碼短，這樣把一篇文件編碼后，就會(huì)壓縮許多。從樹(shù)的角度看，哈夫曼編碼方式是盡量把短碼都利用上。首先，把一階節(jié)點(diǎn)全都用上，如果碼字不夠時(shí)，然后，再?gòu)哪硞€(gè)節(jié)點(diǎn)伸出若干枝，引出二階節(jié)點(diǎn)作為碼字，以此類(lèi)推，顯然所得碼長(zhǎng)最短，再根據(jù)建立的概率統(tǒng)計(jì)表合理分布和放置，使其平均碼長(zhǎng)最短就可以得到最佳碼。該代碼缺少可視化，缺乏實(shí)用性，不具有成為優(yōu)秀代碼的資格。但該代碼的構(gòu)思獨(dú)特，思路清晰，具有簡(jiǎn)約明了等特征，頗具使用性。用取局部最優(yōu)的貪心算法，更簡(jiǎn)單的將問(wèn)