基于数据结构的Huffman编码实现方法的研究

1、 基于数据结构的Huffman编码实现方法的研究马潮,梁泽,张恩溯(兰州大学信息科学与工程学院,甘肃兰州 730000摘要:在信息爆炸的今天,数据压缩的重要性不言而喻,其基本过程有三步:建模表达、二次量化和熵编码。其中熵编码又称之为冗余度压缩。而统计编码又是熵编码的重要内容,其主要包括Huffman编码、游程编码、二进制信源编码、算术编码、LZW编码等等。本文是以Huffman编码作为熵编码的一种代表,介绍8种关于Huffman编码的具体实现办法。关键词 :链表;二叉树;权值;堆排序中图分类号:TN911 文献标识码:A1引言所示。(1 数字传输系统模型如图1 (2 信源编码 :主要是解决有效

2、性的问题。通过对信源的压缩、扰乱、加密等一系列处理,力求用最少的数码传递最大的信息量,使信号更适宜传输。因此,从信息论的角度看,信源编码的一个最主要目的,就是要解决数据的压缩问题,它构成了数据压缩的理论基础1。(3 数据压缩,就是以最少的数码表示信源所发的信号,减少容纳给定消息集合或数据采样集合的信号空间。近代信源编码的理论与方法,主要也以压缩数字编码的数码率为目标,因此在今天,“数据压缩”与“信源编码”已是两个具有相同含义的术语了。数据压缩的意义在于:a.较快地传输各种信源(降低信道占有费用时间域的压缩;b.在现有通信干线上开通更多的并行业务(如电视、传真、电话、可视图文频率域的压缩;c.降

3、低发射机功率能量域的压缩;d.紧缩数据存储容量(降低存储费用空间域的压缩1。2. 统计编码对于各种信源都通用的可逆压缩(无失真编码方法,因为大多数计算机文件都不允许在压缩过程中丢失信息。这类方法主要利用信息或信息序列出现概率的分布特性,注重寻找概率与码字长度间的最优匹配,这叫做统计编码或概率匹配编码。而Huffman编码就是其中具有代表性的一种编码方式1。3. 霍夫曼(Huffman编码原理霍夫曼(Huffman编码是1952年为文本文件而建立,是一种统计编码。它完全依据字符出现概率来构造平均长度最短的异字头码字,属于无损压缩编码。霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短

4、;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度3。步骤进行:(1将信号源的符号按照出现概率递减的顺序排列。(2将两个最小出现概率进行合并相加,得到的结果作为新符号的出现概率。(3重复进行步骤1和2直到概率相加的结果等于1为止。(4在合并运算时,概率大的符号用编码0表示,概率小的符号用编码1表示。(5记录下概率为1处到当前信号源符号之间的0,l序列,从而得到每个符号的编码。4. Huffman编码方法的理论基础:在变长编码中,对出现概率大的信源符号赋予短码字,而对于出现概率小的信源符号赋予长码字。如果码字长度严格按照所对应符号出现概率大小的逆序排列,

5、则编码结果平均码字长度一定小于任何其他排列方式。该定理可以用反证法证明1。下面以一个实例介绍Huffman编码方法2。如图2所示,我们对一组信源符号进行编码的步骤如下:(1 将信源符号按概率递减顺序排列;(2 把两个最小概率相加作为新符号的概率,并按(1重排;(3 重复(1、(2,直到概率为1;(4 在每次合并信源时,将合并的信源分别赋:0“和”1“(本例中概率大的赋“0”,概率小的赋“1”;(5 寻找从每一信源符号到概率为1出的路径,记录路径上的“1”和“0”;(6 写出每一符号的“1”、“0”序列(从树根到信源符号节点。 图2 Huffman 编码过程实例上述编码的平均码字长度:810.4

6、010.1830.1030.1040.0740.0640.0550.0452.61i ii R p =+= 应该指出的是,由于“1”与“0”的指定是任意的,故由上述过程编出的最佳码不是唯一的,但其平均码长是一样的,故不影响编码效率与数据压缩性能。5.Huffman 编码的八种具体实现方法:(1 huffman_a:使用链表结构生成Huffman 树的算法,这是最基本的实现方法,效率最低。(2 huffman_b:使用文献3中给出的算法,将二叉树存放在连续空间里(静态链表,空间的每个结点内仍有左子树、右子树、双亲等指针。(3 huffman_c:使用Canonical Huffman 编码,同时

7、对huffman_b 的存储结构进行改造,将二叉树存放在连续空间tree 里,空间的每个结点类型都和结点权值的数据类型相同,空间大小为2*num,tree0未用,tree1.num是每个元素的权值,生成Huffman 后,tree1.2*num-1中是双亲结点索引。(4 huffman_d:在huffman_c的基础上,增加预先排序的功能先用QuickSort算法对所有元素的权值从小到大排序,这样,排序后最前面的两个元素就是最小的一对元素了。我们可以直接将它们挑出来,组合成一个子树。然后再子树的权值用折半插入法插到已排序的元素表中, 保证所有结点有序。为了保证初始元素的顺序不变,我们另外使用了

8、一个索引数组,所有排序中的交换操作都是在索引数组中进行的。(5 huffman_e:在huffman_d的基础上,将索引数组放在tree的内部。为编码方便,将元素权值放在treenum.2*num-1处。将tree0.num-1作为索引数组。排序改为从大到小。对索引数组排序后,每次从最后选出2个最小值,相加后的结点权值放在索引数组最后,结点索引放在索引数组中倒数第2个位置,然后索引数组大小减1,并将最后一个索引值插入到前面的有序表中,保证索引数组仍然有序。(6 huffman_f:在huffman_e的基础上,将排序改为利用堆排序原理选择最小的两个权值。也即,将所有元素的权值组织成堆后,每次堆

9、内的根结点就是最小值了。每取出一个根结点后,就把堆尾元素调到根结点重建堆。取出两个最小值合并成一个子树后,再把子树作为叶子结点放到堆中,并让其上升到合适的位置,保持堆性质不变。因为每次不必完成整个排序过程,而只是组织成堆,因此,这种方法要比使用快速排序更快。(7 huffman_g:当元素权值已经有序时,可以使用 A. Moffat和J. Katajainen设计的在权值数组内部构建Huffman的方法4。(8 huffman_h:在huffman_f的基础上,增加限制码长的功能。其中限制长度的算法在tree.c的gen_bitlen(函数中4。6.结 论Huffman编码的实现方法还有很多种

10、。本文只是概要描述了8种基于数据结构的的算法。实际上,数据压缩的具体编码方式还有很多种,虽然Huffman编码的优点非常突出(编码效率非常高,有时几乎能达到100%;随着微电子技术的发展,Huffman编码已经做到许多单片的编码/解码集成电路芯片种,并成为许多国际标准中的主要技术之一,实现了用较低的处理代价,来换取昂贵的通信开销,但通过作者的研究,发现在具体的实现过程中,其局限性也不容忽视。主要有:(1 输入符号数受限于可实现的Huffman码表的尺寸。(2 由于事先不知道码长,因此译码复杂度较高。(3 需要知道输入符号集的频率分布(4 由于码长不等,还存在一个输入与输出的速率匹配问题。因此,

11、在今后对huffman编码的研究与应用过程中,应该扬其长、避其短,更好的发挥此编码自身的优势。参考文献1 吴乐南.数据压缩M.北京:电子工业出版社,2003.6.2 王咏刚.奇妙的二叉树D3 严蔚敏,吴伟民.数据结构(C语言版M.北京:清华大学出版社,1997.4 http:/www.cs.mu.oz.au/alistair/abstracts/inplace.htmlResearch on the Technique of Huffman EncodingBased on Data-structureChao Ma, Ze Liang, En-su Zhang(School of infor

12、mation science & engineering, Lanzhou University, Lanzhou, Gansu,China, 730000Abstract: Data compression is very important nowadays, and the key steps include the expression of model building, the secondary quantization and the entropy encoding which is also called redundancy reduction. The statistical encoding, such as Huffman encoding, run-length encoding, binary information source encoding, arithmetic encoding and LZW encoding, is main c