数据压缩与LZ系列算法及其改进.doc

数据压缩与LZ系列算法及其改进 LZ77字典压缩算法简介字典压缩的原理是构建一个字典，用索引来代替重复出现的字符或字符串。如果字符串相对长，那么对整个字符串构建字典，这个字典将会很大，并且随着字典的增大，匹配速度也会快速下降。原始的LZ77算法是利用了字符串中上下文的相关性特点，通过一个滑动窗口（一个查找缓冲区）来作为字典，对要压缩的字符串保留一个look-aheadbuffer。压缩后的字符串采用三元组来表示：，在滑动窗口中从后往前找，如果在窗口中有曾经出现过的相同字符，看最多可以匹配多少字节，完了继续往前查找，查找完了取窗口中最长的匹配串（如果有多个相同长度的串可以匹配，取最后一个），将这个匹配串距当前位置的位移，长度，及下一个字符构成的三元组写出。如果在滑动窗口找不到匹配串，那么位移=长度=0，加上不能压缩的字符一起输出。滑动窗口可以通过循环队列实现。解压缩是一个比较简单而且快速的过程，在需要解压缩时通过位移和长度拷贝之前出现过的字符串就可以完成。LZ77字典压缩的改进LZ77压缩算法的大部分时间都会花在字符串匹配上，针对这一点有多种改进： 构建查找树，该思路也有多种实现方法，如LZSS。 构建链表法实现的哈希表，通过对一个字符串的头三个字节做哈希，快速找到匹配字符串的位置之后再沿链表做顺序搜索，如LZRW。 Deflate算法，其在ZIP和GZIP，以及许多软件中使用到，是使用LZ77的变种和huffman编码结合的一种压缩算法。在ZLib的源码中可以找到详细的算法说明。类似的还有鼎鼎有名的7-ZIP所使用的LZMA算法，也是LZ77算法和算术编码结合的算法，对LZ77的三元组都根据概率再次进行编码，压缩比很高， 但是压缩速度相对较慢。LZ78/LZW系列算法LZ77算法针对过去的数据进行处理，而 LZ78 算法却是针对后来的数据进行处理。LZ78通过对输入缓存数据进行预先扫描与它维护的字典中的数据进行匹配来实现这个功能，在找到字典中不能匹配的数据之前它扫描进所有的数据，这时它将输出数据在字典中的位置、匹配的长度以及找不到匹配的数据，并且将结果数据添加到字典中。比较好的字典数据结构表示是字符查找树(trie，有多种译法),即上一楼提到的解析树(ParseTree)，在这个数据结构中，前缀相同的字符串共享祖先节点，依此衍生。因为要压缩的字符串可能会很长，在LZ78中新出现的symbol并且在字典中没有匹配时，会加入到字典中，字典会不断膨胀，需要限制字典的大小。这里对trie有几种处理方法： 停止继续构造字典，形成一个静态的字典，用现有的字典对数据进行压缩（这个处理方法的缺点就是前面的字符串构造出来的字典对后来的数据不一定有效) 重新开始构造字典。这样会使数据分离为一个一个的块，每个块都有独立的字典。（这个方法保留了LZ77的优点，即新数据比旧数据更有相关性，类似Oracle的块压缩） 从trie中替换节点。但是需要考虑有效的替换算法。 LZW算法是LZ78的变种，假如字符串S在字典中有匹配，但是Sx在字典中无匹配，那么Sx会被加入到字典中。因为字典一开始就被初始化为256个字符，所以无需用到LZ77中的三元组表示法，每一个phrase或char都可以用字典中的一个索引表示（总是能在字典中找到），缺点跟LZ78一样，字典会快速增大。LZW中的字典使用了trie结构。LZMW是LZW的一个改进版本（DB2参考的压缩算法），改进如下： 如果trie满了，应该找到最近最少使用的节点进行替换。一种方法是：找出所有没有子节点的节点（即没有被当做前缀引用的节点），删除其中最老的。 加入字典的phrase由两个子串组成：前匹配项与当前项。LZW中的trie的新增节点表示的是后续不能匹配的symbol，但是LZMW中trie新增节点表示的是后续不能匹配的串。这可以使得字典的单元在逻辑上更自然，生成字典的速度也更快。缺点是： 并不是所有在字典中存在的串其前缀都可以在字典中找到（注：LZW的trie结构是可以的），那么假如一个只部分匹配字典项的串要加入字典中会是个问题，Data compression, the completereference这本书中提到的可能的替代方法是一个串加入trie中时，其所有的前缀也加入到trie中，并且每个节点必须有标志位注明其是否在字典中（因为节点有可能只是上一步提到的前缀节点，而不是实际的字典项）。 查找最长匹配项可能需要回溯。 压缩算法概述作者： 来源：zz 发表时间：2007-12-03 浏览次数： 43045 字号：大中小中国源码网内相关主题链接 LZ77压缩算法 LZW压缩算法 LZW算法之父荣获IEEE奖 几种压缩算法原理介绍 一、 行程长度压缩 原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee，则可用3a1b6c2d3e来代替。对于拥有大面积，相同颜色区域的图像，用RLE压缩方法非常有效。由RLE原理派生出许多具体行程压缩方法: 1.PCX行程压缩方法: 该算法实际上是位映射格式到压缩格式的转换算法，该算法对于连续出现1次的字节Ch，若Ch0xc0则压缩时在该字节前加上0xc1，否则直接输出Ch，对于连续出现N 次的字节Ch，则压缩成0xc0N，Ch这两个字节，因而N最大只能为ffc0=3fh(十进制为63)，当N大于63时， 则需分多次压缩。 2.BI_RLE8压缩方法:在WINDOWS的位图文件中采用了这种压缩方法。该压缩方法编码也是以两个字节为基本单位。其中第一个字节规定了用第二个字节指定的颜色重复次数。 如编码 0504表示从当前位置开始连续显示5个颜色值为04的像素。当第二个字节为零时第二个字节有特殊含义:0表示行末;1表示图末;2转义后面2个字节， 这两个字节分别表示下一像素相对于当前位置的水平位移和垂直位移。这种压缩方法所能压缩的图像像素位数最大为8位(256色)图像。3.BI_RLE压缩方法: 该方法也用于WINDOWS位图文件中，它与 BI_RLE8编码类似，唯一不同是:BI_RLE4的一个字节包含了两个像素的颜色，因此，它只能压缩的颜色数不超过16的图像。因而这种压缩应用范围有限。 4.紧缩位压缩方法(Packbits):该方法是用于Apple公司的Macintosh机上的位图数据压缩 方法， TIFF 规范中使用了这种方法， 这种压缩方法与BI_RLE8压缩方法相似，如1c1c1c2132325648 压缩为:83 1c 21 81 32 56 48，显而易见， 这种压缩方法最好情况是每连续128个字节相同，这128个字节可压缩为一个数值7f。这种方法还是非常有效的。 二、霍夫曼编码压缩: 也是一种常用的压缩方法。是1952年为文本文件建立的，其基本原理是频繁使用的数据用较短的代码代替，很少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。如: 有一个原始数据序列，ABACCDAA则编码为A(0)，B(10)，C(110),(D111)，压缩后为010011011011100。产生霍夫曼编码需要对原始数据扫描两遍，第一遍扫描要精确地统计出原始数据中的每个值出现的频率，第二遍是建立霍夫曼树并进行编码，由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。三、LZW压缩方法 LZW压缩技术比其它大多数压缩技术都复杂， 压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码，在还原程序中再将这个数值还成原来的字符 串，如用数值0x100代替字符串abccddeee这样每当出现该字符串时，都用0x100代替，起到了压缩的作用。 至于0x100与字符串的对应关系则是在压缩过程中动态生成的，而且这种对应关系是隐含在压缩数据中，随着解压缩的进行这张编码表会从压缩数据中逐步得到恢复，后面的压缩数据再根据前面数据产生的对应关系产生更多的对应关系。直到压缩文件结束为止。LZW是可逆的， 所有信息全部保留。属于无损压缩编码，该编码主要用于图像数据的压缩。对于简单图像和平滑且噪声小的信号源具有较高的压缩比，并且有较高的压缩和解压缩速度。 LZW压缩技术把数据流中复杂的数据用简单的代码来表示，并把代码和数据的对应关系建立一个转换表，又叫“字符串表”。 转换表是在压缩或解压缩过程中动态生成的表，该表只在进行压缩或解压缩过程中需要，一旦压缩和解压缩结束，该表将不再起任何作用。四、算术压缩方法 算术压缩与霍夫曼编码压缩方法类似，只不过它比霍夫曼编码更加有效。算术压缩适合于由相同的重复序列组成的文件，算术压缩接近压缩的理论极限。这种方法，是将不同的序列映像到0到1之间的区域内，该区域表示成可变精度(位数 )的二进制小数，越不常见的数据要的精度越高(更多的位数)，这种方法比较复杂，因而不太常用。五、Rice对于由大word（例如：16或32位）组成的数据和教低的数据值，Rice编码能够获得较好的压缩比。音频和高动态变化的图像都是这种类型的数据，它们被某种预言预处理过（例如delta相邻的采样）。尽管哈夫曼编码处理这种数据是最优的，却由于几个原因而不适合处理这种数据（例如：32位大小要求16GB的柱状图缓冲区来进行哈夫曼树编码）。因此一个比较动态的方式更适合由大word组成的数据。Rice编码背后的基本思想是尽可能的用较少的位来存储多个字（正像使用哈夫曼编码一样）。实际上，有人可能想到Rice是静态的哈夫曼编码（例如，编码不是由实际数据内容的统计信息决定，而是由小的值比高的值常见的假定决定）。编码非常简单：将值X用X个1位之后跟一个0位来表示。六、Lempel-Ziv (LZ77)Lempel-Ziv压缩模式有许多不同的变量。基本压缩库有清晰的LZ77算法的实现（Lempel-Ziv，1977），执行的很好，源代码也非常容易理解。LZ编码器能用来通用目标的压缩，特别对于文本执行的很好。它也在RLE和哈夫曼编码器（RLE，LZ，哈夫曼）中使用来大多数情况下获得更多的压缩。在LZ压缩算法的背后是使用RLE算法用先前出现的相同字节序列的引用来替代。简单的讲，LZ算法被认为是字符串匹配的算法。例如：在一段文本中某字符串经常出现，并且可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。例如，在上一段短语“字符串”经常出现，可以将除第一个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。一个字符串引用通过下面的方式来表示：1 唯一的标记2 偏移数量3 字符串长度由编码的模式决定引用是一个固定的或变动的长度。后面的情况经常是首选，因为它允许编码器用引用的大小来交换字符串的大小（例如，如果字符串相当长，增加引用的长度可能是值得的）。七、DEFLATE ( LZ77 與哈夫曼編碼的組合) ZIP、gzip、zlib 與 PNG 檔案在使用 DEFLATE 是同時使用了 LZ77 演算法與哈夫曼編碼的一個無損數據壓縮演算法。它最初是由 Phil Katz 為他的 PKZIP 歸檔工具第二版所定義的，後來在 1951 年定義在 RFC 規範中。人們普遍認為 DEFLATE 不受任何專利所制約，並且在 LZW（GIF 文件格式使用）相關的專利失效之前，這種格式除了在ZIP文件格式中得到應用之外也在 gzip 壓縮文件以及 PNG 圖像文件中得到了應用。DEFLATE 壓縮與解壓的原始碼可以在自由、通用的壓縮庫 zlib 上找到。更高壓縮率的 DEFLATE 是 7-zip 所實現的。AdvanceCOMP 也使用這種實現，它可以對 gzip、PNG、MNG 以及 ZIP 文件進行壓縮從而得到比 zlib 更小的文件大小。在 Ken Silverman 的 KZIP 與 PNGOUT 中使用了一種更加高效同時要求更多用戶輸入的 DEFLATE 程序。LZ77压缩算法作者： 来源：zz 发表时间：2009-04-16 浏览次数： 18220 字号：大中小内容摘要 我们敬佩那两个在数据压缩领域做出了杰出贡献的以色列人，因为正是他们打破了 Huffman 编码一统天下的格局，带给了我们既高效又简便的“字典模型”。至今，几乎我们日常使用的所有通用压缩工具，象 ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR甚至许多硬件如网络设备中内置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。中国源码网内相关主题链接 整数的质因数分解算法 BMH算法原理与实现（模式匹配） 排列组合与回溯算法 A*高效搜索算法 Rainbow Table破解算法 数据交换的特殊算法-经典面试题 BM算法原理与实现 KMP算法原理与实现 我们在第三和第四章中讨论的压缩模型都是基于对信息中单个字符出现频率的统计而设计的，直到 70 年代末期，这种思路在数据压缩领域一直占据着统治地位。在我们今天看来，这种情形在某种程度上显得有些可笑，但事情就是这样，一旦某项技术在某一领域形成了惯例，人们就很难创造出在思路上与其大相径庭的哪怕是更简单更实用的技术来。我们敬佩那两个在数据压缩领域做出了杰出贡献的以色列人，因为正是他们打破了 Huffman 编码一统天下的格局，带给了我们既高效又简便的“字典模型”。至今，几乎我们日常使用的所有通用压缩工具，象 ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR甚至许多硬件如网络设备中内置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。说起来，字典模型的思路相当简单，我们日常生活中就经常在使用这种压缩思想。我们常常跟人说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明白它们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实际就是信息的压缩。我们之所以可以顺利使用这种压缩方式而不产生语义上的误解，是因为在说者和听者的心中都有一个事先定义好的缩略语字典，我们在对信息进行压缩（说）和解压缩（听）的过程中都对字典进行了查询操作。字典压缩模型正是基于这一思路设计实现的。最简单的情况是，我们拥有一本预先定义好的字典。例如，我们要对一篇中文文章进行压缩，我们手中已经有一本现代汉语词典。那么，我们扫描要压缩的文章，并对其中的句子进行分词操作，对每一个独立的词语，我们在现代汉语词典查找它的出现位置，如果找到，我们就输出页码和该词在该页中的序号，如果没有找到，我们就输出一个新词。这就是静态字典模型的基本算法了。你一定可以发现，静态字典模型并不是好的选择。首先，静态模型的适应性不强，我们必须为每类不同的信息建立不同的字典；其次，对静态模型，我们必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。所以，几乎所有通用的字典模型都使用了自适应的方式，也就是说，将已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。根据这一思路，你能从下面这幅图中读出其中包含的原始信息吗？啊，对了，是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。现在你该大致明白自适应字典模型的梗概了吧。好了，下面就让我们来深入学习字典模型的第一类实现LZ77 算法。滑动的窗口LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。参照下图，让我们熟悉一下 LZ77 算法的基本流程。1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。我们结合实例来说明。假设窗口的大小为 10 个字符，我们刚编码过的 10 个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee我们首先发现，可以和要编码字符匹配的最长串为 ab ( off = 0, len = 2 ), ab 的下一个字符为 a，我们输出三元组：( 0, 2, a )现在窗口向后滑动 3 个字符，窗口中的内容为：dbbccaaaba下一个字符 e 在窗口中没有匹配，我们输出三元组：( 0, 0, e )窗口向后滑动 1 个字符，其中内容变为：bbccaaabae我们马上发现，要编码的 aaabae 在窗口中存在( off = 4, len = 6 )，其后的字符为 e，我们可以输出：( 4, 6, e )这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。解压缩的过程十分简单，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c 输出（如果 off 和 len 都为 0 则只输出后继字符 c )即可还原出原始数据。当然，真正实现 LZ77 算法时还有许多复杂的问题需要解决，下面我们就来对可能碰到的问题逐一加以探讨。LZW压缩算法作者： 来源：zz 发表时间：2007-11-08 浏览次数： 10212 字号：大中小中国源码网内相关主题链接 LZ77压缩算法 压缩算法概述 LZW压缩算法 LZW算法之父荣获IEEE奖 几种压缩算法原理介绍 LZW 压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch 三人共同创造，用他们的名字命名。它采用了一种先进的串表压缩不，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃。1.基本原理首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如print 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将print字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出 266所代表的字符串print，在解压缩时，串表可以根据压缩数据重新生成。2.实现方法A.初始化串表 在压缩图象信息时，首先要建立一个字符串表，用以记录每个第一次出现的字符串。一个字符串表最少由两个字符数组构成，一个称为当前数组，一个称为前缀数组，因为在GIF文件中每个基本字符串的长度通常为2（但它表示的实际字符串长度可达几百甚至上千），一个基本字符串由当前字符和它前面的字符（也称前缀）构成。前缀数组中存入字符串中的首字符，当前数组存放字符串中的尾字符，其存入位置相同，因此只要确定一个下标，就可确定它所存贮的基本字符串，所以在数据压缩时，用下标代替基本字符串。一般串表大小为4096个字节（即2 的12次方），这意味着一个串表中最多能存贮4096个基本字符串，在初始化时根据图象中色彩数目多少，将串表中起始位置的字节均赋以数字，通常当前数组中的内容为该元素的序号（即下标），如第一个元素为0，第二个元素为1，第15个元素为14 ，直到下标为色彩数目加2的元素为止。如果色彩数为256，则要初始化到第258个字节，该字节中的数值为257。其中数字256表示清除码，数字257 为图象结束码。后面的字节存放文件中每一个第一次出现的串。同样也要音乐会前缀数组初始化，其中各元素的值为任意数，但一般均将其各位置1，即将开始位置的各元素初始化为0XFF，初始化的元素数目与当前数组相同，其后的元素则要存入每一个第一次出现的字符串了。如果加大串表的长度可进一步提高压缩效率，但会降低解码速度。B.压缩方法了解压缩方法时，先要了解几个名词，一是字符流，二是代码流，三是当前码，四是当前前缀。字符流是源图象文件中未经压缩的图象数据；代码流是压缩后写入GIF 文件的压缩图象数据；当前码是从字符流中刚刚读入的字符；当前前缀是刚读入字符前面的字符。GIF 文件在压缩时，不论图象色彩位数是多少，均要将颜色值按字节的单位放入代码流中，每个字节均表示一种颜色。虽然在源图象文件中用一个字节表示16色、4 色、2色时会出现4位或更多位的浪费（因为用一个字节中的4位就可以表示16色），但用LZW 压缩法时可回收字节中的空闲位。在压缩时，先从字符流中读取第一个字符作为当前前缀，再取第二个字符作为当前码，当前前缀与当前码构成第一个基本字符串（如当前前缀为A，当前码为B则此字符串即为AB），查串表，此时肯定不会找到同样字符串，则将此字符串写入串表，当前前缀写入前缀数组，当前码写入当前数组，并将当前前缀送入代码流，当前码放入当前前缀，接着读取下一个字符，该字符即为当前码了，此时又形成了一个新的基本字符串（若当前码为C，则此基本字符串为BC），查串表，若有此串，则丢弃当前前缀中的值，用该串在串表中的位置代码（即下标）作为当前前缀，再读取下一个字符作为当前码，形成新的基本字符串，直到整幅图象压缩完成。由此可看出，在压缩时，前缀数组中的值就是代码流中的字符，大于色彩数目的代码肯定表示一个字符串，而小于或等于色彩数目的代码即为色彩本身。C.清除码事实上压缩一幅图象时，常常要对串表进行多次初始化，往往一幅图象中出现的第一次出现的基本字符串个数会超过4096个，在压缩过程中只要字符串的长度超过了4096，就要将当前前缀和当前码输入代码流，并向代码流中加入一个清除码，初始化串表，继续按上述方法进行压缩。D.结束码当所有压缩完成后，就向代码流中输出一个图象结束码，其值为色彩数加1，在256色文件中，结束码为257。E.字节空间回收 在GIF文件输出的代码流中的数据，除了以数据包的形式存放之外，所有的代码均按单位存贮，样就有效的节省了存贮空间。这如同4位彩色（16色）的图象，按字节存放时，只能利用其中的4位，另外的4位就浪费了，可按位存贮时，每个字节就可以存放两个颜色代码了。事实上在GIF 文件中，使用了一种可变数的存贮方法，由压缩过程可看出，串表前缀数组中各元素的值颁是有规律的，以256色的GIF文件中，第258-511元素中值的范围是0-510 ，正好可用9位的二进制数表示，第512-1023元素中值的范围是0-1022，正好可用10位的二进制数表示，第1024-2047 元素中值的范围是0-2046，正好用11位的二进制数表示，第2048-4095元素中值的范围是0-4094，正好用12位的二进制数表示。用可变位数存贮代码时，基础位数为图象色彩位数加1，随着代码数的增加，位数也在加大，直到位数超过为12（此时字符串表中的字符串个数正好为2 的12次方，即4096个）。其基本方法是：每向代码流加入一个字符，就要判别此字符所在串在串表中的位置（即下标）是否超过2的当前位数次方，一旦超过，位数加1。如在4位图象中，对于刚开始的代码按5位存贮，第一个字节的低5位放第一个代码，高三位为第二个代码的低3位，第二个字节的低2位放第二个代码的高两位，依次类推。对于8 位（256色）的图象，其基础位数就为9，一个代码最小要放在两个字节。F.压缩范围以下为256色GIF文件编码实例，如果留心您会发现这是一种奇妙的编码方法，同时为什么在压缩完成后不再需要串表，而且还在解码时根据代码流信息能重新创建串表。字 符 串: 1,2,1,1,1,1,2,3,4,1,2,3,4,5,9,当 前 码: 2,1,1,1,1,2,3,4,1,2,3,4,5,9,当前前缀: 1,2,1,1,260,1,258,3,4,1,258,262,4,5,当前数组: 2,1,1, 1, 3,4,1, 4,5,9,数组下标: 258,259,260,261,262,263,264,265,266,267,代 码 流: 1,2,1,260,258,3,4,262,4,5,GIF文件作为一种重要的图形图象文件格式，尽管其编码规则极复杂，但其压缩效率是极高的，特别是对某些平滑过渡的图象的图形，压缩效果更好。同时由于其在压缩过程中的对图象信息能够完整的保存，在目前流行的电子图片及电子图书中得到了广泛的应用。几种压缩算法原理介绍作者：windcsn 来源：cppblog 发表时间：2006-07-25 浏览次数： 78471 字号：大中小中国源码网内相关主题链接 AJAX和XMLHTTP原理 BMH算法原理与实现（模式匹配） epoll的实现原理 散列表(哈希表)工作原理 BM算法原理与实现 KMP算法原理与实现 点阵字模生成原理与方法 gcc profiling的工作原理 RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。1.1. 原理图2.1显示了一个如何使用RLE算法来对一个数据流编码的例子，其中出现六次的符号93已经用3个字节来代替：一个标记字节（0在本例中）重复的次数（6）和符号本身（93）。RLE解码器遇到符号0的时候，它表明后面的两个字节决定了需要输出哪个符号以及输出多少次。1.2. 实现RLE可以使用很多不同的方法。基本压缩库中详细实现的方式是非常有效的一个。一个特殊的标记字节用来指示重复节的开始，而不是对于重复非重复节都coding run。因此非重复节可以有任意长度而不被控制字节打断，除非指定的标记字节出现在非重复节（顶多以两个字节来编码）的稀有情况下。为了最优化效率，标记字节应该是输入流中最少出现的符号（或许就不存在）。重复runs能够在32768字节的时候运转。少于129字节的要求3个字节编码（标记+次数+符号），而大雨128字节要求四个字节（标记+次数的高4位|0x80+次数的低4位）。这是通常所有采用的压缩的做法，并且也是相比较三个字节固定编码（允许使用3个字节来编码256个字节）而言非常少见的有损压缩率的方法。在这种模式下，最坏的压缩结果是：输出大小=257/256*输入大小+12. 哈夫曼哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。2.1. 原理我不打算探究哈夫曼编码的所有实际的细节，但基本的原理是为每个符号找到新的二进制表示，从而通常符号使用很少的位，不常见的符号使用较多的位。简短的说，这个问题的解决方案是为了查找每个符号的通用程度，我们建立一个未压缩数据的柱状图；通过递归拆分这个柱状图为两部分来创建一个二叉树，每个递归的一半应该和另一半具有同样的权（权是NK =1符号数k, N是分之中符号的数量，符号数k是符号k出现的次数）这棵树有两个目的：1 编码器使用这棵树来找到每个符号最优的表示方法2 解码器使用这棵树唯一的标识在压缩流中每个编码的开始和结束，其通过在读压缩数据位的时候自顶向底的遍历树，选择基于数据流中的每个独立位的分支，一旦一个到达叶子节点，解码器知道一个完整的编码已经读出来了。我们来看一个例子会让我们更清楚。图2.2显示了一个10个字节的未压缩的数据。根据符号频率，哈夫曼编码器生成哈夫曼树（图2.4）和相应的编码表示（图2.3）。 你可以看到，常见的符号接近根，因此只要少数位来表示。于是最终的压缩数据流如图2.5所示。压缩后的数据流是24位（三个字节），原来是80位（10个字节）。当然，我应该存储哈夫曼树，这样解码器就能够解码出对应的压缩流了，这就使得该例子中的真正数据流比输入的流数据量大。这是相对较短的数据上的副作用。对于大数据量来说，上面的哈夫曼树就不占太多比例了。解码的时候，从上到下遍历树，为压缩的流选择从左/右分支，每次碰到一个叶子节点的时候，就可以将对应的字节写到解压输出流中，然后再从根开始遍历。2.2. 实现哈夫曼编码器可以在基本压缩库中找到，其是非常直接的实现。这个实现的基本缺陷是：1 慢位流实现2 相当慢的解码（比编码慢）3 最大的树深度是32（编码器在任何超过32位大小的时候退出）。如果我不是搞错的话，这是不可能的，除非输出的数据大于232字节。另一方面，这个实现有几个优点：1 哈夫曼树以一个紧密的形式每个符号要求12位（对于8位的符号）的方式存储，这意味着最大的头为384。2 编码相当容易理解哈夫曼编码在数据有噪音的情况（不是有规律的，例如RLE）下非常好，这中情况下大多数基于字典方式的编码器都有问题。3. Rice对于由大word（例如：16或32位）组成的数据和教低的数据值，Rice编码能够获得较好的压缩比。音频和高动态变化的图像都是这种类型的数据，它们被某种预言预处理过（例如delta相邻的采样）。尽管哈夫曼编码处理这种数据是最优的，却由于几个原因而不适合处理这种数据（例如：32位大小要求16GB的柱状图缓冲区来进行哈夫曼树编码）。因此一个比较动态的方式更适合由大word组成的数据。3.1. 原理Rice编码背后的基本思想是尽可能的用较少的位来存储多个字（正像使用哈夫曼编码一样）。实际上，有人可能想到Rice是静态的哈夫曼编码（例如，编码不是由实际数据内容的统计信息决定，而是由小的值比高的值常见的假定决定）。编码非常简单：将值X用X个1位之后跟一个0位来表示。3.2. 实现在基本压缩库针对Rice做了许多优化：1 每个字最没有意义的位被存储为k和最有意义的N-k位用Rice编码。K作为先前流中少许采样的位平均数。这是通常最好使用Rice编码的方法，隐藏噪音且对于动态变化的范围并不导致非常长的Rice编码。2 如果rice编码比固定的开端长，T，一个可选的编码：输出T个1位，紧跟（log2(X-T)）个1和一个0位，接着是X-T（最没有意义的(log2(X-T)-1位）。这对于大值来说都是比较高效的代码并且阻止可笑的长Rice编码（最坏的情况，对于一个32位word单个Rice编码可能变成232位或512MB）。如果开端是4，下面是结果编码表：X bin Rice Thresholded Rice 0 00000 0 0 1 00001 10 10 2 00010 110 110 3 00011 1110 1110 4 00100 11110 11110 5 00101 111110 111110 6 00110 1111110 11111100 +1 7 00111 11111110 11111101 8 01000 111111110 1111111000 +1 9 01001 1111111110 1111111001 10 01010 11111111110 1111111010 -1 11 01011 111111111110 1111111011 -2 12 01100 1111111111110 111111110000 13 01101 11111111111110 111111110001 -1 14 01110 111111111111110 111111110010 -2 15 01111 1111111111111110 111111110011 -3 16 10000 11111111111111110 111111110100 -4 17 10001 111111111111111110 111111110101 -5 18 10010 1111111111111111110 111111110110 -6 19 10011 11111111111111111110 111111110111 -7 20 10100 111111111111111111110 11111111100000 -5 就像你看到的一样，在这个实现中使用threshold方法仅仅两个编码导致一个最坏的情况；剩下的编码产生比标准Rice编码还要短的编码。3 最坏的情况，输出。4. Lempel-Ziv (LZ77)Lempel-Ziv压缩模式有许多不同的变量。基本压缩库有清晰的LZ77算法的实现（Lempel-Ziv，1977），执行的很好，源代码也非常容易理解。LZ编码器能用来通用目标的压缩，特别对于文本执行的很好。它也在RLE和哈夫曼编码器（RLE，LZ，哈夫曼）中使用来大多数情况下获得更多的压缩。4.1. 原理在LZ压缩算法的背后是使用RLE算法用先前出现的相同字节序列的引用来替代。简单的讲，LZ算法被认为是字符串匹配的算法。例如：在一段文本中某字符串经常出现，并且可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。例如，在上一段短语“字符串”经常出现，可以将除第一个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。一个字符串引用通过下面的方式来表示：1 唯一的标记2 偏移数量3 字符串长度由编码的模式决定引用是一个固定的或变动的长度。后面的情况经常是首选，因为它允许编码器用引用的大小来交换字符串的大小（例如，如果字符串相当长，增加引用的长度可能是值得的）。4.2. 实现使用LZ77的一个问题是由于算法需要字符串匹配，对于每个输入流的单个字节，每个流中此字节前面的哪个字节都必须被作为字符串的开始从而尽可能的进行字符串匹配，这意味着算法非常慢。另一个问题是为了最优化压缩而调整字符串引用的表示形式并不容易。例如，必须决定是否所有的引用和非压缩字节应该在压缩流中的字节边界发生。基本压缩库使用一个清晰的实现来保证所有的符号和引用是字节对齐的，因此牺牲了压缩比率，并且字符串匹配程序并不是最优化的（没有缓存、历史缓冲区或提高速度的小技巧），这意味着程序非常慢。另一方面，解压缩程序非常简单。一个提高LZ77速度的试验已经进行了，这个试验中使用数组索引来加速字符串匹配的过程。然而，它还是比通常的压缩程序慢。压缩算法概述作者： 来源：zz 发表时间：2007-12-03 浏览次数： 43046 字号：大中小中国源码网内相关主题链接 LZ77压缩算法 LZW压缩算法 LZW算法之父荣获IEEE奖 几种压缩算法原理介绍 一、 行程长度压缩 原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee，则可用3a1b6c2d3e来代替。对于拥有大面积，相同颜色区域的图像，用RLE压缩方法非常有效。由RLE原理派生出许多具体行程压缩方法: 1.PCX行程压缩方法: 该算法实际上是位映射格式到压缩格式的转换算法，该算法对于连续出现1次的字节Ch，若Ch0xc0则压缩时在该字节前加上0xc1，否则直接输出Ch，对于连续出现N 次的字节Ch，则压缩成0xc0N，Ch这两个字节，因而N最大只能为ffc0=3fh(十进制为63)，当N大于63时， 则需分多次压缩。 2.BI_RLE8压缩方法:在WINDOWS的位图文件中采用了这种压缩方法。该压缩方法编码也是以两个字节为基本单位。其中第一个字节规定了用第二个字节指定的颜色重复次数。 如编码 0504表示从当前位置开始连续显示5个颜色值为04的像素。当第二个字节为零时第二个字节有特殊含义:0表示行末;1表示图末;2转义后面2个字节， 这两个字节分别表示下一像素相对于当前位置的水平位移和垂直位移。这种压缩方法所能压缩的图像像素位数最大为8位(256色)图像。3.BI_RLE压缩方法: 该方法也用于WINDOWS位图文件中，它与 BI_RLE8编码类似，唯一不同是:BI_RLE4的一个字节包含了两个像素的颜色，因此，它只能压缩的颜色数不超过16的图像。因而这种压缩应用范围有限。 4.紧缩位压缩方法(Packbits):该方法是用于Apple公司的Macintosh机上的位图数据压缩 方法， TIFF 规范中使用了这种方法， 这种压缩方法与BI_RLE8压缩方法相似，如1c1c1c2132325648 压缩为:83 1c 21 81 32 56 48，显而易见， 这种压缩方法最好情况是每连续128个字节相同，这128个字节可压缩为一个数值7f。这种方法还是非常有效的。 二、霍夫曼编码压缩: 也是一种常用的压缩方法。是1952年为文本文件建立的，其基本原理是频繁使用的数据用较短的代码代替，很少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。如: 有一个原始数据序列，ABACCDAA则编码为A(0)，B(10)，C(110),(D111)，压缩后为010011011011100。产生霍夫曼编码需要对原始数据扫描两遍，第一遍扫描要精确地统计出原始数据中的每个值出现的频率，第二遍是建立霍夫曼树并进行编码，由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。三、LZW压缩方法 LZW压缩技术比其它大多数压缩技术都复杂， 压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码，在还原程序中再将这个数值还成原来的字符 串，如用数值0x1