基于改进的四进制哈夫曼树生成算法研究

改进的四进制哈夫曼算法 数据压缩是计算机科学中的一项重要技术。Huffman算法作为通用数据压缩算法已经成为大多数数据压缩程序的基础。目前应用最多的是二进制Huffman算法，但是四进制Huffman算法由于每次可以处理2bit的数据，相对于二进制有占用内存空间小、解码速度快的优点，因此在一些应用场合用四进制Huffman算法比二进制Huffman算法可以获得更好的性能。 Huffman树是一种带权路径WPL（Weighted Path Length）最小的树。衡量一棵Huffman树性能的重要指标有平均码长和编码效率。传统的四进制Huffman算法与二进制Huffman算法类似，都是采用递归调用的方法，区别是二进制Huffman每次取最小的2个节点构造新节点，四进制是取最小的4个节点构造新节点。 传统的四进制Huffman算法过程如下： （1）将字符按照概率由大到小的顺序排列；建立未处理节点集合； （2）将4个最小的概率组合作为一个新的节点；将4个最小的概率从未处理节点集合中去除，并加入新组合的节点，重新排好； （3）重复步骤（2）直到剩余一个根节点为止。 然而，传统的四进制Huffman算法有一种情况没有考虑到：当最后剩余的未编码节点不是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所示。 为了解决这个问题，提出了一种改进的四进制哈夫曼树的生成算法。该算法通过分析算法的平均码长和编码效率，论证了算法相对于传统的四进制算法的优点。并用C语言分别实现两种算法，进行了压缩比和压缩时间的比较，证明了改进算法在压缩比和压缩速度上的提升。 改进后的Huffman树的层数多了1层，但是平均码长却小了，编码效率比改进前的Huffman树提高了10.64%。同时由于压缩比提高，需要输出的数据和压缩耗时也会相应地减少。在实际情况中，如果不能构成完全4个子节点的个数为0，即树中每个父节点都有4个子节点，则改进前后的算法都可以获得更好的性能。 改进的四进制哈夫曼算法可以获得更好的压缩比和压缩速度，提高了数据压缩的效率。