几种常用无损数据压缩算法研究_郑翠
第21卷第9期2011年9月
计算机技术与发展
COMPUTERTECHNOLOGYANDDEVELOPMENT
Vol.21No.9Sep.2011
几种常用无损数据压缩算法研究
郑翠芳
(中国
物理研究院计算机应用研究所,四川绵阳621900)
摘
要:随着网络承载的信息量的飞速增长,数据压缩必然会备受人们重视。数据压缩可分成两种类型,一种叫做无损压
另一种叫做有损压缩。文中主要介绍目前用得最多和技术最成熟的无损数据压缩技术,按照无损压缩方法采用的压缩,
缩技术的不同,从基于统计的压缩思想和基于字典的压缩思想两个方面对其中最具有代
性的无损数据压缩方法进行了并对基于字典压缩算法的一些成熟的改进算法进行了汇总介绍,便于对无损数据压缩技详细的分类讨论和优缺点比较,术感兴趣的同志学习参考。
关键词:数据压缩;无损数据压缩;统计压缩算法;字典压缩算法中图分类号:TP311.5
文献标识码:A
文章编号:1673-629X(2011)09-0073-04
ResearchofSeveralCommonLosslessDataCompressionAlgorithms
ZHENGCui-fang
(InstituteofComputerApplication,ChinaAcademyofEngineeringPhysics,Mianyang621900,China)
Abstract:Withthequickincreaseofnetwork’sinformation,datacompressionispaidmoreandmoreattentionbypeople.Datacompres-sioncanbedividedintotwotypes,oneiscalledlosslesscompression,andtheotheriscalledlosscompression.Ittakeslosslessdatacom-pressionasmainline.Accordingtodifferentcompressiontechnologyoflosslessdatacompression,fromtwoaspectsofstatisticanddic-tionaryideas,itintroducessomerepresentativelosslessdatacompressionapproachesandanalyzesthesekindsofdatacompressionalgo-rithms’advantagesanddisadvantages.Gathersomematurebettermentalgorithmbasedondictionarycompressionalgorithmtogetherandintroducethem;Itisfacilitatereferenceforpeoplewhoisinterestinlosslessdatacompressiontechnology.
Keywords:datacompression;losslessdatacompression;statisticcompressionalgorithm;dictionarycompressionalgorithm
0引言
分类介绍,并对它们各自的优缺点进行归纳总结。由于篇幅的原因,文中并没有对每个算法的具体实现步骤进行描述,而只是引入了对每个算法介绍比较详细的中文文献信息。希望能为对无损压缩算法有兴趣的查询提供方便。同志学习、
随着信息化技术的飞速发展,各行各业都用计算各种系统数据量越来越大,数据在时间机来处理信息,
和空间上日益增长,给信息存储特别是网络传输带来诸多的困难。为了节省信息的存储空间和提高信息的传输效率,必须对大量的实际数据进行有效的压缩。数据压缩作为解决海量信息存储和传输的支持技术受到人们的极大重视。
压缩算法分为无损压缩和有损压缩。相对于有损无损压缩的占用空间大,压缩比不高,但是压缩来说,
它100%地保存了原始信息,没有任何信号丢失并且音质高,不受信号源的影响。而且随着限制无损格式的种种因素逐渐被消除(例如:硬盘容量的急剧增长而且价格越来越低廉),使得无损压缩格式具有广阔对目前的应用前景。文中在查阅大量文献的前提下,国内外的一些具有代表性的无损压缩算法进行详细的
收稿日期:2011-01-27;修回日期:2011-05-09
基金项目:中国工程物理研究院预先研究基金(09-0642)
作者简介:郑翠芳(1977-),女,硕士研究生,研究方向为软件开发。
1无损数据压缩的分类
无损压缩技术即通常所说的通用压缩技术也称为
信息保持编码、熵编码、无失真编码等,也就是根据一定方法对大量数据进行编码处理以达到信息压缩存储在数据的压缩过程中不允许精度的损失,被压缩过程,
的数据应该能够通过解码恢复到压缩以前的原状态。主要用于文本文件、数据库、程序数据和特殊应用场合的图像数据(如指纹图像、医学图像等)的压缩。这类一般为1/2~1/5。算法压缩率较低,
通常压缩对象是文字或数字等要求精确的数据时,无损压缩是必然的选择。无损压缩从压缩模型上大体可以分为基于统计的压缩算法和基于字典的压缩算法。具体的分类图如图1所示。
·74·计算机技术与发展第21卷
图1
1.1
基于统计压缩算法
常用无损数据压缩分类图
Huffman的运行时间与输入串长度成线性比,而存储空间的需求量不依赖输入串长度,是一个常数。
5)算术编码[6]也是一种根据字符出现几率的统是Rissanen在1976年提计结果重新编码的压缩
,
出的,思想和哈夫曼算法类似,是一种高效清除字串冗打破了哈夫曼算法必须用整数来表示字符余的算法,
的限制。可以成功地逼近信息熵极限的编码方法。1.1.2
基于统计压缩算法比较
基于统计的压缩算法各有所长,既有优势的一面,也有不利的一面。表1对每个基于统计的无损压缩算法进行了优缺点以及适用性的比较,方便读者在实际使用中选择合适的压缩算法。
表1
算法名称
优点
实现简单;压缩和还原速度快
基于统计式压缩算法的起源较早,实质是统计字属于熵编码类,符的出现频率来对字符本身重新编码,
与原始数据的排列次序无关而与其出现频率有关,主游程长度编码要的压缩算法有Shanno-Fano编码、(RLC)、哈夫曼编码和算术编码。1.1.1
基于统计压缩算法简单介绍按照压缩算法的产生时间分别介绍如下:1)香浓-凡诺算法(Shanno-Fano编码)由贝尔实验室的Shannon和MIT的RobertFano开发。首先是Shannon在1948年给出了一种简单的编码方法—Shannon编码
[1]
,随后Fano在1952年又进一步提出了
Fano编码。Shannon-Fano编码的核心是构造二叉树,它是一种自顶向下的、非自适应的编码算法。
2)游程长度编码(Run-Length-Coding)
[2]
优缺点比较列表
缺点
呆板,适应性差;平均压缩率低
适用范围复杂度不高的原始点阵图像通常用于压缩
GZIP,
是针对
游程长度编码
一些文本数据的特点所设计的,主要是去除文本中的从而达到减少数据文件冗余字符或字节中的冗余位,
所占的存储空间的目的。RLC的压缩效能取决于整个数据流的重复字符出现次数、平均游程长度及所采用的编码结构。由于该算法是针对文件的某些特点所设计的,所以应用起来具有一定的局限性。为了数据压缩的通用性,一般很少单独采用该方法,主要与其它编码技术配合使用。
3)Huffman编码[3]是D.A.Huffman在1952年发现的一种基于信号概率的数据压缩算法。此方法是根据数据信息中字符重复出现的概率生成的一种前缀编码方法。是目前用于压缩的最普遍方法之一。它的核心也是构造二叉树,但它的构造思想刚好与Shanno-Fano编码相反,是一种自下向上的、非自适应的编码算法。
5]
4)动态哈夫曼[4,又叫自适应哈夫曼(Adaptive
Huffman编码
简单而实用;编码译码时的唯一性
过于受被压缩文件大小的影响;速度较慢
JPEG的数据对字符出现
动态哈夫曼
取消了统计过程,提高了速度
只能去除概率分布不均的冗余
频率不均及大量数据的压缩信源概率比较接近
算术编码压缩率最高速度很慢运算复杂,
1.2基于字典压缩算法
在很长的一段时间内,基于统计的压缩算法占有
很重要的地位,直到1977年由以色列科学家JacabZiv和AbrahamLempel撰写的两篇论文发表后才出现一——基于字典的压缩算法。种新的压缩算法—1.2.1
基于字典压缩算法简单介绍
字典编码方法是以类似查字典的方式进行编码。它的基本原理是以较长的字符串或经常出现的字母组
Huffman),是1978年Gallager在Huffman编码的基础上提出的一种改进算法。此算法取消了统计过程,一边压缩一边动态调整哈夫曼树,提高了速度,动态
第9期郑翠芳:几种常用无损数据压缩算法研究·75·
合构成字典中的各个词条,并用相对较短的数字或符号来表示的方法。是最为简单的压缩算法之一。压缩效果的好坏和重复数据的出现、字典的大小有关。主LZSS算法、LZ78算法、LZW算法要包括:LZ77算法、等几种基本算法。
8]
1)LZ77算法[7,是1977年两位以色列科学家Ja-
基础上根据实际需要提出了很多的改进方法。所有的改进方法可大致分为以下三类:
1)对字典建立的改进。字典越大,代替的子串越多,但应用中字典容量则受一定限制,要权衡利弊选择合适的字典;
2)对字典更新的改进,一般分为抛弃整个字典或者抛弃字典中匹配率较小的节点两种方式;
3)变换代码长度,由于代码长度决定压缩率,代码长度越短,压缩率越高,为了对大、小文件都取得比较好的压缩效果,可以使用变换长度代码的方法。
表2
[14~20]
cobZiv和AbrahamLempel提出的一种不同其他压缩算法的基于字典的压缩算法,利用该算法进行数据压缩、解压缩的过程,就像一个窗口在原始数据中滑动过程,故也常称为基于滑动窗口的自适应的字典压缩方法。它是基于字符串匹配(或词典编码)的第一个具有实用价值的数据压缩算法。在单片机上实现起来较为理想。它的压缩效果好、速度快,但是压缩率相对较低,另外LZ77算法具有明显的空间局限性。
2)LZ78
[9,10]
对国内比较成熟的基于字典压缩算法
的改进算法进行了简单罗列及描述。
表2
序号
基于字典压缩算法的改进算法列表
源于算法
描述
一种基于双串表的改进LZW算
改进算法
压缩算法是1978年JacobZiv和Abra-1
DTLZW
LZW的改进
该算法的实质是通过引入双串法,
表的机制来克服LZ78算法的缺陷
hamLempel提出的改进算法,LZ78算法不同于LZ77算法,它放弃了窗口概念,采用树形结构构造字典和保从而确保文件中的
均能反映到字典中。存短语,
它比较适合处理具有一定区间重复性的情况。它继承了LZ77算法压缩效果好、速度快的优点,但它的编译码方法较复杂,实现起来比较困难。
3)LZSS算法[11]是1982年JamesStorer和ThomasSzymanski为了改进LZ77的性能而提出的改进的实用算法,该算法采用二分搜索树,大大加快了压缩速度,解码时无须生成和维护树而更为迅速。该算法的压缩率较高,编译算法较简单。但不足之处是每次压缩都需要向前搜索到原文开头,对于较长的原文(因建立的二叉树过于庞大而降低了编码的效率)需要的时间是不可忍受的,另外无论匹配长度为多少,都分配相同这显然存在一定的冗余。的代码长度,
12,13]4)LZW算法[10,是1984年Welch提出的基于
2LZSSCHLZSS的改进
从编码方案、自适应索引扩大位和最大索引位长等方面修正LZSS
3LZWCHLZW的改进
更新策略和哈希函数从基本码集、方面修正LZW
此算法是一种基于代码库的自适
4
LZJH
LZ77+LZ78
应数据压缩算法,适用于分组数据网和循环分组业务
本算法在处理字节和单词重复方
5
LZI
LZ78+LZ77
对近期和远程面具有良好的性能,
数据都很敏感,但是实现起来比较复杂
LZ78算法的一个变种压缩算法。主要用于GIF格式的图像数据的压缩。该算法的压缩效果好、速度快且算法描述易于接受,是目前最常用和最有效的无损压缩算法。不足之处是:在压缩过程中给不同的代码字分配固定长度的整数,并且不考虑信息源的概率分布。所需存储空间与输入串长度成正比,并未真正做到最佳地为串表选择串式、最佳地分析输入数据,从而削弱了它的压缩性能。既不适合小文件的压缩也不适合太大文件的压缩,而且LZW码仅仅适合内容具有明显单词结构的文件,如.txt文本文件和C语言源程序文件。1.2.2
改进算法的归纳
字典压缩算法成为目前的主流无损数据压缩算法,得到了人们的极大关注,但在现实使用过程中,由于受到多种因素的限制使得每种压缩算法都存在这样或那样的不足,于是许多研究者就在字典压缩算法的
采用固定编码表的压缩算法和采用预设计滑动窗口与Huffman编
6
DEFLATE码相结合的自适应方式字典编码
压缩算法,在HTTP压缩中非常流行
利用了LZ78和LZ77的互补特性,具有与基于LZ78和LZ77相
7
HLZ
LZ78+LZ77
似的计算复杂度和存储复杂度,但具有更好的全局与局部自适应性、更高的压缩效率
2结束语
文中介绍的几种无损数据压缩算法都比较通用,
·76·计算机技术与发展
1977,23(3):337-343.[8]王忠义,姜[9]
第21卷
每个压缩算法都有自己的优点和缺点,都有自己的适不同算法的复杂性对空间的要求以及压缩率用范围,
也不同。它们不仅仅依赖于压缩方法本身,也依赖于被压缩对象的特点。在具体的应用过程中,要根据实际情况的需要,有针对性地去选择、结合或改进一些算法,尽量发挥每一个无损压缩算法的优势,以得到比较理想的压缩数据。不过从综合特性看LZW算法是目前在无损压缩方面最常用的方法。但是对LZW算法而言其字典的更新速度和较高的压缩率之间的匹配问
还需要进一步的讨论分析。同时研究在保持高压缩比、提高压缩机解压缩速度的同时保持原始数据的完整性还是一个重要的研究课题。
参考文献:
[1]ShannonCE.AmathematicalTheoryofCommunication[J].
TheBellSystemTechnicalJournal,1948,27(7):379-423.[2]刘
.天津理工学院学冰.游程长度编码算法的研究[J]2001,17(4):77-81.报,
[3]张广学.最优二叉树的生成及应用[J].现代电子技术,
2008,273(10):112-114.[4]袁
玫,袁
M].北京:电子文.数据压缩技术及其应用[
J].小升.数据压缩算法分析与改进[
1994.工业出版社,[5]游晓明,陈传波,刘
1999,20(8):570-573.型微型计算机系统,
[6]RissanenJ,LangdonGG.Universalmodelingandcoding[J].
IEEETransonInformationTheory,1981,27(1):12-23.[7]ZivJ,LempelA.AUniversalAlgorithmforSequentialData
Compression[J].IEEETransactionsonInformationTheory,
丹.关于Lempel-Ziv77压缩算法及其实现的
J].计算机研究与发展,1996,33(5):329-340.研究[
ZivJ,LempelA.CompressionofIndividualSequencesviaVariableRateCoding[J].IEEETransactionsonInformationTheory,1978,24(5):530-536.[10]王[11]王
.计算机工平.LZW无损压缩算法的实现与研究[J]
.计算平,茅忠明.LZSS文本压缩算法实现与研究[J]2002,28(7):98-99.程,
2001,27(8):22-24.机工程,
[12]Welch.ATechniqueforHighPerformanceDataCompression
[J].IEEEComputer,1984,17(6):8-19.[13]许
霞,马光思,鱼
涛.LZW无损压缩算法的研究与改
J].计算机技术与发展,2009,19(4):125-127.进[
[14]吴宇新,余松煌.对LZW算法的改进及其在图像无损压缩
J].上海交通大学学报,1998(9):110-113.中的应用[[15]华[16]华
.中文信息学强.中文文本压缩的LZSSCH算法[J]
J].计算机工程强.中西文文本压缩的LZWCH算法[
.无线电通信坚.一种新的数据压缩算法[J]
1998,12(1):50-56.报,
1999,35(3):22-23.与应用,[17]裴文端,吴[18]卓[19]王
2001,27(3):30-32.技术,
越,杨长生,宋广华.一种基于自适应字典的通用无损J].微计算机信刚,刘立柱.ZIP文件压缩编码分析[
越.HLZ:一种采用混合字典的自适
J].计算机工程,2001,27(2):149-151.压缩算法[
2006,22(5):283-285.息,
[20]杨长生,宋广华,卓
(1):40-43.
.浙江大学学报(工学版),2002,36应无损编码算法[J]
檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪
(上接第72页)
(2)对随机光场下采集到的立体像对进行极线校正,提高了本算法匹配的精度与效率。
(3)利用有限视差约束和顺序性约束,同样起到了降低匹配搜索速度与提高匹配精度的作用。
参考文献:
[1]张素苓,李竹林,赵宗涛.一种立体景象匹配技术及其应用
[J].计算机技术与发展,2010,20(3):221-224.
[2]MattocciaS.Alocallyglobalapproachtostereocorrespondence
[C]//3DDigitalImagingandModeling(3DIM2009).Kyoto,Japan:[s.n.],2009:1763-1770.
[3]LhuillierM,QuanL.Matchpropagationforimage-basedmodel-ingandrendering[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2002,24(8):1140-1146.[4]张令涛,曲道奎,徐
枋.一种基于图割的改进立体匹配算
J].机器人,2010,32(1):104-108.法[
[5]时洪光,张凤生,郑春兰.基于图像校正与灰度相关性的立
J].设计与研究,2010,37(8):15-18.体匹配算法研究[
[6]周秀芝,J].计文贡坚,王润生.自适应窗口快速立体匹配[
2006,29(3):473-479.算机学报,[7]
TombariF,MattocciaS,StefanoLD.Fullsearch-equivalentpatternmatchingwithincrementaldissimilarityapproximations[J].IEEETransactionsonPatternAnalysisandMachineIntel-ligence,2009,31(1):129-141.[8]董[9]冯
巍,石光明.改进的轮廓小波变换及其图像去噪应用研鹏,魏
彪,潘英俊,等.一种循环平移的Contourlet变.计波,车向前.一种高效的图像匹配算法[J]
D].西安:西安电子科技大学,2007.究[
J].计算机仿真,2006,23(9):116-118.换去噪新方法[[10]刘忠艳,周
2009,19(4):45-47.算机技术与发展,
[11]BradskiG,KaeblerA.LearningOpenCV[M].北京:清华大学
2008.出版社,[12]陈胜勇,刘
M].盛.基于OpenCV的计算机视觉技术实现[
2008.北京:科学出版社,