基于字典编码的数据压缩技术的改进与实现

毕业设计报告1. 目录毕业设计报告11.目录12.前言13.对字典编码的认识23.1.数据压缩简史23.1.1.通用无损数据压缩23.1.2.多媒体信息的压缩33.2.数据压缩的基本理论与分类43.2.1.什么是熵43.2.2.模型43.2.3.编码53.2.4.压缩技术概貌53.3.字典编码原理64.字典编码方法的分类与特点64.1.LZ77算法64.2.LZ78算法74.3.LZSS算法74.4.LZW算法85.不足与改进105.1.对技术的改进105.1.1.零搜索105.1.2.动态编码长度105.2.设计方法的改进106.算法实现116.1.数据结构116.1.1.常量定义：116.1.2.编码类：116.1.3.解码类：126.2.编码算法136.2.1.流程描述136.2.2.核心代码136.3.解码算法176.3.1.流程描述176.3.2.核心代码187.总结232. 前言1946年,第一台计算机ENIAC诞生.之后的五十多年里,计算机领域有了突飞猛进的发展,计算机所能处理的数据也是成倍的增长.这就对数据存储设备有了更高的要求,同时,数据压缩技术也应运而生.尤其是近年来的”信息爆炸”概念的提出,使得数据压缩成为人们争相研究的对象,因此学习一下数据压缩的知识,研究数据压缩的技术是十分有必要的.3. 对字典编码的认识3.1. 数据压缩简史3.1.1. 通用无损数据压缩很早以前,科学家就在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。1948&1949贝尔实验室的 Claude Shannon (1948) 和 MIT 的 R.M.Fano (1949)几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。1952D.A.Huffman第一次发表了他的论文“最小冗余度代码的构造方法”(A Method for the Construction of Minimum Redundancy Codes)。从此，数据压缩开始在商业程序中实现并被应用在许多技术领域。在数据压缩领域，Huffman 的这一论文事实上开创了数据压缩技术一个值得回忆的时代，60 年代、70 年代乃至 80 年代的早期，数据压缩领域几乎一直被 Huffman 编码及其分支所垄断。如果不是下面的这两个以色列人，也许我们今天还要在 Huffman 编码的 0 和 1 的组合中流连忘返。1977以色列人 Jacob Ziv 和 Abraham Lempel 发表了论文“顺序数据压缩的一个通用算法”(A Universal Alogrithem for Sequential Data Compression)。1978他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(Compression of Individual Sequences via Variable-Rate Coding)。所有的一切都改变了，在这两篇论文中提出的两个压缩技术被称为 LZ77 和 LZ78。简单地说，这两种压缩方法的思路完全不同于从 Shannon 到 Huffman 到算术压缩的传统思路，倒是和本章开头所举的成语辞典的例子颇为相似，因此，人们将基于这一思路的编码方法称作“字典”式编码。字典式编码不但在压缩效果上大大超过了 Huffman，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。1982Storer与Szymanski对LZ77算法进行了改进，并提出相应的LZSS算法。1984Terry Welch 发表了名为“高性能数据压缩技术”(A Technique for High-Performance Data Compression)的论文，描述了他在 Sperry Research Center(现在是 Unisys 的一部分)的研究成果。他实现了 LZ78 算法的一个变种 LZW。LZW 继承了 LZ77 和 LZ78 压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受（有的研究者认为是由于 Welch 的论文比 Ziv 和 Lempel 的更容易理解），实现也比较简单。不久，UNIX 上出现了使用 LZW 算法的 Compress 程序，该程序性能优良，并有高水平的文档，很快成为了 UNIX 世界的压缩程序标准。紧随其后的是 MS-DOS 环境下的 ARC 程序( System Enhancement Associates, 1985 )，还有象 PKWare、PKARC 等仿制品。LZ78 和 LZW 一时间统治了 UNIX 和 DOS 两大平台。1985-人们对 LZ77 进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。Haruyasu Yoshizaki(Yoshi) 的 LHarc 和 Robert Jung 的 ARJ 是其中两个著名的例子。LZ77 得以和 LZ78、LZW 一起垄断当今的通用数据压缩领域。目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的 PKZip 到现在的 WinZip，特别是随着 Internet 上文件传输的流行，ZIP 格式成为了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持 ZIP 格式。3.1.2. 多媒体信息的压缩对声音、图像、视频等多媒体信息的压缩有两条思路，要么采用成熟的通用数据压缩技术进行压缩，要么根据媒体信息的特性设计新的压缩方法。事实上，人们在两条道路上都作了卓有成效的探索。网页中常使用的GIF 可以把原始图形文件以非常小数据量存储，可以在同一个文件中存储多幅图像从而实现动画效果。GIF 中的图像使用的压缩得法就是-LZW。GIF 大概是使用通用压缩技术压缩图像信息的最成功的例子，当然，GIF 文件中除了经过 LZW 压缩的像素信息以外，还保存有图像的各种属性信息以及图像所使用的调色板信息等。GIF 精确地保留了原始图像的每一个像素信息，是无损图像压缩的代表。根据媒体特性量身定制的压缩方法中，行程编码(RLE: Run-Length Encoding)是最为简单、最容易被想到的一种。大多数计算机中产生的图像(和现实世界的图像例如照片不同)都具有着大面积重复的颜色块，为什么非要用无数个完全相同的颜色值来表示某块图像呢？我们完全可以用一个颜色值加一个重复次数来表示这一块图像，冗余度由此减小了，这就是 RLE 方法的基本思路。显然，它不适于用来压缩照片、声音等很少连续重复信息的数据。RLE 方法最有代表性的实现有 PCX 和 Targa 图形格式。如果分别考察的话，只有黑白两种颜色的二值图像以及只有 256 级灰度变化的图像具有一些独特的地方，可以被压缩算法加以利用。我们知道，传真图像是一种典型的二值图像。国际电报电话咨询委员会( CCITT )为此建立了一系列的压缩标准，专门用于压缩传递二值图像（可以是无损的或有损的）。对于灰度图像，除了著名的 JPEG 标准以外，一种叫 FELICS 的算法可以实现效果非常好的无损压缩。70 年代末 80 年代初，人们逐渐意识到，对到多数灰度或是彩色图像乃至声音文件，没有必要忠实地保留其所有信息，在允许一定的精度损失的情况下，可以实现更为有效的压缩方法。到 80 年代末，许多人已经在这一领域取得了不小的收获，设计出了一批在压缩效果上让人惊讶不已的声音和图像压缩算法。在此基础上，国际标准化组织( ISO )和 CCITT 联合组成了两个委员会。委员会的名字我们大概都已经非常熟悉了：静态图像联合专家小组( JPEG )和动态图像联合专家小组( MPEG )。JPEG 的压缩目标是静止图像（灰度的和彩色的），MPEG 的目标则是声音和视频。但他们的基本思路是完全一样的，即保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去其他不重要的数据。他们都取得了令人赞叹的成就。3.2. 数据压缩的基本理论与分类3.2.1. 什么是熵数据压缩起源于40年代由 Claude Shannon 首创的信息论，其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”来表示一条信息中真正需要编码的信息量：考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的位数位为：En = - log2( Pn )整条信息的熵也即表示整条信息所需的位数为：E = En举个例子，对下面这条只出现了 a b c 三个字符的字符串：aabbaccbaa字符串长度为 10，字符 a b c 分别出现了 5 3 2 次，则 a b c 在信息中出现的概率分别为 0.5 0.3 0.2，他们的熵分别为：Ea = -log2(0.5) = 1Eb = -log2(0.3) = 1.737Ec = -log2(0.2) = 2.322整条信息的熵也即表达整个字符串需要的位数为：E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位如果用计算机中常用的 ASCII 编码，表示上面的字符串需要整整 80 位！信息之所以能被被压缩而不丢失原有的信息内容,简单地讲，就是用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。3.2.2. 模型要压缩一条信息，首先要分析清楚信息中每个符号出现的概率。不同的压缩程序通过不同的方法确定符号的出现概率，对符号的概率计算得越准确，也就越容易得到好的压缩效果。在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做模型。模型大致可分为两大类: “统计模型”和“字典模型”。而“统计模型”又可分“静态统计模型”和“自适应模型”。所谓“静态统计模型”，就是预先扫描文件中的所有字符，统计出每个字符出现的概率。在实际应用中很少使用“静态统计模型”，因为不同的文件中，字符有不同的分布概率，要么先花上大量的时间统计要压缩的所有文件中的字符概率，要么为每一个单独的文件保存一份概率表以备解压缩时需要。不但扫描文件要消耗大量时间，而且保存一份概率表也使压缩后的文件增大了不少。真正的压缩程序中使用的大多是“自适应模型”。自适应模型是一台具有学习功能的自动机。它在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，它统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。自适应模型在压缩开始时压缩效果并不理想，但随着压缩的进行，它会越来越接近字符概率的准确值，并达到理想的压缩效果。自适应模型还可以适应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表。之所以称为“统计模型”，因为他们都是基于对每个字符出现次数的统计得到字符概率的。另一大类模型叫做“字典模型”。字典模型并不直接计算字符出现的概率，而是使用一本字典，随着输入信息的读入，模型找出输入信息在字典中匹配的最长的字符串，然后输出该字符串在字典中的索引信息。匹配越长，压缩效果越好。事实上，字典模型本质上仍然是基于对字符概率的计算的，只不过，字典模型使用整个字符串的匹配代替了对某一字符重复次数的统计。可以证明，字典模型得到的压缩效果仍然无法突破熵的极限。当然，对通用的压缩程序来说，保存一本大字典所需的空间仍然是无法让人忍受的，况且，任何一本预先定义的字典都无法适应不同文件中数据的变化情况。对了，字典模型也有相应的“自适应”方案。我们可以随着信息的不断输入，从已经输入的信息中建立合适的字典，并不断更新这本字典，以适应数据的不断变化。3.2.3. 编码通过模型，就已经确定了对某一个符号该用多少位二进制数进行编码。接下来的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。最先被考虑的问题是，如果对 a 用 3 个二进制位就可以表示，而对 b 用 4 个二进制位就可以表示，那么，在解码时，面对一连串的二进制流，我怎么知道哪三个位是 a，哪四个位是 b 呢？所以，必须设计出一种编码方式，使得解码程序可以方便地分离每个字符的编码部分。于是有了一种叫“前缀编码”的技术。该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位 0 或 1 组成。不同的模型使用不同的方法计算字符的出现概率，由此概率可以得出字符的熵；然后使用不同的编码方法，尽量接近我们期望得到的熵值。所以，压缩效果的好坏一方面取决于模型能否准确地得到字符概率，另一方面也取决于编码方法能否准确地用期望的位数输出字符代码。换句话说，压缩 = 模型 + 编码。如下图所示：- 符号 - 概率 - 代码 -| 输入 |-| 模型 |-| 编码 |-| 输出 |- - - - 3.2.4. 压缩技术概貌压缩技术大致可以按照以下的方法分类： 压缩技术 | /- 通用无损数据压缩 多媒体数据压缩(大多为有损压缩) | | /- /-基于统计 基于字典 音频压缩 图像压缩 视频压缩模型的压 模型的压 | | |缩技术 缩技术 MP3等 /-、 AVI | | 二值 灰度 彩色 矢量 MPEG2等 /- /- 图像 图像 图像 图像Huffman 算术 LZ77 LZ78 LZSS LZW | | | |编码 编码 -/ 传真机 FELICS GIF PostScript | | | 标准 JPEG等 JPEG等 Windows WMF等UNIX下 接近无损 PKZIP、LHarc、ARJ、的COMPACT 压缩极限 UNIX下的COMPRESS程序等 的高级应用 程序等3.3. 字典编码原理目前广泛采用的字典压缩方法包括两种类型：一种是在数据压缩过程中，寻找当前等待进行压缩处理的数据串中是否在已经处理过的数据串中出现过，如果确实曾经出现过，则利用指向该已经进行处理数据串的指针代替当前等待进行压缩的数据串。此时，字典是隐式的，它用曾经处理过的数据描述。这类字典压缩算法都是基于Abraham与Jakob Ziv于1977年提出并发表的LZ77算法，该算法提出后，Storer与Szymanski于1982年对其进行了改进，并提出相应的LZSS算法，成为现在实践中广泛使用的该类算法的基础。如流行的压缩程序：WINZIP，PKZIP等就是基于这种算法的。另外一种字典压缩算法是为输入数据创建一个短语字典，如果在当前等待进行压缩的数据流中发现字典中已经存在相应的短语，则利用该短语在字典中的相应索引值取代原始数据，这种类型的算法基于Lampel与Ziv在1978年提出并发表的LZ78算法。后来该压缩算法由Sperry公司的研究员Welch于1984年在硬件设计过程中，改进并用于高性能磁盘控制器的设计，同时，由Lempel和Ziv在实际工作中实现，LZW编码也由此而得名。这种编码不仅可以用于文字数据的压缩，而且也可以成功地用于某些图像数据的压缩处理，如GIF和TIFF等图像格式。4. 字典编码方法的分类与特点4.1. LZ77算法滑动的窗口LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。LZ77 算法的基本流程如下图所示1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。解压缩的过程十分简单，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c 输出（如果 off 和 len 都为 0 则只输出后继字符 c ) 即可还原出原始数据。LZ77算法出现的比较早,与其它后继算法相比它可以说没有什么优点可言.4.2. LZ78算法LZ78的编码步骤如下：1.把编码位置置于输入数据流的开始位置。2.在前向缓冲存储器中查找与窗口中最长的匹配串 Pointer ：=匹配串指针。 Length ：=匹配串长度。3.判断匹配串长度是否大于等于最小匹配串长度(Length MIN_LENGTH)， 如果“是”：输出指针，然后把编码位置向前移动Length个字符。 如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前 移动一个字符。 4.如果前向缓冲存储器不是空的，就返回到步骤2。4.3. LZSS算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。编码算法的具体执行步骤如下： 1.把编码位置置于输入数据流的开始位置。2.在前向缓冲存储器中查找与窗口中最长的匹配串 Pointer ：=匹配串指针。 Length ：=匹配串长度。 3.判断匹配串长度是否大于等于最小匹配串长度(Length MIN_LENGTH)， 如果“是”：输出指针，然后把编码位置向前移动Length个字符。 如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。4.如果前向缓冲存储器不是空的，就返回到步骤2。在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。 LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。4.4. LZW算法编码算法 LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号，如下表所示。这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图象中出现的可变长度ASCII字符串。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。Welch的论文中用了12位，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)。 码字(Code word) 前缀(Prefix) 1 193 A 194 B 255 1305 AbcdefxyF01234 LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Charstream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Codestream)，码字代表单个字符或多个字符组成的字符串。 LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流Charstream的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀Prefix。用已知的前缀Prefix加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串缀-符串String：Prefix.C。这个新的缀-符串String是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串String就变成前缀Prefix，继续输入新的字符，否则就把这个缀-符串String写到词典中生成一个新的前缀Prefix，并给一个代码。 LZW编码算法的具体执行步骤如下： 步骤1： 开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；步骤2： 当前字符(C) ：=字符流中的下一个字符；步骤3： 判断缀-符串P+C是否在词典中 (1) 如果“是”：P ：= P+C / (用C扩展P) ； (2) 如果“否” 把代表当前前缀P的码字输出到码字流; 把缀-符串P+C添加到词典; 令P ：= C /(现在的P仅包含一个字符C); 步骤4： 判断码字流中是否还有码字要译 (1) 如果“是”，就返回到步骤2； (2) 如果“否” 把代表当前前缀P的码字输出到码字流; 结束。译码算法 LZW译码算法中还用到另外两个术语： 当前码字(Current code word)：指当前正在处理的码字，用cW表示，用string.cW表示当前缀-符串； 先前码字(Previous code word)：指先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串。 LZW译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根(roots)。LZW算法在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到词典中。 LZW译码算法的具体执行步骤如下：步骤1： 在开始译码时词典包含所有可能的前缀根(Root)；步骤2： cW ：=码字流中的第一个码字；步骤3： 输出当前缀-符串string.cW到码字流；步骤4： 先前码字pW：= 当前码字cW；步骤5： 当前码字cW ：= 码字流中的下一个码字； 步骤6： 判断先前缀-符串string.pW是否在词典中 (1) 如果“是”： 把先前缀-符串string.pW输出到字符流； 当前前缀P ：=先前缀-符串string.pW； 当前字符C ：=当前前缀-符串string.cW的第一个字符； 把缀-符串P+C添加到词典； (2) 如果“否”： 当前前缀P ：=先前缀-符串string.pW； 当前字符C ：=当前缀-符串string.cW的第一个字符； 输出缀-符串P+C到字符流，然后把它添加到词典中。 步骤7： 判断码字流中是否还有码字要译 (1) 如果“是”，就返回到步骤4； (2) 如果“否”, 结束。 LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图象格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。 5. 不足与改进5.1. 对技术的改进5.1.1. 零搜索本文实现了真正意义上的零搜索，这也是LZW算法区别于LZSS算法的一点。对于LZSS算法来说，查找过程作为其核心过程总不可避免的存在，而传统LZW算法在早期由于内存空间的限制，编码表不能过大，但这样导致以字头码和字尾码建立索引时，要依赖于一个有效的索引公式。但不同的字头码和字尾码可能产生相同的索引值，字典存放地址也就可能会被占用，于是还得查找一个自由的地址空间，这样使得算法在查找过程上开销不少。如何才能使根据字头码和字尾码建立的索引值不重复，显而易见的办法是以其本身的值合成为内存地址，依靠指针进行定位，从而不再需要查找过程。但在16位操作系统下，若数据处理位是8位的话，至少需要的空间为216，刚好是16位操作系统寻址能力的极限，操作系统无法分配这样大的堆空间。降低数据处理位也许是一种方法，但理论上其编码效率是低于8位的，而且在编码时还要进行复杂的位处理过程，于是这种方法也不可取。如今32位操作系统已成主流，其寻址能力可达4GB，再加上硬件设施大大提高，物理内存空间一般达到了128MB，技术上虚拟内存可达4GB，使得上述方法成为可能。在标准数据处理上采用这种方法，编码表实际使用内存空间仅为2MB。5.1.2. 动态编码长度这是借鉴了LZW For GIF的思想，使用动态编码长度进一步提高了算法效率。这种方法允许压缩代码长度的更改，即利用不固定长度的代码存储压缩数据。LZW算法一般从9位开始编码，这时存储代码也是9位，直到编码增加到10位时，存储代码才增加到10位。传统的LZW算法是直接存储最大编码位的，这样做导致非编码数据也要存储这样大的位数，浪费了完全没有用处的几个高位。考虑到字典编码是按位逐渐增大的，于是应用动态编码既能保证字典编码的完整，又能起到对非编码数据的优化作用。但应用动态编码在存储代码时需要增加一个位处理过程。5.2. 设计方法的改进使用面向对象设计方法对于用户来说是有利的。如用户在用该算法进行数据压缩时，只需创建一个编码对象，使用对象的三个方法：GetBegin，Execute，GetEnd即可轻松实现。在对算法功能进行改进或添加时，只需继承该类和重载方法。6. 算法实现本文使用的开发工具是Delphi7.0，封装过程定义了ExportData和Execute这两个虚方法，重设这两个方法可以修改或扩充算法执行过程和数据输出过程。其中编码和解码类都使用Execute方法作为核心过程，Execute方法的说明如下：procedure Execute(Data: array of Byte; DataSize: Integer); virtual;Data是一个指针，指向待处理数据的首地址；DataSize是待处理数据的大小；处理完毕后的数据保存在对象内部，使用GetExportPointer方法可得到该地址指针，然后调用GetExportSize方法返回输出数据的大小。6.1. 数据结构6.1.1. 常量定义：NOCODE = -1; / 空编码LZWBITS = 8; / 字对处理位LZWBUFFER = $FFFF; / 编码处理缓存容量（输入缓存容量）LZWMAXBITS = 12; / 最大的编码位（增加该值会增加编码表的内存空间）LZWSTACKBUFFERSIZE = $FFFF; / 栈缓存容量（要保证它足够大）LZWEXPORTBLOCKSIZE = $FFFF; / 输出缓存容量LZWMAXCODES = 1 shl LZWMAXBITS; / 最大编码（4096）LZWTABLESIZE = 1 shl (LZWBITS + LZWMAXBITS); / 编码表容量（2MB空间）6.1.2. 编码类：TLZWEncode = class(TObject) private EncodeTable: array 0.LZWTABLESIZE - 1 of Word; / 编码表 EncodePointer: array 0.LZWMAXCODES - 1 of LongWord; / 经过编码的缓存 ExportBlock: Pointer; / 存放编码后的数据指针（输出缓存块指针） ExportBlockPtr: array of Byte; / 该指针指向 ExportBlock ，用于访问数组 InitBits: Integer; / 压缩数据的起始位数 ClearCode: Integer; / 清除码 EofCode: Integer; / 结束码 PrefixCode: Integer; / 字头码 SuffixCode: Integer; / 字尾码 Encode: Integer; / 压缩编码 RunBits: Integer; / 当前处理位 MaxCodeSize: Integer; / 当前处理最大编码 FBegin: Boolean; / 开始处理标志 FExportSize: Integer; / 输出数据块大小 FExportIndex: Integer; / 输出数据块索引 FExportTotalSize: Integer; / 记录输出缓存块大小 ShiftBits: Integer; / 用于位处理，作临时位 ShiftCode: Integer; / 用于位处理，作临时代码 protected procedure ExportData(AData: Integer); virtual; / 输出数据（虚方法） public function GetExportPointer: Pointer; / 返回输出指针 function GetExportSize: Integer; / 返回输出大小 procedure GetBegin; / 置开始编码标志 procedure GetEnd; / 置结束编码标志 procedure Execute(Data: array of Byte; DataSize: Integer); virtual; / 执行编码过程（虚方法） constructor Create; destructor Destroy; override; end;6.1.3. 解码类：TLZWUnencode = class(TObject) private InitBits: Integer; / 压缩数据的起始位数 ClearCode: Integer; / 清除码 EofCode: Integer; / 结束码 PrefixCode: Integer; / 字头码 SuffixCode: Integer; / 字尾码 Encode: Integer; / 压缩编码 RunBits: Integer; / 当前处理位 MaxCodeSize: Integer; / 当前处理最大编码 ExportBlock: Pointer; / 存放编码后的数据指针（输出缓存块指针） ExportBlockPtr: array of Byte; / 该指针指向 ExportBlock ，用于访问数组 StackIndex: Integer; / 栈索引 StackTable: array 0.LZWSTACKBUFFERSIZE - 1 of Byte; / 栈表 PrefixTable: array 0.LZWMAXCODES - 1 of Word; / 字头表 SuffixTable: array 0.LZWMAXCODES - 1 of Byte; / 字尾表 FExportSize: Integer; / 输出数据块大小 FExportIndex: Integer; / 输出数据块索引 FExportTotalSize: Integer; / 记录输出缓存块大小 ShiftBits: Integer; / 用于位处理，作临时位 ShiftCode: Integer; / 用于位处理，作临时代码 protected procedure ExportData(AData: Integer); virtual; / 输出数据（虚方法） public function GetExportPointer: Pointer; / 返回输出指针 function GetExportSize: Integer; / 返回输出大小 procedure GetBegin; / 开始解码（分配输出内存空间） procedure GetEnd; / 结束解码（释放输出内存空间） procedure Execute(Data: array of Byte; DataSize: Integer); virtual; / 执行解码过程（虚方法） constructor Create; destructor Destroy; override; end;6.2. 编码算法变量初始化取出数据构造地址输出字头取编码值重置字典加入字典增加处理位编码结束字对未编码数据未处理完达到最大编码值未达到最大编码值达到最大处理编码值数据未处理完数据处理完毕数据处理完毕字对已经编码6.2.1. 流程描述6.2.2. 核心代码implementation TLZWEncode 对象初始化 =constructor TLZWEncode.Create;begin InitBits := LZWBITS; ClearCode := 1 shl InitBits; EofCode := ClearCode + 1; Encode := EofCode + 1; RunBits := InitBits + 1; MaxCodeSize := 1 shl RunBits; FBegin := False; FExportSize := 0; FExportIndex := 0; FExportTotalSize := 0; ShiftBits := 0; ShiftCode := 0;end; 销毁对象 =destructor TLZWEncode.Destroy;begin FreeMem(ExportBlock); inherited;end;=procedure TLZWEncode.Execute(Data: array of Byte; DataSize: Integer);var AIndex: Integer; ArrayIndex: Integer; Vi: Integer;begin AIndex := 0; FExportIndex := 0; FExportTotalSize := LZWEXPORTBLOCKSIZE; 处理文件首字节，赋值给字头码 if FBegin then begin FBegin := False; ExportData(ClearCode); PrefixCode := DataAIndex; Inc(AIndex); end; 编码过程 while AIndex = LZWBITS do begin ExportBlockPtrFExportIndex := ShiftCode and $00FF; Inc(FExportIndex); if FExportIndex = FExportTotalSize then begin 重新分配内存后首地址可能改变 ReallocMem(ExportBlock, FExportIndex + LZWEXPORTBLOCKSIZE); Pointer(ExportBlockPtr) := ExportBlock; Inc(FExportTotalSize, LZWEXPORTBLOCKSIZE); end; ShiftCode := ShiftCode shr LZWBITS; Dec(ShiftBits, LZWBITS); end;end;=begin 输出位总是大于 LZWBITS 的 ShiftCode := AData shl ShiftBits + ShiftCode; Inc(ShiftBits, RunBits); ExportProcedure;end;=function TLZWEncode.GetExportPointer: Pointer;begin Result := ExportBlock;end;=function TLZWEncode.GetExportSize: Integer;begin FExportSize := FExportIndex; Result := FExportSize;end;=procedure TLZWEncode.GetBegin;begin FBegin := True; 有可能输出缓存大于输入缓存，如果发生，到时再重新分配内存 ExportBlock := AllocMem(LZWEXPORTBLOCKSIZE); Pointer(ExportBlockPtr) := ExportBlock;end;=procedure TLZWEncode.GetEnd;begin ExportData(PrefixCode); EXportData(EofCode); 最后的处理是看看有没有没处理的位 while ShiftBits 0 do begin ExportBlockPtrFExportIndex := ShiftCode and $00FF; Inc(FExportIndex); if FExportIndex = FExportTotalSize then begin ReallocMem(ExportBlock, FExportIndex + LZWEXPORTBLOCKSIZE); Pointer(ExportBlockPtr) := ExportBlock; Inc(FExportTotalSize, LZWEXPORTBLOCKSIZE); end; ShiftCode := ShiftCode shr LZWBITS; Dec(ShiftBits, LZWBITS); end;end;end.6.3. 解码算法解码算法相对来说较为简单，因为这些都是编码过程的逆过程。值得注意的是，取出数据的位数也是动态调整的，即最开始是9位，然后是10位，接下去增加到11位，以此类推。另外解码过程得到的数据可能很大，因为一个字典可能会代表一大串数据，所以在输出过程也要建立一个可动态调整的内存区。6.3.1. 流程描述是清除码重置字典是结束码数据未处理完变