包冬梅

摘   要：數据及通信业务的扩大给信息传输及网络传输带来极大的压力。为了更快、更有效地存储及传输数据，需要对数据进行压缩。数据压缩不仅节省数据的存储空间，而且能提高传输过程中的安全及效率。文章介绍了常用的几种数据压缩算法，包括香农-范诺编码、哈夫曼编码、游程长度编码和算数编码等。

关键词：数据压缩;编码;算法

1    数据压缩分析

数据压缩是一种技术方法，在有用的信息不丢失的前提下还可缩减数据量、减少存储的空间，可提高其存储、处理效率及传输技术的方法。数据压缩包含了两种压缩，分别是有损压缩和无损压缩。（1）有损压缩是指重构使用压缩后的数据，其重构数据后与原来的数据大有不用，但数据表达信息的方式不受影响，这种算法压缩效率极高[1]。有损压缩大多用于语音、图像及视频的数据压缩。（2）无损数据压缩是指对使用后的数据进行重构，重构后的数据与原始的数据相同，主要用于文本文件、数据库特殊的图像数据及程序数据等类似的压缩数据。该算法可把普通文件的数据压缩到原本文件的1/4～1/2。常用的基于统计的无损压缩算法有香农-范诺编码、哈夫曼编码、游程长度编码和算数编码等。文中主要介绍无损数据压缩算法。

2    无损压缩技术

2.1  香农-范诺编码

香农-范诺编码（Shannon-Fano Coding）最早由Shannon[2]提出，可把短编码分派给概率大的符号，通过二叉树标出每个码元发生出的概率。香农-范诺编码原理的具体算法如下：

（1）给出一组原始的数据集，再通过统计的方式来取得其中各个字符出现的频率，并且通过列表显示。

（2）根据各种字符出现的频在进行排序，出现率最高者可列于左边，出现率最低者配列于右边。

（3）把列表分为两部分，让左部分的总频率和数尽量接近于右部分的总频率和数。

（4）数字“0”分配于左半边的二进制数，数字“1”是右半边的二进制数。

（5）最左、最右两部分分别递增操作第3～4步骤，每细分化一次都添加一位编码，到最后，各个部分只含一个字符为终点。

为了更清楚地说明上述编码的过程，可通过实例来演示：已知一组原始数据集中各个字符的出现频次以及频率从高到低排序，如表1所示。

根据香农-范诺编码流程示例得出的编码如表2所示。

据此可以得到这段数据的平均码字长度：

2.2  哈夫曼编码

哈夫曼编码（Huffman Coding）[3]是1952年为压缩文本文件而设计的编码方法，是一种基于统计模型的无损压缩编码方法，是目前消除视频信息冗余最常用的方法之一。主要思想是：针对符号出现概率进行编码，为出现概率最大的符号赋予最短的码字，从而使表示每个符号的平均比特数最小。这种算法是最佳的逐个符号编码方式。哈夫曼编码过程如下：

（1）将信源符号按概率从大到小排列。

（2）分配码字长度时，将另个出现概率最小的两个符号的概率相加，产生新的概率。

（3）把合成产生的新概率集合重新排序，重复（2），直到最后两个概率之和为1。

（4）从下到上构造编码树，根据树的结构得到符号对应的编码。

按照表1的例子得出的哈夫曼编码如图2所示。

根据哈夫曼编码流程示例得出的编码如表3所示。

据此可以得到这段数据的平均码字长度：

2.3  游程长度编码结果实例

游程长度编码（run-length code）是栅格数据压缩的重要编码方法，利用空间冗余进行压缩。基本算法是：将具体类似值的连续串用其长度或一个代表值来进行代替。游程长度编码中，3个字节表示一个字符串;Sc是第一个字节的压缩指示字符，第二个字节记录连续出现的字符，第三个字节记录重复字符出现的次数。由此可得出：当RL>3时，进行数据压缩才有意义。因此，编码时要判断RL的数值，随后再决定是否进行游程长度编码。具体的游程编码结果实例的源数据流如图3所示。

相对其他无损压缩算法，游程长度编码实现原理更简单，在编程上更容易实现，适用于二值图像，在传真压缩中应用广泛。如果图像中具有相同灰度值的图像块越大，压缩率就越高。为了数据压缩的通用性，通常将游程长度编码和其他编码技术综合使用。

2.4  算数编码

算数编码是20世纪80年代发展起来的熵编码方法，原理是：将被编码的数据序列表示成[0，1）区间，该间隔的位置与输入数据的概率分布有关。信息越长，编码表示的间隔就越小，表示间隔所需的二进制位数就越多。算数编码的过程如下：

（1）按照各信源信号出现的频率，将[0， 1）这个区间分成若干段，最终每个信号源会有对应的区间。

（2）将[0， 1）这个区间设置为初始间隔。

（3）按照待处理的信号，将一个个信号源读入，每读入一个信号，就将该信号源在[0， 1）上的范围等比例地缩小到最新得到的间隔中。

（4）依次迭代，不断重复进行步骤（3），直到最后信号中的信源信号全部被读完为止。

3    结语

综上所述，文中对几种数据压缩算法进行了阐述，通过对一些简单的压缩算法进行介绍，了解了数据压缩的实现原理也掌握了不同压缩算法的优点及缺点。文中几种压缩算法的思路各有各的优点，且相互补充多种压缩软件结合几类算法，再根据具体应用中的数据流特点来进行改进，从而开发出适用的软硬件压缩器。

[参考文献]

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

[2]吴乐南.数据压缩[M].北京：电子工业出版社，2012.

[3]高潇.地震波正演波场高效压缩方法[D].合肥：中国科学技术大学，2019.

Research on data compression algorithm

Bao Dongmei

（College of Computer， Hulunbuir University， Hulunbuir 021000， China）

Abstract：With the expansion of data and communication services， great pressure is brought to information transmission and network transmission. In order to store and transmit data faster and more effectively， data compression is needed. Data compression not only saves the storage space of data， but also improves the security and efficiency in the process of transmission. This paper introduces several commonly used data compression algorithms， including Shannon-Fano coding， Huffman coding， run length code and arithmetic coding.

Key words：data compression; coding; algorithms