摘  要： 提出了一種改進(jìn)的四進(jìn)制哈夫曼樹的生成算法，通過分析算法的平均碼長和編碼效率，論證了算法相對于傳統(tǒng)的四進(jìn)制算法的優(yōu)點(diǎn)。并用C語言分別實(shí)現(xiàn)兩種算法，進(jìn)行了壓縮比和壓縮時(shí)間的比較，證明了改進(jìn)算法在壓縮比和壓縮速度上的提升。
關(guān)鍵詞： 數(shù)據(jù)壓縮；哈夫曼；四叉樹

    數(shù)據(jù)壓縮是計(jì)算機(jī)科學(xué)中的一項(xiàng)重要技術(shù)[1]。Huffman算法作為通用數(shù)據(jù)壓縮算法[2]已經(jīng)成為大多數(shù)數(shù)據(jù)壓縮程序的基礎(chǔ)[3]。目前應(yīng)用最多的是二進(jìn)制Huffman算法。由于四進(jìn)制Huffman算法每次可以處理2 bit的數(shù)據(jù)，相對于二進(jìn)制有占用內(nèi)存空間小、解碼速度快的優(yōu)點(diǎn)，因此在一些應(yīng)用場合用四進(jìn)制Huffman算法比二進(jìn)制Huffman算法可以獲得更好的性能。
    Huffman樹是一種帶權(quán)路徑WPL(Weighted Path Length)最小的樹。衡量一棵Huffman樹性能的重要指標(biāo)有平均碼長和編碼效率[4]。
    
1 四進(jìn)制Huffman算法
    傳統(tǒng)的四進(jìn)制Huffman算法與二進(jìn)制Huffman算法類似，都是采用遞歸調(diào)用的方法，區(qū)別是二進(jìn)制Huffman每次取最小的2個(gè)節(jié)點(diǎn)構(gòu)造新節(jié)點(diǎn)，四進(jìn)制是取最小的4個(gè)節(jié)點(diǎn)構(gòu)造新節(jié)點(diǎn)。傳統(tǒng)的四進(jìn)制Huffman算法過程如下：
    (1)將字符按照概率由大到小的順序排列；建立未處理節(jié)點(diǎn)集合；
    (2)將4個(gè)最小的概率組合作為一個(gè)新的節(jié)點(diǎn)；將4個(gè)最小的概率從未處理節(jié)點(diǎn)集合中去除，并加入新組合的節(jié)點(diǎn)，重新排好；
    (3)重復(fù)步驟(2)直到剩余一個(gè)根節(jié)點(diǎn)為止。
    這種算法有一種情況沒有考慮到：當(dāng)最后剩余的未編碼節(jié)點(diǎn)不是4個(gè)的時(shí)候，就會(huì)產(chǎn)生在根部的子節(jié)點(diǎn)不是4個(gè)的情況，也就是權(quán)重最小的節(jié)點(diǎn)沒有使用，而使用了權(quán)重最大的節(jié)點(diǎn)。例如，有12個(gè)待編碼字符（A，B，C，D，E，F(xiàn)，G，H，I，J，K，L)，其概率分別是(0.23，0.22，
0.13，0.12，0.07，0.06，0.05，0.04，0.03，0.025，0.015，0.01)，傳統(tǒng)算法生成的四進(jìn)制Huffman樹如圖1所示。

    雖然改進(jìn)后的Huffman樹的層數(shù)多了1層，但是平均碼長卻小了，編碼效率比改進(jìn)前的Huffman樹提高了10.64%。同時(shí)由于壓縮比提高，需要輸出的數(shù)據(jù)和壓縮耗時(shí)也會(huì)相應(yīng)地減少。
    在實(shí)際情況中，如果不能構(gòu)成完全4個(gè)子節(jié)點(diǎn)的個(gè)數(shù)為0，即樹中每個(gè)父節(jié)點(diǎn)都有4個(gè)子節(jié)點(diǎn)，則改進(jìn)前后的算法結(jié)果一樣。
3 算法比較
    用C語言實(shí)現(xiàn)了改進(jìn)前后的四進(jìn)制Huffman壓縮算法，隨機(jī)選取了7個(gè)不同類型的文件，并用隨機(jī)數(shù)產(chǎn)生了由256個(gè)節(jié)點(diǎn)構(gòu)成的文件，分別壓縮這8個(gè)文件，比較它們的壓縮比和壓縮時(shí)間，比較結(jié)果如表1所示。

    由表1可以看出，在不能構(gòu)成完全4個(gè)子節(jié)點(diǎn)的個(gè)數(shù)不為0的情況下，改進(jìn)后的算法比傳統(tǒng)的算法在壓縮比上有較大提高，壓縮速度也提高很多；在不能構(gòu)成完全4個(gè)子節(jié)點(diǎn)的個(gè)數(shù)為0的情況下，兩者的壓縮比沒有差別，壓縮速度差別也不大；而且兩種壓縮算法的解壓縮過程完全相同。
    Huffman算法是一種有效的無損壓縮算法，針對傳統(tǒng)四進(jìn)制Huffman算法的不足，提出了改進(jìn)的四進(jìn)制Huffman算法。主要改進(jìn)了在不能構(gòu)成完全4個(gè)子節(jié)點(diǎn)的個(gè)數(shù)不為0的情況下的壓縮效率和壓縮速度。這種改進(jìn)不論出現(xiàn)哪種情況，用算法生成的四進(jìn)制Huffman樹是平均碼長最短、編碼效率最高的四進(jìn)制Huffman樹。最后將兩種算法用8個(gè)大小不同的文件進(jìn)行了對比，實(shí)驗(yàn)表明，改進(jìn)的算法在壓縮比和壓縮速度上有絕對的優(yōu)勢。
參考文獻(xiàn)
[1] 孫學(xué)琛，李新潔.哈夫曼樹的圖形化算法設(shè)計(jì)[J].山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，22(6)：108-110.
[2] SALOMON D.數(shù)據(jù)壓縮原理與應(yīng)用(第2版)[M].吳樂南，譯.北京：電子工業(yè)出版社，2003.
[3] 張鳳林，劉思峰.Huffman*：一個(gè)改進(jìn)的Huffman數(shù)據(jù)壓縮算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(2)：73-74.
[4] 吳家安.數(shù)據(jù)壓縮技術(shù)及應(yīng)用[M].北京：科學(xué)技術(shù)出版社，2009.