关于LZW压缩编码

作者:不详  来源:网络  2014-9-21

LZW压缩编码

LZW(Lempel Ziv Welch)压缩编码是一种先进的数据压缩技术,属于无损压缩编码,该编码主要用于图像数据的压缩。对于简单图像和平滑且噪声小的信号源具有较高的压缩比,并且有较高的压缩和解压缩速度。

1977年,两位以色列教授Lempel和Ziv提出了查找冗余字符和用较短的符号标记替代冗余字符的概念。1985年,由Welch加以充实而形成LZW,简称“LZW”技术。

1、LZW压缩基本原理

LZW压缩技术把数据流中复杂的数据用简单的代码来表示,并把代码和数据的对应关系建立一个转换表,又叫“字符串表”。

转换表是在压缩或解压缩过程中动态生成的表,该表只在进行压缩或解压缩过程中需要,一旦压缩和解压缩结束,该表将不再起任何作用。

2、LZW算法

LZW算法基于转换串表(字典)T,将输入字符串映射成定长(通常为12位)的码字。在12位4096种可能的代码中,256个代表单字符,剩下3840给出现的字符串。

LZW字典中的字符串具有前缀性,即 。

LZW算法流程:

1) 初始化:将所有的单字符串放入串表;

2) 读第一个输入字符给前缀串ω;

3) Step: 读下一个输入字符K;

if 没有这样的K(输入已穷尽):

码字(ω) 输出;结束。

If ωK 已存在于串表中:

ωK:=ω;repeat Step;

else ωK不在于串表中:

码字(ω) 输出;

ωK加进串表;

K:=ω;repeat Step.

例子:ababcbababaaaaaaa

LZW编码:a,b,c,ab,ba,abc,cb,bab,baba,aa,aaa,aaaa

3、LZW压缩的特点

LZW码能有效利用字符出现频率冗余度进行压缩,且字典是自适应生成的,但通常不能有效地利用位置冗余度。

具体特点如下:

l) LZW压缩技术对于可预测性不大的数据具有较好的处理效果,常用于GIF格式的图像压缩,其平均压缩比在2:1以上,最高压缩比可达到3:1。

2) 对于数据流中连续重复出现的字节和字串,LZW压缩技术具有很高的压缩比。

3) 除了用于图像数据处理以外,LZW压缩技术还被用于文本程序等数据压缩领域。

4) LZW压缩技术有很多变体,例如常见的ARC、RKARC、PKZIP高效压缩程序。

5) 对于任意宽度和像素位长度的图像,都具有稳定的压缩过程。压缩和解压缩速度较快。

6) 对机器硬件条件要求不高,在 Intel 80386的计算机上即可进行压缩和解压缩。

猜您喜欢

© 2004-2030 m.chinagif.com

QQ:3815864 chinagif@163.com