笨笨数据压缩教程

笨笨数据压缩教程大家好，我叫王笨笨。在过去的几个月里，因为工作需要，我比较多的关注了数据压缩技术的现状及其发展，并亲自动手实现了几个数据压缩模块。在这一过程中，我发现这一领域的中文技术资料极其匮乏。为此，王笨笨决定编写这本《数据压缩教程》，以便有一个总结记录这几个月学习过程的机会。谁需要看这本书如果你仅仅希望将你自己的一大堆霸占硬盘空间的大文件压缩成单个的小文件，那么不要看这本书，去看Winzip，ARJ，RAR等应用程序的帮助好了；如果你仅仅想把手中的精美图片、语音信息、CD音轨乃至动画、视频压缩保存，那么不要看这本书，去学习和使用Photoshop、MP3Compress等多媒体文件编辑压缩工具就足够了。如果你对数据能被压缩到如此之小感到惊讶和迷惑不解，如果你想知道上面提到的这许多压缩工具是如何工作的，如果你正要为自己的应用程序加入灵活的压缩、解压缩模块，如果你正在编写自己的图形图像编辑工具……那么，这本书就是你的选择，这里有详细的算法描述，有可供直接使用的源代码，有Internet上关于压缩技术的资源介绍，有对你进一步学习压缩技术的有效建议，快来吧！不过记住，王笨笨比较笨，书中一定有不少缺点和错误，还望诸位高手指正。压缩技术概貌首先大致了解一下压缩技术的现状吧，不懂没有关系，了解一下而已。压缩技术大致可以按照以下的方法分类：;;;;;;;;;;;;;压缩技术;;;;;;;;;;;;;;;|;;;;;;;;;;/------------------------------\;;;;;通用无损数据压缩;;;;;;多媒体数据压缩(大多为有损压缩);;;;;;;;;|;;;;;;;;;;;;;;;;;;;;|;;/----------------\;;;;;;;/------------------------------------\基于统计;;;;;基于字典;;音频压缩;;;;图像压缩;;;;;;;;;;视频压缩模型的压;;;;;模型的压;;;;|;;;;;;;;|;;;;;;;;;;;;;;|缩技术;;;;;;缩技术;;;;;MP3等;;;/-------------------、;;;AVI;;|;;;;;;;;;;|;;;;;;;;;;;二值;灰度;彩色;矢量;;MPEG2等;/------\;;;;;;/-------------\;;;图像;图像;图像;图像Huffman;算术;;;LZ77;LZ78;LZW;;;;|;;;|;;;|;;;|编码;;编码;;;;\-------------/;;传真机;FELICS;GIF;ostScript;|;;;;;|;;;;;;;;;|;;;;;;;标准;;JPEG等;JPEG等WindowsWMF等UNIX下;;接近无损;;PKZIP、LHarc、ARJ、的COMPACT压缩极限;;UNIX下的COMPRESS程序等;;的高级应用;程序等本书也将大致遵循上面的结构展开，准备好了吗？开始关于版权问题的几点补充说明《笨笨数据压缩教程》中介绍的压缩算法中，有一部分受到美国专利法的保护（例如LZW算法的某些部分和高阶算术压缩算法的某些细节等）。虽然在这一问题上王笨笨认为在计算机领域对某种抽象的算法而非程序实现加以保护有阻碍技术进步之嫌，但仍然需要提醒那些试图在自己的程序中实现某种压缩技术并将程序用于商业目的的人们，在实现以前，最好先对技术专利情况加以了解，以免最终陷入商业被动。《笨笨数据压缩教程》中提供的源代码有一部分由王笨笨本人编写，有一部分由文思软件工作室的其他程序员编写，还有部分源代码由王笨笨从因特网上获得，但这些代码全部都是“自由代码”(freecode)。如果你打算在你的程序中使用这些代码，你必须仔细阅读并遵守以下所有规定：你可以使用、复制、发布、修改这些代码，并将其用于包括个人、组织、商业在内的各种目的，你不需要为此向我们支付任何款项。我们不为使用这些代码的后果承担任何法律责任。但如果你在代码中发现了错误或对代码存有疑问，你可以使用E-Mail方式通知我们，我们会在力所能及的前提下提供技术支持。不要以任何方式假定是你编写了这些代码。如果你将这些代码用于你的程序中，请你务必于程序的显著位置（例如About对话框或Readme文档中）注明“本程序中的某些代码由文思软件工作室提供”。目录第一章：轻松一下：数据压缩简史第二章：技术准备：概率、模型和编码第三章：奇妙的二叉树：Huffman的贡献第四章：向极限挑战：算术编码第五章：聪明的以色列人(上)：LZ77第六章：聪明的以色列人(下)：LZ78和LZW第七章：小结一下：压缩方法的比较和应用（附索引数据的压缩）第八章：抓住特性：从行程编码到二值和灰度图像压缩第九章：熟悉的格式：GIF和TIFF第十章：损失一点精度：伟大的JPEG第十一章：媒体世界：声音和视频第十二章：更高的目标：回顾与展望你一定看出了本书目录中显现出来的层次关系。是的，本书是按照前言中对压缩技术的分类编排的。假如你想系统地学习和掌握压缩技术，最好按照章节顺序依次阅读；当然，如果你仅仅把本书当作了解压缩技术的窗口，或者将本书作为一本速查手册，那么，你完全可以根据你的需要进行跳跃式的浏览。第一章轻松一下：数据压缩简史算起来，数据压缩的起源要比计机的起源早得多，有兴趣的读者可以翻阅一下任何一本成语辞典，查查诸如“二桃三士”、“萧规曹随”之类的短语涵盖了多少信息内容。认真一点：数据压缩技术在计算机技术的萌芽时期就已经被提上了议事日程，有关信息如何被高效存储和传递的话题不断被军事科学家、数学家、电子学家讨论来、讨论去。终于，随着信息论的产生和发展，数据压缩也由热门话题演变成了真正的技术。通用无损数据压缩科学家在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。贝尔实验室的ClaudeShannon和MIT的R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的Shannon-Fano编码方法。D.A.Huffman于1952年第一次发表了他的论文“最小冗余度代码的构造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。从此，数据压缩开始在商业程序中实现并被应用在许多技术领域。UNIX系统上一个不太为现代人熟知的压缩程序COMPACT就是Huffman0阶自适应编码的具体实现。80年代初，Huffman编码又在CP/M和DOS系统中实现，其代表程序叫SQ。在数据压缩领域，Huffman的这一论文事实上开创了数据压缩技术一个值得回忆的时代，60年代、70年代乃至80年代的早期，数据压缩领域几乎一直被Huffman编码及其分支所垄断。如果不是后面将要提到的那两个以色列人，也许我们今天还要在Huffman编码的0和1的组合中流连忘返。让我们沿着Huffman的轨迹再向后跳跃几年，80年代，数学家们不满足于Huffman编码中的某些致命弱点，他们从新的角度入手，遵循Huffman编码的主导思想，设计出另一种更为精确，更能接近信息论中“熵”极限的编码方法——算术编码。凭借算术编码的精妙设计和卓越表现，人们终于可以向着数据压缩的极限前进了。可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。当然，算术编码同时也给程序员和计算机带来了新的挑战：要实现和运行算术编码，需要更为艰苦的编程劳动和更加快速的计算机系统。也就是说，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间。这就是为什么算术编码不能在我们日常使用的压缩工具中实现的主要原因。那么，能不能既在压缩效果上超越Huffman，又不增加程序对系统资源和时间的需求呢？我们必须感谢下面将要介绍的两个以色列人。直到1977年，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，研究者们一直在绞尽脑汁为使用Huffman编码的程序找出更快、更好的改进方法。1977年以后，一切都改变了。1977年，以色列人JacobZiv和AbrahamLempel发表了论文“顺序数据压缩的一个通用算法”(AUniversalAlogrithemforSequentialDataCompression)。1978年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(CompressionofIndividualSequencesviaVariable-RateCoding)。所有的一切都改变了，在这两篇论文中提出的两个压缩技术被称为LZ77和LZ78(不知为什么，作者名字的首字母被倒置了)。简单地说，这两种压缩方法的思路完全不同于从Shannon到Huffman到算术压缩的传统思路，倒是和本章开头所举的成语辞典的例子颇为相似，因此，人们将基于这一思路的编码方法称作“字典”式编码。字典式编码不但在压缩效果上大大超过了Huffman，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。1984年，TerryWelch发表了名为“高性能数据压缩技术”(ATechniqueforHigh-PerformanceDataCompression)的论文，描述了他在SperryResearchCenter(现在是Unisys的一部分)的研究成果。他实现了LZ78算法的一个变种——LZW。LZW继承了LZ77和LZ78压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受（有的研究者认为是由于Welch的论文比Ziv和Lempel的更容易理解），实现也比较简单。不久，UNIX上出现了使用LZW算法的Compress程序，该程序性能优良，并有高水平的文档，很快成为了UNIX世界的压缩程序标准。紧随其后的是MS-DOS环境下的ARC程序(SystemEnhancementAssociates,1985)，还有象PKWare、PKARC等仿制品。LZ78和LZW一时间统治了UNIX和DOS两大平台。80年代中期以后，人们对LZ77进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。HaruyasuYoshizaki(Yoshi)的LHarc和RobertJung的ARJ是其中两个著名的例子。LZ77得以和LZ78、LZW一起垄断当今的通用数据压缩领域。目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的PKZip到现在的WinZip，特别是随着Internet上文件传输的流行，Z[wiki]IP[/wiki]格式成为了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持ZIP格式。多媒体信息的压缩今天的程序员们和设计师们往往乐此不疲地为计算机更换更大的硬盘，增加更多的内存，其主要目的是为了存放和处理越来越多的声音、图像和视频数据。对声音、图像、视频等多媒体信息的压缩有两条思路，要么采用成熟的通用数据压缩技术进行压缩，要么根据媒体信息的特性设计新的压缩方法。事实上，人们在两条道路上都作了卓有成效的探索。还记得GIF格式吗？GIF可以把原始图形文件以非常小数据量存储，可以在同一个文件中存储多幅图像从而实现动画效果。知道GIF中的图像使用什么方法压缩的吗？LZW!原来如此啊。GIF大概是使用通用压缩技术压缩图像信息的最成功的例子，当然，GIF文件中除了经过LZW压缩的像素信息以外，还保存有图像的各种属性信息以及图像所使用的调色板信息等。GIF精确地保留了原始图像的每一个像素信息，是无损图像压缩的代表。根据媒体特性量身定制的压缩方法中，行程编码(RLE:Run-LengthEncoding)是最为简单、最容易被想到的一种。大多数计算机中产生的图像(和现实世界的图像例如照片不同)都具有着大面积重复的颜色块，为什么非要用无数个完全相同的颜色值来表示某块图像呢？我们完全可以用一个颜色值加一个重复次数来表示这一块图像，冗余度由此减小了，这就是RLE方法的基本思路。显然，它不适于用来压缩照片、声音等很少连续重复信息的数据。RL