摘要：编码技术研究的一个重要方面是信源编码。文章介绍了日常生活、生产实践中的几种常见信源编码方法，如等长编码、香农编码、哈夫曼编码，另外还介绍了静态奇偶编码和动态的哈夫曼编码，重点是用程序算法来实现这些编码方法。通过对这几种最常见也是最基本的编码方法的介绍及程序实现，并对编码结果和算法的时间复杂性进行比较分析，使读者对信息论和数据结构知识有进一步的理解，认识到选择一种好的编码技术或者一个好的算法具有非常重要的现实意义。

关键词：编码技术；信源编码；动态哈夫曼编码；静态奇偶编码

中图分类号：TU757文献标识码：A文章编号：1009－2374(2009)12－0001－02

一、编码

(一)编码简介

我们处在一个信息飞速增长的时代，随着科技与经济的迅速发展，海量的信息进入了我们的生活，各种信息传输设备也随之发展，鉴于人们对信息传输有效性和可靠性的不断要求，如何正确而迅速的处理和传输数据就成为目前科学界急待解决的一大问题，因此，编码技术研究在人们生产生活中的重要性也日益显现。

(二)信源编码的意义

电路通常只有两中稳定状态：导通与阻塞、高电位与低电位，因此用二进制0、1来表示各种信息，这样实现起来比较容易，电路简单，成本低廉。而存贮在计算机中的形形色色的信息或数据，在本质上来讲都是一些“0”和“1”组成的序列。

计算机中普遍使用的ASCII码采用7位二进制数来表示字符，它实际是一种等长编码。在实际应用中，经常使用的字符比较集中，每个字符使用的频率相差很大，如果能根据信源中字符使用频率的高低不同，采用不同长度的二进制来表示字符，用短一些的编码来表示使用频率高的字符，而用相对长一些的编码来表示使用频率低的字符，很显然这样就可以直接减少数据存储和传输时的开销，同时也能对数据起到保护作用，而这也正式信源须要进行编码的原因和意义。

二、信源编码方法

(一)哈夫曼编码介绍

哈夫曼树又称最优树，是一类带权路径长度最短的树，在实际中有着广泛的应用。给出路径和路径长度的概念，在树形存贮结构中，一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的带权路径长度则是树中所有叶子结点的带权路径长度之和，通常记为WPL=w₁*l₁+…W_n*l_n，w_i表示该结点的权重，1_i表示该结点的路径长度。其中带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。哈夫曼树在解某些判定问题时往往可以得到最佳的判定算法。例如要判定一个班级学生的分数等级，共有差、中、好三等，可以通过哈夫曼编码来实现，如果判定过程需要反复的使用，而且每次的输入量很大，则需要考虑这一方法的质量问题，实际上，这三种成绩段的分布显然是不均匀的，假设其分布规律为：0～59分段占总数的5％、60～84分段占总数的60％、85～100分段各占总数的35％。则其中60％的人需要进行2次的比较、35％的人需要进行3次的比较才能得出结果，假设有100名同学的话，需要判断5+60*2+35*3=230次。

将这种思想运用到编码实践中，便得到了哈夫曼编码，以二元码为例，设有离散信源s，所得信源符号列为{s₁，S₂，…，S_m｝，取值于有限符号集A，A={a₁，a₂，…，a_n｝，而该集合A中每个字符dj在信源S中出现的概率为：P={p₁，p₂，…，p_n}，其中p_i=L/M，L_i为符号a_j在信源S中出现的次数或频度。

显然按这种方式的话，信源X中概率最高的符号，被分配的码字也一定最短，反之出现频率最低的符号，被分配的码字一定最长，虽然最终这样获得的码字其长度是不相等的，但可以保证所得平均码字长度最短，这也就是我们通常所说的最佳编码思想。

(二)静态奇偶编码介绍

哈夫曼编码效率虽然高，其算法却略显复杂，特别是无论什么样的数据，该算法在开始编码前，都要对其进行扫描统计以生成各字符的概率，还涉及到反复的排序计算，所以比较费时，而且生成的码字总是不定的，它随着信源的不同而不同，这就增加了译码的难度。因而有人针对这一情况提出了静态奇偶编码，这种算法也是基于概率排序的，即编码前，总是先统计出信源中各字符出现的概率，然后根据概率分配码字，其具体的生成方式是：对于一个符号，若其概率大小排序为第n位，则给这个符号分配的码字的码长是l_n=int[(n+1)／2]+1。

这样，在编码过程中可先行判断其概率排序n是奇数还是偶数，如果n是奇数，则码字中的前(n-1)位是“1”，最后一位是“0”；反之如果n是奇数，则码字中的前(n-1)位是“0”，最后一位是“1”。其码字结构非常的有规律，如果一个码字前一部分是全“0”，则其结尾必定为一个“1”；反之如果一个码前一部分是全“1”，则其结尾必定为一个“0”；而且表中的码字总是成对出现，非奇即偶，奇偶码互为取反，静态奇偶编码也是因此而得名。

静态奇偶编码算法的编码过程很简单：首先根据信源符号出现的概率排序，并由此确定各符号的码长，之后每提取一个字符，就可以直接给出其码字；同时其译码过程也很简单，只须扫描所接收到的码序列，从第一位开始搜索，如果是“0”，则到下一个非“0”为的这一段便是一个码字，如果开始位是“1”，则到下一个非“1”为的这一段便是一个码字，显然要比哈夫曼编码的译码过程简单的多。

(三)动态哈夫曼编码介绍

为了便于说明，我们定义si，表示信源字符串中的第i个字符。

在编码开始前，需要首先引入一个空的叶结点，它的重量权值始终为0。初始的哈夫曼树中只有一个根结点和一个空叶结点。

编码子程序读入第一个字符时，它将该字符加到根结点的右分枝上，而空叶结点仍留在左分枝上，然后将该字符以ASCII码方式输出。

以后每读进一个字符S_i，编码子程序都执行以下的步骤：首先它检查s_i是否出现在编码树中，如果是，编码子程序就以静态哈夫曼编码中相同的方式对s_i进行编码；如果S_i；不在编码树中，编码子程序首先对空叶结点进行编码，然后将S_i以ASCII码的方式输出，最后在编码树增加两个

结点：在空叶结点的右分枝加入一个新结点，并将S_i放在里面，然后在其左分枝上加入一个新的空叶结点。

每处理一个字符，编码子程序都需要修改各自的哈夫曼树，为了修改的方便，树中每个结点都具有一个序号，它是根据结点的重量由大到小排列而确定的一个递减序列，不同层间从上到下，同层中的结点从右到左递减。

动态哈夫曼编码技术的关键就是如何将前t个字符的哈夫曼树调整成一棵前(t+1)个字符的哈夫曼树。为了解决上述问题，我们分两步来进行，第一步我们把前t个字符的哈夫曼树转换成它的另一种形式，在该树中只须在第二步中简单地把由根到叶结点s_i路径上的所有结点重量加1，就可以变成前(t+1)个字符的哈夫曼树。其过程就是以叶结点s_i为初始的当前结点，重复地将当前结点与具有同样重量的序号最大的结点进行交换，并使得后者的父结点成为新的当前结点，直到遇到根结点为止。

三、各编码方法的比较

依据前面部分的论述，对于同—信源符号列“hatismath”，分别施以不同的编码方法得到不同的编码结果。

当然仅凭一个例子的运行时间并不能说明一个算法的优劣，但是算法的时间复杂度在宏观上给算法提供了一个衡量的尺度，表中等长编码的时间复杂度最小，在程序运行过程中只须给该信源符号一个不同与其它符号的记录号即可，不涉及排序等问题，将该记录号转换成对应的二进制便得到其对应码字，而香农编码则须要先进行排序以方便后面过程中概率的累计等计算，同时还要对其概率进行二进制的转换，因而起算法的时间复杂度要高与等长编码。同样道理可得到哈夫曼编码的时间复杂度，不过哈夫曼编码能保证平均码长最小，因而优与香农编码。静态奇偶编码在排序后即可直接的出各自的码字，这也是其编吗迅速的主要原因。至于动态哈夫曼编码其时间复杂度也同样为0(n²)，但是在动态编码中，各信源符号的码字是实时生成的，同时也是不断变化的。

四、结论

通过前文的论述及比较，可得到如下结论：等长编码只是一种比较初级的编码方法，虽然其实现起来比较容易，但是它的编码效率很低。香农编码较之等长编码来说，理论上有很大的进步，基本上实现了给出现概率高的字符配以较短的码字，出现概率低的字符配以相对来说稍长的码字，但是它仍然无法实现平均码长的最短。

哈夫曼编码又称为最优编码，编码效率在这几种编码方法中最好，但是其实现起来对时间和空间的要求较高，静态奇偶编码在信源字符集中元素不是很多，据相关统计分析为小于等于16时，有和哈夫曼编码相当的编码效率，而且静态奇偶编码实现起来要比哈夫曼编码简单的多。值得一提的是，经过静态奇偶编码后的码字序列其0、1分布是比较集中的其码字形式为111…0或000…1，因此有利于进一步的压缩。至于动态哈夫曼编码，显然其最终状态是同哈夫曼编码一致的，哈夫曼编码需要统计各信源字符的概率，且各字符的码字是编码程序最终一起完成的，相比之下动态哈夫曼编码则不须要统计各信源符号的概率，并且能够实现即时编码，对于一些须要快速传递控制信息的实时场合，动态哈夫曼编码能在进行编码的同时进行传输，并且它的编码效率是趋近于哈夫曼编码的。

参考文献

[1]李亦农，李梅，信息论基础教程[M]，北京：北京邮电大学出版社，2005

[2]石峰，莫忠息，信息论基础[M]，武汉：武汉大学出版社，2002

[3]严蔚敏，吴伟民，数据结构C语言版[M]，北京：清华大学出版社，1997

[4]严蔚敏，吴伟民，数据结构习题集C语言版[M]北京：清华大学出版社，1997

[5]郭福顺，廖明宏，数据结构与算法基础[M]大连理工大学出版社，2000

作者简介：徐国臣，男，黑龙江安达人，兴安岭地区公安边防支队助理工程师，研究方向：通讯。