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 （页面存档备份，存于互联网档案馆）