LZW压缩算法介绍

《LZW压缩算法介绍》由会员分享，可在线阅读，更多相关《LZW压缩算法介绍（4页珍藏版）》请在装配图网上搜索。

1、LZW压缩算法介绍（2009-09-1622:08:24）LZW是啥意思？懒子王！一听这名就知道这算法不是一般的懒子，要不怎么也称王呢。懒子王压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch三人共同创造，用他们的名字命名。它采用了一种先进的字典压缩，将每个第一次出现的串放在一个字典中，用一个数字来表示串，压缩文件只存储数字，不存贮串，从而使图象文件的压缩效率得到较大的提高。懒子的是，压缩完了之后这个字典就可以给扔了，解压时会重建起这个字典。在懒子王算法中，有这么几个概念：1.字符：不一定是指ASCII字符，就是一个8位二进制数，0-255，unsignedchar或是uint8

2、或是BYTE型能表示的。2串：一个字符的序列，没有C语言中用0封尾的那种要求。3. 字典：里面存放串，每一个串对应的编码都与字典中的位置形成一一对应。4根：字典产生时就带有的东西，比如带有的字符叫根字符，可以分别是0-255,根字符和空前缀组成根串，根串的编码称为根编码。一个串被表示成（前缀，后缀）格式，前缀可以是一个字符，也可以是一个串的编码，为统一形式，一个字符用对应的根编码表示，所以，前缀是一个编码。后缀就是一个字符，没有别的形式。还有一点，在字典中有两个特殊的条目，一个是CLEAR，一个是END，比如字典的根编码是0-255，则CLEAR=256，END=257。现在我们来以一个具体的

3、例子说明这个算法是怎么个懒子法的，假设这个字典的根字符是A，B，C，D，4个，加上CLEAR和END一共6个，占用000-101，现在编码长度是3位。输入流里面的字符序列是ABABABABBBABABAA第一步，取第一个字符，是A，A已经在我们的字典中了（根字符），也就是说，我们已经（认识）它了，就把它的编码作前缀，成（A,）。下一步，取第二个字符，现在的取到的串为（A，B）。以前没见过，不认识，好，现在把（A,B）编码为6,下次再碰到就认识了。把A放入到输出流中，让后缀B作前缀（实际是根字符B的编码，为了方便才写B）。第三步，读下一个字符，是A，现在串是（B，A），还是不认识，用一个新编码来

4、表示它，令7=（B,A）。把前缀B放入到输出流，后缀A变前缀。第四步，取下一个字符，是B,现在串是（A,B）,嘿，这次认识了，不就是老6嘛，好了，让6作前缀去。第五步，取下一个，是A,现在串是（6,A）,又不认识了，令8=（6,A）。等等，有情况！刚才新建的字典条目6，7已经把3位的编码给占满了，这可咋整呀？懒子王是一定有办法解决的，现在懒子王算法的第二点懒子之处就体现出来了，变长编码。刚才编码用3位表示，现在不行了，就用4位表示，现在能表示8了，其它照常，输出前缀6，后缀A变前缀。就这样，输入流中的数据变成了AB68放到输出流中，怎么样，变短了吧，嘿嘿。现在问题又来了，字典里3位不够了用4位

5、来表示可以，因为咱这字典里有地方嘛，可是要是咱建个12位的字典，已经有4096个条目，存满了，再来新串咋整呀，别忘了咱最开始说懒子王的时候说它是怎么懒子的了？字典用完就扔了，解压时能重建，对吧，想想啊，一个字典已经建满了，解压的时候也可以把这个字典重建到满，对吧，如果现在这个输入流结束了，再来个输入流，会出现什么情况呢？压缩时新建个字典，解压时再重建这个字典，对吧，那解决方案就来了，旧字典字典不要了，当作上一个输入流结束下一个输入流开始，从只有根串的字典开始再建一个，怎么样，懒子吧，但这招它就是好使。总结一下，懒子王压缩算法的基本流程大致如下：1. 从输入流中读入一个字符，作为当前串的后缀。2

6、. 如果当前串在字典中，就用当前串的编码作前缀，转到第1步。3. 如果当前串不在字典中，就把当前串放到字典中，并把前缀放到输出流，后缀变前缀，转到第1步。4. 当输入流读完了后，串中应该还剩一个前缀，把它放到输出流，结束。解压算法实际就是查字典的过程，也是对串进行处理，以上面的例子为例，输入流是AB68第一步，读第一个编码，是A,在字典中，就作为后缀，现在串是（，A）,串也在字典中，不作其它处理，把编码A作为前缀，并放入输出流（实际上是把前缀对应的最原始串放入输出流）。第二步，读下一个编码，是B,也在字典中，作为后缀，现在串是（A,B），不在字典中，就把它加入到字典中，令6=（A,B），把当前

7、编码B作前缀，并放入输出流。第三步，读下一个编码，是6,在字典中，作为后缀？看看开头的定义，后缀是一个字符，可不能是编码呀，把6展开，6=AB，我们把6的第一个字符，即A,作为后缀，现在串是（B,A）,不在字典中，令7=（B,A）,把当前编码6（不是它是第一个字符A）作为前缀，并把前缀6代表的最原始的串（字符的序列）放入输出流（为方便，说成把6放入输出流）。第四步，读下一个编码，是8?是呀，咋了，上面写着呢，现在输入流中的二进制数据是1000，读3位读到的应该是4呀，怎么会成8了呢，注意到字典建到7了，3位已经满了，接下来再建字典就应该是4位的了，所以现在读输入流时改成一次读4位，这就是8了，

8、8这个编码不在字典中，建一个吧，令8=（6,8）,这怎么能行呢，别说后缀不能是编码了，就算能是编码，怎么能用自己来定义自己呢，那咋整呀，咱回头想想这个8是咋来的啊，它的前缀是6,所以8=（AB）,可见8的第一个字符就是6的第一个字符A,好了，令8=（6,A）,然后把8作前缀，并放入输出流。现在输出流中的字符是ABABABA.,与原文件一致。总结一个算法流程：1. 在输入流中读一个字符。2. 如果当前编码在字典中，则把当前编码的第一个字符作为当前串的后缀，如果当前串不在字典中，就把它加入到字典中，然后把当前编码作为串的前缀，转到第4步。3. 如果当前编码不在字典中，就把前缀的第一个字符作为后缀，

9、把串加入到字典中，用当前串的编码作前缀，转到第4步。4. 把前缀放到输出流，转到第1步。到现在为止，这个算法已经很懒子了，但是要称王，恐怕还没有绝对的把握。压缩率已经通过变长编码来提高了，现在再做一件懒子事吧，来说说怎么提高算法的速度。要说速度主要还是要从字典和字典条目的结构说起，如果字典条目的结构就是一个（前缀，后缀），且字典是顺序结构来存储这些条目的，那么在查字典时就在一个一个的比对，非常浪费时间，所以我们有必要想一些改进方法来让算法更懒子。空间换时间的方法：这个算法在那份改进的字典压缩LZW算法中提出过。建立一个数组，大小是字典大小*根字符数量*字典大小战胜的字节数。比如建的字典大小是4

10、096，根字符是256个，那这个数组就可以定义为uint8dict4096256,大小就是4096*256*2=2M。字典先初始化成全0，在清空字典后也要设成全0再重建。具体算法如下：开始：后缀=读入的字符；编码二数组前缀后缀;f（编码=0）/串（前缀，后缀）还没有出现过，不在字典中数组前缀后缀=当前字典大小；当前字典大小；输出流+=前缀；前缀=后缀；else/串在字典中前缀=编码；goto开始；可以看出，这个算法每一步只需一次查找，速度当然是非常快了，只不过这个速度是靠内存的大量消耗的代价来取得的。虽然2M的内存在今天好像算不上什么，但是想一想这个算法可是在1978年提出，1984年实现的，

11、那个时候2M的内存简直就是天文数字，而那时的巨型机速度也比不上现在的PC机，所以那时是不可能用以上的两种算法来实现的，无论是第二种算法速度上的开销还是上面这种算法内存上的开销，都是那时不可能承受的，因此，他们一定是采用了别的算法，兼顾了速度和内存的开销。一种兼顾时间和空间的方法：首先，定义一个结构体。本编码的后缀；第一个子编码；下一个兄弟编码StructCode/结构编码Wordsuffix;/WordFirstSon;/WordNextBrother;/说明一下。第一个子编码就是第一个以这个编码为前缀的编码，下一个兄弟编码是指下一个与这个编码前缀相同的编码。建立一个编码结构数组，如果最大字长

12、12位的话，数组长度就是4096个。建立好了以后就把它全部清零。那么每一次读取一个新的字符后的操作为：1.读取这个编码的FirstSon。如果FirstSon为空，则表示还没有以这个编码为前缀的编码,就可以在当前的最后一个编码后建立一个新的编码，将FirstSon设置为这个新编码，将新编码的suffix设置为这个刚读取的字符，将当前的前缀放入输出流，后缀变成前缀。读入下一个字符2. 如果FirstSon不为空，就跳到这个编码上，比对这个编码的后缀和当前的后缀，如果相同，则表明找到了，把这个编码作为当前字符串的前缀，读下一个字符。3. 如果这个编码的后缀不等于当前后缀，那么就跳到他的NextBr

13、other标记，比对两个后缀,直到找到或者NextBrother为空。4. 如果NextBrother为空了，表示还没有表示这个串的编码，那么在当前的最后一个编码后建立一个新编码，将当前编码的NextBrother设置成新编码，将新编码的后缀设置成当前后缀，将当前前缀放到输出流，后缀变前缀。读入下一个字符。按照这种算法，每次需要查找的次数大大减少，最好的可能一次就找到，最坏的可能是255次，但是这种可能实在太小，我想应该在10次以内吧。而且这个算法的内存使用很少，一个标记只占6个字节，比第二种算法多2个。实际上如果是以8位来处理，标记最大长度12位来算的话，一个标记结构所需要的位数为8+12+

14、12=32位，正好4个字节，所以可以用一个byte存后缀，一个word的低12位存NextBrother,高四位存FirstSon的高4位,再用一个byte存FistSon的低字节。因为每次FirstSon只用一次，所以处理麻烦些无所谓。这样算来，字典所用的空间就是4K*4=16K。也许你觉得没必要在内存空间的使用上如此计较。当然，如果是在PC机上，这个几十K的空间，确实没必要这么计较。实际上这种单纯的LZW算法已经很少单独在PC机上使用了。不过在很多的嵌入系统中，需要存储很多的记录数据，这种记录的数据往往重复的内容很多，如果压缩后，体积会大大减小。而嵌入式系统的存储空间又是很有限的，它的内存

15、大小和CPU的速度又不能支持复杂的、比较吃内存的压缩算法，这时这种简单而又消耗小的算法就有用武之地了。大家以后如果遇到这种情况，可以考虑使用这种算法。我的散列表方法：建立一个大小为4096的散列表，先用散列函数求出256个根字符的散列值（在散列表中的位置），字典就初始化完成了，然后每来一个新串，就用散列函数计算出它的散列值，把它加到字典中的相应位置。关于字符串的散列函数，有挺多经典的，不过我用的是最简单的，就是取模，具体是怎么取的一会再说。再说说散列表的另一个重要的事，冲突处理：一般有三种方法：线性再散列，拉链，外散列，但我用的是暴雪的一种方法，同时使用三个不同的散列函数来确定串，这样重复的概率可以降低到1/2人23级。看星际和魔兽里有什么.mpq文件吧，那就是用这种方法做的数据包。我是把前缀和后缀拼起来，分别取它的低、中、高K位，K=编码长度。前缀12位，后缀8位，拼起来20位，三个散列函数最少能取27位，谁要说冲突，你可以跟他赌国足拿世界杯，虽然你不能赢，但也不会输。什么内散列法，外散列法的，其实在这种情况下都没有顺延法好用。以我目前的水平来推测，现在算法已经懒子到可以称王的程度了，也许会有其它的牛人，会想到让这个算法更懒子的方案，欢迎分享讨论。懒子王的口号是：没有最懒子，只有更懒子！