LZWforGIF算法原理和实现转载

1、.LZW for GIF 算法原理和实现 转载本文转载自：for GIF算法原理和实现Why 2004-4-6废话少说。先说LZW for GIF的原理。LZW是一个字典式压缩算法，他在压缩原始数据时，对每一个新出现的原始数据串赋一个数值作为标号，那么下次又出现了这个串后，就可以用这个值来代替了。比方原始数据：ABCCAABCDDAACCDB，ABCD可以用03的数来表示。那么注意这个字符串中出现了好几个重复的字串：ABCCAABCDDAACCDB那么就可以用4来代表AB，5来代表CC等等，原来的字符串就变为压缩后的数据：45A4CDDAA5DB,变短了一点点。实际上上面这个字符串号可以进一步

2、的压缩，等会再谈。为了区别代表串的值和原来的单个的数据值，需要使它们的数值域不重合，比方说原来的数我们是以8位为单位来处理的就算实际上不是8位的，我们也可以看作是8位的，反正是一个0101的数据流，那么就认为原始的数的范围是0255，压缩程序生成的标号的范围就不能为0255，可以从256开场，但是这样一来就超过了8位的表示范围了，所以LZW算法必需要扩展数据的位数，至少要扩一位，这样看起来不是反而是增加了数据流的体积了吗?不过假设能用一个数据代表一个原始数据串，那么还是划得来的。从这个原理也可以看出LZW算法的适用范围，那就是原始数据串最好是有大量的子串屡次重复出现，重复的越多，压缩效果越好。

3、反之那么越差，可能真的不减反增了。LZW算法在处理数据时，随着新的串的不断发现，标号的值也就不断增加，增加到一定的程度，出与查找效率和标号集也就是字典所需存储空间的考虑，就不能再让它增加了，那么怎么办呢?干脆就从头开场，在这里做一个标记去除标志CLEAR，表示从这里我重新开场构造字典字典了，以前的所有标记作废，开场使用新的标记。这个标号集的大小多少比较适宜呢?据说理论上是越大压缩率越高我个人感觉太大了也不见得就好，不过处理的开销也呈指数增长，一般都是根据处理速度和内存空间选定一个大小，GIF标准规定的是12位，超过12位的表达范围就推倒重来，并且GIF为了进步压缩率，采用的是变长的字长。比方说

4、原始数据是8位，那么一开场，先加上一位再说，开场的字长就成了9位，然后开场加标号，当标号加到512时，也就是超过9为所能表达的最大数据时，也就意味着后面的标号要用10位字长才能表示了，那么从这里开场，后面的字长就是10位了。依此类推，到了212也就是4096时，在这里插一个去除标志，从后面开场，从9位再来。GIF规定的去除标志CLEAR的数值是原始数据字长表示的最大值加1，假设原始数据字长是8去除标志就是256，假设原始数据字长为4那么就是16。另外GIF还规定了一个完毕标志END，它的值是去除标志CLEAR再加1。由于GIF规定的位数有1位单色图，4位16色和8位256色，而1位的情况下假设

5、只扩展1位，只能表示4种状态，那么加上一个去除标志和完毕标志就用完了，所以1位的情况下就必须扩大到3位。其它两种情况初始的字长就为5位和9位。好了，如今开场谈谈LZW的详细算法。前面已经说了，LZW是基于字典的压缩方法，那么这个字典是怎么来的呢?难道先编一本"大百科字典"，随压缩包免费奉送?这显然是不可能的。LZW算法的优点就是可以动态生成字典，并且这个字典的信息已经包含在压缩后的数据流中了，不必再另外储存字典信息了。下面以一个压缩过程为例来说明一下。这个例子是Bob Montgomery给出的，非常的经典，我这里充当一个翻译的工作，并略微加一点我的解释。比方有一个字符串，

6、是由A、B、C、D四个字符构成的，那么就可以用0 12 3来表示，两位就够了。A BA BA BA BB BA BA BA AC DA CD AD CA BA AA BA B.首先要扩大一位，变成3位，定义Clear=4，End=5。那么以后的标号就从6开场。第一步，取第一个字符，是A，A已经在我们的定义中了，也就是说，我们已经认识他了，就不做处理了。下一步，取第二个字符，如今的取到的字符串为A，B，注意，这里引入一个前缀prefix和后缀suffix的概念，一个字符串可以用一个前缀加一个后缀来表示即前缀，后缀前缀是一个标号，可以是原始的字符，也可以是一个代表字符串的标号，后缀那么是一个字符。

7、那么这里取到了A，A，以前没见过，不认识，好，如今用6代表A，B，下次就认识了。因为有不认识的了，所以把前缀A放入到输出流中，只保存后缀B，让它变成前缀。第三步，取下一个字符，是A，如今的字符串是B，A，还是不认得，用一个新标号来表示他，7=B，A。把前缀B放入到输出流，A变成前缀。第四步，取下一个字符，是B，那么取道的是A，B，哈，这次认得了，不就是老6么。好，把字符串规约到6，以6来作为前缀。第五步，取下一个，是A，即为6，A，又不认得了，就令8=6，A，把前缀6放到输出流。如今的前缀变成A了。注意，到这里标号已经超过3位可以表示的最大范围了，所以接下来必需要扩展数据位，那么接下来的数据就

8、是以4位字长来表示了。接下来的流程不一一讲述了，如以下图A BA BA BA BB BA BA BA AC DA CD AD CA BA AA BA B.输入流./-/-/-/-/-/-/-/-/-/6 78 910 11 12 13 14 15 16 17 18 19 20 21 22 23标号6 810 914 16 813 7前缀Color Code Prefix Suffix String Output位数A 0-B 1-C 2-D 3-Clear 4-End 5-AA AFirst color is aspecial case.B/ AB ABA 3A|/7 BA BAB 3B|A/

9、|8 6A ABA6 3B|A|B/9 8B ABAB8 4B/|10 BB BB B4 B|A|/11 10 ABBA10B|A|B|A/ 9A ABABA9 A/13 AA AAA C/ AC ACA D/15 CD CDC A/|16 DA DA D4 C|D|/17 14 DACD14 5A|D/ 16 DDAD16 C/19 DC DCD A/|20 CA CAC B|A|A|/21 8A ABAA8 A|B/|22 13 BAAB13 A|B/23 7B BAB7输出数据流为：A B6 8B 10 9A AC D14 16 DC 8.LZW的解压LZW的解压过程就是一个查字典的过程

10、。那么这个字典是从哪里来的呢?这就是LZW的最大优点之一，那的字典信息是完全包含在压缩后的数据中的，解压程序可以动态的从压缩过的数据中构造出来，因此解压过程也非常类似于压缩过程。以上面的例子压缩结果为例，它的输出就是我们的输入，为：待解压的数据流为：A B6 8B 10 9A AC D14 16 DC 8.解压的过程是以一对一对数据来处理的。首先我们要知道原始数据的位数，这一点是要在处理压缩数据以前就知道的。在GIF文件中，可以从。我们来一步步分析这个过程：第一步，取第一个和第二个数据，是A，B，不认得，令6=A，B，把前缀A放入输出流中，后缀B变成前缀；第二步，取第三个数据，如今变为B，6。

11、不认得，那么令7=B，6吗?NO！请先回过头去看压缩过程，我们定义一个新的标志，前缀可以是一个代表子串的标号，但是后缀都是一个单个的数据的，所以这里我们也不能让后缀是一个字串标号。那么后缀是什么呢?让我们把6展开，6是A B，那么这里原来的字串就是B AB，如今知道了把，其实7=B，A，那么7的后缀就是6代表的字符串的第一个字符。如今我们把B放入输出流。第三步，取第四个数据。第四个数据是?怎么，不就是8吗。那是，明摆着写着呢。假设我不这样写，写成0001100001011001你还认得是8吗?由于GIF是变位长的，所以我们一定要清楚在这里到地取几位。先回过头来看上一步，由于上一步我们已经把标号

12、排到7了，7是3位的最大数值，所以从这一步以后，就应该把字长加一位，所以这里我们要取4位，就是1000，也就是8了。好了，如今得到的是6，8。不认得，那么令8=6，8?。8我们还不知道呢，怎么能用它来定义自己呢?回忆一下上一步我们定义7的时候，取的后缀是6的第一个字符，那么这里我8的后缀也应该是8的第一个字符，我们知道8的前缀是6，那么8的第一个字符也就是6的第一个字符。也就是A。所以8=6，A，如今把6代表的字符串AB放入输出流，让前缀变为8；第四步，取第五个数，如今是8，B，让9=8，B，把8=6A=AB A放入输出流，前缀为B。第五步，取第六个，B，10，同第三步，令10=B，10的第一

13、个字符=B，B，把B放入输出流如今的输出流是1 23 45A BAB AB AB和原来的数据比较一下：A BA BA BA BB BA BA BA AC DA CD完全一样。就这样，完成理解压缩的过程。算法的实现根据前面的介绍的原理，就可以设计程序的了。其实看起来，好似是很简单的，压缩就是一个一个的读，已经认识的就用代表它的标记来代替，不认识的就定义一个新标记来代表它，同时把前缀放到输出流中；解压过程就是一对一对的读，每次都可以定义一个新标记，同时把前缀展开，放入输出流。有什么难的?确实，看起来很简单，实际上编起来也不难，然而，却有一个很重要的问题需要好好的考虑，那就是，怎么样才能知道当前的字

14、符串是已经遇见过的?假设是遇见过的，它的标号是多少呢?显而易见，必须把已经遇见过并且标了好的字符串以某种方式储存起来，每次读入一个新的字符，就要去查找储存起来的数据。由于每次读一个字符都要查找储存的数据，所以花在查找上的时间就成为了压缩过程最主要的开销，因此以什么方式储存这些数据并用什么方式来查找就决定了这个算法的效率。以下就说说几种储存方式的区别。1.最直观的方法最直观的方法，当然是把每个标号所代表的字符串都存起来。建立一个字符串数组，比方上面的例子，6=AB，7=BA，8=ABA，9=ABAB等等等等，那么就建立一个字符串数组，令S6="AB"；S7="BA&

15、quot;；S8="ABA"；S9="ABAB"；看到这里可能大家心里都在摇头，这样存实在是太蠢了。一来所耗的空间太大，二来根本没提供任何信息帮助查询，要检查一个字符串是否匹配，就要一个一个的比对，想一想假设以12位最大字长来算，就有4000左右的标号，每一个字符串又可长可短，假设按最大可能来分配算了，我都不想算了。假设进展一次查找，以最坏的可能的话，可能会进展上万次比对。所以这种存法，虽然直观，但完全没有使用价值。2.最节省内存的算法请注意，其实每个字符串都是由一个前缀和一个后缀组成的，从我的这篇文章中大家可以很轻易的注意到这一点，因为我在前面的说明中

16、反复的强调了这一点，但是我在学习过程中所看的资料对这个都没有做明确的说明，一笔带过了，所以我总结出这个原理的重点和优化算法的关键实在是花了不少的功夫。注意到了这一点，我们就可以对一个标号只存一个前缀和一个后缀，以最大字长12位为例，我们可以建立这样一个构造数组，构造为：typedef struct标号word前缀；word后缀；构造数组为：标号标号组4096；其实用不着4096个，因为前面的2n+2n是原始数据字长个是不用记的，那些值是原始数据和去除标记还有完毕标记。只不过这样可以使标记的数值正好可以等于它的下标，不用在换算了，假设一定要省掉前面那些也无所谓，只不过需要转换一下数值和下标而已。

17、做个简单的加减法，不过每次都要做，开销还是有点大好，我们开场，如上例，我们先把这块内存清空，并定义一些变量：memset标号组，0，sizeof标号组；/一共是16Kint当前最大标号=6；word前缀，后缀；byte输入流x；byte输出流最大长度；int输入序号=0，输出序号=0；然后，我们读入第一个字符A和第二个字符B。前缀=输入流输入序号；输入序号+；从这里开场，我们开场压缩过程，直到把数据处理玩：int I=6；for输入序号；输入序号X；输入序号+后缀=输入流输入序号；/查找当前串在表中的位置bool found=false；whileI当前最大标号if前缀！=标号组I。前缀I+；

18、continue；if后缀！=标号组I。后缀I+；continue；/找到了，就是这个串found=true；前缀=I；/把当前串规约到标号I+；break；if！found/没找到，把这个串加到标号组中标号组当前最大标号。前缀=前缀；标号组当前最大标号。后缀=后缀；当前最大标号+；输出流输出序号=前缀；输出序号+；前缀=后缀；if当前最大标号4095/已经超过了最大的长度当前最大标号=6；输出流输出序号=去除标志；输出序号+；I=6；输出流输出序号=前缀；后面的处理输出串的就省略了。这个算法的原理就是，查找标号组，找到了，就把串归约到标号，把标号作为前缀，再读入下一个字符，因为假设这时有匹配

19、的串，那么它的标号也肯定比方今的前缀大，所以可以从前缀+1的地方开场搜索。假设搜索到当前最大的标号还没有匹配的话，那么就说明没有匹配的标号。就要增加一个新的标号，放到标号组的最后，并把前缀放到输出流中，后缀变成前缀。可以看出这个算法是非常的节省内存的，它只需要为每个标号分配4个字节，但是它的效率却也不高，因为他每输出一个标号到输出流，实际上都要把整个表号组挨个搜索一遍，那么越到后面，开销就越大。所以这个方法也不好。那么怎么样才能把搜索速度加快呢?下面的这个方法速度绝对快，但是它的内存开销也非常大，是典型的以空间换时间方法。3.以空间换时间的算法这个算法就是在那份?改进的字典压缩LZW编码向君?

20、包含在我发上的GIF文档中中提出的算法。他的程序是用Pasic写的，我是看都没看看不懂，不过从他的说明中，我明白了他的做法。我们来看看LZW的主要时间开销，就是读入一个新的字符后，怎么样才能把当前的字符串规约到一个标号无论是的还是未知的，这个过程需要查找表号组，那么为了减少时间开销，最直接的方法就是减少查找的次数。我们读入一个新的字符后，得到的字符串为前缀，新字符，其中前缀是上一次已经归约好了的，是的，新字符也是的，怎样才能根据这两个数值来一次找到它所属的标号呢?假设有一个二维数组数组xy，我们知道了一个元素的x，y以后，可以很快的算出他在数组中的位置，那么，在这里，我们也可以建立一个数组，他

21、的大小=标号最大数量*字符集数量*标号字节数。以字符为8位，表号长度为12位来计算，这个数组的大小就是4096*256*2=2M。建立了这个数组后，首先是要把它的内容全部清0。并且每次到达最大字长，从头再来后都要全部清0，而不像上一种算法，只需要改变当前最大标号值，对表号组中的数可以不去除。这个算法详细的做法是：开场：后缀=输入流输入当前位置+；标号=标号数组前缀后缀；if标号=0/这种前缀，后缀还没有出现过表号组前缀后缀=当前最大标号；当前最大标号+；输出流输出当前位置+=前缀；前缀=后缀；else/这个组合已出现过了，前缀=标号；goto开场；可以看出，这个算法每一步只需一次查找，速度当然

22、是非常快了，只不过这个速度是靠内存的大量消耗的代价来获得的。虽然2M的内存在今天好似算不上什么，但是想一想这个LZ78算法可是在1978年提出，1984年实现的，那个时候2M的内存简直就是天文数字，而那时的巨型机速度也比不上如今的PC机，所以那时是不可能用以上的两种算法来实现的，无论是第二种算法速度上的开销还是上面这种算法内存上的开销，都是那时不可能承受的，因此，他们一定是采用了别的算法，兼顾了速度和内存的开销。4.一个我没看懂的方法就是在我提供的那个GIF的VCL控件中作者使用的算法了。只不过我这人最不喜欢看代码了，而且文件里一行注释都没有，格式也很乱可能高手都这样吧，所以我怎么也看不明白。

23、因为我没看懂，所以也就不多说了，不过我在看程序的时候，看到他用了这样一个名称：Hash_Table，想必是使用了哈希表。大家可以去回忆一下哈希表的内容，作者可能是构造了一个哈希表来解决这个空间与时间的矛盾。5.我的方法在看过前面说的第三种方法后，由于那个源代码我实在看不懂，所以我决定还是自己想。经过一天的考虑，想出了一个算法。这个算法每读一个字符所需查找的次数可以降到很少，而所需的内存空间也只比第二种方法大一点点。首先，定义一个构造体。Struct Mark/构造标记Word suffix；/本标记的后缀；Word FirstSon；/第一个子标记；Word NextBrother；/下一个兄

24、弟标记；/说明一下。第一个子标记就是第一个以这个标记为前缀的标记，下一个兄弟标记是指下一个与这个标记前缀一样的标记。建立一个标记构造数组，假设最大字长12位的话，数组长度就是4096个。建立好了以后就把它全部清零。那么每一次读取一个新的字符后的操作为：1.读取这个标记的FirstSon。假设FirstSon为空，那么表示还没有以这个标记为前缀的标记，就可以在当前的最后一个标记后建立一个新的标记，将FirstSon设置为这个新标记，将新标记的suffix设置为这个刚读取的字符，将当前的前缀放入输出流，后缀变成前缀。读入下一个字符2.假设FirstSon不为空，就跳到这个标记上，比对这个标记的后缀和当前的后缀，假设一样，那么说明找到了，把当前字符串的前缀规约到这个标记，读下一个字符。3.假设这个标记的后缀不等于当前后缀，那么就跳到他的NextBrother标记，比对两个后缀，直到找到或者NextBrother为空。4.假设NextBrother为空了，表示还没有表示这个组合的标记，那么在当前的最后一个标记后建立一个新标记，将当前标记的NextBrother设置成新标记，将新标记的后缀设置成当前后缀，将当前前缀放到输出流，后缀等于前缀。读入下一个字符按照这种算法，每次需要查找的次数大大减少，最好的可能一次就找到，最坏的可