霍夫曼编码实现方法的研究

摘要：在信息爆炸的今天，数据压缩的重要性不言而喻，基本过程有三步：建模表达、二次量化和熵编码。其中熵编码又称为冗余度压缩。而统计编码又是熵编码的重要内容，其主要包括霍夫曼（huffman）编码、游程编码、二进制信源编码、算术编码、lzw编码等。本文以huffman编码作为熵编码的一种代表，介绍关于huffman编码的具体实现方法。 关键词：huffman编码；二叉树；权值

中图分类号：g2.0？摇 文献标志码：a ？摇文章编号：1674-9324（2013）26-0248-02 一、引言

1.数值传输系统模型如图1所示。

2.信源编码：主要是解决有效性的问题。通过对信源的压缩、扰乱、加密等一系列处理，力求用最少的数码传递最大的信息量，使信号更适宜传输。

3.数据压缩：就是以最少的数码表示信源所发的信号，减少容纳给定消息集合或数据采样集合的信号空间。 二、统计编码

对于各种信源都通用的可逆压缩（无失真编码）方法，因为大多数计算机文件都不允许在压缩过程中丢失信息。这类方法主要利用信息或信息序列出现的概率的分布特性，注重寻找概率与码字长度问题的最优匹配，这叫做统计编码或概率匹配编码。而霍夫曼

（huffman）编码就是其中具有代表性的一种编码方案[1]。 三、霍夫曼（huffman）编码原理

huffman编码是1952年为文本文件而建立的，是一种统计编码。它完全依据字符出现的概率来构造平均长度最短的异字头码字，属于无损压缩编码。huffman编码的码长是变化的，对于出现概率高的信息，编码的长度较短；而对于出现概率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度[2]。方法、步骤：（1）将信号源的符号出现的概率（在此称为权值）{w1，w2，...，wn}构造成n棵二叉树集合f={t1，t2，...，tn}，其中每棵二叉树ti中只有一个带权为wi的根结点，其左右子树均为空。（2）在f中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。（3）在f中删除这两棵树，同时将新得到的二叉树加入f中。（4）重复（2）和（3），直到f只含一棵树为止。这棵树便是霍夫曼（huffman）树。（5）在合并中约定权值小的根结点在左子树上，权值大的在右子树上。然后在每个左分支上标记为“0”，右分支上标记为“1”。最后记录从霍夫曼（huffman）树的根结点到每个叶子结点所经过的分支上的“0”或“1”的序列，从而得到每个符号的huffman编码。[3]

上述编码的平均码字长度r=（2+2+2+3+3）/5=2.4。说明：由于“1”和“0”的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。

四、huffman编码的具体实现

//——-以下部分代码是在huffman树上从根逆向求每个字符的huffman编码——-hc=（huffmancode）malloc（（n+1）*sizeof（char*））；

cd=（char*）malloc（n*sizeof（char））；cdn-1]=“.parent；f！=0；c=f，f=htf].parent）

if（htf].lchild==c）cd——start]=“0”；elsecd——start]=“1”；

hci]=（char*）malloc（n-start）*sizeof（char））； strcpy（hci]，&cdstart]）； }free（cd）； }//huffmancoding 五、结论

huffamn编码的实现方法有很多种，本文只是概述了基于数据结构的huffman编码的算法思想。

虽然huffman编码优点非常突出，但通过作者的研究发现，在具体的实现过程中，其局限性也不容忽视。因此，在今后对huffman编码的研究与应用中，应该扬长避短，更好发挥此编码的自身优势。 参考文献：

[1]吴乐南.数据压缩[m].北京：电子工业出版社，2003. [2]严蔚敏，吴伟民.数据结构（c语言版）[m].北京：清华大学出版社，1997.

[3]王永刚.奇妙的二叉树[d].程序员，2003，（9）.