實驗報告-哈夫曼參考模板

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

2、棵完全二義樹，即樹中任意節(jié)點都有2個兒子。帶權值的結(jié)點都是葉子結(jié)點。權值越小的結(jié)點，其到根結(jié)點的路徑越長。所謂前綴碼是指，對字符集進行編碼時，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，比如常見的等長編碼就是前綴碼。所謂最優(yōu)前綴碼是指，平均碼長或文件總長最小的前綴編碼稱為最優(yōu)的前綴碼(這里的平均碼長相當于碼長的期望值)。哈夫曼編碼算法實現(xiàn)字申最優(yōu)前綴碼的生成，這是壓縮的一種方式，在實際生活中應用廣泛，一般采用貪心算法，二、問題的解決方案/算法選擇/設計思路。(1) 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二義樹To(2) 算法以|C|個葉結(jié)點開始，執(zhí)行|C|1次的“合并”運算后

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

4、點的權值之和。(3) 將新的二義樹加入到F中，刪除原兩棵根結(jié)點權值最小的樹；重復(2)和(3)直到F中只含一棵樹為止，這棵樹就是哈夫曼樹圖1在隊列中取最小的兩個數(shù)，根的權值是這兩個數(shù)的和，在將根的值帶回隊列中，在取最小的兩個數(shù)，重復進行，得到哈夫曼樹。記左子樹為0,右子樹為1,得到最優(yōu)前綴數(shù)。三、算法設計/問題求解中所遇到的問題及分析解決方案生成樹/*功能用丁生成哈夫曼樹*/huffmanctrHuffmanTree(intn)intm=2*n-1;/1n存儲葉子結(jié)點n+1m。儲樹的n-1個內(nèi)部結(jié)點huffmantree=(huffman)malloc(sizeof(huffmanNode)*

5、(m+1);/用于存儲哈夫曼樹各結(jié)點priorityqueueh;/用于存儲優(yōu)先隊歹U首地址inti;if(tree=NULL)(printf("outofspace");exit(-1);/*生成葉子結(jié)點*/for(i=1;i<=n;i+)printf("輸入d字母和權重："，i);scanf("%c%f",&treei.c,&treei.f);treei.i=i;treei.parent=treei.lchild=treei.rchild=-1;treei.code=NULL;getchar();/吸收回車/

6、*初始化優(yōu)先隊列*/h=initializePrioQueue(n,tree);/*生成n-1個內(nèi)部結(jié)點*/for(i=n+1;i<=m;i+)huffmanNodex,y,z;x=popPrioQueue(h);y=popPrioQueue(h);z.f=x.f+y.f;乙Ichild=x.i;z.rchild=y.i;z.parent=-1;乙i=i;treex.i.parent=i;treey.i.parent=i;treei=z;pushPrioQueue(h,z);/*前綴碼生成*/for(i=1;i<=n;i+)char*c=(char*)malloc(sizeof(n

7、);intstart=n-1;intj=i;if(c=NULL)printf("outofspace");exit(-1);cn-1='0'while(treej.parent!=-1)if(treetreej.parent.lchild=j)c-start='0elsec-start='1j=treej.parent;/*給編碼申請空間*/treei.code=(char*)malloc(sizeof(char)*(n-start);strcpy(treei.code,c+start);/*釋放優(yōu)先隊列空間*/free(h->elem

8、ent);free(h);returntree;四、算法設計/問題求解特色及關鍵技術特點：隨機生成權重。貪心算法：二義樹T表示字符集C的一個最優(yōu)前綴碼，證明可以對T作適當修改后得到一棵新的二義樹T”，在T”中x和y是最深葉子且為兄弟，同時T”表示的前綴碼也是C的最優(yōu)前綴碼。設b和c是二義樹T的最深葉子，且為兄弟。設f(b)<=f(c),f(x)<=f(y)。由丁x和y是C中具有最小頻率的兩個字符，有f(x)<=f(b),f(y)<=f(c)。首先，在樹T中交換葉子b和x的位置得到T',然后再樹T'中交換葉子c和y的位置，得到樹T”。將原問題變?yōu)橐粋€相似的

9、、但規(guī)模更小的子問題、而后的每一步都是當前看似最佳的選擇。這種選擇依賴丁已做出的選擇，但不依賴丁未做出的選擇。/優(yōu)先隊列初始化voidpushPrioQueue(priorityqueueh,huffmanNodex)(inti;if(isFull(h)printf("隊列已滿n");return;for(i=+h->size;h->elementi/2.f>x.f;i/=2)h->elementi=h->elementi/2;/父結(jié)點向下移h->elementi=x;五、算法測試。冷母國蜥骨尚毋母MJ.母葺43舟BS?Irhldklnn

10、h妙II爐&寸11|。"*郭日nd-<-.一*|1！|.二二Ed*-t_-.r£fy至H.jL*-二i_-=言專一xk_He#=M二q二£<三村盤和廣-R的廣.我？柯SfiCM朋H0£768典觀觀W7y«n«MW畛金月廈nU41EIUEin眄四W麗MGHMM跚時牌tr/itiidKXH1SWH5點QHCHmxRWIHE里？mfr-Hntn+i亍=I-Hin+里?rr-HT里Wn*n-Hln-Huiniirtsir-s4-二更7.-T："茵呸町瀘?刷=1伍*1標忘苛看:勇蹴票:甄罅盤ML慧優(yōu)成原編當”-多也

11、卜輜！；：湖2123.ff?L貌史；LftfW傾蜀儼±ij.mwuiLiisum1is廚碼；fWMH以蜩十:XiiWtiK*耳疆研Im仍無岱漏儼；LMIfHixa短ife碼msneiiBeizttiitlwti，布:網(wǎng)儼EFE涮喙扁秒Hl朋二心N點J啟功1隔包-"嘰豎綜辨舌IEtM班I，yiVp.FL1,匝&亦;時miw】4nfi9-$tajgjfi©：ifnihi號心L最u啟啜編成:ieejr入墨蝙媽的田心趴訂1911mi1G0B010100130010111B13G1111拒LL二連It的烏*imHMlB«tHIR1WIUHAIA!ihea9

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