搜索
托斯卡纳文艺复兴的最初摇篮，意大利的静谧空间…首页关于珞樱推荐留言记忆«基于颜色特征的图像检索系统设计入侵检测通信机制的设计»基于算术编码的数据压缩算法研究与实现六月25th,2008在现今的电子信息技术领域，由于需要处理的数字化的信息（尤其是多媒体信息）通常会特别庞大，如果不对其进行有效压缩就难以得到实际应用，数据压缩的目的即是通过有效减少数据文件的冗余信息而使数据文件可以以更快的速度传输或在更少的空间储存。因此数据压缩技术已成为当今数字通信、存储和多媒体娱乐的一项关键的共性技术。本文由香农熵理论和统计编码的原理开始，逐步展开对基于算术编码的数据压缩的研究与应用的讨论：从算术编码的原理、产生条件、以及研究算术编码的目的意义等，到具体算术编码方案的分析比较以及其C++语言的实现方案，有重点的对算术编码的特点进行了分析和阐述。而针对算术编码在处理二元符号时高压缩比、低复杂度的特点，本文着重探讨了算术编码方法处理二元数据流的过程的特点和效率优势，并将算术编码的不同实现方法进行了分析和比较，特别是对N阶自适应编码的特点和处理文字信息的优势进行了分析，然后将其和与之较为类似的Huffman编码进行了比较，通过比较得出了算术编码具有但Huffman编码不具有的在处理数据流方面的优势，即Huffman编码必须在得到全部数据文件之后才可以对文件进行编码处理，而算术编码方法可以在只得到数据流片段的情况下就开始对数据进行压缩，使得当处理数据流信息时在保证高压缩比的同时具有了很大的灵活性。本文通过对算术算法特点和应用方向的研究，阐明其在数据压缩领域不可取代的地位及在处理流片段数据所具有的在压缩比和灵活性方面的优势，展示出算术编码的强大生命力和独特优势。最后，应用文中研究得到的算术编码方法和实现模型，在Windows系统下，使用VisualC++作为编程工具，实现了算术编码及其应用程序界面，，对于接近二进制流的文件，本设计具体令人满意的压缩效果，对其他格式的文件也有较好的压缩效果，达到了论文的设计目标。关键词：算术编码、无损压缩、自适应模式目录摘要IIABSTRACTIII第一章绪论11.1数据压缩11.2数据压缩的现状与发展趋势21.3课题研究的意义4第二章算术编码原理及特点52.1统计编码52.2算术编码原理62.2.1算术编码理论62.2.2算术压缩模式8第三章典型算术编码方案分析123.1WNC算法算术编码123.2基于上下文的二进制算术编码143.3自适应算术编码算术及其实现16第四章算术编码系统的实现204.1软件模块设计204.2软件模块的具体实现214.2.1输入输出模块的实现214.2.2压缩模块的实现244.2.3解压模块的实现274.3压缩效率分析304.4软件设计的优点与不足314.5软件设计值得改进的地方31第五章算术编码总结33参考文献35致谢36附录37算法源代码37摘要ABSTRACTNowadays,asthedigitalinformation(especiallythemultimediainformation)becomesmorevoluminousinthetelegraphyfield,theinformationshouldbecompressedavailably.Thepurposeofdatacompressionisreducingtheredundancyofdatafileseffectivelyforfastertransferand/orsmallerspaceforstorage.Sothedatacompressiontechnologybecomesacommonpivotaltechnologyfordigitalcommunication,storageandmultimediaentertainment.FromShannonentropytheoryandthestatisticscodingtheory,thispapersetsforththeresearchandapplicationofthedatacompressionwhichbasedonArithmeticCoding,includingthearithmeticcodingtheory,thehavingconditionsandthepurposeofarithmeticcodingandthentheresearchofthespecificimplementationplanwithC++languageofarithmeticcoding.Againstthepointofarithmeticcoding,thispaperanalysisandexpoundsitssuperiorityaboutit.Forthecharacteristicofthesuperiorityofcompressionratioandcomplexity,thispaperprobeintotheprocessofdealwiththebinarydatastreamsandthesuperiorityofefficiency.Andtakingcomparedbetweenthedifferentimplementationplan,especiallythecharacteristicofOrder-Nadaptivecodingandthesuperiorityindealingwiththetextualinformation.ThencomparesarithmeticcodingwiththeHuffmancodingmethodwhichisveryresembleswithit,gettingthesuperiorityindealingwiththedatastreamfragment:arithmeticcodingdoesn’tneedthecompletefilebeforeneedtoencodeit,butHuffmancodingmethodcannotdoitlikethis.Thatmeansarithmeticdonotonlyhavethesuperiorityincompressionratiobutalsoinflexibility.Throughtheresearchofthecharacteristicandtheapplicationdirectionofarithmeticcoding,thispaperilluminatestheunplacedstatusofArithmeticCoding,theoutstandingcompressratioandagilityindealwithdatastreamfragmentsandbringsforththelifeforceanditsuniquesuperiority.Atlast,bythearithmeticcodingmethodandimplementmodelresearchedinthispaper,completedthecodingmethodanditscorrespondinglyapplicationprocedureinterfaceusingVisualC++programmingtoolsintheWindowsoperatingsystem.Thetestresultshowsthattothefilesclosetothebinaryfiles,thisdesignprocuresasatisfactoryoutcome.Andtothefilesinotherformat,thisdesignalsogetapreferablyresults.So,thedesignachievesthegoalrequiredinthispaper.KEYWORDSarithmeticcoding,losslesscompression,adaptivemodel第一章绪论1.1数据压缩数据压缩，用一句话说，就是用最少的数码来表示信号，即将字符串的一种表示方式转换为另一种表示方式，新的表示方式包含相同的信息量，但是长度比原来的方式尽可能的短。其作用是：能较快地传输各种信号，如传真、Modem通信等；在现有的通信干线并行开通更多的多媒体业务，如各种增值业务；紧缩数据存储容量，如CD－ROM、VCD和DVD等；降低发信机功率，这对于多媒体移动通信系统尤为重要。也就是说，通信时间、传输带宽、存储空间甚至发射能量，都可能成为数据压缩的对象。数据之所以能够被压缩是基于以下几点的考量：首先，数据中间常存在一些多余成分，既冗余度。如在一份计算机文件中，某些符号会重复出现、某些符号比其他符号出现得更频繁、某些字符总是在各数据块中可预见的位置上出现等，这些冗余部分便可在数据编码中除去或减少。冗余度压缩是一个可逆过程，因此叫做无失真压缩，或称保持型编码。其次，数据中间尤其是相邻的数据之间，常存在着相关性。如图片中常常有色彩均匀的背影，电视信号的相邻两帧之间可能只有少量的变化影物是不同的，声音信号有时具有一定的规律性和周期性等等。因此，有可能利用某些变换来尽可能地去掉这些相关性。但这种变换有时会带来不可恢复的损失和误差，因此叫做不可逆压缩，或称有失真编码、摘压缩等。此外，人们在欣赏音像节目时，由于耳、目对信号的时间变化和幅度变化的感受能力都有一定的极限，如人眼对影视节目有视觉暂留效应，人眼或人耳对低于某一极限的幅度变化已无法感知等，故可将信号中这部分感觉不出的分量压缩掉或”掩蔽掉”。这种压缩方法同样是一种不可逆压缩。数据压缩跟编码技术联系紧密，压缩的实质就是根据数据的内在联系将数据从一种编码映射为另一种编码。压缩前的数据要被划分为一个一个的基本单元。基本单元既可以是单个字符，也可以是多个字符组成的字符串。称这些基本单元为源消息，所有的源消息构成源消息集。源消息集映射的结果为码字集。可见，压缩前的数据是源消息序列，压缩后的数据是码字序列。若定义块为固定长度的字符或字符串，可变长为长度可变的字符或字符串，则编码可分为块到块编码、块到可变长编码、可变长到块编码、可变长到可变长编码等。应用最广泛的ASCII编码就是块到块编码。对于数据压缩技术而言，最基本的要求就是要尽量降低数字化的在码事，同时仍保持一定的信号质量。不难想象，数据压缩的方法应该是很多的，但本质上不外乎上述完全可逆的冗余度压缩和实际上不可逆的嫡压缩两类。冗余度压缩常用于磁盘文件、数据通信和气象卫星云图等不允许在压缩过程中有丝毫损失的场合中，但它的压缩比通常只有几倍，远远不能满足数字视听应用的要求。在实际的数字视听设备中，差不多都采用压缩比更高但实际有损的媳压缩技术。只要作为最终用户的人觉察不出或能够容忍这些失真，就允许对数字音像信号进一步压缩以换取更高的编码效率。摘压缩主要有特征抽取和量化两种方法，指纹的模式识别是前者的典型例子，后者则是一种更通用的摘压缩技术。1.2数据压缩的现状与发展趋势设计具体的压缩算法时，设计者首先要做的是寻找一种能尽量精确地统计或估计信息中符号出现概率的方法，然后还要设计一套用最短的代码描述每个符号的编码规则。统计学知识对于前一项工作相当有效，迄今为止，人们已经陆续实现了静态模型、半静态模型、自适应模型、Markov模型、部分匹配预测模型等概率统计模型。第一个实用的编码方法是由D.A.Huffman在1952年的论文”最小冗余度代码的构造方法”[1]中提出的。直到今天，许多”数据结构”教材在讨论二叉树时仍要提及这种被后人称为Huffman编码的方法。Huffman编码看似简单，但却影响深远，其编码效率高，运算速度快，实现方式灵活，从20世纪60年代至今，在数据压缩领域得到了广泛的应用。1968年前后，P.Elias[2]发展了Shannon和Fano的编码方法，构造出从数学角度看来更为完美的Shan