davirain

引言

历史

• 法律问题
• 紧缩政策的兴起

当前档案软件

未来发展

压缩技术

• Run-Length Encoding 游程编码
• Burrow-Length Transform 布鲁斯 - 惠勒变换
• Entropy Encoding 熵编码法
  • Shannon-Fano CodingHuffman
  • CodingArithmetic Coding

压缩算法

• Sliding Window Algorithm 滑动窗口算法
  • LZ77
  • LZR
  • DEFLATE
  • DEFLATE64
  • LZSS
  • LZH
  • LZB
  • ROLZ
  • LZP
  • LZRW11
  • LZJB
  • LZS
  • LZX
  • LZO
  • LZMA
  • LZMA2

Dictionary Algorithm 字典算法

• LZ78
• LZW
• ZLC
• LZTL
• ZMW
• LZAP
• LZWL
• LZJ

Non-dictionary Algorithm 非字典算法

• PPM
• bzip2
• PAQ

参考资料

1 Introduction#

压缩算法主要有两大类： 有损和无损。有损数据压缩算法通常通过删除需要大量保真数据的小细节来减少文件的大小。在有损数据压缩中。由于删除了基本数据，不可能恢复原始文件。有损数据压缩通常用于存储图像和音频数据，虽然可以通过数据删除实现非常高的压缩比，但本文并未涉及。无损数据压缩是文件的大小减少，这样一个解压函数完全可以恢复原始文件，没有数据丢失。无损数据压缩在计算机中无处不在，从节省个人电脑空间到通过网络发送数据，通过安全 shell 进行通信，或者查看 PNG 或 GIF 图像。

无损数据压缩算法工作原理是，任何非随机文件都包含重复信息，这些信息可以通过使用统计建模技术来浓缩，从而确定字符或短语出现的概率。然后可以使用这些统计模型根据发生概率为特定字符或短语生成代码，并未最常见的数据分配最短的代码。这些技术包括熵编码法、游程编码和使用字典进行压缩。使用这些技术和其他技术，一个 8 位字符或这种字符的字符串可以用几位表示，从而删除大量冗余数据。

2 History#

20 世纪 70 年代，互联网变得越来越流行，Lempel-Ziv 算法被发明出来，自从那里以后，数据压缩才在计算机领域发挥了重要作用。但它在计算机之外的历史要悠久的多。莫尔斯电码发明于 1838 年，是数据压缩最早的例子，因为英语中最常见的字母如 'e' 和 't' 被赋予较短的莫尔斯电码。后来，随着大型计算机在 1949 年开始占据主导地位，Claude Shannon, Robert Fano 发明了 Shanno-Fano 编码。他们的算法基于符合出现的概率，为给定数据块中符号分配代码。符号出现的概率与代码长度成反比，因此用较短的方式表示数据。[1]

两年后，David Huffman 在麻省理工学院学习信息论，并和 Robert Fano 一起上课， Fano 让学生选择是写学期论文还是参加期末考试。Huffman 选择了学期论文，该论文是关于寻找最有效的二进制编码方法。在工作了几个月却一无所获之后，huffman 准备丢掉它所有的工作，开始为期末开始而学习，而不是写论文。就在那个时候，它突然灵光一现，发现了一种与 Shannon-Fano 编码非常相似但更有效的计数。Shannon-Fano 编码和 Huffman 编码的关键区别在于，前者的概率树是自下而上构建的，产生的结果不是最优的，而后者是自上而下构建的。[2]

Shannon-Fano 和 Huffman 编码的早期实现都是使用硬件和硬件编码完成的。直到 20 世纪 70 年代，随着互联网和在线存储的出现。软件压缩才得以实现，Huffamn 编码是基于输入数据动态生成的 [1]. 后来， 在 1997 年，Abraham Lempel, Jacob Ziv 发表了他们开创性的 LZ77 算法，这是第一个使用字典数据的算法。更具体地说，LZ77 经常使用一种称为滑动窗口的动态字典。[3] 1978 年，同样是两个人发布了他们的 LZ78 算法，该算法也使用了字典，与 LZ77 不同的是，该算法解析输入数据并生成了静态字典，而不是动态生成。[4]

2.1 Legal Issues#

LZ77 和 LZ78 算法都迅速流行起来，产生了许多变种，如图所示。

自这些算法被发明以来， 大多数算法已经消亡了，现在只有少数算法被广泛使用，包括 DEFLATE, LZMA, LZX. 大多数常用算法都是从 LZ77 算法派生出来的。这不是因为技术上的优越性，而是因为 LZ78 算法在 1984 年 Sperry 申请了衍生物 LZW 算法的专利，并开始起诉软件供应商、服务器管理员，甚至终端用于在没有许可证的情况下使用 GIF 格式，之后，就成了专利受限算法 [5][6]

当时，UNIX 压缩使用程序对 LZW 算法进行了非常小的修改，称为 LZC，后来由于专利问题而停止使用。其他 UNIX 开发人员也开始偏离使用 LZW 算法，转而使用开源算法。这导致 UNIX 社区采用了基于 deflate 的 gzip 和基于 Burrows-Wheeler transform 的 bzip2 格式。从长远来看，这对 UNIX 社区是一个好处。因为 gzip 和 bzip2 几乎总是比 LZW 格式实现更高的压缩比。随着 LZW 算法的专利在 2003 年到期。围绕 LZW 的专利问题已经平息 [5]. 尽管如此，LZW 算法已经被很大程序上取代，并且只有在 GIF 压缩中普遍使用。此后也出现了一些 LZW 衍生品，但他们也没有得到广泛应用，LZ77 算法仍然占据主导地位。

另一场关于 LZS 算法的法律战于 1993 年爆发，是由 Stac 电子公司开发的，用于磁盘压缩软件，比如 Stacker. 微软使用 LZS 算法来开发磁盘压缩软件，这款软件是 MS-DOS 6.0 下发布的。据说可以使磁盘的容量翻一番。当 Stac 电子发现其知识产权被使用时。他对微软提起了诉讼。微软后来被判有罪，并被判向 Stac 电子支持 1.2 亿美元的损害补偿，减去 1360 万美元的反诉裁定，微软的侵权并非估计 [7], 尽管 stac 电子公司诉微软公司一案有很大的判决，但它并没有像 LZW 专利纠纷那样阻碍 Lempel-Ziv 算法的发展。唯一的结果似乎是 LZS 没有被分配到任何新的算法。

2.2 The Rise of Deflate#

自从 Lempel-Ziv 算法被发表以来，企业和其他大型实体就一直在使用数据压缩，因为它们的存储需求不断增加，而数据压缩可以帮助它们满足这些需求。然而，直到互联网开始兴起，数据压缩才开始得到广泛应用，这是因为在 1980 年代末，出现了对数据压缩的需求。带宽要么受到限制，要么很昂贵，而数据压缩有助于缓解这些瓶颈。当万维网被开发出来时，压缩变得尤为重要，因为人们开始分享更多的图像和其他格式，这些格式比文本要大得多。为了满足需求，开发了几种新的文件格式，包括 ZIP、GIF 和 PNG，其中包含了压缩技术。

1985 年，Thom Henderson 通过他的公司 System Enhancement Associates 发布了第一个商业上成功的档案格式 ARC。由于 ARC 是能够打包和压缩文件的首个程序之一，因此在 BBS 社区中特别受欢迎，同时它也是开源的。ARC 格式使用对 LZW 算法的修改来压缩数据。Phil Katz 注意到 ARC 的流行，并决定通过使用汇编语言编写压缩和解压缩程序来改进它。他在 1987 年发布了 PKARC 程序作为共享软件，并因版权侵权被 Henderson 起诉。他被认定有罪，并被迫支付版税和其他罚款，作为跨许可协议的一部分。他被认定有罪，因为 PKARC 是 ARC 的一个显然的副本；在某些情况下，甚至注释中的拼写错误都是相同的。[8]

由于交叉许可协议的限制，Phil Katz 在 1988 年后不能再销售 PKARC。因此，他在 1989 年创建了一个经过调整的 PKARC 版本，现在被称为 ZIP 格式。由于它使用了 LZW，所以被认为是受专利限制的，后来 Katz 选择切换到新的 IMPLODE 算法。在 1993 年，Katz 发布了 PKZIP 2.0，实现了 DEFLATE 算法以及其他功能，如分割卷。尽管其已经有很长时间了，但是今天几乎所有的.zip 文件都遵循 PKZIP 2.0 格式，因此这个 ZIP 格式的版本是无处不在的。

GIF，全称 Graphics Interchange Format，是由 CompuServe 于 1987 年开发的一种图形交换格式，旨在允许位图在传输时不会丢失数据（尽管该格式每帧仅限制为 256 种颜色），同时大幅减小文件大小以便在拨号调制解调器上传输。然而，像 ZIP 格式一样，GIF 也基于 LZW 算法。尽管受到专利限制，但 Unisys 未能充分执行其专利以阻止该格式的传播。即使是在 20 多年后，GIF 仍然广泛使用，特别是因其能够制作动画。[9]

虽然 GIF 无法被阻止，CompuServe 仍然寻求一个没有专利限制的格式，于 1994 年推出了 Portable Network Graphics（PNG）格式。和 ZIP 一样，PNG 标准使用 DEFLATE 算法来进行压缩。尽管 DEFLATE 是由 Katz 获得专利的 [10]，但这一专利从未被执行，因此 PNG 和其他基于 DEFLATE 的格式避免了侵犯专利。虽然 LZW 在压缩的早期被广泛采用，但由于 Unisys 的好诉性质，它已经逐渐退出历史舞台，被速度更快、更高效的 DEFLATE 算法所取代。DEFLATE 是目前最常用的数据压缩算法，有点像压缩中的瑞士军刀。

除了在 PNG 和 ZIP 格式中使用 DEFLATE，DEFLATE 在计算机领域的其他地方也非常常见。例如，gzip（.gz）文件格式使用 DEFLATE，因为它本质上是 ZIP 的开源版本。DEFLATE 的其他用途包括 HTTP、SSL 和其他旨在在网络上实现高效数据压缩的技术。

不幸的是，Phil Katz 没有活着看到他的 DEFLATE 算法征服计算机世界。他多年来一直酗酒，他的生活在 1990 年代末开始瓦解，曾因酒后驾车和其他违规行为多次被捕。2000 年 4 月 14 日，37 岁的卡茨被发现死在一家旅馆房间里。死因是急性胰腺出血，由他尸体旁发现的许多空酒瓶引起的酒精中毒。[11]

2.3 Current Archival Software#

到了 1990 年代中期，新的和更好的格式开始出现，ZIP 格式和其他基于 DEFLATE 的格式不再占据主导地位。1993 年，Eugene Roshal 发布了他的压缩软件 WinRAR，使用专有的 RAR 格式。RAR 的最新版本使用了 PPM 和 LZSS 算法的组合，但较早的实现情况并不为人所知。RAR 已成为在互联网上共享文件的标准格式，特别是在分发盗版媒体方面。一个名为 bzip2 的开源 Burrows-Wheeler 变换实现于 1996 年发布，迅速在 UNIX 平台上对 DEFLATE-based gzip 格式产生了很大的竞争。另一个开源压缩程序在 1999 年发布，即 7-Zip 或.7z 格式。由于其通常较高的压缩比率以及格式的模块化和开放性，7-Zip 可能是首个挑战 ZIP 和 RAR 主导地位的格式。这种格式不限于使用一个压缩算法，而是可以在 bzip2、LZMA、LZMA2 和 PPMd 等算法之间进行选择。最后，在存档软件的前沿是 PAQ * 格式。第一个 PAQ 格式由 Matt Mahoney 于 2002 年发布，称为 PAQ1。PAQ 通过使用称为上下文混合的技术将两个或多个统计模型结合起来，从而显著改进了 PPM 算法，以生成比任何一个模型单独预测下一个符号更好的预测。

3 Future Developments#

未来从来都是不确定的，但基于当前的趋势，可以对数据压缩的未来做出一些预测。如 PAQ 及其变种的上下文混合算法开始受到欢迎，它们往往可以实现最高的压缩比，但速度通常较慢。随着硬件速度呈指数级增长，遵循摩尔定律，上下文混合算法将很可能在高压缩比的情况下大放异彩，因为速度惩罚将被更快的硬件所克服。PAQ 旨在改进的预测部分匹配（PPM）算法也可能会出现新的变种。最后，Lempel-Ziv Markov Chain 算法（LZMA）一直表现出优秀的速度和高压缩比之间的平衡，将很可能产生更多的变种。随着 LZMA 自从在 7-Zip 格式中推出以来，已经被广泛采用于许多竞争的压缩格式中，它甚至可能成为 “赢家”。另一个潜在的发展方向是使用子串枚举压缩（CSE），这是一种新兴的压缩技术，尚未看到许多软件实现。在其朴素形式下，它的表现类似于 bzip2 和 PPM，并且研究人员一直在努力提高其效率。[12]

4 Compression Techniques#

许多不同的技术被用于压缩数据。大多数压缩技术不能独立存在，必须结合起来形成一个压缩算法。那些可以独立存在的压缩技术通常会在与其他压缩技术结合时更加有效。大多数这些技术属于熵编码器，但还有其他一些常用的技术，如游程编码和 Burrows-Wheeler 变换。

4.1 Run-Length Encoding#

运行长度编码是一种非常简单的压缩技术，它用一个数字来表示同一字符的连续出现次数，后面跟着这个字符；单个字符编码为 1 次连续出现。RLE 对于高度冗余的数据，具有许多相同颜色的像素行的索引图像或与其他压缩技术（如 Burrows-Wheeler 变换）结合使用是非常有用的。

下面是 RLE 的一个快速示例：

输入：AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

输出：3A2B4C1D6E38A

4.2 Burrows-Wheeler Transform#

Burrows-Wheeler 变换是一种于 1994 年发明的压缩技术，旨在可逆地转换输入数据块，使得相同字符的重复出现数量最大化。BWT 本身并不执行任何压缩操作，它只是将输入转换为更有效地由游程编码器或其他次要压缩技术编码的形式。

BWT 的算法很简单：

1. 创建一个字符串数组。
2. 生成输入字符串的所有可能旋转，并将每个旋转存储在数组中。
3. 按字典序对数组进行排序。
4. 返回数组的最后一列。[13]

BWT 通常在具有许多交替出现相同字符的长输入上效果最佳。以下是在理想输入上运行该算法的示例。请注意，＆是文件结束字符：

由于其交替相同的字符，对此输入执行 BWT 会生成一个最优的结果，另一个算法可以进一步压缩，例如 RLE，将产生 “3H＆3A”。尽管这个例子产生了一个最优的结果，但它在大多数真实数据上并不会产生最优结果。

4.3 Entropy Encoding#

在数据压缩中，熵指的是平均需要表示一个符号或文字所需的最少比特数。基本的熵编码器结合了统计模型和编码器。输入文件被解析并用于生成统计模型，该模型由给定符号出现的概率组成。然后，编码器将使用统计模型来确定为每个符号分配什么位或字节码，以使最常见的符号具有最短的代码，最不常见的符号具有最长的代码。

4.3.1 Shannon-Fano Coding#

这是一种最早的压缩技术，由 Claude Shannon 和 Robert Fano 于 1949 年发明。这种技术涉及生成一个二叉树来表示每个符号出现的概率。这些符号被排序，以便最常见的符号出现在树的顶部，最不可能出现的符号出现在底部。

给定一个符号的编码是通过在 Shannon-Fano 树中搜索该符号，并附加每个左或右分支的值（0 或 1）来获取的。例如，如果 “A” 是两个左分支和一个右分支，它的编码将是 “0012”。由于它从下往上构建二叉树的方式，Shannon-Fano 编码并不总是生成最优代码。因此，通常使用 Huffman 编码，因为它能为任何给定的输入生成最优代码。

生成 Shannon-Fano 编码的算法相当简单：

1. 解析输入，计算每个符号的出现次数。
2. 使用符号计数确定每个符号的概率。
3. 按概率排序符号，最可能的符号排在最前面。
4. 为每个符号生成叶节点。
5. 将列表分成两个部分，同时使左分支的概率大致相等于右分支的概率。
6. 将 0 和 1 分别添加到左和右节点的代码前面。
7. 递归地将步骤 5 和 6 应用于左和右子树，直到每个节点都是树中的叶子。

4.3.2 Huffman Coding#

Huffman 编码是熵编码的另一种变体，工作方式与 Shannon-Fano 编码非常相似，但二叉树是从上向下构建的，以生成最优结果。

生成 Huffman 编码的算法与 Shannon-Fano 共享其前几个步骤：

1. 解析输入，计算每个符号的出现次数。

2. 使用符号计数确定每个符号的概率。将符号按概率排序，最可能的排在前面。

3. 为每个符号生成叶节点，包括 P，然后将它们添加到队列中。

4. 当队列中的节点数量 > 1 时执行以下操作：

   • 从队列中删除两个概率最低的节点。
   • 将 0 和 1 分别添加到左右节点的代码前缀中。
   • 创建一个新节点，其值等于两个节点的概率之和。
   • 将第一个节点分配到左分支，将第二个节点分配到右分支。
   • 将节点添加到队列中。

5. 队列中剩下的最后一个节点是 Huffman 树的根节点。[16]

4.3.3 Arithmetic Coding#

这种方法是在 1979 年 IBM 公司开发的，当时该公司正在研究用于其大型计算机的数据压缩技术。如果目标是获得最佳的压缩比，算术编码可以说是最优秀的熵编码技术，因为它通常比 Huffman 编码获得更好的结果。然而，相对于其他编码技术，算术编码要复杂得多。

算术编码不是将符号的概率分裂成树形结构，而是通过更改基数并为 0 到基数之间的每个唯一符号分配一个单一值，将输入数据转换为 0 到 1 之间的一个有理数。然后，它进一步转换为一个固定小数位数的二进制数，这是编码结果。可以通过将基数从二进制更改回原始基数，并将值替换为它们对应的符号，将该值解码为原始输出。

计算算术编码的一般算法如下：

1. 计算输入中唯一符号的数量。
2. 这个数字表示算术编码的基数 b（例如，基数 2 是二进制）。
3. 按照它们出现的顺序，为每个唯一的符号分配从 0 到 b 的值。
4. 使用步骤 2 中的值，用它们的编码替换输入中的符号。
5. 将步骤 3 中的结果从基数 b 转换为足够长的固定小数位二进制数，以保留精度。
6. 将输入字符串的长度记录在结果中，因为这对解码过程是必需的。

以下是一个示例编码操作，给定输入 “ABCDAABD”：

1. 发现输入中有 4 个唯一符号，因此基数为 4。
   长度为 8
2. 为符号分配值：A=0，B=1，C=2，D=3
3. 使用代码替换输入：“0.012300134”，其中前导的 0 不是符号。
4. 将 “0.012311234” 从基数 4 转换为基数 2：“0.011011000001112”
5. 找到结果。请注意，在结果中，输入长度为 8。

假设为 8 位字符，则输入长度为 64 位，而其算术编码仅为 15 位，导致优秀的压缩比为 24％。此示例演示了在给定有限字符集时，算术编码如何进行良好的压缩。

5 Compression Algorithms#

5.1 Sliding Window Algorithms#

5.1.1 LZ77#

发表于 1977 年的 LZ77 算法是开创先河的算法。它首次引入了 “滑动窗口” 的概念，这带来了比更原始算法更大的压缩比改进。LZ77 使用三元组来维护字典，这些三元组表示偏移量、运行长度和一个偏差字符。偏移量表示给定短语从文件的开头开始的距离，运行长度表示从偏移量到偏移量 + 长度的字符数。偏差字符只是表示发现了一个新的短语，并且该短语等于从偏移量到偏移量 + 长度加上偏差字符。使用的字典根据解析文件时滑动窗口的变化而动态改变。例如，滑动窗口可能是 64MB，这意味着字典将包含过去 64MB 输入数据的条目。

给定输入 “abbadabba”，输出将类似于 “abb (0,1,'d')(0,3,'a')”，如下面的示例所示：

虽然这种替换的大小略大于输入，但通常在输入数据更长的情况下，它会获得更小的结果。[3]

5.1.2 LZR#

LZR 是由 Michael Rodeh 在 1981 年改进的 LZ77 算法。该算法旨在成为 LZ77 的线性时间替代方法。然而，编码指针可以指向文件中的任何偏移量，这意味着 LZR 会消耗大量的内存。加上其较差的压缩比（LZ77 通常更优），这使得 LZR 成为一个不可行的变种。[18][19]

5.1.3 DEFLATE#

DEFLATE 是由 Phil Katz 在 1993 年发明的，是今天大部分压缩任务的基础。它只是简单地将 LZ77 或 LZSS 预处理器与后端的 Huffman 编码相结合，以在短时间内实现适度压缩的结果。

5.1.4 DEFLATE64#

DEFLATE64 是 DEFLATE 算法的一种专有扩展，它将字典大小增加到 64KB（因此得名），并允许在滑动窗口中有更大的距离。与 DEFLATE 相比，它提高了性能和压缩比。然而，DEFLATE64 的专有性质以及与 DEFLATE 相比的温和改进导致该格式的采用受限。相反，通常使用像 LZMA 这样的开源算法。

5.1.5 LZSS#

LZSS（Lempel-Ziv-Storer-Szymanski）算法是由 James Storer 和 Thomas Szymanski 于 1982 年首次发布。LZSS 改进了 LZ77，因为它可以检测替换是否会减小文件大小。如果没有大小减小，输入将作为字面值保留在输出中。否则，输入的部分将被替换为一个（偏移量，长度）对，其中偏移量表示距离输入开头多少个字节，长度表示从该位置读取多少个字符。与 LZ77 相比，LZSS 的另一个改进是消除了 “下一个字符”，只使用偏移量和长度对。

以下是一个简短的示例，给定输入 “these theses”，产生了 “ these (0,6) s”，它只节省了一个字节，但对于更大的输入节省了更多的空间。

LZSS 仍然被许多流行的存档格式使用，其中最著名的是 RAR。它有时也用于网络数据压缩。

5.1.6 LZH#

LZH 是在 1987 年开发的，“Lempel-Ziv Huffman” 的缩写。它是 LZSS 的一个变种，利用 Huffman 编码来压缩指针，从而获得稍微更好的压缩效果。然而，使用 Huffman 编码带来的改进微不足道，而且压缩效果不值得使用 Huffman 编码所付出的性能代价。

5.1.7 LZB#

LZB 是由 Timothy Bell 等人于 1987 年开发的 LZSS 变体。与 LZH 类似，LZB 旨在通过更有效地编码 LZSS 指针来减少压缩文件的大小。它通过逐渐增加指针的大小来实现这一目标，随着滑动窗口的增大，指针也变得更大。与 LZSS 和 LZH 相比，它可以实现更高的压缩率，但由于指针的额外编码步骤，它仍然比 LZSS 慢。

5.1.8 ROLZ#

ROLZ 指的是 “Reduced Offset Lempel-Ziv”，它的目标是通过限制 offset length 来减少编码 offset-length 对所需的数据量，从而提高 LZ77 的压缩率。这种 LZ77 的衍生算法最初出现在 Ross Williams 的 LZRW4 算法中，其他实现包括 BALZ、QUAD 和 RZM。高度优化的 ROLZ 可以实现几乎与 LZMA 相同的压缩比，但是由于缺乏广泛的应用，ROLZ 的流行度较低。

5.1.9 LZP#

LZP 是 “Lempel-Ziv + Prediction” 的缩写。它是 ROLZ 算法的一个特例，其中偏移量被减小到 1。有几种不同的变体，使用不同的技术来实现更快的操作或更好的压缩比率。LZW4 实现了算术编码器，以获得最佳的压缩比率，但代价是速度较慢。[22]

5.1.10 LZRW1#

Ron Williams 在 1991 年创建了 LZRW1 算法，首次引入了 “减少偏移量的 Lempel-Ziv 压缩” 概念。LZRW1 可以实现高压缩比，同时保持速度快和高效的特点。Ron Williams 还创建了几个改进 LZRW1 的变体，例如 LZRW1-A、2、3、3-A 和 4 等。

5.1.11 LZJB#

Jeff Bonwick 于 1998 年创建了他的 Lempel-Ziv Jeff Bonwick 算法，用于 Solaris Z 文件系统（ZFS）。它被认为是 LZRW 算法的变体，特别是 LZRW1 变体，旨在实现最大压缩速度。由于它用于文件系统，速度尤为重要，以确保压缩算法不成为磁盘操作的瓶颈。

5.1.12 LZS#

Lempel-Ziv-Stac 算法是由 Stac Electronics 于 1994 年为磁盘压缩软件开发的一种改进型 LZ77 算法。它在输出中区分了字面符号和偏移长度对，同时省略了下一个遇到的符号，LZS 算法在功能上与 LZSS 算法最相似。

5.1.13 LZX#

LZX 算法是由 Jonathan Forbes 和 Tomi Poutanen 于 1995 年为 Amiga 计算机开发的。LZX 中的 X 没有特殊含义。Forbes 于 1996 年将该算法出售给了微软，并为微软工作，使其进一步改进以用于 Microsoft 的 cabinet (.CAB) 格式。该算法也被微软用于压缩压缩的 HTML 帮助（CHM）文件，Windows Imaging Format（WIM）文件和 Xbox Live Avatars。

5.1.14 LZO#

LZO 是由 Markus Oberhumer 在 1996 年开发的，其开发目标是实现快速的压缩和解压缩。它允许调整压缩级别，并且最高压缩级别仅需要额外的 64KB 内存，而解压缩仅需要输入和输出缓冲区。LZO 的功能与 LZSS 算法非常相似，但其针对的是速度而不是压缩比率。[26]

5.1.15 LZMA#

Lempel-Ziv Markov chain 算法最早在 1998 年随 7-Zip 压缩软件的发布而公开，用于.7z 文件格式。它通常能够比 bzip2、DEFLATE 和其他算法获得更好的压缩效果。LZMA 使用一系列压缩技术来实现输出。首先，采用修改版的 LZ77 算法对数据进行位级别的解析，而不是传统的字节级别。然后，LZ77 算法的输出经过算术编码。根据特定的 LZMA 实现，可以应用更多技术。结果通常比大多数其他 LZ 变种的压缩比例都要好，这主要是由于采用了位级别的压缩方法，而不是字节级别的压缩。

5.1.16 LZMA2#

LZMA2 是对原始 LZMA 算法的渐进改进，最初在 2009 年通过 7-Zip 存档软件的更新引入 [28]。LZMA2 改善了 LZMA 算法的多线程能力和性能，并更好地处理无法压缩的数据，从而实现略微更好的压缩。

5.1.17 Statistical Lempel-Ziv#

统计 Lempel-Ziv 是由 Sam Kwong 博士和 Yu Fan Ho 在 2001 年提出的概念。它的基本原则是将数据的统计分析与 LZ77 变体算法相结合，以进一步优化存储在字典中的编码。[29]

5.2 Dictionary Algorithms#

5.2.1 LZ78#

LZ78 算法是由 Lempel 和 Ziv 于 1978 年创造的，因此缩写中包含 “78”。与使用滑动窗口生成字典的方法不同，输入数据可以预处理以生成具有输入无限范围的字典，或者在解析文件时形成字典。LZ78 采用后一种策略。字典大小通常限制为几兆字节，或所有代码均为一定数量的字节，例如 8 个字节；这样做是为了减少内存要求。大多数 LZ78 类型算法如何处理字典已满是它们的区别所在。

在解析文件的过程中，LZ78 算法将遇到的每个新字符或字符串添加到字典中。对于输入中的每个符号，都会生成一个以字典索引和未知符号为形式的字典条目；如果一个符号已经在字典中，则字典将被搜索以查找当前符号和其后面的符号的子字符串。最长子字符串匹配的索引用于字典索引。由字典索引指向的数据将添加到未知子串的最后一个字符。如果当前符号未知，则将字典索引设置为 0，以指示它是一个单字符条目。这些条目形成了一个类似于链表的数据结构。

例如输入 "abbadabbaabaad" 将生成输出 "(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)"，下面的示例演示了它是如何得出的：

5.2.2 LZW#

LZW 是 Lempel-Ziv-Welch 算法，由特里・韦尔奇在 1984 年创建。尽管存在严重的专利问题，但 LZW 是 LZ78 算法家族中使用最广泛的算法。与 LZ78 类似，LZW 通过消除输出中的冗余字符并使输出完全由指针构成来改进 LZ78。在开始压缩之前，它还将字典中的每个字符包括在内，并采用其他技巧来提高压缩效果，例如将每个新短语的最后一个字符编码为下一个短语的第一个字符。LZW 通常出现在图形交换格式 (GIF) 以及 ZIP 格式的早期规范和其他专用应用程序中。LZW 非常快，但与大多数新算法相比，压缩效果较差，而有些算法既更快速，又可以实现更好的压缩效果。

5.2.3 LZC#

LZC（Lempel-Ziv Compress）是对 UNIX 压缩实用程序中使用的 LZW 算法的轻微修改。LZC 和 LZW 之间的主要区别在于，LZC 监控输出的压缩比。一旦比率超过某个阈值，字典就被丢弃并重建。[19]

5.2.4 LZT#

Lempel-Ziv Tischer 算法是 LZC 的一种改进，当词典满时，它会删除最近最少使用的短语，并用新条目替换它。有一些其他的渐进式改进，但是 LZC 和 LZT 今天都不常用。

5.2.5 LZMW#

LZMW 算法是由 Victor Miller 和 Mark Wegman 于 1984 年发明的，与 LZT 类似，采用最近未使用的短语替换策略。但是，LZMW 不是将字典中的相似条目合并，而是将最后两个编码的短语合并，并将结果存储为新条目。因此，字典的大小可以迅速扩大，必须更频繁地丢弃 LRUs。与 LZT 相比，LZMW 通常实现更好的压缩，但它是另一个不太常见的算法。[19]

5.2.6 LZAP#

LZAP 是由詹姆斯・斯托勒于 1988 年修改 LZMW 算法创建的。AP 代表 “所有前缀”，即字典不仅存储单个短语，而是存储每个排列组合。例如，如果上一个短语是 “last”，当前短语是 “next”，那么字典将存储 “lastn”、“lastne”、“lastnex” 和 “lastnext”。[30]

5.2.7 LZWL#

LZWL 是一个修改后的 LZW 算法，于 2006 年创造，它使用音节而不是单个字符进行压缩。LZWL 的设计旨在更好地处理具有许多常见音节的特定数据集，例如 XML 数据。通常，此类算法与预处理器一起使用，将输入数据分解为音节。

5.2.8 LZJ#

Matti Jakobsson 在 1985 年发布了 LZJ 算法 [32]，它是唯一与 LZW 不同的 LZ78 算法之一。该算法通过在字典中存储已处理的输入中的每个唯一字符串（长度不超过一个任意的最大长度）并为每个字符串分配代码来工作。当字典已满时，将删除仅出现一次的所有条目。[19]

5.3 Non-dictionary Algorithms#

5.3.1 PPM#

预测通过部分匹配是一种统计建模技术，它使用输入中一组先前的符号来预测下一个符号，以减少输出数据的熵。这与字典不同，因为 PPM 预测下一个符号，而不是尝试在字典中找到下一个符号进行编码。通常将 PPM 与编码器结合使用，如算术编码或自适应霍夫曼编码。PPM 或其变体 PPMd 被实现在许多存档格式中，包括 7-Zip 和 RAR。

5.3.2 bzip2#

bzip2 是 Burrows-Wheeler 变换的一个开源实现。它的工作原理非常简单，但它们在速度和压缩比之间取得了非常好的平衡，这使得 bzip2 格式在 UNIX 环境中非常受欢迎。首先，对数据应用运行长度编码。接下来，应用 Burrows-Wheeler 变换。然后，应用移动到前面的变换，旨在创建大量形成运行的相同符号，以供另一个运行长度编码器使用。最后，结果进行霍夫曼编码并包装在一个头文件中。

5.3.3 PAQ#

PAQ 是由 Matt Mahoney 于 2002 年创建的，旨在改进旧的 PPM（d）算法。它使用一种被称为上下文混合的革命性技术，将多个统计模型（PPM 是其中之一）智能组合在一起，以比任何单个模型更好地预测下一个符号。PAQ 是最有前途的算法之一，因为它具有极高的压缩比和非常活跃的开发。自其诞生以来，已经创建了 20 多个变种，其中一些变种实现了创纪录的压缩比。 PAQ 最大的缺点是由于使用多个统计模型以获得最佳压缩比而导致速度缓慢。但是，随着硬件不断变得更快，它可能成为未来的标准。 PAQ 正在慢慢被采用，可在 Windows 上的 PeaZip 程序中找到带有 64 位支持和主要速度改进的 PAQ8O 变体。其他 PAQ 格式大多是仅限命令行的。

6 References#

1. Wolfram, Stephen. A New Kind of Science. Champaign, IL: Wolfram Media, 2002. 1069. Print.

2. Ken Huffman. Profile: David A. Huffman, Scientific American, September 1991, pp. 54–58.

3. Ziv J., Lempel A., “A Universal Algorithm for Sequential Data Compression”, IEEE Transactions on Information Theory, Vol. 23, No. 3 (1977), pp. 337-343.

4. Ziv J., Lempel A., “Compression of Individual Sequences via Variable-Rate Coding”, IEEE Transactions on Information Theory, Vol. 24, No. 5, pp. 530-536.

5. USPTO Patent #4814746. See http://www.theregister.co.uk/1999/09/01/unisys_demands_5k_licence_fee

6. blog [Fedora & Linux Tips]

7. http://www.msversus.org/archive/stac.html

8. ARC Info

9. comp.compression Frequently Asked Questions (part 1/3)Section - [8] What about patents on data compression algorithms?

10. USPTO Patent #5051745

11. Phil Katz' Death

12. Iwata, K., Arimura, M., and Shima, Y., "An Improvement in Lossless Data Compression via Substring Enumeration", , 2011 IEEE/ACIS 10th International Conference on Computer and Information Science (ICIS).

13. Burrows M., and Wheeler, D. J. 1994. A Block-Sorting Lossless Data Compression Algorithm. SRC Research Report 124, Digital Systems Research Center.

14. http://www.cs.tau.ac.il/~dcor/Graphics/adv-slides/entropy.pdf

15. Shannon, C.E. (July 1948). "A Mathematical Theory of Communication". Bell System Technical Journal 27: 379–423.

16. HUFFMAN, D. A. 1952. A method for the construction of minimum-redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40, 9 (Sept.), pp. 1098-1101.

17. RISSANEN, J., AND LANGDON, G. G. 1979. Arithmetic coding. IBM J. Res. Dev. 23, 2 (Mar.), 149-162.

18. RODEH, M., PRATT, V. R., AND EVEN, S. 1981. Linear algorithm for data compression via string matching. J. ACM 28, 1 (Jan.), 16-24.

19. Bell, T., Witten, I., Cleary, J., "Modeling for Text Compression", ACM Computing Surveys, Vol. 21, No. 4 (1989).

20. DEFLATE64 benchmarks

21. STORER, J. A., AND SZYMANSKI, T. G. 1982. Data compression via textual substitution. J. ACM 29, 4 (Oct.), 928-951.

22. Bloom, C., "LZP: a new data compression algorithm", Data Compression Conference, 1996. DCC '96. Proceedings, p. 425 10.1109/DCC.1996.488353.

23. Dr Ross's Compression Crypt

24. "Data Compression Method - Adaptive Coding witih Sliding Window for Information Interchange", American National Standard for Information Systems, August 30, 1994.

25. LZX Sold to Microsoft

26. LZO Info

27. LZMA Accessed on 12/10/2011.

28. LZMA2 Release Date

29. Kwong, S., Ho, Y.F., "A Statistical Lempel-Ziv Compression Algorithm for Personal Digital Assistant (PDA)", IEEE Transactions on Consumer Electronics, Vol. 47, No. 1, February 2001, pp 154-162.

30. David Salomon, Data Compression – The complete reference, 4th ed., page 212

31. Chernik, K., Lansky, J., Galambos, L., "Syllable-based Compression for XML Documents", Dateso 2006, pp 21-31, ISBN 80-248-1025-5.

32. Jakobsson, M., "Compression of Character Strings by an Adaptive Dictionary", BIT Computer Science and Numerical Mathematics, Vol. 25 No. 4 (1985). doi>10.1007/BF01936138

33. Cleary, J., Witten, I., "Data Compression Using Adaptive Coding and Partial String Matching", IEEE Transactions on Communications, Vol. COM-32, No. 4, April 1984, pp 396-402.

34. Seward, J., "bzip2 and libbzip2", bzip2 Manual, March 2000.

35. Mahoney, M., "Adaptive Weighting of Context Models for Lossless Data Compression", Unknown, 2002.