本页使用了标题或全文手工转换

LZW

维基百科,自由的百科全书
跳到导航 跳到搜索

蓝波-立夫-卫曲编码法(Lempel-Ziv-Welch,缩写LZW),是亚伯拉罕·蓝波英语Abraham Lempel杰可布·立夫英语Jacob Ziv泰瑞·卫曲英语Terry Welch共同提出的一种无损数据压缩演算法

它在1984年由泰瑞·卫曲改良亚伯拉罕·蓝与杰可布·立夫在1978年发表的LZ78的版本而来(主要是基于蓝波、立夫的压缩概念,设计出一套具有可逆推的逻辑程序)。

霍夫曼编码相比,蓝波-立夫-卫曲编码法被视作将不同长度字串以固定长的码编辑(霍夫曼编码将固定长度字元用不同长度的码编辑)。其优点在于此方法只需储存一个相当小的表格,即可储存资料还原时相对应的值,所以所需成本相对地低;然而,这种算法的设计著重在实现的速度,由于它并没有对数据做任何分析,所以并不一定是最好的演算法(参考LZMALZ77)。

演算法概念[编辑]

编码[编辑]

编码依据是先将资料的个别单一字元先建立成一个字串编码表(CSET),再分别给予编号,例如原始资料为aabcaac,其字串编码表为:

字串
a 1
b 2
c 3

在随后的编(解)码过程,字串编码表会随著字串键入而逐渐扩大,如下:

字串
a 1
b 2
c 3
aa 4
ab 5
bc 6
ca 7
aac 8

因此aabcaac压缩后为15343。

解码[编辑]

解码依据是将压缩资料与原先字串编码表对照,并将对应的字元放于一个暂存伫列中,依序将压缩资料读入,若为重复资料保存于伫列中,若不为重复资料,则扩充一个新的码置于字串编码表中。例如压缩资料112343,其字串编码表为:

字串
a 1
b 2
c 3

步骤1:读取“1”,查字串编码表为“a”,则:

伫列Q:

a

输出:

a

步骤2:接著,再读取下一笔资料“1”,查字串编码表为“a”,则:

伫列Q:

a a

输出:

aa

因为aa在字串编码表内没有,因此扩充字串编码表为:

字串
a 1
b 2
c 3
aa 4

步骤3:此时将伫列Q(1)丢弃,将Q(2)移至Q(1)位置,读取下一个资料“2”,则:

伫列Q:

a b

输出:

aab

依上述步骤重复运作,最后可将压缩资料112343还原成原始资料aabcaac。

另一种演算法说明[编辑]

方法的主要关键是,它会在将要压缩的文本中,自动地建立一个先前见过字串的字典。这些字典并不需要与这些压缩的文本一起被传输,因为如果正确地编码,解压缩器也能够依照压缩器一样的方法把它建出来,将会有完全与压缩器字典在文本的同一点有同样之字串。

字典会从256个条目开始,每一个是给每种可能的字元(单一位元字串)。每一次一个字串在字典中并被见过,那么文字中,附加在单一字元后,接著该字串的一个较长文字,就会被储存到字典中。

输出是包含字典的整数索引。这些一开始每个是9位元,当字典成长时候,可以最大增加到16位元。一个特别的符号,保留来"清空字典",会把字典回复到原先的256个条目,和9位元的索引。这对于压缩文字中含有变动字元很有用处,因为在初期的资料在文字后部份并不会有太多用处。

可变动地增加索引大小的使用是Welch贡献之一。其他是用来详细说明储存字典的一种有效率资料结构。

字典基础压缩算法的简单范例[编辑]

一般而言,字典基础的压缩会以标记(token)来取代片语(phrase)。如果标记得位元数量是少于片语所需的位元数目,那么压缩就如此产生。未压缩的文本为:

I am dumb and because I am dumb, I can't even tell you that I am dumb.

压缩过的文本:

$1 and because $1, I can't even tell you that $1. $1=[I am dumb]

这与有效实用上还很遥远,但是它透过片语取代举例说明了压缩方法。

应用[编辑]

这个方法在程式"压缩"上变为广泛地被使用,大约在1986年或多或少变成Unix系统中的标准工具(自很多法律和技术的原因消失之后)。数种其他受欢迎的压缩工具也使用这种方法,或者是有紧密关系的方法。

于1987年,在它变为GIF影像格式的一部份后,它变成非常广泛地被使用。它也可以(可选择)被使用于TIFF档案。

在大部份的应用中,LZW压缩算法和当时已有且广为人知的方法相比,能够提供一个比较好的压缩率。lzw压缩算法是使用在电脑上的,第一个被广泛用于一般资料的压缩,对于大的英文文本,一般可以使用lzw将其压缩到大约原来大小的一半。另外,对于其他的种类资料的压缩,它在很多情况下也相当有用。

专利议题[编辑]

对于LZW和类似的算法,在美国和其他国家已经发行数个专利。LZ78是包含在美国专利 4,464,650,由兰波、立夫、柯亨(Cohn)和伊士曼(Eastman)指派给史佩瑞(Sperry)公司,后来是优利系统公司,申请于1981年8月10日,而且现在已经到期。

针对LZW算法有两个美国专利:由维克特·S·米勒(Victor S. Miller)和马克·N·维格曼(Mark N. Wegman)的美国专利 4,814,746,指派给IBM,原本于1983年6月1日申请和卫曲的美国专利 4,558,302,让受给史佩瑞公司,后来为优利系统公司,于1983年6月20日申请。

美国专利4,558,302是最常导致争论的一个。优利系统在当时授权免除使用费的专利执照给自由软体免费获得私有软体之开发者;该公司于1999年八月终止该执照。很多法律的专家已断定该专利并不包含只能解压缩LZW资料而无法压缩它的各种装置;因为这个原因,普遍使用的Gzip程式只能读取.Z档但是不能写入。

Debian每周新闻以comp.compression讨论串为基础所作的报导,称在美国的优利系统专利于它被授权后的17年又10天之后的2002年12月20日到期。大部份其他来源宣称该专利于它提出申请的20年后的2003年6月到期。

根据优利系统网站上的一个陈述,在英国、法国、德国、义大利、和日本之LZW相对应的专利,已经在2004年6月过期,而加拿大的专利于2004年7月7日到期。

IBM的美国专利已于2006年8月11日到期。

名称问题[编辑]

虽然LZW缩写明显地是意指Lempel、Ziv、和Welch这些发明者,某些人声称知识产权是给Ziv为第一位,因此这个方法必须称为Ziv-Lempel-Welch算法,而不是Lempel-Ziv-Welch算法

参考资料[编辑]