LZW
 |
蓝波-立夫-卫曲编码法（Lempel-Ziv-Welch，缩写LZW），是以色列科学家亚伯拉罕·蓝波、杰可布·立夫与美国学者泰瑞·卫曲共同提出的一种无损数据压缩演算法。
它在1984年由泰瑞·卫曲改良，亚伯拉罕·蓝波与杰可布·立夫在1978年发表的LZ78的版本而来（主要是基于蓝波、立夫的压缩概念，设计出一套具有可逆推的逻辑程序）。
与霍夫曼编码相比，蓝波-立夫-卫曲编码法受视作将不同长度字串以固定长的码编辑（霍夫曼编码将固定长度字元用不同长度的码编辑）。其优点在于此方法只需储存一个相当小的表格，即可储存资料还原时相对应的值，所以所需成本相对地低；然而，这种算法的设计著重在实现的速度，由于它并没有对数据做任何分析，所以并不一定是最好的演算法（参考LZMA，LZ77）。
概念
[编辑]演算法
[编辑]编码和解码的演算法分别如下：
编码
[编辑]- 先将资料的个别单一字元建立成一个字串编码表（CSET），再分别给予编号。与此同时设 S 为输入字串的第一个字元。
- 设 C 为在字串的下一个字元，并且将字串 C 连接到 S 的后面。设 W 为这个新的字串。
- 确认 W 有没有在字串编码表内，针对存在与否可以有以下两种反应：
- 假如字串编码表内存在字串 W ，则将 S 设成 W 。
- 假如字串编码表内不存在字串 W ，则我们将 S 所对应到的编码加到输出编码序列的最末端，接著将 W 新增到字串编码表里，最后再将 S 设成 C 。
- 重复步骤 2~3 直到输入字串里所有的字元都已经编码完成。
- 最后将字串 S 所对应到的编码加到输出编码序列的最末端，即完成整个编码程序。
解码
[编辑]- 先将资料的个别单一字元建立成一个字串编码表（CSET），再分别给予编号。与此同时设 S 为一空字串。
- 从编码序列的第一个编码开始，设定当前的编码所对应字元(串)为 W ，并且将该字元(串)加到输出字串的最末端。
- 假如目前字串 S 并非空字串，则我们将字串 W 的第一个字元连接到字串 S 的后面，并且将这个新字串新增到字串编码表里。
- 将 S 设成 W ，然后复步骤 2~3 直到输入编码序列里所有的编码都已经复原完成。
范例
[编辑]编码
[编辑]设原始资料为aabcaac，我们先将资料的个别单一字元先建立成一个字串编码表（CSET），再分别给予编号如下：
| 字串 | 编码 |
|---|---|
| a | 1 |
| b | 2 |
| c | 3 |
依照上面所示的编码过程，字串编码表会随著字串键入而逐渐扩大而扩展成如下列表：
| 字串 | 编码 |
|---|---|
| a | 1 |
| b | 2 |
| c | 3 |
| aa | 4 |
| ab | 5 |
| bc | 6 |
| ca | 7 |
| aac | 8 |
则原始字串 aabcaac 经过编码压缩后就是编码序列112343。
解码
[编辑]解码的首要步骤亦为将资料的个别单一字元先建立成一个字串编码表（CSET），并将对应的字元放于一个暂存伫列中。依序将编码压缩资料读入，若为该编码存在于字串编码表中就将对应字元(串)保存于输出伫列中，若不存在则扩充一个新的码置于字串编码表中。例如压缩资料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算法。
参考资料
[编辑]- 资料压缩原理与实务。张真诚，蔡文辉著。松岗电脑图书资料股份有限公司。1994/4/12。
- Welch, T.A., "A Technique for High-Performance Data Compression" ,Computers, Vol. C-17, No.6; 1984, pp.8-19.
- 美国专利4,558,302 （页面存档备份，存于互联网档案馆）
- "LZW Data Compression", by Mark Nelson （页面存档备份，存于互联网档案馆）（DDJ Article with source code）
- Sad day... GIF patent dead at 20 （页面存档备份，存于互联网档案馆）（简短且可能过于简化的简单故事内容，更多历史细节可以在GIF条目找到）
- Bringing back LZW compression by Nathan Willis
- LZW函式库，论文，以及其他资源的列表 （页面存档备份，存于互联网档案馆）
- 应用于LZW压缩序列之高效能字串比对机制 Efficient Pattern Matching Scheme in LZW Compressed Sequences （页面存档备份，存于互联网档案馆）