改进的四进制哈夫曼算法

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

大电流电感

请推荐非隔离无电感电源方案输入：180~240VAC输出：25V/400mA你的负载稳定吗 ？为甚一定要求无电感 ？

[开关电源]开关电源的反馈问题原图给出的电路，R3的下端接到s，而s不是开关高压吗，参考地不稳定，这样的反馈，能有效吗？而且当导通周期时，不会逆向损坏C5吗？然而事实证明这样的电路实际上是有效的，但是我理论上搞不清楚。 然后我觉得可以直接接输出端反馈（如我画的图），不知道为什么要搞一个一模一样的LDC电路作反馈。 。 。 请高手指点指点！顶顶，这个问题困扰我很久了啊，这次特地申请了账号来提问的，求大神回复浮驱buckS脚是整个控制IC的参考地，即反馈脚FB，电源脚FB的参考地。 C5的负

关于MOS VDS尖峰请教！如题：现有一款隔离DC-DC ,18Vdc-30Vdc输入，12V-2A输出。测得前端MOS VDS电压波形异常，尖峰也太高了。请教各位，帮忙找找原因！


这个你一定是推挽做的吧，闭环了，所以，搞100伏耐压的

注塑加工厂