基于不同信源的三种常用无损压缩算法的研究

北京林业大学理学院 邓富博 李墨豪 温恺林 张朝璇 陈 晨



基于不同信源的三种常用无损压缩算法的研究

北京林业大学理学院 邓富博 李墨豪 温恺林 张朝璇 陈 晨

【摘要】随着社会的发展和科技的进步，数据压缩越来越受到人们的重视。压缩算法可分为有损压缩和无损压缩。本文基于不同信源对常用的三种无损压缩算法（霍夫曼编码、游程编码及LZW编码）进行了研究与总结。对它们各自的原理进行了简单的介绍，并在最后归纳了它们的优缺点、适用范围及大体压缩率情况。

【关键词】霍夫曼；LZW； 游程；优缺点；适用范围

0 引言

数据压缩是指在不丢失有用信息的前提下，以最小的数码表示信源所发出的信号，或按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间的一种技术方法［1］。总的来说数据压缩包括有损压缩和无损压缩。

随着社会的发展和科技的进步，无损压缩算法的种类越来越多，效果也越来越好。主要有霍夫曼算法、游程编码、LZ系列等等。本文主要对霍夫曼算法、游程编码以及LZW算法进行了研究与讨论，并总结了它们在不同信源下的效果，优缺点及压缩率等。

1 霍夫曼压缩算法

1.1 基本原理

霍夫曼算法是D.A.Huffman 在1952 年发现的一种基于信号概率的数据无损压缩算

法［2］。它的压缩思想的核心是构建霍夫曼树，又称为最优二叉树。通过“叶子”和分支的权重，来寻找带权路径最小的二叉树［3］。

比如有五个权重分别为1，1，2，2，4的符号，构建最优二叉树步骤如图1所示：

图1 构建最优二叉树步骤图

最后，根据构建好的二叉树按左0右1的规则进行编码，易懂且简单方便。

1.2 算法结果分析

霍夫曼编码与其它的压缩算法相比，速度还是较快的。它主要针对统计结果的字符进行编码［4］，可以说是完全根据字符出现的频率来进行编码的，形式灵活多变。它对不同的信源编码效率是不同的，对于有些信源可达到100%的编码效率；可若信号源符号的概率相等时，则编码效率最低［5］。还有就是编出的码并不唯一，但平均码长相等。

2 游程压缩算法

2.1 信源

信源就是信息的来源，信息的发生或传播者。信源发出信息的时候，一般以某种讯息的方式表现出来，可以是符号也可以是信号，比如文字，图像等。

2.2 基本原理

游程编码（RLC，Run Length Coding），又称”运行长度编码”或”行程编码”，是一种统计编码，该编码属于无损压缩编码。

用一个符号值或串长代替具有相同值的连续符号，使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。

例如：55555555 777 99999 666666，变为（5，8）（7，3）（9，5）（6，6），这样编码位数远小于原始数据的位数。

2.3 算法结果分析

因为游程算法更适用于图像数据的压缩，所以本文对几种不同类型的图像的压缩结果进行了讨论。

2.3.1 GIF和PNG类型的图像

对于这两种信源的压缩，游程编码不能很完美的实现无损压缩，压缩后的效果不是很好。

2.3.2 JPG类型的图像

JPG图像压缩后，信源有时会存在一定的损伤，但是其正确率较高，压缩效果较好。但有时会出现越压越大的现象，这是由于JPG图像是一种以文件牺牲图像质量为代价的压缩比可以达 到100：1的图像冗余度很小的图像格式。而对于原始的，未经压缩的，冗余度大的JPG图像游程编码并不太适用。

图2 JPG图像压缩前

图3 JPG图像压缩后

2.3.3 bmp图像

对于冗余度较高的bmp图像，压缩前后差距很小，几乎是一样的，正确率比上面两种情况要高出很多。而对于冗余度相对较低的bmp图像，正确率也是很高，但有时会出现越压越大的情况，此时压缩率约为111%左右。

图4 bmp图像压缩前

图5 bmp图像压缩后

3 LZW算法

3.1 基本原理

LZW算法是1984年Welch提出的基于LZ78算法的一个变种压缩算法［2］。

LZW算法压缩时，按顺序判断数据序列是否存在于词典中，用词典索引字符替代一部分字符串，以达到压缩目的；解压时，根据压缩后的数据，还原出所用词典，并进一步还原出原文。

3.2 算法结果分析

它的主要优势是对于大多数数据，能提供较好的压缩率；某种特定实现方法仅需随压缩后数据传输一个相对较小的词典，另一种实现方法不需要随数据发送词典，可以通过压缩后数据还原。不足之处就是注重实现速度，按顺序执行压缩的过程，没有对数据进行分析［6］。

总的来说，它适用于大多数一般数据的压缩，较为好用。

4 三种算法小结

表1 三种算法总结表

5 结语

本文对常用的三种无损压缩算法的原理及适用情况进行了研究与总结。根据信源的不同，这三种算法的压缩效果不同。霍夫曼和游程算法压缩速度较快，LZW的适用范围最为广阔，并且有较好的压缩率。总之，根据信源的不同可以选择不同的压缩算法，以达到想要的效果。

参考文献

［1］叶倩，张俊兰，冯雄伟.浅析数据压缩技术［J］.延安大学学报（自然科学版），2008，27（4）﹕29-33.

［2］郑翠芳.几种常用无损数据压缩算法研究［J］.计算机技术与发展，2011，21（9）﹕73-76

［3］时国平.关于霍夫曼编码数据压缩效果［J］.池州学院学报，2008，22（5）﹕46-48

［4］李雷定，马铁华，尤文斌.常用数据无损压缩算法分析［J］.电子设计工程，2009，17（1）﹕49-50，53.

［5］任维政，徐连明，邓中亮.民用GPS数据准无损压缩算法［J］.数据采集与处理，2010，25（2）﹕245-249.

［6］王平.LZW无损压缩算法的实现与研究［J］.计算机工程，2002，28（7）﹕98-99，150.

指导教师：汪沛，副教授。