實(shí)驗(yàn)2 huffman編碼對(duì)英文文本的壓縮和解壓縮

1、《信息論與編碼》《信息論與編碼》實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告班級(jí)：學(xué)號(hào)：姓名：完成時(shí)間：2011年6月2日二叉樹(shù)存放在連續(xù)空間里（靜態(tài)鏈表），空間的每個(gè)結(jié)點(diǎn)內(nèi)仍有左子樹(shù)、右子樹(shù)、雙親等指針。3.huffman_c使用CanonicalHuffman編碼，同時(shí)對(duì)huffman_b的存儲(chǔ)結(jié)構(gòu)進(jìn)行改造，將二叉樹(shù)存放在連續(xù)空間tree里，空間的每個(gè)結(jié)點(diǎn)類型都和結(jié)點(diǎn)權(quán)值的數(shù)據(jù)類型相同，空間大小為2num，tree[0]未用，tree[1..num]是每個(gè)元素

2、的權(quán)值，生成Huffman后，tree[1..2num1]中是雙親結(jié)點(diǎn)索引。4.huffman_d在huffman_c的基礎(chǔ)上，增加預(yù)先排序的功能先用QuickSt算法對(duì)所有元素的權(quán)值從小到大排序，這樣，排序后最前面的兩個(gè)元素就是最小的一對(duì)元素了。我們可以直接將它們挑出來(lái)，組合成一個(gè)子樹(shù)。然后再子樹(shù)的權(quán)值用折半插入法插到已排序的元素表中，保證所有結(jié)點(diǎn)有序。為了保證初始元素的順序不變，我們另外使用了一個(gè)索引數(shù)組，所有排序中的交換操作都是在

3、索引數(shù)組中進(jìn)行的。5.huffman_e在huffman_d的基礎(chǔ)上，將索引數(shù)組放在tree的內(nèi)部。為編碼方便，將元素權(quán)值放在tree[num..2num1]處。將tree[0..num1]作為索引數(shù)組。排序改為從大到小。對(duì)索引數(shù)組排序后，每次從最后選出2個(gè)最小值，相加后的結(jié)點(diǎn)權(quán)值放在索引數(shù)組最后，結(jié)點(diǎn)索引放在索引數(shù)組中倒數(shù)第2個(gè)位置，然后索引數(shù)組大小減1，并將最后一個(gè)索引值插入到前面的有序表中，保證索引數(shù)組仍然有序。6.huffman

4、_f在huffman_e的基礎(chǔ)上，將排序改為利用堆排序原理選擇最小的兩個(gè)權(quán)值。也即，將所有元素的權(quán)值組織成堆后，每次堆內(nèi)的根結(jié)點(diǎn)就是最小值了。每取出一個(gè)根結(jié)點(diǎn)后，就把堆尾元素調(diào)到根結(jié)點(diǎn)重建堆。取出兩個(gè)最小值合并成一個(gè)子樹(shù)后，再把子樹(shù)作為葉子結(jié)點(diǎn)放到堆中，并讓其上升到合適的位置，保持堆性質(zhì)不變。因?yàn)槊看尾槐赝瓿烧麄€(gè)排序過(guò)程，而只是組織成堆，因此，這種方法要比使用快速排序更快。上述算法參考了mg1.2.1中Huffman編碼的實(shí)現(xiàn)，見(jiàn):ww

5、w.cs.mu.oz.aumg7.huffman_g當(dāng)元素權(quán)值已經(jīng)有序時(shí)，可以使用A.Moffat和J.Katajainen設(shè)計(jì)的在權(quán)值數(shù)組內(nèi)部構(gòu)建Huffman的方法。A.Moffat和J.Katajainen對(duì)該算法的描述見(jiàn):www.cs.mu.oz.au~alistairabstractsinplace.html8.huffman_h在huffman_f的基礎(chǔ)上，增加限制碼長(zhǎng)的功能。限制碼長(zhǎng)的算法參考了zlib1.1.4中構(gòu)造限制