LZW压缩算法介绍LZW是啥意思?懒子王!一听这名就知道这算法不是一般的懒子,要不怎么也称王呢。
懒子王压缩算法是一种新颖的压缩方法,由Lemple-Ziv-Welch 三人共同创造,用他们的名字命名。它采用了一种先进的字典压缩,将每个第一次出现的串放在一个字典中,用一个数字来表示串,压缩文件只存储数字,不存贮串,从而使图象文件的压缩效率得到较大的提高。懒子的是,压缩完了之后这个字典就可以给扔了,解压时会重建起这个字典。 在懒子王算法中,有这么几个概念: 1.字符:不一定是指ASCII字符,就是一个8位二进制数,0--255,unsigned char或是uint8或是BYTE型能表示的。 2.串:一个字符的序列,没有C语言中用'\0'封尾的那种要求。 3.字典:里面存放串,每一个串对应的编码都与字典中的位置形成一一对应。 4.根:字典产生时就带有的东西,比如带有的字符叫根字符,可以分别是0--255,根字符和空前缀组成根串,根串的编码称为根编码。 一个串被表示成(前缀,后缀)格式,前缀可以是一个字符,也可以是一个串的编码,为统一形式,一个字符用对应的根编码表示,所以,前缀是一个编码。后缀就是一个字符,没有别的形式。 还有一点,在字典中有两个特殊的条目,一个是CLEAR,一个是END,比如字典的根编码是0--255,则CLEAR = 256,END = 257。 现在我们来以一个具体的例子说明这个算法是怎么个懒子法的,假设这个字典的根字符是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),还是不认识,用一个新编码来表示它,令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位来表示可以,因为咱这字典里有地方嘛,可是要是咱建个12位的字典,已经有4096个条目,存满了,再来新串咋整呀,别忘了咱最开始说懒子王的时候说它是怎么懒子的了?字典用完就扔了,解压时能重建,对吧,想想啊,一个字典已经建满了,解压的时候也可以把这个字典重建到满,对吧,如果现在这个输入流结束了,再来个输入流,会出现什么情况呢?压缩时新建个字典,解压时再重建这个字典,对吧,那解决方案就来了,旧字典字典不要了,当作上一个输入流结束下一个输入流开始,从只有根串的字典开始再建一个,怎么样,懒子吧,但这招它就是好使。 总结一下,懒子王压缩算法的基本流程大致如下: 1.从输入流中读入一个字符,作为当前串的后缀。 2.如果当前串在字典中,就用当前串的编码作前缀,转到第1步。 3.如果当前串不在字典中,就把当前串放到字典中,并把前缀放到输出流,后缀变前缀,转到第1步。 4.当输入流读完了后,串中应该还剩一个前缀,把它放到输出流,结束。 解压算法实际就是查字典的过程,也是对串进行处理,以上面的例子为例,输入流是AB68…… 第一步,读第一个编码,是A,在字典中,就作为后缀,现在串是(,A),串也在字典中,不作其它处理,把编码A作为前缀,并放入输出流(实际上是把前缀对应的最原始串放入输出流)。 第二步,读下一个编码,是B,也在字典中,作为后缀,现在串是(A,B),不在字典中,就把它加入到字典中,令6=(A,B),把当前编码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=(6,8),这怎么能行呢,别说后缀不能是编码了,就算能是编码,怎么能用自己来定义自己呢,那咋整呀,咱回头想想这个8是咋来的啊,它的前缀是6,所以8=(AB……),可见8的第一个字符就是6的第一个字符A,好了,令8=(6,A),然后把8作前缀,并放入输出流。 现在输出流中的字符是A B AB ABA ……,与原文件一致。 总结一个算法流程: 1.在输入流中读一个字符。 2.如果当前编码在字典中,则把当前编码的第一个字符作为当前串的后缀,如果当前串不在字典中,就把它加入到字典中,然后把当前编码作为串的前缀,转到第4步。 3.如果当前编码不在字典中,就把前缀的第一个字符作为后缀,把串加入到字典中,用当前串的编码作前缀,转到第4步。 4.把前缀放到输出流,转到第1步。 到现在为止,这个算法已经很懒子了,但是要称王,恐怕还没有绝对的把握。 压缩率已经通过变长编码来提高了,现在再做一件懒子事吧,来说说怎么提高算法的速度。 要说速度主要还是要从字典和字典条目的结构说起,如果字典条目的结构就是一个(前缀,后缀),且字典是顺序结构来存储这些条目的,那么在查字典时就在一个一个的比对,非常浪费时间,所以我们有必要想一些改进方法来让算法更懒子。 空间换时间的方法: 这个算法在那份《改进的字典压缩LZW算法》中提出过。建立一个数组,大小是字典大小*根字符数量*字典大小战胜的字节数。比如建的字典大小是4096,根字符是256个,那这个数组就可以定义为uint8 dict[4096][256],大小就是4096*256*2=2M。字典先初始化成全0,在清空字典后也要设成全0再重建。具体算法如下: 开始:
一种兼顾时间和空间的方法: 首先,定义一个结构体。 我的散列表方法: 建立一个大小为4096的散列表,先用散列函数求出256个根字符的散列值(在散列表中的位置),字典就初始化完成了,然后每来一个新串,就用散列函数计算出它的散列值,把它加到字典中的相应位置。 关于字符串的散列函数,有挺多经典的,不过我用的是最简单的,就是取模,具体是怎么取的一会再说。 再说说散列表的另一个重要的事,冲突处理:一般有三种方法:线性再散列,拉链,外散列,但我用的是暴雪的一种方法,同时使用三个不同的散列函数来确定串,这样重复的概率可以降低到1/2^23级。看星际和魔兽里有什么.mpq文件吧,那就是用这种方法做的数据包。我是把前缀和后缀拼起来,分别取它的低、中、高K位,K=编码长度。前缀12位,后缀8位,拼起来20位,三个散列函数最少能取27位,谁要说冲突,你可以跟他赌国足拿世界杯,虽然你不能赢,但也不会输。什么内散列法,外散列法的,其实在这种情况下都没有顺延法好用。 以我目前的水平来推测,现在算法已经懒子到可以称王的程度了,也许会有其它的牛人,会想到让这个算法更懒子的方案,欢迎分享讨论。懒子王的口号是:没有最懒子,只有更懒子! 参考文献:http://blog.csdn.net/whycadi/archive/2006/05/29/760576.aspx |
|