LZ算法

数据压缩与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结构是可以的），那么假如一个只部分匹配字典项的串要加入字典中会是个问题，《Datacompression,thecompletereference》这本书中提到的可能的替代方法是一个串加入trie中时，其所有的前缀也加入到trie中，并且每个节点必须有标志位注明其是否在字典中（因为节点有可能只是上一步提到的前缀节点，而不是实际的字典项）。查找最长匹配项可能需要回溯。压缩算法概述作者：来源：zz发表时间：2007-12-03浏览次数：43045字号：大中小中国源码网内相关主题链接LZ77压缩算法LZW压缩算法LZW算法之父荣获IEEE奖几种压缩算法原理介绍一、行程长度压缩原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee，则可用3a1b6c2d3e来代替。对于拥有大面积，相同颜色区域的图像，用RLE压缩方法非常有效。由RLE原理派生出许多具体行程压缩方法:1.PCX行程压缩方法:该算法实际上是位映射格式到压缩格式的转换算法，该算法对于连续出现1次的字节Ch，若Ch0xc0则压缩时在该字节前加上0xc1，否则直接输出Ch，对于连续出现N次的字节Ch，则压缩成0xc0＋N，Ch这两个字节，因而N最大只能为ff－c0=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压缩为:831c2181325648，显而易见，这种压缩方法最好情况是每连续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演算法與哈夫曼編碼的一個無損數據壓縮演算法。它最初是由PhilKatz為他的PKZIP歸檔工具第二版所定義的，後來在1951年定義在RFC規範中。人們普遍認為DEFLATE不受任何專利所制約，並且在LZW（GIF文件格式使用）相關的專利失效之前，這種格式除了在ZIP文件格式中得到應用之外也在gzip壓縮文件以及PNG圖像文件中得到了應用。DEFLATE壓縮與解壓的原始碼可以在自由、通用的壓縮庫zlib上找到。更高壓縮率的DEFLATE是7-zip所實現的。AdvanceCOMP也使用這種實現，它可以對gzip、PNG、MNG以及ZIP文件進行壓縮從而得到比zlib更小的文件大小。在KenSilverman的KZIP與PNGOUT中使用了一種