无损数据压缩与解压算法的介绍与实现

2024年3月16日发(作者：)

算法语言

信息与电脑

China Computer&Communication

2016年第1期

无损数据压缩与解压算法的介绍与实现

余兴阁

（巴彦淖尔西部铜业有限公司，内蒙古 巴彦淖尔 015000）

摘　要：

数据压缩是数字化日益普及和计算机、数字通信、数字信号处理及各种数据处理设备日益广泛应用并渗透

到各行各业所产生的巨大客观需求。随着信息化社会的发展，人们面对急剧增长的海量信息，存储、传输和处理这些海

量信息的压力越来越大。在这种情况下，进行数据压缩是一种必然选择。数据压缩又分为有损数据压缩和无损数据压缩，

这篇文章主要讨论无损数据压缩，无损数据压缩适用于文本文件、数据库、程序等数据压缩，其特点是数据经压缩、解压后，

可以完全与压缩前的数据一样。

关键词：

压缩；解压；计算机技术

中图分类

号：TP274  文献标识码：A  文章编号：1003-9767（2016）01-064-02

１　数据压缩的意义

信息时代带来了“信息爆炸”，例如，一幅未经压缩的

图片可能高达数十兆，一部一小时的原始视频序列可能需要

十几张光盘才能存下。如果不进行数据压缩，无论多大的内

存也不能满足我们生活的需要。所以数据压缩是十分必要的，

数据压缩是一个减少数据和去除过多冗余信息的过程。通过

数据压缩，原来需要十几张光盘才能存储的高品质电影可以

存储在一张只读光盘上；传输原始的电视节目，将需要发射

多颗通信卫星，而经过压缩的电视只需要一颗就够了。因此，

如果不使用数据压缩技术，则无论对于信息的传输或存储都很

难实用化。而数据压缩的好处就在于：较快地传输各种信源（降

低信道占用费用）——时间域的压缩；在现有通信干线上开

通更多的并行业务（如电视、传真、电话、可视图文等）——

频率域的压缩；降低发射功率（这对于依靠电池供电的移动通

信终端尤为重要）——能量域的压缩；紧缩数据存储容量（降

低存储费用）——空间域的压缩。鉴于数据压缩技术的各种优

点，研究数据压缩与解压缩技术是很有必要的。

编码、解码速度却很快的编码算法，在二值图中使用广泛。

2.1.2 哈夫曼编码

哈夫曼编码首先统计各个字符的出现频率，然后将信源

信息符号按出现次数的大小进行排序，将出现次数最少的两

个符号进行合并，生成一个新的符号，其概率为两个合并符

号的概率之和，然后将合并的两个符号在序列中删除，将新

产生的符号放入序列中，不断重复这一过程，直至剩下两个

符号，对最后剩下的两个符号分别赋予二进制元0，1，逆向

沿着刚才的合成过程，分别找到合成生成符号的对应两个符

号，对这两个符号也分别赋予二进制元0，1，重复这一过程

直到最后被赋予二进制元的符号下面没有更低级的合成元，

这样就可以用较少位数表示出现次数较多的字符，用较多的

位数表示出现次数较少的字符，从而有效的对数据进行压缩。

2.1.3 算术编码

算术编码进行编码时，实数区间[0,1)根据符号的出现

频率被划分为多个区间。每输入一个符号，将相应符号的出

现频率加1，并且选择此符号对应的区间按照新的频率比重

进一步划分为更小的区间。不断重复这一过程，直至所有符

号输入完成。对于最后选择的区间，输出属于该区间的一个

小数，这个数据就是算术编码的最终结果，也就是所有数据

的编码。算术编码的主要思想是将所有要编码的符号全部映

射到[0,1)的实数区间中，编码结束后只需要输出一个大于0

并且小于1的小数，因此，算术编码的压缩率理论上特别高。

2.2 基于字典压缩算法

2.2.1 LZ77算法

LZ77算法在编码时生成一个固定大小的窗口进行信息

匹配，而不是在已经编码的信息中寻找匹配，因此又被称为

“滑动窗口压缩”。在编码进行过程中，窗口的前边是已编

码部分，后面是未编码部分，随着压缩的进行，不断向后滑

动字典窗口，使窗口总是包含最近刚编码过的信息，窗口后

面则为待编码的信息。

２　数据压缩算法

无损数据压缩算法按照压缩模型主要分为两类：基于

统计压缩算法和基于字典压缩算法。基于统计压缩算法主要

包括：游程长度编码、哈夫曼编码、算术编码；基于字典的

压缩算法主要包括：LZ77算法、LZ78算法、LZW算法和

LZSS算法。

2.1 基于统计压缩算法

2.1.1 游程长度编码

游程长度编码（Run Length Encoding，即RLE）的编码

思想很简单：就是对于一串字符串，若某些字符重复出现，

则对于重复的部分，用重复的次数代替重复的字符存储，从

而使整个字符长度减小。因此，游程编码是一种实现简单，

作者简介：

余兴阁（1991-），男，江西上饶人，本科，网络工程师。研究方向：数据处理。

—　　　６４　　　—

2016年第1期

信息与电脑

China Computer&Communication

算法语言

2.2.2 LZ78算法

LZ78的编码思想是从字符流中寻找出从没出现过的新

的前缀+字符串，也称为新“词条”，然后用特殊的码字来

表示这个“词条”。这样，原来的字符流就变为了一系列码

字表示的码字流，从而达到压缩数据的目的。在编码开始时

词典是空的，不包含任何词条。在这种情况下编码器就会输

出一个用来表示空字符串的特殊码字(例如“0”)和字符流

中的第一个字符C，并把这个字符C添加到词典中作为一个

由这个字符组成的词条。在编码过程中，如果出现类似情况，

即字符不在字典中，则生成由字符组成的新词条。在词典中

已经包含某些词条之后，如果“当前前缀P +当前字符C”

已经在词典中，就用字符C来扩展这个前缀，这样的扩展操

作一直重复到获得一个在词典中没有的词条为止。此时就输

出表示当前前缀P的码字和字符C，并把P+C添加到词典中

作为前缀，然后开始处理字符流中的下一个前缀。

2.2.3 LZW算法

LZW算法是LZ78算法的一个变种算法，LZ78是每读

入一个字符的同时，将其编入自己的字典，然后，再读入字

符的同时，则在已有的字典里查找，没有的话该字符就在新

编入辞典，如此循环。LZW则在编码前就建立了ASCII码

的字典，由于一共有256个ASCII码，所以这个字典需要花

费8个字节的存储空间。然后像LZ78一样读入字符，没有

的就编入字典，如此循环。通常，LZW编码表的每一项用

12位表示，以此来表示一个字符串。所以编码表可以存储

4096个项，及字典中存储了4096个词条，并且，通常0-255

固定的用来表示ASCII对应的字符。由于考虑到可能4096

个项不够用，所以，用256表示开始一个新的编码表，即编

码重新开始，用257表示编码结束。

距离表示重复的部分相对窗口边界的距离，并且应该以离当

前字符串距离最近的那个作为记录的依据（也就是指向离自

己最近那个重复字符串），长度表示重复字符的长度。这样，

文本数据转换为一定大小之间的数字；然后，对这些数字采

用哈夫曼编码，进一步对数据进行压缩；由于压缩后的数据

会存在一连串的0编码，这时可以使用游程长度编码进一步

压缩，提高压缩效率。

4.2 对比其他压缩软件

现在压缩技术发展较好，也因此产生了很多性能非常好

的压缩软件，如WinRAR、7Z、快压、360压缩和好压等。

这些压缩软件在压缩率、压缩时间和支持的文件格式等方面

都有着不错的表现，下面将本程序设计的压缩算法与这些压

缩软件进行比较，分析程序可用性和实用性。将一个由txt、

doc、xlsx、pdf文件组成的大小为88.1MB的文件夹用各压

缩软件进行压缩，压缩结果见表1。

表１　和其他软件的比较

测试项目

样本

压缩后大小

压缩时间

压缩率

WinRAR

59212kb

20s

65.6%

7-Zip

44949kb

50s

49.8%

快压

57740kb

65s

64.0%

好压

67807kb

15s

75.1%

360压缩

67588kb

30s

74.9%

本程序

67807kb

3min

75.1%

由txt、doc、xlsx、pdf文件组成的大小为88.1MB的文件夹

５　结　语

本篇论文对数据压缩与解压过程进行了简单的论述，通

过了解一些常用的压缩算法，可以帮助理解数据压缩的实现

原理。但是数据压缩算法多种多样，以上只介绍了基本的算

法，在这些算法上进行一些改进又可以产生很多不同的算法。

我们常用的压缩软件也是基于这些压缩算法实现的，在对文

件进行压缩的过程中使用一种压缩算法往往达不到需要的效

率，而是要了解不同压缩算法的优缺点，将其结合起来，算

法的选择对程序最终的压缩效果产生直接的影响。

３　数据解压算法

解压是压缩的逆过程，不同的压缩算法对应特定的解压

算法，也就是说，数据是怎么压缩的，那么就怎么解压。因此，

进行数据压缩时就要提前考虑解压的实现。比如，进行哈夫

曼编码压缩数据时要使用一个哈夫曼树将数据转换为对应编

码，那么压缩时就要存储这颗编码树，解压时根据存储的信

息重新构建出这颗编码树，将编码转换为对应的数据。在进

行解压时第一步就是从相应的文件中获得数据压缩时的一些

重要信息，通过这些信息重现压缩过程，然后推导出解压步

骤，完成数据的复原过程。

参考文献

[1]美·萨尤得.数据压缩导论[M].北京：人民邮电出版

社,2013.

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

[3]吴家安.数据压缩技术及应用[M].北京：科学出版

社,2008.

[4]刘冰.游程长度编码算法的研究[D].天津：天津理

工学院学报,2006(10).

[5]美·Mark,美·Nelson.数据压缩技术原理与范例[M].

北京：科学出版社,1995.

[6]美·David Salomun.数据压缩原理与应用[M].北京：

电子工业出版社,2003.

[7]王平.LZW无损压缩算法的实现与研究[J].计算机工

程,2002(28).

４　压缩软件的实现

4.1 实现过程

在研究过一些压缩和解压算法后，笔者使用Java编程

语言实现了一个简单的压缩程序。程序使用了三种压缩算法，

首先，采用类似于LZ77压缩算法中的滑动窗口机制，滑动

窗口设置为32kb，对于重复出现的部分用（距离，长度）表示，

—　　　６５　　　—