无损数据压缩算法的历史

无损数据压缩算法的历史 引言 有两种主要的压缩算法：有损和无损。有损压缩算法通过移除在保真情形下需 要大量的数据去存储的小细节，从而使文件变小。在有损压缩里，因某些必要 数据的移除，恢复原文件是不可能的。有损压缩主要用来存储图像和音频文件， 同时通过移除数据可以达到一个比较高的压缩率，不过本文不讨论有损压缩。 无损压缩，也使文件变小，但对应的解压缩功能可以精确的恢复原文件，不丢 失任何数据。无损数据压缩被广泛的应用在计算机领域，从节省你个人电脑的 空间，到通过 web 发送数据。使用 Secure Shell 交流，查看 PNG 或 GIF 图片。 无损压缩算法可行的基本原理是，任意一个非随机文件都含有重复数据，这些 重复数据可以通过用来确定字符或短语出现概率的统计建模技术来压缩。统计 模型可以用来为特定的字符或者短语生成代码，基于它们出现的频率，配置最 短的代码给最常用的数据。这些技术包括熵编码(entropy encoding)、游程编 码(run-length encoding)以及字典压缩。运用这些技术以及其它技术，一个 8-bit 长度的字符或者字符串可以用很少的 bit 来表示，从而大量的重复数据 被移除。 历史 直到 20 世纪 70 年代，数据压缩才在计算机领域开始扮演重要角色，那时互联 网变得更加流行，Lempel-Ziv 算法被发明出来，但压缩算法在计算机领域之外 有着更悠久的历史。发明于 1838 年的 Morse code，是最早的数据压缩实例， 为英语中最常用的字母比如”e”和”t”分配更短的 Morse code。之后，随着 大型机的兴起，Claude Shannon 和 Robert Fano 发明了 Shannon-Fano 编码算 法。他们的算法基于符号(symbol)出现的概率来给符号分配编码(code)。一个 符号出现的概率大小与对应的编码成反比，从而用更短的方式来表示符号。 两年后，David Huffman 在 MIT 学习信息理论并上了一门 Robert Fano 老师的 课，Fano 给班级的同学两个选项，写一篇学期论文或者参加期末考试。 Huffman 选择的是写学期论文，题目是寻找二叉编码的最优算法。经过几个月 的努力后依然没有任何成果，Huffman 决定放弃所有论文相关的工作，开始学 习为参加期末考试做准备。正在那时，灵感爆发，Huffman 找到一个与 Shannon-Fano 编码相类似但是更有效的编码算法。Shannon-Fano 编码和 Huffman 编码的主要区别是构建概率树的过程不同，前者是自下而上，得到一 个次优结果，而后者是自上而下。 早期的 Shannon-Fano 编码和 Huffman 编码算法实现是使用硬件和硬编码完成的。 直到 20 世纪 70 年代互联网以及在线存储的出现，软件压缩才被实现为 Huffman 编码依据输入数据动态产生。随后，1977 年 Abraham Lempel 和 Jacob Ziv 发表了他们独创性的 LZ77 算法，第一个使用字典来压缩数据的算法。 特别的，LZ77 使用了一个叫做 slidingwindow 的动态字典。1978 年，这对搭档 发表了同样使用字典的 LZ78 算法。与 LZ77 不同，LZ78 解析输入数据，生成一 个静态字典，不像 LZ77 动态产生。 法律问题 LZ77 和 LZ78 都快速的流行开来，衍生出多个下图中所示的压缩算法。其中的 大多数已经沉寂了，只有那么几个现在被大范围的使用，包括 DEFLATE，LZMA 以及 LZX。绝大多数常用的压缩算法都衍生于 LZ77，这不是因为 LZ77 技术更好， 只是由于 Sperry 在 1984 年申请了 LZ78 衍生算法 LZW 的专利，从而发展受到了 专利的阻碍，Sperry 开始因专利侵权而起诉软件提供商，服务器管理员，甚至 是使用 GIF 格式但没有 License 的终端用户。 同时，UNIX 压缩工具使用了一个叫 LZC 的 LZW 算法微调整版本，之后由于专利 问题而被弃用。其他的 UNIX 开发者也开始放弃使用 LZW。这导致 UNIX 社区采 用基于 DEFLATE 的 gzip 和基于 Burrows-Wheeler Transform 的 bzip2 算法。长 远来说，对于 UNIX 社区这是有好处的，因为 gzip 和 bzip2 格式几乎总是比 LZW 有更好的压缩比。围绕 LZW 的专利问题已经结束，因为 LZW 的专利 2003 年 就到期了。尽管这样，LZW 算法已经很大程度上被替代掉了，仅仅被使用于 GIF 压缩中。自那以后，也有一些 LZW 的衍生算法，不过都没有流行开来，LZ77 算 法仍然是主流。 另外一场法律官司发生于 1993，关于 LZS 算法。LZS 是由 Stac Electronics 开 发的，用于硬盘压缩软件，如 Stacker。微软在开发影片压缩软件时使用了 LZS 算法，开发的软件随着 MS-DOS 6.0 一起发布，声称能够使硬盘容量翻倍。当 Stac Electronics 发现自己的知识财产被使用后，起诉了微软。微软随后被判 专利侵权并赔偿 Stac Electronics1 亿 2000 万美元，后因微软上诉因非故意侵 权而减少了 1360 万美元。尽管 Stac Electronics 和微软发生了一个那么大的 官司，但它没有阻碍 Lempel-Ziv 算法的开发，不像 LZW 专利纠纷那样。唯一的 结果就是 LZS 没有衍生出任何算法。 Deflate 的崛起 自从 Lempel-Ziv 算法被发表以来，随着对存储需求的不断增长，一些公司及其 他团体开始使用数据压缩技术，这能让他们满足这些需求。然而，数据压缩并 没有被大范围的使用，这一局面直到 20 世纪 80 年代末期随着互联网的腾飞才 开始改变，那时数据压缩的需求出现了。带宽限额，昂贵，数据压缩能够帮助 缓解这些瓶颈。当万维网发展起来之后人们开始分享更多的图片以及其它格式 的数据，这些数据远比文本大得多，压缩开始变得极其重要。为了满足这些需 求，几个新的文件格式被开发出来，包括 ZIP，GIF，和 PNG。 Thom Henderson 通过他的公司发布了第一个成功的商业存档格式，叫做 ARC， 公司名为为 System Enhancement Associates。ARC 在 BBS 社区尤为流行，这是 因为它是第一个既可以打包又可以压缩的程序，此外还开放了源代码。ARC 格 式使用一个 LZW 的衍生算法来压缩数据。一个叫做 Phil Katz 的家注意到了 ARC 的流行并决定用汇编语言来重写压缩和解压缩程序，希望改进 ARC。他于 1987 发布了他的共享软件 PKARC 程序，不久被 Henderson 以侵犯版权为由起诉。 Katz 被认定为有罪，并被迫支付版权费用以及其它许可协议费用。他之所以被 认定侵权，是由于 PKARC 是明显抄袭 ARC，甚至于一些注释里面的错别字都相 同。 Phil Katz 自 1988 年之后就因许可证问题不能继续出售 PKARC，所以 1989 年他 创建了一个 PKARC 的修改版，就是现在大家熟知的 ZIP 格式。由于使用了 LZW，它被认为专利侵权的，之后 Katz 选择转而使用新的 IMPLODE 算法，这种 格式于 1993 年再次被修改，那时 Kata 发布了 PKZIP 的 2.0 版本，那个版本实 现了 DEFLATE 算法以及一些其它特性，如分割容量等。这个 ZIP 版本也是我们 现在随处可见的格式，所有的 ZIP 文件都遵循 PKZIP 2.0 格式，尽管它年代久 远。 GIF 格式，全称 Graphics Interchange Format，于 1987 年由 CompuServe 创建， 允许图像无失真地被共享(尽管这种格式被限定每一帧最多 256 种颜色)，同时 减小文件的大小以允许通过数据机传输。然而，像 ZIP 格式一样，GIF 也是基 于 LZW 算法。尽管专利侵权，Unisys 没有办法去阻止 GIF 的传播。即使是现在， 20 年后的今天，GIF 仍然被使用着，特别是它的动画能力。 尽管 GIF 没有办法被叫停，CompuServe 需找一种不受专利束缚的格式，并于 1994 年引入了 Portable Network Graphics (PNG) 格式。像 ZIP 一样，PNG 使 用 DEFLATE 算法来处理压缩。尽管 DELLATE 的专利属于 Katz，这个专利并不是 强性制的，正是这样，PNG 以及其它基于 DEFLATE 的格式避免了专利侵权。尽 管 LZW 在压缩历史的初期占据霸主位置，由于 Unisys 公司的好诉讼作为，LZW 慢慢的淡出主流，大家转而使用更快更高效的 DEFLATE 算法。现在 DEFLATE 是 使用得最多的算法，有些压缩世界里瑞士军刀的味道。 除了用于 PNG 和 ZIP 格式之外，计算机世界里 DEFLATE 也被频繁的用在其它地 方。例如 gzip(.gz)文件格式也使用 DEFLATE，gzip 是 ZIP 的一个开源版本。 其它还包括 HTTP, SSL, 以及其它的高效压缩网络传输数据的技术。 遗憾的是，Phil Katz 英年早逝，没能看到他的 DEFLATE 算法统治计算机世界。 有几年的时间他酗酒成性，生活也于 20 世纪 90 年代末期开始支离破碎，好几 次因酒驾或者其它违法行为而被逮捕。Katz 于 2000 年 4 月 14 号被发现死于一 个酒店的房间，终年 37 岁。死因是酒精导致的严重胰腺出血，身旁是一堆的空 酒瓶。 当前的一些归档软件 ZIP 以及其它基于 DEFLATE 的格式一直占据主导地位，直到 20 世纪 90 年代中 期，一些新的改进的格式开始出现。1993 年，Eugene Roshal 发布了一个叫做 WinRAR 的归档软件，该软件使用 RAR 格式。最新的 RAR 结合了 PPM 和 LZSS 算 法，前面的版本就不太清楚了。RAR 开始在互联网分享文件方面成为事实标准， 特别是盗版影像的传播。1996 年一个叫 bzip2d 的 Burrows-Wheeler Transform 算法开源实现发布，并很快在 UNIX 平台上面流行开来，大有对抗基于 DEFLATE 算法的 gzip 格式。1999 年另外一个开源压缩程序发布了，以 7-Zip 或.7z 的格 式存在，7-Zip 应该是第一个能够挑战 ZIP 和 RAR 霸主地位的格式，这源于它 的高压缩比，模块化以及开放性。这种格式并不仅限于使用一种压缩算法，而 是可以在 bzip2, LZMA, LZMA2, 和 PPMd 算法之间任意选择。最后，归档软件 中较新的一个格式是 PAQ*格式。第一个 PAQ 版本于 2002 年由 Matt Mahoney 发 布，叫做 PAQ1。PAQ 主要使用一种叫做 context mixing 的技术来改进 PPM 算法， context mixing 结合了两个甚至是多个统计模型来产生一个更好的符号概率预 测，这要比其中的任意一个模型都要好。 压缩技术 有许多不同的技术被用来压缩数据。大多数技术都不能单独使用，需要结合起 来形成一套算法。那些能够单独使用的 技术比需要结合的技术通常更加有效。其中的绝大部分都归于 entropy 编码类 别下面，但其它的一些技术也挺常用，如 Run-Length Encoding 和 Burrows- Wheeler Transform。 Run-Length Encoding Run-Length Encoding 是一个非常简单的压缩技术，把重复出现的多个字符替 换为重复次数外加字符。单个字符次数为 1。RLE 非常适合数据重复度比较高的 数据，同一行有很多像素颜色相同的渐进图片，也可以结合 Burrows-Wheeler Transform 等其它技术一起使用。 下面是 RLE 的一个简单例子: 输入: AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 输出: 3A2B4C1D6E38A Burrows-Wheeler Transform Burrows-Wheeler Transform 是 1994 年发明的技术，目的是可逆的处理一段输 入数据，使得相同字符连续出现的次数最大化。BWT 自身并不做任何的压缩操 作，仅简单地转化数据，让 Run-Length Encoder 等压缩算法可以更有效的编码。 BWT 算法很简单: 1. 创建一个字符串数组。 2. 把输入字符串的所有排列组合塞入上述字符串数组。 3. 按照字符顺序为字符串数组排序。 4. 返回数组的最后一列。 BWT 通常处理有很多交叉重复字符的长字符串时效果很好。下面是一个有着理 想输入的例子，注意&是文件结束符： 因为交换相同的符号到一起，输入数据在 BWT 处理之后得到优化后的结果，另 外一个算法可以对该结果进行压缩，比如 RLE 会得到”3H&3A”。尽管这个例子 得到了一个较优的结果，不过现实世界中的数据它不总是这样。 Entropy Encoding 数据压缩中，平均来说为了表示一个字符或短语，Entropy 意味着所需要的最 少 bit 数。一个基本的 entropy 编码器包括一个分析模型以及一套编码。输入 文件被解析，并产生一个由字符出现概率组成的统计模型。然后，编码器可以 利用该统计模型去决定该给每一个字符多少个 bit，从而使得最常用的字符用 最短的编码，反之最不常用的字符用最长的编码。 Shannon-Fano Coding 这是最早的压缩技术，于 1949 年由 Claude Shannon 和 Robert Fano 发明。这 个技术的其中一个步骤是产生一个代表字符出现概率的二叉树。字符以这样一 种方式排序，出现得越频繁的字符越靠近树的顶端，越不常见的越靠近树的底 部。 一个字符对应的编码通过搜索 Shannon-Fano 来获得，此外，左分支后面加 0， 右分支加 1。例如，”A”是两个左节点后接一个右节点，那么对于的编码为” 0012。Shannon-Fano coding 不总是能够产生最优的编码，主要是由于二叉 树是自下而上构建的。由于这个原因，使用的较多的还是对于任意输入都能够 得到最优编码的 Huffman coding。 产生 Shannon-Fano 编码的算法很简单: 1. 解析输入，统计每一个字符出现的频率。 2. 根据是上述频率计算字符的概率。 3. 依据概率对字符降序排序。 4. 为每一个字符生成一个叶节点(LeafNode) 5. 把字符列表分为左右两部分，使得左边的概率与右边的概率大致相当。 6. 左节点加编码”0，右节点加编码”1。 7. 对两棵子树重复的步骤 5 和 6，直到所有的字符节点都成为叶子节点。 Huffman Coding Huffman Coding 是另外一个 entropy coding 的例子，与 Shannon-Fano Coding 非常的相似，只是为了产生最优编码 二叉树是自上而下构建的。 生成 Huffman 编码的算法前面的三个步骤与 Shannon-Fano 完全相同: 1. 解析输入，统计每一个字符出现的频率。 2. 根据是上述频率计算字符的概率。 3. 依据概率对字符降序排序。 4. 为每一个字符生成一个叶节点(LeafNode)，节点包含概率信息 P，把节 点存入一个队列 Queue。 5. While (Nodes in Queue 1) o 从队列里面取出概率最小的两个节点。 o 给左节点分配编码”0，右节点分配编码”1。 o 创建一个新的节点，其概率为上面步骤中的两个节点之和。 o 把两个节点中的第一个设置为新建节点的左节点，第二个节点为 新建节点的右节点。 o 把新建节点存入队列 6. 最后一个节点就是二叉树的根节点。 Arithmetic Coding 1979 年该算法在 IBM 被开发出来，当时 IBM 正在调研一些压缩算法，以期用于 它们的大型机上。如果单论压缩比，Arithmetic coding 确实是一个最优的 entropy coding 技术，通常压缩比方面 Arithmetic Coding 要比 Huffman Coding 表现得更好。然而，它却也比其它技术复杂得多。 不像其它技术会把字符概率构建成一棵树，arithmetic coding 把输入转化为 一个 0 到 1 之间的有理数，输入字符的个数记为 base，里面每一个不同的字符 都分配一个 0 到 base 之间的值。然后，最后转化为二进制得到最终的结果。结 果也可以通过把 base 恢复为原来的 base 值，替换为对应字符而得到原输入值。 一个基本的计算 arithmetic code 算法如下: 1. 计算输入数据里面不同字符的个数。这个数字记为 base b(比如 base 2 代表 2 二进制)。 2. 按字符出现的顺序分别给每一个字符分配一个 0 到 b 之间的值。 3. 使用步骤 2 中德值，把输入中的字符替换为对应的数字(编码)。 4. 把步骤 3 中得到的结果从 b 进制转化为 2 进制。 5. 如果解码需要的话，记录输入的字符总个数。 下面是一个编码操作的例子，输入为”ABCDAABD”： 1. 找到共有 4 个不同的字符输入, base = 4, length = 8。 2. 按出现顺序为不同的字符赋值: A=0, B=1, C=2, D=3。 3. 用编码替换字符，得到“0.012300134”，注意最前面的”0.”是为了得 到小数而加上去的。最后的 4 表示 base=4。 4. 把“0.012300134”从 4 进制转化为 2 进制，得到 “0.011011000001112”。最后的 2 表示 base=2。 5. 在结果中标识输入的总字符数为 8。 假设字符为 8 个 bit 表示，输入共需要 64 个 bit 空间，然而对应的 arithmetic coding 只有 15 个 bit，压缩比为 24%， 效果显著。这个例子展示了 arithmetic coding 是如何良好的压缩固定字符串 的。 压缩算法 Sliding Window Algorithms LZ77 LZ77 发表于 1977 年，是名副其实的压缩算法开山之作。它首次引入sliding window的概念，相较几个主要的压缩算法，压缩比都有非常明显的提高。 LZ77 维护了一个字典，用一个三元组来表示 offset，run length 和分割字符。 offset 表示从文件起始位置到当前 Phase 的起始位置的距离，run length 记录 当前 Phase 有多少个字符，分割符仅用于分割不同的 Phase。Phase 就是 offset 到 offset+length 之间的子串减掉分隔符。随着文件解析的进行，基于 sliding window 字典会动态的变化。例如，64MB 的 sliding window 意味着四 点将包含 64M 的输入数据的信息。 给定一个输入为”abbadabba”，那么输出可能像”abb(0,1,d)(0,3,a)” ，如下图所示: 尽管上述的替换看起来比原数据还要大，当输入数据更大一些的时候，效果会 比较好。 LZR LZR 是 LZ77 的修改版本，于 1981 年由 Michael Rodeh 发明。这个算法目标是 成为 LZ77 的一个线性时间替换算法。然而，编码后 Udell 指针可能指向文件的 任意 offset，意味着需要耗费可观的内存。加之压缩比表现也差强人意(LZ77 好得多)，LZR 算是一个不成功的 LZ77 衍生算法。 DEFLATE DEFLATE 于 1993 年由 Phil Katz 发明，是现代绝大多数压缩任务的基石。它仅 仅结合了两种算法，先用 LZ77 或 LZSS 预处理，然后用 Huffman 编码，快速的 得到不错的压缩结果。 DEFLATE64 DEFLATE64 是 DEFLATE 的一个有专利的扩展，把字典的大小提高到 64K(名字随 之)，从而允许在 sliding window 里面有更大的距离。相比于 DEFLATE，DEFLATE64 在性能和压缩比方面都有提高。然而，由于 DEFLATE64 的 专利保护以及相较 DEFLATE 并没有特别明显的提高，DEFLATE64 很少被采用。 相反一些开源算法如 LZMA 被大量的使用。 LZSS LZSS，全称 Lempel-Ziv-Storer-Szymanski，于 1982 年由 James Storer 发表。 LZSS 相较 LZ77 有所提高，它能检测到一个替换是否真的减小了文件大小。如 果文件大小没有减小，不再替换输入值。此外，输入段被(offset, length)数 据对替换，其中 offset 表示离输入起始位置的 bytes 数量，length 表示从该 位置读取了多少个字符。另外一个改进是去除了”next character”信息，仅 仅使用 offset-length 数据对。 下面是一个输入为” these theses”简单的例子，结果为” these(0,6)s”， 仅仅节省了一个 Byte，不过输入数据大的时候效果会好得多。 LZSS 依然被用在许多使用广泛的归档格式中，其中最知名的是 RAR。LZSS 有时 也被用于网络数据压缩。 LZH LZH 发明于 1987 年，全称为”Lempel-Ziv Huffman”。它是 LZSS 的一个衍生 算法，利用 Huffman coding 压缩指针，压缩效果有微小的提高。然而使用 Huffman coding 带来的提高实在是很有限，相较于使用 Huffman coding 带来 的性能损失，不足为取。 LZB LZB 同样发明于 1987 年，同样是 LZSS 的衍生算法。如 LZH 一样，LZB 也致力于 通过更加有效的编码指针以达到更好的压缩效果。它的做法是随着 sliding window 变大，逐步的增大指针的数量。它的压缩效果确实比 LZSS 和 LZH 要好， 不过因为额外的编码步骤，速度上比 LZSS 慢得多。 ROLZ ROLZ 全称”Reduced Offset Lempel-Ziv”，它的目标是提高 LZ77 的压缩效果， 通过限制 offset 的大小，从而减少为 offset-length 数据对编码的数据量。这 项 LZ77 的衍生技术于 1991 年首次出现在 Ross Williams 的 LZRW4 算法里面。 其它的实现包括 BALZ，QUAD，和 RZM。高度优化的 ROLZ 能够达到接近 LZMA 的 压缩比，不过 ROLZ 不太流行。 LZP LZP 全称”Lempel-Ziv + Prediction”。它是 ROLZ 算法的一个特殊案例， offset 减小到 1。 有几个衍生的算法使用不同的技术来实现或加快压缩速度，或提高压缩比的目 标。LZW4 实现了一个数字编码器 达到了最好的压缩比，不过牺牲了部分速度。 LZRW1 Ron Williams 于 1991 年发明了这个算法，第一次引入了 Reduced-Offset Lempel-Ziv compressiond 的概念。LZRW1 能够达到很高的压缩比，同时保持快速有效。Ron Williams 也发明另外几个基 于 LZRW1 改进的衍生算法，如 LZRW1-A, 2, 3, 3-A, 和 4。 LZJB Jeff Bonwick 于 1998 年发明了 Lempel-Ziv Jeff Bonwick 算法，用于 Solaris 操作系统的 Z 文件系统(ZFS)。它被认为是 LZRW 算法的一个衍生算法，特别是 LZRW1，目标是改进压缩速度。既然它是被 用于操作系统，速度显得尤为重要， 不能因为压缩算法的原因而使得磁盘操作成为瓶颈。 LZS Lempel-Ziv-Stac 算法于 1994 年由 Stac Electronics 发明，用于磁盘压缩软 件。它是 LZ77 的一个修改版本，区分了输出的文字符号与 offset-length 数据 对，此外还移除了分隔符。功能上来说，LZS 与 LZSS 算法很相似。 LZX LZX 算法于 1995 年由 Jonathan Forbes 和 Tomi Poutanen 发明，用于 Amiga 计 算机。LZX 中 X 没有什么特殊的意义。Forbes 于 1996 年把该算法出售给了微软， 并且受雇于微软，那那儿该算法被继续优化并用于微软的 cabinet(.CAB)格式。 这个算法也被微软用于压缩 Compressed HTML Help (CHM) 文件，Windows Imaging Format (WIM) 文件，和 Xbox Live Avatars。 LZO LZO 于 1996 年由 Markus 发明，该算法的目标是快速的压缩和解压缩。它允许 调整压缩级别，并且在最高级别下仍仅需 64KB 额外的内存空间，同时解压缩仅 需要输入和输出的空间。LZO 功能上非常类似 LZSS，不过是为了速度，而非压 缩比做的优化。 LZMA Lempel-Ziv Markov chain Algorithm 算法于 1998 年首次发表，是随着 7-Zip 归档软件一起发布的。大多数情况下它比 bzip2, DEFLATE 以及其它算法表现都 要好。LZMA 使用一系列技术来完成输出。首先时一个 LZ77 的修改版本，它操 作的是 bitwise 级别，而非传统上的 bytewise 级别，用于解析数据。LZ77 算 法解析后的输出经过数字编码。更多的技术可被使用，这依赖于具体的 LZMA 实 现。相比其它 LZ 衍生算法，LZMA 在压缩比方面提高明显，这要归功于操作 bitewise，而非 bytewise。 LZMA2 LZMA2 是 LZMA 的一个增量改进版本，于 2009 年在 7-Zip 归档软件的一个更新 版本里面首次引入。LZMA2 改进了多线程处理功能，同时优化对不可压缩数据 的处理，这也稍微提高了压缩效果。 Statistical Lempel-Ziv Statistical Lempel-Ziv 是于 2001 年由 Sam Kwong 博士和 Yu Fan Ho 博士提 出的一个概念。基本的原则是数据的统计分析结果可以与 LZ77 衍生算法结合起 来，进一步优化什么样的编码将存储在字典中。 Dictionary Algorithms LZ78 LZ78 于 1978 年由 Lempel 和 Ziv 发明，缩写正是来源于此。不再使用 sliding window 来生成字典，输入数据要么被预处理之后用来生成字典，或者字典在文 件解析过程中逐渐形成。LZ78 采用了后者。字典的大小通常被限定为几兆的大 小，或者所有编码上限为几个比特，比如 8 个。这是出于减少对内存要求的考 量。算法如何处理正是 LZ78 的各个衍生算法的区别所在。 解析文件的时候，LZ78 把新碰到的字符或者字符串加到字典中。针对每一个符 号，形如(dictionary index, unknown symbol)的字典记录会对应地生成。如 果符号已经存在于字典中，那么将从字典中搜索该符号的子字符串以及其后的 其它符号。最长子串的位置即为字典索引(Index)。字典索引对应的数据被设置 为最后一个未知子串。如果当前字符是未知的，那么字典索引设置为 0，表示 它是单字符对。这些数据对形成一个链表数据结构。 形如”abbadabbaabaad”的输入，将会产生”(0,a)(0,b)(2,a)(0,d)(1,b)(3,a) (6,d)”这样的输出。 你能从下面的例子里面看到它是如何演化的: LZW LZW 于 1984 年由 Terry Welch 发明，全称为 Lempel-Ziv-Welch。它是 LZ78 大 家族中被用得最多的算法，尽管被专利严重的阻碍了使用。LZW 改进 LZ78 的方 法与 LZSS 类似。它删除输出中冗余的数据，使得输出中不再包含指针。压缩之 前它就在字典里面包含了每一个字符，也引入了一些技术改进压缩效果，比如 把每一个语句的最后一个字符编码为下一个语句的第一个字符。LZW 在图像转 换格式中较为常见，早期也曾用于 ZIP 格式里面，也包括一些其他的专业应用。 LZW 非常的快，不过相较于一些新的算法，压缩效果就显得比较平庸。一些算 法会更快，压缩效果也更好。 LZC LZC，全称 Lempel-Ziv Compress，是 LZW 算法的一个微小修改版本，用于 UNIX 压缩工具中。LZC 与 LZW 两者的区别在于，LZC 会监控输出的压缩比。当压缩比 超过某一个临界值的时候，字典被丢弃并重构。 LZT Lempel-Ziv Tischer 是 LZC 的修改版，当字典满了，删除最不常用的的语句， 用新的记录替换它。还有一些其它的小改进，不过现在 LZC 和 LZT 都不常用了。 LZMW 于 1984 年由 Victor Miller 和 Mark Wegman 发明，LZMW 算法非常类似于 LZT， 它也采用了替换最不常用语句的策略。然而，不是连接字典中相似的语句，而 是连接 LZMW 最后被编码的两个语句并且存储为一条记录。因此，字典的容量能 够快速扩展并且 L