LZW（Lempel-Ziv-Welch）是 Abraham Lempel、Jacob Ziv 与 Terry Welch 创造的一种通用无损数据压缩算法。它在1984年 由 Terry Welch 作为 Abraham Lempel 与 Jacob Ziv 在 1978 年发表的 LZ78 的改进版本而发表的。这种算法的设计侧重于实现的速度，由于它并没有对数据做任何分析所以并不一定是最好的算法（参考LZMA，LZ77）。
目录 |
方法的主要关键是，它会在将要压缩的文本中，自动地建立一个先前见过字串的字典。这些字典并不需要与这些压缩的文本一起被传输，因为如果正确地编码，解压缩器也能够依照压缩器一样的方法把它建出来，将会有完全与压缩器字典在文本的同一点有同样之字串。
字典会从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和类似的算法，在美国和其他国家已经发行数个专利。LZ78是包含在（英文）美国专利 4,464,650，由Lempel, Ziv, Cohn，和 Eastman，指派给Sperry公司，后来是Unisys公司，申请于1981年8月10日，而且大概现在已经到期。针对LZW算法有两个美国专利：由Victor S. Miller和Mark N. Wegman的（英文）美国专利 4,814,746，指派给IBM，原本于1983年6月1日申请，和Welch的（英文）美国专利 4,558,302，让受给Sperry公司，后来为Unisys公司，于1983年6月20日申请。
美国专利4,558,302是最常导致争论的一个。Unisys在当时授权免除使用费的专利执照给自由软件和免费获得的私有软件之开发者；该公司于1999年八月终止该执照。很多法律的专家已断定该专利并不包含只能解压缩LZW资料而无法压缩它的各种装置；因为这个原因，普遍使用的Gzip程式只能读取.Z档但是不能写入。
Debian每周新闻以comp.compression 讨论串为基础所作的报道，在美国的Unisys专利于2002年12月20日到期 - 在它被授权后的17年又10天之后。大部份其他来源宣称该专利于2003年6月到期，在它申请的20年后。
根据Unisys网站上的一个陈述，在英国、法国、德国、意大利、和日本之LZW相对应的专利，已经在2004年6月过期，而加拿大的专利于2004年7月7日到期。
虽然LZW缩写明显地是意指Lempel、Ziv、和Welch这些发明者，某些人声称智慧财产权是给Ziv为第一位，因此这个方法必须称为Ziv-Lempel-Welch算法，而不是Lempel-Ziv-Welch算法。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
stock | retire | vm
Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History