LZW

蓝波-立夫-卫曲编码法（Lempel-Ziv-Welch，缩写LZW），是以色列科学家亚伯拉罕·蓝波、杰可布·立夫与美国学者泰瑞·卫曲共同提出的一种无损数据压缩算法。

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

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

算法概念

编码

编码依据是先将资料的个别单一字符先创建成一个字符串编码表（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压缩后为112343。

解码

解码依据是将压缩资料与原先字符串编码表对照，并将对应的字符放于一个暂存队列中，依序将压缩资料读入，若为重复资料保存于队列中，若不为重复资料，则扩展一个新的码置于字符串编码表中。例如压缩资料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算法。

参考资料