摘  要： 提出了一种改进的四进制哈夫曼树的生成算法，通过分析算法的平均码长和编码效率，论证了算法相对于传统的四进制算法的优点。并用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.