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

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

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

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