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

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

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

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