Lzw 针对大量的子串多次重复出现的压缩 

    之前用了一个哈弗曼算法给大家实现了文件的压缩处理，其实上，文件压缩的原理很简单，无非就是把重复出现的元素，用一个特定的方式转化为跟少量的信息来存储。今天我所给大家分享的就是一个更为引用广泛的压缩算法lzw压缩算法。

一、lzw的介绍

     LZW压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch 三人共同创造，用他们的名字命名。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃。

 

简单的说明一下：

Ababcabab这个字符串，开起来9个字符组成的，但是会发现一点就是ab这个字符组合比较的多。如果我们用一个数字，也就是7来表示ab的话，则字符串就变为了77c77，这样一来字符串的字符个数就变为了5个，如果大家仔细些会发现，如果我们用一个数字8来表示abab，则原来的字符串就变为了8c8只有3个字符了，是不是很神奇哈。

从这个例子我们就可以看出LZW算法的适用范围是原始数据串最好是有大量的子串多次重复出现，重复的越多，压缩效果越好。反之则越差，可能真的不减反增了。

比如：

一个如此重复的文件：

大小为：

 

 

压缩后效果就非常的显著：

 

 

文件大小变为原来的1/30

 

 具体思想：

比如我们大家所熟知的ASCII码，这个码表是与我们常见的字符是一一对应的，比如我们说‘a’,我们也可以写成97，这两者就是等价的。其实上这就是一个码表。所以人们就想到，我们可不可以用以一个码表示一个或者多个的字符，比如8表示ab这两字符，我们就能将abcab这种的字符串缩小为8c8了。 但是我们知道字节只有0~255，如果我们要扩展的话就必须增加自己的定义。既，我假设我用增加了256~65534这么一段表示新的码表。

 

具体步骤：

①打开一个待压缩文件与存放压缩后的文件

②读入一个字节作为后缀，判断这个词字典中是否存在，存在则直接输出，不存在则加入字典中。

③如果超过了最大的长度则，将当前码表写出到文件中，清空，再次读入

④最后，将没有写完的信息，和码表都输出，压缩就完成了

 

举一个例子说明：

先说两个概念

前缀prefix：一个词组的前面一个字符 ，比如 ab,前缀为a，8f前缀为8

后最suffix：反之，为后一个字符，比如 ab,后缀为b，8f后缀为f

有了前缀后缀，我们就能清楚的表示出来一个词了。

 

同样，我们还来做一个字符串 ababbacb  8个字符 

 

第几步	前缀	后缀	词	存在对应码	输出	码
1		a	(,a)
2	a	b	(a,b)	no	a	256
3	b	a	(b,a)	no	b	257
4	a	b	(a,b)	yes
5	256	b	(256,b)	no	256	258
6	b	a	(b,a)	yes
7	257	c	(257,c)	no	257	259
8	c	b	(c,b)	no	c	260

 

把输出来的和最后一个后缀连在一起则是：

  a,b,256,257,c,b        

6个字符，那么就达到了压缩的目的。

对应生成的码表则是：

 

256	257	258	259	260
（a,b）	(b,a)	(256,b)	(257,c)	(c,b)

 

解压缩就很简单了，将输出字符串按照码表对应转化回来就实现了。

即

  a,b,256（ab）,257(ba),c,b

即 ababbacb

压缩成功。

 

 

当然我们不能一直无穷之境的增加码表的长度，再说内存也容不下这么长的码表。正如我之前所说的，我用了0~65534保存字节所对应的编码，0~255是系统字节的长度，256~65534是我自己定义的。如果超过了65534的话，我们这必须再次编码。即将原来所对应的编码输出，将256~65534这一段清空，再次编码就可以了。

为了记录我们是在哪里清空的，所有又在文件中写一个字符，表示 “清除”，我的程序中用的是65535表示。

  

详细代码设计

 

 

 

压缩过程

①打开一个待压缩文件与存放压缩后的文件

	//打开被压缩文件
			java.io.FileInputStream fis = new java.io.FileInputStream(path);
			//压缩文件输出流
			java.io.FileOutputStream fos = new java.io.FileOutputStream(path+".stzip");
			java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);

  

②读入一个字节作为后缀，判断这个词字典中是否存在，存在则直接输出，不存在则加入字典中。

prefix=fis.read();//读入一个字节
while(fis.available()>0){
suffix=fis.read();//读入一个后缀
			    index=lz.getIndex(prefix, suffix);//得到对应的下标
				if(index!=-1){//存在元素在表里面
					prefix=index;//前序变为标号
				}else{//在表里不存在
				//	System.out.println("输出了~"+prefix);
					dos.writeChar(prefix);//输出前缀
					lz.add(prefix,suffix);//加入到表中
					prefix=suffix;//前缀变为后缀

				}
}

 

 

③如果超过了最大的长度则，将当前码表写出到文件中，清空，再次读入

 

 

	if(lz.length==lzw.Max_Length){//超过最大长度则，重置
					dos.writeChar(65535);//写出一个65535作为重置的标示 与码表的打印
					//写出码表
			//		dos.writeInt(lz.length);//码表长度
					System.out.println("写出长度~"+lz.length);
					for(int i=256;i<lz.length;i++){
						dos.writeChar(lz.node[i].prefix);//前缀写出
						dos.writeChar(lz.node[i].suffix);//后缀写出
					}
					
					lz = new lzw();//清空原来信息
				}

 

④最后，将没有写完的信息，和码表都输出，压缩就完成了

dos.writeChar(prefix);//输出最后一个没有配对的
			
			//输出最后的的码表
		//	System.out.println("写出标记~"+65535);
			dos.writeChar(65535);//写出一个-1作为重置的标示 与码表的打印
			//写出码表
			dos.writeInt(lz.length-256);//码表长度
			//System.out.println("写出长度~"+(lz.length-256));
			for(int i=256;i<lz.length;i++){
				//System.out.println("写出前后缀~"+lz.node[i].prefix+","+lz.node[i].suffix);
				dos.writeChar(lz.node[i].prefix);//前缀写出
				dos.writeChar(lz.node[i].suffix);//后缀写出
			}

 

解压缩过程:

①读入码表之前的压缩信息

char data;
				int current=0;
				char []codeData = new char[65536];
				lzw lz = new lzw();//自定义码表
				
				data=dis.readChar();
				//System.out.println("读取字符~"+data);
				while(data!=65535){//把码表钱的东西读取出来
				//	System.out.println("开打文件中有的内容"+current+"是"+data);
					codeData[current]=data;
					current++;//当前位置增加
					data=dis.readChar();
				}

 

②读入对应长度的码表

int length = dis.readInt();//得到码表的长度
				//System.out.println("独到的长度"+length);
				for(int i=0;i<length;i++){//读入码表
					int prefix = dis.readChar();
					int suffix = dis.readChar();
					//System.out.println("第"+i+"个的数据"+prefix+","+suffix);
					
					lz.add(prefix, suffix);
				}

 

③翻译编码，写出源文件

//解压缩、写出该部分的源文件
				for(int i=0;i<current;i++){
					//System.out.println("传进来的数据是~"+codeData[i]);
					lz.writeIt(dos, codeData[i]);


	public void writeIt(java.io.DataOutputStream dos,int index){
	//	System.out.println("进来的index是"+index);
		if(index>255){//是生成的码则需要转化为byte输出
			writeIt(dos,node[index].prefix);
			writeIt(dos,node[index].suffix);
		}else{
			try {
		//		System.out.println("解压输出了~"+index);
				//char data=(char) index;
				dos.write((char)index);
				//dos.writeChar(data);
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}

 

<!--EndFragment--><!--EndFragment--><!--EndFragment--><!--EndFragment-->

这个应该就是GIF所使用的压缩编码方式吧？

Lzw是lz78的变体，LZ77、LZ78是1978年Abraham Lempel与Jacob Ziv，而gzip使用的算法就是lzw和huffman的综合。所以此算法并不算新颖。《MG》在第二章就有很详细的解释。话说java里就有gzip的实现。分别叫GZipInputStream和GZipOutputStream，主要应用于解码环境较苛刻要求较高的情形。

是的，忘记说了，lzw的主要应用就是GIF

标题党　充其量是个算法的例子

讲得挺好啊.压缩数据还是第一次看到有这个好例子,挺不错.我现在要做的IPHONE网游后台也涉及到了数据压缩,但是必需得以抛包的形式传递,目前还没有思路!