毕业设计（论文）-基于多源传感器数据的无损压缩算法研究.docx

北京林业大学本科毕业论文（设计）基于多源传感器数据的无损压缩算法研究全套设计加扣3012250582 摘要近年来，多源传感器系统已经广泛应用在军事、农业，林业等多个领域，然而随之而来的问题是，信息表现的多样性、信息数量的巨大性，信息关系的复杂性，以及要求信息处理的实时性，都已大大超出一般计算机的综合处理能力。对多源传感器数据压缩技术研究，可以有效的解决上述问题，这对多源传感器系统的发展起着重要意义。通过传感器采集的数据通常会进行后续处理，以获得诸如植被、森里砍伐等不同数值指标，此类数据在压缩前后不应该出现任何差异，因此本文以无损压缩算法为主要研究对象。本文首先以信息论的概念为出发点，介绍了数据压缩的概念和基础理论，其中给出了压缩算法性能评价指标，并指出了压缩的极限所在。之后，研究了基于统计的Shannon编码、Huffman编码和算术编码，基于字典的LZW算法，作了理论与算法层面分析。考虑到经典压缩算法通常只关注通用性，并不追求压缩的高效性，而本文希望针对多源传感器数据找出一种更有效的压缩算法。之后，本文通过大量研究发现DEFLATE算法编码特点与传感器数据的“近邻原则”相吻合，这是一种结合了LZ77和Huffman的算法，在理论上它应能更有效的处理多源传感器数据。之后，为了进一步针对待测数据提升算法性能，本文提出在DEFLATE算法匹配过程中，增加“副搜索”功能，这个改进有效的增加找到更长匹配串的可能性，从而进一步降低编码长度。为了将改进的DEFLATE算法与经典压缩算法作对比，本文在最后一章给出了Huffman算法、LZW、改进deflate算法压缩与解压缩的具体实现方法，通过最终对比实验发现，DEFLATE算法对多源传感器数据的压缩性能优越。关键字：多源传感器，DEFLATE算法，副搜索，Huffman算法，LZW算法Research on Lossless Compression Algorithm Based on Multi-sensor DataAbstractIn recent years, multi sensor system has been widely used in military, agricultural, forestry and other fields, but the ensuing problem is, the diversity of presented information and the enormous amount of information, information on the complexity of the relationship, as well as the requirements of real-time information processing, are significantly higher than general computer integrated processing capabilities. Research on multi-source data compression, can effectively solve the problem, which plays an important role in the development of multi sensor system.Data collected by sensors typically for subsequent processing in order to obtain different numerical indicators such as vegetation, forest felling, such data should not be any difference before and after compression, therefore, lossless compression algorithms are the main object of this thesis. Firstly started from the concepts of Information Theory, introduces the concept of data compression and basic theory, which gives the assessment criteria of compression algorithm performance, and points out the compressed limits. This thesis studies Shannon coding, Huffman coding and arithmetic coding, LZW algorithm. Taking into account the classical compression algorithms usually only focus on versatility, and we hope for multi sensor data to figure out a more efficient compression algorithms. This thesis through a large number of characteristics encoded DEFLATE algorithm with the sensor data the study found neighbor principle match, which is a combination of the LZ77 algorithm and Huffman, in theory, it should be able to handle multiple sources of data more effectively. And in order to further improving algorithm performance test data presented in the DEFLATE algorithm in the matching process, increase in search function, this effectively increases the likelihood of longer match is found, further reducing code length. In order to improve compared with classic compression algorithm DEFLATE algorithm, based on the final chapter gives a Huffman algorithm, LZW compression and decompression algorithm realization methods, according to the final experiment found that DEFLATE algorithm for multi-source data compression and superior performance.Keywords: multi-sensor, DEFLATE, subsidiary searching, Huffman algorithm, LZW algorithm目录1 绪论11.1 研究背景11.1.1 多源传感器应用综述11.1.2 研究数据压缩的意义21.2 国内外发展现状21.3 本文研究的主要内容和论文结构42 数据压缩理论基础62.1 压缩技术62.1.1 无损压缩62.1.2 有损压缩72.2 信息论简介72.2.1 信源82.2.2 信息量与熵82.3 压缩性能评价指标93 经典无损压缩算法113.1 香农编码113.2 霍夫曼编码123.2.1 霍夫曼编码方法123.2.2 霍夫曼解码方法143.2.3 霍夫曼编码算法程序模块143.3 算术编码153.3.1 算术编码原理153.3.2 算术编码算法程序模块183.3.3 算术编码伪代码183.3.4 算术编码最优压缩性32193.4 LZW编码203.4.1 LZW字典结构203.4.2 LZW算法描述203.4.3 LZW编码过程203.4.4 LZW解码过程234 基于多源传感器数据无损压缩算法设计264.1 算法总体设计264.2 Deflate算法274.2.1 LZ77算法字串匹配274.2.2 Huffman算法二次编码294.3 对DEFLATE算法匹配过程改进295 无损压缩算法实现及对比实验315.1 无损压缩算法实现315.1.1 Huffman算法的具体实现315.1.2 LZW算法的具体实现335.1.3 改进DEFLATE算法的具体实现355.2 算法的对比实验及结果分析395.2.1 数据源395.2.2 Huffman算法测试405.2.3 LZW算法测试425.2.4 Deflate与改进Deflate算法测试445.2.5 测试结果对比分析466 总结与展望48致 谢49参考文献50511 绪论1.1 研究背景随着微电子技术、集成电路及其设计技术、计算机技术、近代信号处理技术和传感器技术的发展，各种面向复杂应用背景的多传感器系统大量涌现。多传感器的数据融合(Data Fusion)，它是20世纪80年代形成和发展起来的一种自动化信息综合处理技术，是指对来自多个传感器的数据进行多级别、多方面、多层次的处理，从而产生新的有意义的信息，而这种新信息是任何单一传感器所无法获得的1。然而该技术在发展过程中面临着如信息量巨大带来的问题，这对多传感器数据的传输、保存造成很大影响，因此现在对基于此类数据的压缩算法的需求日趋迫切。1.1.1 多源传感器应用综述随着现代科学技术在军事领域的广泛应用，现代战争已经突破了传统模式，发展成为陆、海、空、天、电磁五位一体的战争2。在现代战术系统中，依靠单一传感器提供信息已无法满足作战需要，必须运用包括雷达、红外、激光、电子支援措施（Electronic Support Measures, ESM）等在内的多种有源、无源传感器来提供观测信息。这就需要对多数据源获取的信息进行综合处理，实时进行目标发现和优化综合处理来获取目标状态估计、目标属性及目标身份、态势评估、威胁估计等作战信息3。多传感器系统具有更强的生存能力，扩展了空间覆盖范围，并能够减少信息的模糊性而得到更精确的估计结果，这些优点都使得多传感器系统的应用越来越重要。在农业工程中，应用最多的是遥感系统。遥感应用主要是对地面目标或实体进行监视、识别与定位。其中，包括对自然资源，如水利资源、森林资源和矿产资源等的调查与定位；对自然灾害、原油泄露、核泄露、森林火灾和自然环境变化进行监测等。对一个农业资源监视系统，不仅可以对农作物的生长情况、种植面积、水肥状况、自然灾害监测、是否发生病虫害等进行监测和了解，而且还可以对农作物进行估产，通过遥感数据提取农作物的生物物理和生物化学参数，进行重要的生物和农学参数的反演和对一些重要的生态系统过程（如光合作用、碳氮循环等）的研究模拟，通过研究光谱数据与干物质产量、叶面积指数等基本农学参数间的关系，建立估产模型4；一个气象卫星上的遥感传感器要全天候地对天气与气候进行监视、预测，还要实时获取气象动云图。除了军事、农业，在医疗、林业和工业等领域也有广泛应用，然而在多传感器系统中，信息表现的多样性，信息数量的巨大性，信息关系的复杂性，以及要求信息处理的实时性，都已大大超出了一般计算机的信息综合处理能力，人们希望寻求一种新的方式来解决大量数据传输、储存时出现的问题。因此，对多源传感器数据的压缩算法研究便迫在眉睫。1.1.2 研究数据压缩的意义现代社会是一个信息大爆炸的社会，纷繁复杂的信息导致了人们要面对海量的数据。所以怎样快速高效的把数据压缩一直是人们追求的目标。数据压缩广泛应用于各个领域。公司企业的数据的备份需要把大量数据压缩以减少存储空间。为了充分利用信道，电视信号，流媒体等信息需要压缩。卫星探测后传输数据需要高效压缩。数据压缩通常分为无损压缩和有损压缩。对于不是很注重细节的数据如图像、视频，人们大都采用有损压缩技术，如MPEG，H.263，H.264等当今流行的压缩技术。8,9,10而对于像程序，电子档案等类似的重要信息，则必须采用无损压缩技术。从而数据恢复时不会破坏其完整性。人们对无损压缩技术的研究由来己久，其中最重要的无损压缩技术当属LZ系列的压缩算法和最小冗余度构造算法Huffman算法。当今的压缩技术基本基于这些算法衍生而来。11,12,13,14现今的多传感器测量系统中，为了精确测量一些冲击信号，需要对传感器输出信号进行高速、高分辨率采样15,16。这样势必会产生大量的需要存储的数据，占用很大的存储空间，同时也不便于实时传输。而在一些嵌入式系统中，存储器空间由于受到工艺、成本等各种因素的限制而非常有限，以至于经常采取降低采样率的办法来达到节省存储空间的目的，这是很不可取的。因此，为了保证测量精度，在采样率和分辨率均不能降低的情况下，对传感器信号进行压缩存储、传输是十分必要的。本课题就是在这种背景下产生的，它在研究并实现了LZW、Huffman、算术编码等一系列现今主流压缩编码的基础上，通过大量实验，采取LZ77和Huffman结合的一种方法去处理多源传感器的数据，并取得良好的效果。本课题的研究将有利于多源传感器系统的进一步发展，有效提高传输的效率，减少所用存储空间。1.2 国内外发展现状数据压缩技术是随着计算机、数字通信、信号处理和其他信息技术的迅速发展和广泛应用而发展起来，并于近年来逐渐发展形成为一门独立的学科。按照时间来划分，我们可将其产生和发展过程大致分为四个阶段，即发展初期、发展中期、发展近期和目前状况17,18,19,20。 （1）发展初期发展初期大约从18世纪末至20世纪50年代初，是数据压缩的萌芽时期。18世纪末Shepards 最早提出数据压缩的设想，他的关于“实数舍入为固定十进制数”的研究及相关论文，被认为是最早的数据压缩理论和实践活动。1939年，美国贝尔实验室的Dudley发明了第一个语音数据压缩系统声码器。1943年，莫尔斯发明了莫尔斯电报码，这是最早的基于统计方法的数据压缩的实例。取得这些卓越成就的先驱者，为数据压缩技术的发展做出了巨大的贡献21,22。 （2）发展中期 发展中期即发展成长期，大约从20世纪50年代初至70年代中，这段时期是理论基础飞速发展时期。信息论之父c. e. Shannon创立的信息论奠定了所有数据压缩算法的理论基础。1948年，Shannon 提出了信息熵理论，同时也给出了一种简单的编码方法Shannon编码23。1952年，r. m. fano又进一步提出了fano编码24。1952年，霍夫曼提出了著名的霍夫曼编码25，是一种经典的基于统计方法的数据压缩技术。1968年前后，p. elias发展了shannon和fano的编码方法，从数学角度构造出更为完美的shannon-fano-elias编码。沿着这一编码方法的思路，1976 年，j. rissane提出了一种可以成功地逼近信息熵极限的编码方法算术编码26。1982年，rissanen和g. g. langdon一起改进了算术编码。之后，人们又将算术编码与j. g. cleary和i. h. witten于1984年提出的部分匹配预测模型（ppm）相结合，开发出了压缩效果近乎完美的算法。 （3）发展近期发展近期是指数据压缩开始成为理论和技术上比较系统的一门独立学科的时期，大约从20世纪70年代中期至80年代末期。统计编码已经发展到了一个巅峰，大多数人沿着这一思路设法进行算法上的改进，始终达不到理想的效果。两个聪明的犹太人j. ziv和a. lempel完全跳出基于统计编码的设计思路，而是采用我们所熟知的查字典方法，创造出了压缩效果更好更快捷的基于字典的编码。我们通常用这两个犹太人姓氏的缩写，将这些算法统称为LZ系列算法。按照时间顺序，LZ系列算法的发展历程大致如下。1977年，ziv和lempel发表了一篇题为“顺序数据压缩的一个通用算法(a universal algorithm for sequential data compression)”的论文，论文中描述的算法被后人称为LZ77算法27。1978年，二人又发表了该论文的续篇“通过可变比率编码的独立序列的压缩(compression of individual sequences via variable rate coding)”，论文中描述了后来被命名为LZ78的压缩算法28。1984 年，t. a. welch发表了名为“高性能数据压缩技术(a technique for high performance data compression)”的论文，描述了他的研究成果，也就是后来非常有名的LZW算法，这种算法实质是LZ78算法的变种29。1990年后，t. c. bell等人又陆续提出了许多LZ算法的改进版本。 （4）目前状况 大约从20世纪90年代到至今的十几年时间，是目前数据压缩技术的目前状况。各个学科的发展和互联网的广泛应用为数据压缩技术提供了强大的动力和技术支持，数据压缩技术进入了一个迅速发展和广泛应用的新时期。数据压缩发展了几十年，人们不断提出新的压缩方法，使得数据压缩系统的各项指标不断提高，数据压缩的应用越来越广。近几年来，越来越多的数据压缩软件被开发和使用。2006年5月，IBM推出一款代号“Venom”的新数据压缩软件，来帮助用户砍掉他们一半的存储硬件成本和使用。2008年2月，微软推出了SQL Server 2008社区测试试用版，该项技术得到进一步发展，可以应用到几乎所有类型的数据。2008年9月，创业型数据精简厂商Ocarina Networks 推广其ECO System存储优化产品。这一产品拥有一系列新的功能，并能够支持更多的文件类型。在减少数据占用空间上，该公司承诺10：1的缩减比。在国内来讲，许多高校和学者对多媒体数据压缩技术和压缩标准做了很多的研究工作。例如90年代普遍发展CVD技术，尤其是近几年来，由北京大学、中科院、哈尔滨工业大学等高校联合研发，自主制定的音视频编解码标准AVS已获批准成为国家和国际标准。我们所熟知的国产软件超星数字图书馆，成功地采用了小波变换这一高比率的图像压缩算法30。 然而目前针对多源传感器数据压缩的研究在国内屈指可数。在2006年，刘贞等人提出了一种基于改进的二叉树算法对原始采样数据进行实时压缩31。根据多传感器系统信息冗余量大的特点，充分利用多传感器信号之间相关性和采样点之间相关性，对采样数据在二维方向上做去冗余处理，取得较好的压缩效果。但总体而言，这方面的研究十分欠缺。进入 21 世纪以来，科学技术的飞速发展，相关学科以及边缘学科的不断出现，拓宽了人们的研究思路，给数据压缩技术的发展注入了新的活力。因此，基于多源传感器数据的压缩技术一定会迅速发展和日益普及。1.3 本文研究的主要内容和论文结构本文在研究并实现了LZW、Huffman、算术编码等一系列现今主流压缩编码的基础上，通过大量实验和理论分析，选择采取LZ77和Huffman结合的一种方法去处理多源传感器的数据，并取得良好的效果。本文研究工作量很大，代码总计7700余行。本论文的构架如下：第一章：介绍了多源传感器系统在不同领域的应用，研究数据压缩的意义，以及通用数据压缩算法的发展历程和现今多源传感器数据压缩算法研究现状。 第二章：主要介绍了数据压缩的理论基础。首先以信息论的概念为出发点，介绍了熵的概念，给出了压缩算法性能评价指标，并指明压缩的极限所在。第三章：主要介绍了几种经典无损压缩算法，比如香农编码、Huffman编码、算术编码、LZW编码。第四章：介绍本文用来处理多源传感器数据的DEFLATE算法，在此基础上对算法进行一定改进，使其尽可能匹配更长字串，进一步缩短编码字长。第五章：在实现Huffman、LZW、deflate算法的基础上，针对多源传感器数据，使用改进DEFLATE算法与经典压缩算法作对比实验，并得出结论。第六章：对文章的内容进行总结，并对未来工作进行展望。2 数据压缩理论基础2.1 压缩技术对于压缩技术，实际上是指两种算法。一种是压缩算法，它取得输入X，生成一种需要较少二进制位的表示Xc，另一种是重构算法，它对压缩后的表示Xc执行操作，生成重构结果Y。这些操作的示意图如图2.1所示。本文将沿循惯例，将压缩算法和重构算法合在一起，称为压缩算法。图2.1 压缩与重构Fig.2.1 Compression and reconstruction根据重构需求，可以将数据压缩方法分为两大类：第一类是无损压缩，重构结果Y与X相同；第二类是有损压缩，这类压缩实现的压缩比通常高于无损压缩，但重构结果Y可能与X不同。2.1.1 无损压缩由名字可以看出，无损压缩技术中不存在信息损失。数据经过无损压缩后，可以从压缩数据中准确地恢复出原数据。无损压缩通常用在一些不允许原数据与重构数据之间存在任何差别的应用中。文本压缩是无损压缩的一个重要应用领域。重构结果与原文本完全一致是非常重要的，因为文本陈述中的毫厘之差，都可能造成语义谬以千里。例如下面两个句子“Do not send money”（不要打款）和“Do now send money”（现在就打款）。计算机文件和特定类型的数据（例如银行记录）同样要求不能有丝毫不同。无论是什么类型的数据，只要还会进行后续处理或“增强”，以给出更多信息，那保持数据的完整性就非常重要。在很多需要压缩的情况下，我们都希望重构结果与原数据完全相同。不过，也有许多其他情况，有可能为了获得更大的压缩比而放松这一要求。在这些情况下，可以采用有损压缩技术。2.1.2 有损压缩有损压缩技术会造成一些信息损失，采用有损技术压缩后的数据通常不能再准确还原或重构。但是，如果可以接受重构结果中存在这种失真，那么它所实现的压缩比通常要比无损压缩高得多。在许多应用中，并不需要实现准确重构。例如，在存储或传送语音时，并不需要每个语音采样的准确值。根据重构语音所需的质量，可以容忍每个采样值有不同程度的信息损失。如果重构语音的质量类似于在电话中听到的语音质量，那么可以容忍很大程度的信息损失。但是，如果要求重构语音达到CD光盘上听到的品质，那么可以容忍的信息损失量就要低得多。同样，在观看一段重构的视频时，重构结果与原视频之间存在一些差别通常没有什么问题，只要不出现虚像就行。因此，视频压缩通常采用有损方法。设计出一种数据压缩方案之后，需要能够测量它的性能。数据压缩的应用领域多种多样，所以用于描述和测量压缩性能的术语也有所不同。2.2 信息论简介尽管数据压缩的思想提出已有一千多年，然而系统的、理论的研究是始于香农创立的信息论，这一理论正是经典数据压缩技术的理论基础。香农创立的信息论，既给出了数据压缩的理论极限，同时又指出了数据压缩技术的实现途径。数据压缩与信息论是密不可分的。20世纪40年代末期，美国贝尔实验室的香农(C.E. Shannon)创立了信息论。一般来说，信息论理论基础的建立，始于香农1948年发表的被誉为信息论的开山之作通信的数学理论。他采用了专业术语熵，该术语原先在热力学中用来表示物理系统中的无序程度。这篇伟大的论文提出的信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，信息冗余的程度恰恰被信息熵及相关的定理用数学的手段进行了精确的描述。数据压缩的步骤一般分为三个部分：建模表达、二次量化和熵编码。首先，建立一定的模型，把原始数据转化为一种模型参考，然后通过二次量化，把模型参考转化为量化符号，最后，通过熵编码把二次量化后的符号变为压缩码流进行输出。数据压缩的一般步骤如图2.2所示。图2.2 数据压缩一般步骤Fig.2.2 General steps of data compression压缩码流量化符号原始数据原始数据建模表达二次量化熵编码2.2.1 信源信源是发出消息的源，这些消息承载着信息。按照信源输出符号的形式情况，可将信源分为离散信源和连续信源两大类。离散信源是指信源输出的符号可以取值于某一离散集合。连续信源是指信源输出的符号可以取值于某一连续区间。声音、图像等连续信源可以通过采样、量化编码等手段转化为离散信源，我们关心的是离散信源。按照信源输出符号序列的统计特性，可将信源划分为无记忆信源和有记忆信源。当信源输出符号序列统计独立时，称这种信源为无记忆信源；当信源输出符号序列统计不独立时，称这种信源为有记忆信源。本文着重讨论离散无记忆信源。2.2.2 信息量与熵设一个离散信源为X，集合A=x1,x2,xn表示N个符号的集合，在信源中，每个符号出现的概率是确定的，即存在一个概率分布表p1,p2,pn，并且满足k=1Npk=1。如果各符号的出现是各不相干的，或是说独立的，在信息论中，称信源X是无记忆的。设p(xi)为X在某时刻发出符号xi这一事件的概率，Shannon定义xi的信息量I(xi)为Ixi=-logpxi (2.1)式中i=1,2,n。Ixi的单位由对数的底来决定。当以2为底时，Ixi=-log2pxi，信息量的单位为比特（bit），当以自然数e为底时，其单位为奈特（nat）。由上式可见，信息量函数是一个减函数。具体来说就是一个随机事件发生的可能性越小，其信息量越多；发生的可能性越大，则信息量越少。当X代表信源输出的所有可能的符号集合时，将X的各符号xi的信息量Ixi按概率Pxi进行平均，可得X的各符号的平均信息量为HX=i=1NlogpxiIxi=-i=1Npxilogpxi (2.2)因为这个表示式与热力学中的“熵”的形式相同，所以在信息论中HX称为信源 X的熵。信息论的原理表明，如果知道一个无记忆信源X的熵HX，那么总能找到一种信息源的压缩编码方法，使每个符号所需的比特数尽量接近HX。Shannon信息论认为，信源的平均信息量（熵）就是无失真编码的理论极限。对于离散无记忆信源，当以等概率输出所有的信息符号时（即pxi=1n），此时可求得信源的熵为 HX=-i=1N1nlog1n=-log1n=logn (2.3)此值是熵的最大值，定义为最大熵H0X。2.3 压缩性能评价指标可以用多种方式来评估一种压缩算法。我们可以测量算法的相对复杂度、实现算法所需要的内存量、算法在给定计算机上的运行速度、压缩比、压缩时间、编码后信道的信息传输率、编码效率，以及码的冗余度。在算法理论评估时通常关注后3点，在实际应用上，仅关注压缩比、压缩时间。现对其进行讨论。1） 压缩比压缩比R是很亮数据压缩系统性能好坏的一个重要指标，其定义为C=压缩数据长度（比特）原数据长度（比特） (2.4)其物理含义，是表示被压缩之后的数据流长度所占原始输入数据流长度的百分比。例如，C=0.7，表示经过压缩器压缩之后的输出数据流的长度占原始输入数据流长度的70%。通常C1，则表示不再是压缩，而是扩大。压缩比C有时也称为bpb，是bit per bit（每比特比特）的缩写，表示压缩输入数据流中一比特平均所需的比特数。在图像压缩中，压缩比C又称为bpp，是bit per pixel（每像素比特）的缩写，表示压缩输入图像的每个像素平均所需的比特数。在文本压缩中，压缩比C又称为bpc，是bit per character（每字符比特）的缩写，表示压缩输入数据流中一个字符平均所需的比特数。2） 编码后信道的信息传输率编码后信道的信息传输率是指编码后信道传送的平均每个码元载荷的信息量，简称为码率，单位为“比特/码元”或“比特/码符号”。当原始信源S给定时，信源熵H(S)就给定了，而编码后每个信源符号平均用L个码元来表示，故编码后信道的信息传输率R=H(S)L（比特/码元） (2.5)3） 编码效率为衡量编码效果，引入编码效率，它表示编码后实际信息量和能载荷最大信息量的比值。假设码元序列为r进制码元，则每个码元所能载荷的最大信息量Rmax=logr。因此编码效率可以定义每个码元载荷的平均信息量与它所能载荷的最大信息量的比值，表示为=RRmax=H(S)Llogr (2.6)4） 冗余度为了衡量各种编码方法与理想编码的差距，定义码的冗余度为=1- (2.7）3 经典无损压缩算法无损压缩技术即通常所说的通用压缩技术也称为信息保持编码、熵编码、无失真编码等，也就是根据一定方法对大量数据进行编码处理以达到信息压缩存储过程，在数据的压缩过程中不允许精度的损失，被压缩的数据应该能够通过解码恢复到压缩以前的原状态。主要用于文本文件、数据库、程序数据和特殊应用场合的图像数据（如指纹图像、医学图像等）的压缩。这类算法压缩率较低，一般为1/21/5。通常压缩对象是文字或数字等要求精确的数据时，无损压缩是必然的选择。无损压缩从压缩模型上大体可以分为基于统计的压缩算法和基于字典的压缩算法。具体的分类图如图3.1所示。无损数据压缩基于统计压缩算法基于字典压缩算法香农编码(Shannon)游程编码(RLC)霍夫曼编码(Huffman)算术编码ArithmeticLZ77算法LZ78算法LZW算法图3.1 无损压缩算法分类Fig.3.1 Classification of lossless compression algorithms3.1 香农编码香农编码是最早的最佳变长编码方法。其编码方法由香农第一定理的证明过程给出，选择码字长度Li满足下式：-logpi Li-logpi+1 (i=1,2,q) (3.1)香农编码的基本思想是概率匹配原则，即概率大的信源符号用短码，概率小的信源符号用长码，以使减小平均码长，提高编码效率。香农编码的步骤如下：1）将信源发出的q个消息，按出现概率递减顺序进行排列；p1p2pq2）由（3.1）公式计算出码长Li；3）计算第i个消息的累积分布函数Fi=k=1i-1P(sk)；4）将累积分布函数Fi变换成二进制数；5）取Fi二进制数的小数点后Li位作为第i个符号的二进制码字Wi。由式（3.1）可知，香农码的平均码长L满足HSLpj，则LiLj。即概率大的信源符号所对应的码长不大于概率小的信源符号所对应的码长。2）对于二元最佳码，两个最小概率的信源符号所对应的码字具有相同码长。而且这两个码字，除了最后一位码元不同以外，前面各位码元都相同。1952年，霍夫曼提出了一种构造最佳码的方法。所得的码字平均码长最短，是一种最佳变长码。二元霍夫曼码的编码步骤如下：1）将q个信源符号si按出现概率P(si)递减次序排列；2）将两个最小的概率进行组合，然后将该组合后的概率之后作为一个新的符号概率，重新按照步骤1排列好，并继续这一步骤，始终将较大的概率分支放在上部，较小的概率分支放在下部，一直到概率总和为1为止。3）对每对组合中的上边指定为0，下边指定为1，或相反；4）将上述结果由下至上构造一颗哈夫曼树，由树的结构就可以决定每个字符的码字。现举例说明，已知信源的5个符号及其出现概率如图3.2所示。对其进行霍夫曼编码的方法步骤如下： a5601a6 0.025a5 0.025a4 0.050a3 0.150a2 0.250a1 0.50001a450a34000a2300a121.00图3.2 Huffman编码树Fig.3.2 Huffman coding tree 1）将最下边两个符号a5，a6合为一组，上边指定为0，下边指定为1，然后将a5，a6合并为一个辅助符号a56，概率为0.05。2）将概率最小的a4与a56组合为一组，上边指定为0，下边指定为1，然后将a4与a56合并为辅助符号a45，概率为0.10。3）将概率最小的a3与a45组合为一组，上边指定为0，下边指定为1，然后将a3与a45合并为辅助符号a34，概率为0.25。4）将概率最小的a2与a34组合为一组，上边指定为0，下边指定为1，然后将a2与a34合并为辅助符号a23，概率为0.50。5）将概率最小的a1与a23组合为一组，上边指定为0，下边指定为1，然后将a1与a23合并为辅助符号a12，概率为1.00。于是，便完成了编码过程，形成了树的构造，如图所示。右边是树根，左边是树叶。这样，就得到了六个信源符号的编码码字分别为：0，10，110，1110，11110，11111。此例中，平均码长为：L=i=16lipi=0.51+0.252+0.153+0.054+0.0255+0.0255=1.9 （码元/信源符号）3.2.2 霍夫曼解码方法霍夫曼解码是霍夫曼编码的反变换。接受端对收到的已编码的压缩数据流译码时，必须根据编码树，或者根据由编码树编制的编码表，才能进行译码。因此发送端应将编码树或编码表的压缩数据流一起发送到接收端。在上例中霍夫曼编码的编码树所编制的编码表如表3.1所示。接收端按照发送端发来的码表或码树即可实现译码。表3.1 Huffman编码表Table.3.1 Huffman coding table信源符号编码码长a101a2102a31103a411104a5111105a6111115霍夫曼解码算法如下：从树根开始，读入压缩数据流（霍夫曼码）的第一位，若为0，则沿树的上分支走，若为1，则沿树的下分支走；然后，读入压缩数据流（霍夫曼码）第二位，向树叶前进一节；如此一直到树叶，于是就得到了原始未压缩的码字。3.2.3 霍夫曼编码算法程序模块霍夫曼编码的效率虽然很高，但是霍夫曼编码假定压缩器（编码器）事先知道信源输出的所有符号的发生概率，而在实际应用中很难事先确知信源输出数据中各符号发生的概率，因此，也就很难保证准确按照各符号发生的概率进行霍夫曼编码。为了解决这个问题，起初人们一般是根据常用的文本中各符号出现的统计规律得出的字符集概率进行霍夫曼编码。但由于在实际系统中，不同的信源，其输出字符的概率差异较大，因而编码效果不太理想，达不到预期目的。为了解决上述问题，本文采取对需要编码的源数据进行扫描，统计计算出各字符出现的概率，然后进行霍夫曼编码。相应的算法用以下程序模块图表示，如图3.3。压缩模块对源数据编码显示霍夫曼模型霍夫曼树转化成代码构造霍夫曼树输出统计计数值调整计数值数量级统计字符概率图3.3 Huffman算法程序模块图Fig.3.3 Program module graph for Huffman3.3 算术编码3.3.1 算术编码原理理论上，用Huffman方法对源数据流进行编码可达到最佳编码效果。但由于计算机中存储、处理的最小单位是“位”，因此，在一些情况下，实际压缩效果与理论压缩比的极限相去甚远。例如，源数据流由X和Y两个符号构成。它们出现的概率分别是2/3和1/3。理论上，根据字符X的熵确定的X的最优码长为：HX=-log23=0.585 bit字符Y的最优码长为：HY=-log13=1.58 bit这表明，若要达到最佳编码效果，字符X的码长应取为0.585位，字符Y的码长应取为1.58位。计算机中不可能有非整数位出现。硬件的限制使得编码只能按整数位进行。用Huffman方法对这两个字符进行编码，得到X、Y的编码码字分别为0和1。显然，对于出现概率较大的字符X不能给予较短的码字。这就是实际编码效果不能达到理论上给出的压缩比的原因。为了解决由于计算机中必须用整数位进行编码而带来Huffman方法压缩效果不理想的问题，人们进行了许多研究，提出了算术编码方法。算术编码没有延用数据编码技术中用一个特定的码字代替一个输入字符的一般做法，它把要压缩处理的整段数据映射到实数0,1)区间内的某一小区段，构造出区间内的某个数值。这个数值是输入数据流的唯一可译代码。下面用一个例子来说明算术编码的原理。设信源符号集S由5个信源符号a,e,i,o,u组成，其出现概率和顺序如表3.2所示。表3.2 信源符号及其范围table.3.2 Source symbols and their probability range信源符号概率范围a0.20,0.2)e0.30.2,0.5)i0.20.5,0.7)o0.10.7,0.8)u0.20.8,1)假设需要进行编码的符号流eaii。在编码开始前，对应的数值范围是整个半开区间0, 1)。编码完第一个信源符号后，范围缩小到0.2, 0.5)。然后当编码符号a时，范围压缩到新区间的前1/5，即区间为0.2, 0.26)。如此继续下去，编码器的输出数值范围不断缩小，最终的区间为0.236, 0.2384)，则最后编码的值v可为区间0.236, 0.2384)上的任一值，设为0.2365。图3.4显示了整个编码的区间变化过程。而解码过程与其正好相反，首先查看最后编码的值落入哪一个信源符号的数值范围（表3.2中的范围列），本例所示编码值0.2365在区间0.2,0.5)之间，所以第一个符号为“e”；然后从编码数值中消去第一个符号“e”的影响，即减去“e”的下界值，然后除以“e”对应的宽度（概率值），即(0.2365-0.2)/0.3=0.1216，查找这一结果落入哪个符号对应的数值范围，得到第二个符号a。重复上述两步直到解出整个符号流为止。uoieauoieauoieauoieauoiea 编码流： e a i i 1 0.5 0.26 0.242 0.2384 0 0.2 0.2 0.23 0.236图3.4 算术编码每一步区间变化过程Fig.3.4 Process of interval changing of arithmetic coding可以把算术编码分成三部分：建模，概率统计和编码。在这三个部分中通常人们视觉可以感受到的是建模的过程，而最不可见的是编码器。在这两个模块之间的是概率统计模块，通过对数据结构的操作来记录符号概率的频数。而且概率统计的过程通常是由编码器完成，并且需要在给出当前需要编码的符号之前给出所有符号目前的统计概率（记录当前符号总共出现的次数）。建模过程和编码过程对于整个编码机制都是透明的，即建模模块并不知道每个符号的概率，编码器也没有符号的识别器和所有符号表的大小。以上三部分的组织情况如图3.5所示。图3.5 建模，概率统计及编码器模块组织情况Fig.3.5 the organization of modeling, probability counting and encoder module但是在1987年Witten等人提出的算术编码实现中实际只有一个接口层，就是只采用建模和编码两个模块。而这种实现方法使用一个cum_freq数组来记录累积概率，而图3.5中的符号识别器实际是每个符号在模型和编码器之间传输的过程。这就使得建模和编码两个模块同时使用一个数组来保存他们的信息。3.3.2 算术编码算法程序模块与基本Huffman方法类似，用基本算术编码方法编码需要对源文件进行两遍扫描处理。第一次扫描统计出各字符出现的次数，然后调整统计数字的范围和数量级，使之适应算术编码方法的要求。算法的程序结构如图3.6。压缩模块输出码字刷新编码器为文件编码初始化算术编码器输出统