LZW压缩算法简介

日期：2008年5月28日作者：

　　称:LZW压缩算法简介
作者:宋成
描述:一篇关于LZW压缩算法简介的文章，通俗易懂，值得一看！
备注:该文章整理自软件报1998年合订本上册。

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

1.基本原理
    首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如"print" 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将"print"字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串"print"，在解压缩时，串表可以根据压缩数据重新生成。

2.实现方法
  A.初始化串表
    在压缩图象信息时，首先要建立一个字符串表，用以记录每个第一次出现的字符串。一个字符串表最少由两个字符数组构成，一个称为当前数组，一个称为前缀数组，因为在GIF文件中每个基本字符串的长度通常为2（但它表示的实际字符串长度可达几百甚至上千），一个基本字符串由当前字符和它前面的字符（也称前缀）构成。前缀数组中存入字符串中的首字符，当前数组存放字符串中的尾字符，其存入位置相同，因此只要确定一个下标，就可确定它所存贮的基本字符串，所以在数据压缩时，用下标代替基本字符串。一般串表大小为4096个字节（即2 的12次方），这意味着一个串表中最多能存贮4096个基本字符串，在初始化时根据图象中色彩数目多少，将串表中起始位置的字节均赋以数字，通常当前数组中的内容为该元素的序号（即下标），如第一个元素为0，第二个元素为1，第15个元素为14 ，直到下标为色彩数目加2的元素为止。如果色彩数为256，则要初始化到第258个字节，该字节中的数值为257。其中数字256表示清除码，数字257 为图象结束码。后面的字节存放文件中每一个第一次出现的串。同样也要音乐会前缀数组初始化，其中各元素的值为任意数，但一般均将其各位置1，即将开始位置的各元素初始化为0XFF，初始化的元素数目与当前数组相同，其后的元素则要存入每一个第一次出现的字符串了。如果加大串表的长度可进一步提高压缩效率，但会降低解码速度。

  B.压缩方法
    了解压缩方法时，先要了解几个名词，一是字符流，二是代码流，三是当前码，四是当前前缀。字符流是源图象文件中未经压缩的图象数据；代码流是压缩后写入GIF 文件的压缩图象数据；当前码是从字符流中刚刚读入的字符；当前前缀是刚读入字符前面的字符。
GIF 文件在压缩时，不论图象色彩位数是多少，均要将颜色值按字节的单位放入代码流中，每个字节均表示一种颜色。虽然在源图象文件中用一个字节表示16色、4色、2色时会出现4位或更多位的浪费（因为用一个字节中的4位就可以表示16色），但用LZW 压缩法时可回收字节中的空闲位。在压缩时，先从字符流中读取第一个字符作为当前前缀，再取第二个字符作为当前码，当前前缀与当前码构成第一个基本字符串（如当前前缀为A，当前码为B则此字符串即为AB），查串表，此时肯定不会找到同样字符串，则将此字符串写入串表，当前前缀写入前缀数组，当前码写入当前数组，并将当前前缀送入代码流，当前码放入当前前缀，接着读取下一个字符，该字符即为当前码了，此时又形成了一个新的基本字符串（若当前码为C，则此基本字符串为BC），查串表，若有此串，则丢弃当前前缀中的值，用该串在串表中的位置代码（即下标）作为当前前缀，再读取下一个字符作为当前码，形成新的基本字符串，直到整幅图象压缩完成。由此可看出，在压缩时，前缀数组中的值就是代码流中的字符，大于色彩数目的代码肯定表示一个字符串，而小于或等于色彩数目的代码即为色彩本身。
[1] [2] 下一页
LZW压缩算法简介相关文章：
·Linux操作系统介绍
·Oracle触发器详细介绍
·《麻将写真馆》介绍 - 手机游戏攻略秘籍 - 手机游戏
·密码破解简介
·远程破OICQ密码给工具QQExplorer ver 1.25介绍
·管理信息系统介绍
·J2SE简介
·路由原理介绍
·TCP/IP协议简介
·Linux常用命令全介绍
LZW压缩算法简介相关软件
·LogonLoader（登录介面更换器） V2.1.0 绿色版
·英语《自我介绍》
·《仙剑奇侠传》推介片动人音乐
·jdk工具介绍
·《孤岛惊魂》E3高清晰推介动画
·蒋介石宋美龄在台湾的日子
·满汉全席简介
·半条命高动态范围渲染效果演示介绍
·庐山旅游介绍
·《太阁立志传5》介绍详解

上一篇:论游戏中的搜索问题(初级篇）

下一篇:GIF文件格式

特别声明：本站除部分特别声明禁止转载的专稿外的其他文章可以自由转载，但请务必注明出处和原始作
者.文章版权归文章原始作者所有.对于被本站转载文章的个人和网站，我们表示深深的谢意。如果本站转
载的文章有版权问题请联系编辑人员,我们尽快予以更正. 转载请注明来源：http://www.hackhome.com

LZW压缩算法简介

精品推荐

热点TOP10

特别推荐