1 Introduction

有两种主要的压缩算法类型：有损和无损。有损压缩算法通常涉及减小文件的大小，通过删除需要大量数据以保持完整保真度的细节。在有损压缩中，由于删除了关键数据，不可能恢复原始文件。有损压缩最常用于存储图像和音频数据，并且虽然可以通过数据删除实现非常高的压缩比，但本文不涵盖此类压缩算法。无损数据压缩是将文件大小减小，以便解压缩功能可以完全恢复原始文件并且不会丢失数据。无损数据压缩在计算机领域中被广泛应用，从在个人电脑上节省空间，到通过网络发送数据，通过安全 shell 进行通信或查看 PNG 或 GIF 图像。

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

2 History

数据压缩在计算机领域中的作用自1970年代以来才变得显著，当时互联网变得更加流行并发明了Lempel-Ziv算法，但它在计算机之外有着更悠久的历史。莫尔斯电码是最早的数据压缩实例，发明于1838年，英语中最常见的字母，如“e”和“t”被赋予较短的莫尔斯电码。随后，当主机计算机开始在1949年掌握时，Claude Shannon和Robert Fano发明了Shannon-Fano编码。他们的算法基于符号在给定数据块中出现的概率分配代码。符号出现的概率与代码的长度成反比，从而使数据更短的表示方式。[1]

两年后，David Huffman在麻省理工学院学习信息理论，并与Robert Fano上了一堂课。Fano给这门课提供了两个选择，要么写一篇学期论文，要么参加期末考试。Huffman选择了写学期论文，题目是找到最有效的二进制编码方法。在工作数月后，没有任何进展，Huffman已经准备放弃所有工作，开始为期末考试而学习。就在那时，他恍然大悟，想出了一种非常类似但更有效的技术，即Huffman编码。Shannon-Fano编码和Huffman编码之间的关键区别在于前者是自下而上构建概率树，从而得到次优结果，而后者是自上而下构建概率树。[2]

早期的Shannon-Fano和Huffman编码实现是使用硬件和硬编码的方式进行的。直到1970年代和互联网和在线存储的出现，软件压缩才开始实现，并且Huffman编码是基于输入数据动态生成的。[1] 稍后，在1977年，Abraham Lempel和Jacob Ziv发布了他们开创性的LZ77算法，这是第一个使用字典来压缩数据的算法。更具体地说，LZ77使用动态字典，通常称为滑动窗口。[3] 1978年，这个团队发表了他们的LZ78算法，也使用了字典。与LZ77不同的是，该算法解析输入数据并生成静态字典，而不是动态生成字典。[4]

LZ77和LZ78算法都迅速流行起来，产生了许多变种，如右图所示。这些算法中的大多数自发明以来已经消失了，只有少数几个如DEFLATE、LZMA和LZX被广泛使用。其中大多数常用算法都是源自LZ77算法。这不是因为其技术优越，而是因为LZ78算法在Sperry在1984年为其派生的LZW算法取得专利后，成为受专利保护的，开始起诉软件供应商、服务器管理员，甚至最终用户未经许可使用GIF格式。[5][6]

当时，UNIX压缩实用程序使用了一种名为LZC的LZW算法的微小修改，并因专利问题而被停止使用。其他UNIX开发者也开始摒弃使用LZW算法，转而使用开源算法。这使得UNIX社区采用了基于DEFLATE和基于Burrows-Wheeler变换的bzip2格式。从长远来看，这对UNIX社区是有益的，因为gzip和bzip2格式几乎总能实现比LZW格式更高的压缩比。[6] 关于LZW的专利问题已经消失，因为LZW算法的专利在2003年已经过期。[5]尽管如此，LZW算法已经被大部分替换，只在GIF压缩中常用。此后也有一些LZW的派生算法，但它们并没有普及，LZ77算法仍然是主流。

另一场法律纠纷于1993年爆发，涉及LZS算法。LZS是由Stac Electronics开发的磁盘压缩软件，例如Stacker使用的算法。Microsoft在开发与MS-DOS 6.0一起发布的磁盘压缩软件时使用了LZS算法，声称可以将硬盘容量翻倍。当Stac Electronics发现其知识产权被使用时，便对Microsoft提起了诉讼。后来，Microsoft被裁定侵犯专利权，并被命令向Stac Electronics支付1.2亿美元的赔偿金，扣除了1360万美元的反诉判决，认为Microsoft的侵权并非故意的[7]。尽管Stac Electronics v. Microsoft的判决很大，但它并没有像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通常在具有许多交替出现相同字符的长输入上效果最佳。以下是在理想输入上运行该算法的示例。请注意，＆是文件结束字符： inster /table

由于其交替相同的字符，对此输入执行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. 将符号按概率排序，最可能的排在前面。
  4. 为每个符号生成叶节点，包括 P，然后将它们添加到队列中。
  5. 当队列中的节点数量 > 1 时执行以下操作：
    • 从队列中删除两个概率最低的节点。
    • 将 0 和 1 分别添加到左右节点的代码前缀中。
    • 创建一个新节点，其值等于两个节点的概率之和。
    • 将第一个节点分配到左分支，将第二个节点分配到右分支。
    • 将节点添加到队列中。
  6. 队列中剩下的最后一个节点是Huffman树的根节点。[16]

4.3.3 Arithmetic Coding

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

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

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

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

以下是一个示例编码操作，给定输入“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’)”，如下面的示例所示：

insert table

虽然这种替换的大小略大于输入，但通常在输入数据更长的情况下，它会获得更小的结果。[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”，它只节省了一个字节，但对于更大的输入节省了更多的空间。

// insert table

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)”，下面的示例演示了它是如何得出的：

insert table

Input:   a b ba d ab baa baad
Dictionary Index 0 1 2 3 4 5 6 7
Output NULL (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. http://stephane.lesimple.fr/wiki/blog/lzop_vs_compress_vs_gzip_vs_bzip2_vs_lzma_vs_lzma2-xz_benchmark_reloaded
  7. http://www.msversus.org/archive/stac.html
  8. ARC Info
  9. http://www.faqs.org/faqs/compression-faq/part1/section-7.html
  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. http://www.ross.net/compression/
  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.