- 浏览: 202520 次
- 性别:
- 来自: 长沙
最新评论
-
螺旋懒虫:
原本是想自己画点阵的,一来画的不标准,也不好解析(用excel ...
超级详细解析——字模 -
螺旋懒虫:
这个程序解决了我怎么加载点阵字库文件的问题,和怎么去拿到汉字对 ...
超级详细解析——字模 -
慕容墨风:
你好,我用你的测试程序发现数字提取不了
超级详细解析——字模 -
文之若素:
求代码,我最近在学这个,公司需要,呜呜呜,159374403 ...
初学EXTJS做的系统界面 -
csrhlu:
为什么我压缩之后文件还变大了呢? 而且解压eclipse下边会 ...
自己动手写压缩软件,超详细解释(哈夫曼实现)
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(); } } }
比较,lzw和哈弗曼做比较,lzw的代码更为简便,实现更为简单,效率也比哈弗曼高。但是LZW得算法比较难以理解。
评论
是的,忘记说了,lzw的主要应用就是GIF
发表评论
-
《动感地下城》,让宅男变猛男
2011-10-03 11:11 1557动感地下城 写在之前: 好久都没有发表文章了, ... -
RGP游戏的非主流应用——虚拟地图
2011-06-30 01:02 6051RGP游戏的非主流应用——虚拟地图 写在之前: 本 ... -
一个项目完整制作过程的分享
2011-05-22 14:23 8194St书店管理系统 写在文章之前: 本项 ... -
一个项目完整制作过程的分享
2011-05-22 14:18 0St书店管理系统 写在文章之前: 本项 ... -
eclipse下的1245个图标
2011-05-19 17:23 2101eclipse下的1245个图标 大家随便拿写 ... -
超级详细解析——字模
2011-05-17 21:09 6575超级详细解析——字模 一、简介 汉字库: 即 ... -
JavaSE 的MV模式(国际化)
2011-05-14 12:13 2719JavaSE 的 MV 模式 ... -
分享一个绿色版本的 JAR TO EXE工具(附上一个视频教程)
2011-03-15 14:05 1536如题,使用灰常简单 附上一个视频教程: -
偶然玩分形 java测试
2011-03-09 13:54 2547分形世界 我从拉丁文形容词fractus(分裂的)造出了fr ... -
Oracle, SQL Server, My SQL数据分页查询语句汇总
2011-03-05 23:16 1987之前一直在学习SQL Server,然而其的分 ... -
小议MVC模式开发
2011-02-27 22:08 1234做web项目是所经常提到的mvc模式。 MVC是三个 ... -
菜鸟 利用VE、截图 快速打造仿QQ绚丽界面
2011-02-12 02:52 2923自绘菜鸟 利用VE、截图 快速打造仿QQ绚丽界面 ... -
JAVA的几个重要概念小总结
2011-01-17 12:20 1377JAVA的几个重要概念小总结 方法声明: 写一个方 ... -
几个文字编码小总结
2011-01-17 12:03 1176ASCII 我们入门学习是最 ... -
超详细解释常用网络命令
2011-01-15 12:10 1557常用网络命令 PING请求 Ping www.google ... -
达通杯 赛后感想
2010-12-23 13:09 3556比赛结束两三天了今天才抽出了时间写写心得。 其实想想自己 ... -
自己动手写压缩软件,超详细解释(哈夫曼实现)
2010-12-04 10:58 19610说到文件压缩大家很容 ... -
JAVA BMP解码 超详细解释
2010-11-21 23:02 13276首先,对于BMP 格式的图片大家都不感觉到陌生吧。 ... -
Java 挂链 Hash表 手动实现
2010-11-19 13:08 2151前些天一直在纠结的 ... -
五子棋 图片版
2010-11-16 12:45 5493近来发现自绘的东西怎么都比不了自己PS加载图片所作的界面好看。 ...
相关推荐
LZW压缩算法(VC++实现):比Huffman编码更有效、比算法编码更快捷的压缩算法。
1. 避免了LZW算法会增大文件大小这个缺陷 2. 提供存储的压缩方法 3. 提升了压缩比 4. 提升了程序的执行速度 程序使用ANSI C语言编写,可在多平台下编译。压缩包内附编译好的程序、源代码和说明文档。谢谢大家的支持...
对于简单图像和平滑且噪声小的信号源具有较高的压缩比,并且有较高的压缩和解压缩速度。 LZW压缩技术把数据流中复杂的数据用简单的代码来表示,并把代码和数据的对应关系建立一个转换表,又叫“字符串表”。 转换...
自己在研究无损压缩做的小程序,能对任意二进制流进行LZW无损压缩,可控压缩比,程序无界面,带有简单示例.
采用LZW压缩算法实现的文本压缩器,在文本中有重复的数据将有很高的压缩比,内涵注释,需要学习的朋友可以下来看
用C++代码来实现LZW的压缩和解压的算法。压缩比可以达到20%。
结合中文文本中的汉字编码方式、大字符集以及重复字串不长三个...改进后的算法对中文文本的压缩比平均比LZW19提高了19%且压缩和解压速度与后者相当,其对较长的中文文本的平均压缩比已接近或者超过了压缩软件WinRAR。
压缩上N×使用的无损压缩算法(RLE,霍夫曼,LZW,算术)1的灰度级图像的N挡,并计算相应的压缩比
介绍LZW算法和滑动滤波算法的基本理论,详细阐述用单片FPGA实现两种算法的方法。最终测试结果表明,该设计方案能够有效滤除数据中的高频噪声,同时也可获得较好的压缩比和压缩速度,具有一定实用价值。
这个是多媒体技术中的压缩算法 是一种自适应的算法 是比算术和哈弗曼自适应算法更好的算法
压缩是一种快速,简单的LZW文件压缩器。 压缩没有最高的压缩率,但是它是压缩数据最快的程序之一。 压缩是UNIX社区中用于压缩文件的事实上的标准。 (N)compress 4.2引入了一种特殊的快速压缩哈希算法。 该算法比...
为了解决挖掘机远程故障诊断系统终端因采集到的数据量巨大,而无法实时有效地传输到远程...仿真表明,在压缩率几乎相等的情况下,硬件实现比软件实现在压缩速度上得到了极大提高,从而使故障诊断的实时性得到了保证。
摘要本文分析了艺和刀算法在文本压缩中各自的长处和不足, 以它们的实用算法和】的中文文本...的样本文本文件取得的压缩比均高于比和」, 高出幅度分别达到一。算法无须任何预处理, 并可用于压缩其它文字的 文本文件。
实现LZW算法是基于字典查找的一种优秀算法,该算法的名称来源于它的三个创始人Lemple-Ziv-Welch。它的压缩比通常在1:1--1:3之间,一些数据重复较多的文件采用此压缩方法的效果会更好。下面将详细阐述LZW算法的压缩与...
8. JPEG图像JPEG标准时目前比较流行的连续色调静止画面标准,是一种很灵活的格式,具有调节图像质量的功能,允许用不同的压缩比列对文件进行压缩,支持多种压缩级别;27 9. GIF图像:GIF文件的数据...
在低比特率(即高压缩比)下,子带变换(例如小波变换)产生的大多数系数将为零,或非常接近于零。 发生这种情况是因为“真实世界”图像往往包含大部分低频信息(高度相关)。 然而,在确实出现高频信息的情况下...
该方案充分考虑灰度文本图像的特征,用阂值差分算法将灰度文本图像分解为黑白图像和灰度残差图像,然后采用JBIG(iointbi-levelimagegroup)和LZW(Lempel-Ziv-Welch)压缩算法分别对黑白图像和灰度残差图像进行压缩。...