《数据压缩入门》笔记-Part 1

一篇文章显得略长（超过1w字），本文对应原书序言、前言、第1-5章。
第6-10章请参考Part 2，第11-15章，请参考Part 3。

序言

几点发现：

• 数据压缩需要花费时间并可能会导致软件变慢；
• 改变数据的组织结构可以让数据压缩得更小；
• 复杂的数据压缩算法各式各样。

运用压缩的几种方式：

• 改变压缩算法有可能让软件运行得更快；
• 针对数据的组织结构选择正确的压缩算法，可使数据变得更小；
• 选择不匹配的数据组织结构或压缩算法，可能会导致数据变大或运行变慢。

有两大类数据压缩算法很适合电子游戏数据：

• 无损方法
  • 去掉重复数据：LZ算法
  • 熵压缩：哈夫曼编码、算术编码
• 有损方法
  • 降低精度：截断或降采样
  • 图像/视频压缩
  • 音频压缩

对文本字符串和二进制数据使用LZ算法，可以将完全重复的数据压缩掉。对像素数据使用有损的矢量量化（vector quantization，VQ）算法，可以将像素映射为调色板。对音频数据使用有损的降采样和线性预测编码（linear predictive coding，LPC）算法，可以减少每秒的二进制位数。如果CPU足够快，前述所有这些压缩算法的输出都可以再用无损的哈夫曼算法进行一次额外的统计熵压缩。

前言

数据压缩的基础是数学。数学很难。不过现在做一名程序员不需要多少数学知识。

数据压缩领域，早期是基于统计：寻找并发现操纵数据集中符号的概率分布的不同方法，并利用这些方法来生成包含同样的信息但更小的数据集。

推荐观看：柯尔特在YouTube上的Compressor Head系列视频。

并非无趣的一章

本书的主题是数据压缩，而数据压缩无非是用最紧凑的方式来表示数据。

5类数据压缩算法

5类：

• VLC：Variable Length Codes，变长编码
• Statistical Compression：统计压缩
• Dictionary Encodings：字典编码
• Context Modeling：上下文模型
• Multicontext Modeling：多上下文模型

所有这5类算法都有很多变种，每类算法的变种在输入数据、算法性能、内存要求以及输出大小方面存在细微的差别。可混合使用。

克劳德•香农

香农发表《通信的数学理论》，开启信息论(Information Theory)这一学科。

对消息进行编码有多种方式：字母表、摩尔斯码。

信息熵，Information Entropy，香农的发明一种度量消息所携带信息内容的方法。对每一个特定的消息来说，都有一个最佳的编码方式，最佳指的是传递消息时用到的字母或符号（二进制位，即信息单位）最少。至于最少到底是多少，则取决于消息所包含的信息内容。香农的研究工作的一项实际应用，就是数据压缩。

数据压缩：在保证信息能恢复的前提下，可以将消息变得多么紧凑，如何变得紧凑。

数据压缩可以理解为对信息熵的挑战。计算机科学家所写的每一个数据压缩算法都是为了反驳香农的研究，使数据的压缩程度超过用香农发明的公式计算出来的信息熵。

数据压缩必知

数据压缩的两个思路：

• 减少数据中不同符号的数量，即让字母表尽可能小；
• 用更少的位数对更常见的符号进行编码，即最常见的字母所用的位数最少。

数据压缩研究都可归结到上面两个思路上，数据压缩中的每一个算法都聚焦于解决这两件事情中的一件。每一个压缩算法，要么通过打乱符号或减少符号的数量，将数据转换得更便于压缩；要么利用其中一些符号比其他符号更常见的事实，通过用最少的位数编码最常见的符号，实现压缩的目的。

进行实际的数据压缩时，需要综合考虑以下些因素：

• 不同数据的处理方法不同；
• 有些数据必须经过转换才能变得更容易压缩；
• 数据可能是偏态的。

我们当下生活在其中的这个计算世界，完全建立在数据压缩算法之上。

1990s，WAV是创建、存储和传输音频数据的主流格式。几乎所有人在用WAV格式。其问题在于，文件特别大。

1996年，MP3的出现改变这一切。1998年，苹果公司推出iPod。

莱娜图是用来测试图像压缩算法的标准测试图。

BWT是最有效的存储DNA信息的压缩格式，甚至无须解压就能对数据进行操作。

2014年，通过将可扩展的云计算与主机之间的压缩数据传输结合起来，创造全球最快的蛋白质折叠计算。拓展阅读：Protein Folding，Folding@home。

不容错过的一章

二进制

因为数据压缩所做的无非就是尽可能减少表示特定数据集时所需的二进制位数量。

巴比伦计数法：六十进制，以60为底数的进位制，源于苏美人，后传至巴比伦，流传至今仍用作纪录时间、角度和地理座标。

二进制与十进制之间的互相转换，还有八进制和十六进制。

LSB：Least Significant Bit，最低有效位；
MSB：Most Significant Bit，最高有效位。

信息论

信息论：从数学的角度研究如何利用符号序列、脉冲序列或其他形式，对信息进行编码，以及信息能以多快的速度在计算机电路或电信信道中传输。

一个数值所包含的信息内容等于，为了在一个集合中唯一地确定这个数值，需要做出的二选一（是/否）决定的次数。

20 Questions：20个问题。玩家A随便在心里想一个东西，玩家B通过提问来猜出这件东西，后者最多可提问20次。玩家A针对每次提问都用是或否来回答。

20个问题的思考：从数学角度来看，如果每一个问题都能排除一半的东西，20个问题则可以让提问者区分$2^{20}$即1048576个东西。

二分查找：将数组分成两半，判断要找的数值比处于中间位置的枢轴值是大还是小；进而得到个数变成一半的数组，然后重复这一过程。

熵：表示一个数所需要的最少二进制位数。

问题：给定一个整数，求它需要占几个二进制位？

数学家给出公式：$$lb(x)=\frac{logx}{log2}$$

此公式计算结果是一个浮点数，因此需要向上取整：$$LOG2(x)=ceil(\frac{logx}{log2})$$

如果此数正好是2的幂，此公式所得结果比实际需要的二进制位数小1个。因此需要进一步修正：$$LOG2(x)=ceil(\frac{log(x+1)}{log2})$$

香农将一个数对应的LOG2函数的值定义为它的熵，即用二进制来表示这个数所需的最少二进制位数。

数值的LOG2表示形式虽然高效，但对于制造计算机元件的方式来说并不实用。

问题：如果用最少的二进制位数来表示一个数，在解码相应的二进制字符串时会产生混乱（因为并不知道该数对应的LOG2长度），会与硬件的执行性能相冲突，两者不能兼顾。

现代计算机采用折中方案，用固定长度的二进制位数来表示大小不同的整数。最基本的存储单元是一个字节，由8个二进制位组成。

比如，十进制数10，对应的二进制数为1010，但在实际存储中是短整型（用16个二进制位），在计算机中的实际表示为0000000000001010，浪费很多二进制位。

突破熵

理解熵

将一个数的熵这一概念拓展到数据集，整个数据集所需要的最少二进制位数，就是集合的熵：$H(S)=-\sum _{i=1}^n{p}_{i}lb(p_i)$

信息论里的熵：对在特定的消息或语言中信息传输速度的一种对数度量。

物理学里的熵，也是一个热力学量，表示一个系统中无法转换为机械功的热能的量，通常被解释为该系统的无序度或随机度。无序或缺乏可预测性，逐渐退化为混乱。

熵的用途

为了使表示某个数据集所需的二进制位数最少，数据集中的每个符号平均所需的最小二进制位数就是熵。

理解概率

从本质上来说，香农所定义的熵，是以一种倒排序的方式建立在数据流中每个符号出现概率的估算之上的。

总的来说，一个符号出现得越频繁，它对整个数据集包含的信息内容的贡献就会越少，这看起来似乎完全违背直觉。钓鱼就是这样一个真实的例子，我们感兴趣的是鱼在咬钩这样的事件，其他的都是冗余信息。

打地鼠游戏，地鼠出现在每个洞的可能性相同，事先永远不会知道地鼠会从哪个洞里钻出来。

突破熵

香农对熵的定义里，只考虑符号出现的概率，完全没有考虑符号之间的排序。而对真实数据集来说，排序是一项基本的信息，符号之间的关系同样如此。

举例：

• 排好序的[1,2,3,4]和未排序的[4,1,2,3]两个集合的信息量显然不一样，而根据香农的定义，两者的熵相同；
• [Q,U,A,R,K]和[K,R,U,Q,A]两个集合也有相同的熵，但前者是一个单词。且字母出现也满足某种规则，如字母Q后面通常会跟着U。

突破熵的关键在于，通过利用数据集的结构信息将其转换为一种新的表示形式，而这种新表示形式的熵比源信息的熵小。

增量编码

因此，通过利用真实数据的两个性质，完全有可能将数据压缩得比熵定义的还要小。这两个性质是：

• 所有的符号都等可能地出现，并且没有重复的符号；
• 集合A和集合A元素的顺序被打乱后的集合B的熵相等。

增量编码：Delta Coding，DC，将一系列的数转换为其与上一个数的差后再编码。

根据熵的定义，符号之间的顺序无关紧要，但增量编码证明事实并非如此。如果相邻的值之间高度相关，用增量编码的方法可以转换数据，使其熵变得更小。

符号分组

符号分组，就是相邻的字符高度相关，提高字符分隔大小到短语（而非单词）级别。

排列

通过消除编码法压缩排列。

信息论与数据压缩

在谈到信息论和熵时，还是有一些回旋的空间的。熵定义的只是在对数据流进行编码时，每个符号平均所需的最小二进制位数。有些符号需要的二进制位数比熵小，而有些符号需要的二进制位数则比熵大。

数据压缩算法的艺术，就在于真正试图去突破熵的限定，或者说是将数据转换成一种熵值更小的、新的表现形式。

本书的全部内容：怎样应用数据转换以创造熵更小的数据流（然后再用适当的方法进行压缩）。

柯尔莫哥洛夫复杂性，Kolmogorov Complexity，度量确定一个对象所需要的计算资源。

如果某个生成的字符串有较强的规律性，生成字符串的程序比字符串本身小。完全可考虑把这段程序发送给某个人，然后让他运行程序重新生成字符串。这不失为一种有效的数据压缩方法，当然至少需要满足2个条件：

• 数据有规律性；
• 程序依赖某个库或脚本，需要执行环境。

柯尔莫哥洛夫复杂性的另一个理解：指为了准确地生成数据，所需要的生成程序的大小。

可以证明，任何字符串的柯尔莫哥洛夫复杂性顶多比字符串本身的长度大几个字节。基本上，也就是一个程序输出字符串的每个元素。那些柯尔莫哥洛夫复杂性比字符串本身小很多的字符串都很简单。

当开始讨论用逻辑综合（logic synthesis）或程序综合（program synthesis）进行数据压缩时，柯尔莫哥洛夫复杂性就开始真正起作用，本质上它取的是数据集以及反向生成产生字符串的程序的二进制位流。

VLC

两个问题：

• 可通过用更少或更多的二进制位对某些符号编码来节省所需要的总空间；
• 当数据集中有重复符号时，方法不太有用。

在真实的数据集中，符号重复几乎无法避免。这就是为什么LOG2方法无法正确地表示一个数据集中所真正包含的信息内容。

摩尔斯码

1836年，3位美国人，画家Samuel F. B. Morse、物理学家Joseph Henry和机械师Alfred Vail，共同发明第一套电报系统。

英语中一些字母比其他字母用得更频繁。摩尔斯码为英语字母表中的每一个字符都分配或长或短的脉冲，某字母用得越频繁，其编码也就越短、越简单。

符号分配变长编码。，VLC最初实现之一，其目的则在于减少传输信息过程中所需要的总工作量。

概率、熵与码字长度

压缩数据要做的事情：给定一个数据集中的符号，将最短的编码分配给最可能出现的符号。

从表里得出的规律：

• 当$P(A)=P(B)$，也就是两个符号等可能出现时，数据集对应的熵取最大值 LOG2（符号的个数），此时数据集很难压缩；
• 其中一个符号出现的可能越大，数据集的熵值就越小，此时数据集也越容易压缩；
• 对只包含两个符号的数据集来说，两个符号互换概率不影响其熵值，可看到$H([0.9,0.1])$等于$H([0.1,0.9])$。

得到的启示：

• 随数据集的冗余度下降，它的熵在变大，其最大值为数据集中不同符号个数的LOG2值；
• 数据集中一个符号出现的概率越大，整个数据集的熵就越小，数据集也就越容易压缩；
• 码字的长度与符号的出现概率密切相关，而与符号本身没有太大关系。

VLC

对于给定的输入数据集，可先计算涉及的符号的出现概率，然后就可以通过VLC将字长最短的码字分配给最可能出现的符号，从而实现压缩数据。

存在两个问题没有解决：

• 怎样在应用程序中运用VLC来进行压缩呢？
• 对于给定的数据集，怎样构造VLC呢？

运用VLC

对数据进行VLC的3个步骤：

• 遍历数据集中的所有符号并计算每个符号的出现概率；
• 根据概率为每个符号分配码字，一个符号出现的概率越大，所分配的码字就越短；
• 再次遍历数据集，对每一个符号进行编码，并将对应的码字输出到压缩后的数据流中。

计算符号的概率：需要遍历数据集，并计算出每个符号出现的次数

为字符分配码字：根据出现的频数进行排序，给每个符号分配一个VLC，从VLC集中码字最短的开始。得出码字表，Codeword Table。

编码：处理完整个输入流之后，再将符号码字对应表添加到输出流的前面。

解码：编码的逆过程。由于码字的长度并非固定，解码时，会一二进制位一二进制位地读取数据，直到读取的二进制位流与其中的某个码字相匹配。一旦匹配，就会输出相应的符号，并继续读取下一个码字。

创建VLC

为了确保正确，在设计VLC集的码字时，必须考虑两个原则：

• 越频繁出现的符号，其对应的码字越短；
• 码字需满足前缀性质。

前缀性质：在某个码字被分配给一个符号之后，其他的码字就不能用该码字作为前缀。

换句话说，每个符号都能通过其码字前缀唯一地确定，只有这样，VLC才能正常工作。

前缀性质是VLC能正常工作所必须具有的性质。这也就意味着，与二进制表示相比，VLC要更长一些。

VLC示例

通用编码：Universal Codes，为正整数赋上一个长度可变的二进制码字。遵循原则：数值越小，其对应的码字也越短；基于一个假定：小整数比大整数出现得更频繁。

通用编码是一类特殊的前缀编码。每一种前缀编码都是唯一可译的和非奇异的。唯一可译码：Uniquely Decodable Codes。非奇异码：Nonsingular Codes。

二进制编码

习惯用$B(n)$来表示整数$n$的标准二进制表示，被称为beta编码或二进制编码，不满足前缀性质。

给定$0\sim n$的任意整数，都能用$1+floor(lb(n))$个二进制位来表示。即，只要提前知道$n$的值，就能通过固定长度表示法来避开前缀问题。如果不能提前知道数据集中有多少个不同的整数，就不能用固定长度表示法。

在纠错码方面，Elias教授1955年引入卷积码（convolutional codes），作为分组码（block codes）的一种替代方法。还建立二进制删除信道（binary erasure channel），并提出用纠错码的列表译码（list decoding of error-correcting codes）来代替唯一可译码。

一元码

任意正整数$n$，它的一元码表示都是$n-1$个1后面跟着1个0。

一元码满足前缀性质，因此可以将它作为VLC使用。

随着整数$n$加1，其一元码码字的长度也线性地加1，因此其码字的长度$L$总是等于$n$。而在二进制编码中，码字的长度每增加1个二进制位，能表示的整数则呈指数级增长。

因此，将一元码应用在那些前一个符号的出现概率是后一个符号2倍的数据集上，效果最佳。

解一元码时，只需要从输入流中一直读取直到遇到分隔符0，然后数一下1的个数再加上1，最后将这个值输出即可。

Elias Gamma编码

主要用于事先无法确定其上界的整数的编码，即不知道最大的整数会是多大。

最主要的思想是不再对整数直接编码，而是用其数量级作为前缀。这样一来，相应的码字就由两部分组成，即与此整数相当的2的次幂再加上余数。

与简单的一元编码类似，Elias Gamma编码对那些整数$n$的出现概率$P(n)=1/(2n^2)$的情形比较适用。

Elias Delta编码

Elias还在前面加上二进制的长度。

工作原理如下面步骤所示：

• 将要编码的数$n$用二进制表示；
• 数一下$n$的二进制位数，并将这个位数转化为二进制，作为C；
• 去掉$n$的二进制表示的最左边一位。可推断出这个值肯定是1；
• 将C的二进制表示加在去掉最左边一位后的$n$的二进制表示前；
• 在上一步骤所得的结果前加上C的二进制位数减1个0作为最终的编码。

其他编码方法

VLC存在以下问题，只能用于压缩数据流：

• 它们不按字节/字/整型对齐；
• 对于大的数值$n$，为方便解码，其码字长度的增长速度一般会超过$lb(n)$个二进制位；
• 解码速度很慢，每次只能读取一个二进制位。

避免压缩整数：escaping for compressed integers，1972年提出的概念。以此为基础的新的可变长度整数模型，在搜索引擎和其他海量数据系统中得到广泛应用。

Varint是一种表示整数的方法，它用一个或多个字节来表示一个整数，数值越小用的字节数越少，数值越大用的字节数越多。

该方法将几个字节连接起来表示整数，并用每个字节的MSB作为布尔标志，来判断当前的字节是否为该整数的最后一个字节；而每个字节的低7位则用来存储该数的二进制补码（two’s complement representation）。

Varint表示方法结合VLC的灵活性和现代计算机体系结构的高效率，是一种很好的混合方法。它既允许表示可变范围内的整数，同时还对自身的数据进行对齐以提高解码的效率，达到双赢。

最适合

当给定符号的概率分布期望不同时，这些VLC编码方法的表现也不同。

在为数据集选择一种VLC编码方法时，必须要先考虑数据集的整体大小和数据范围，并计算各个符号的出现概率。

在理想的概率设定下，符号总数相同时，使用不同的方法需要用多少二进制位来表示，如下图所示：

统计编码

统计

VLC方法的前提：数据集中符号的概率分布与使用VLC方法背后的概率模型相匹配。

因此引入统计编码(Statistical Encoders)算法：无须将特定的整数转换为特定的码字，而是通过数据集中符号的出现概率，来确定新的、唯一的变长码字。

另一个定义：以数据流中符号的频率为依据，为该数据流中的各个符号分配长度可变的码字，从而使最终的输出压缩得更小。

熵编码的定义有些模糊，和统计编码不完全是一回事。

哈夫曼编码

哈夫曼编码可能是生成自定义VLC最直接最有名的方法。给定一组符号及其出现频率，该方法能生成一组符号平均长度最短的VLC。工作原理是将数据排序后建立决策树(decision tree)，然后从树干一直往下直到树叶为止，并记录下所做的是/否选择。

香农–范诺编码虽然在大多数的现代系统中没有太大价值（没有达到最短的码字长度预期，但已经很接近），却是最早通过符号及其出现概率来生成VLC的方法之一。

PKZIP/IMPLODE格式没有使用哈夫曼编码，而是使用两到三棵香农–范诺树(Shannon-Fano tree)。

构造哈夫曼树

使用二叉树。

生成码字

为了能生成码字，给所有左子树赋值0，为所有右子树赋值1。为了获得给定符号（叶子节点）的码字，需要从根节点沿着树枝往下走。

编码和解码

创建哈夫曼树（需使用计算资源）要比传输符号码字对应表（会增加数据流大小）困难得多，因此总是应该将码字对应表加在数据流的前面，而不是在解码时再重新创建一次。

实际的实现方法

产生各种能在特定性能、内存阈值、特定概率分布的各种哈夫曼编码变体。

算术编码

哈夫曼编码简单高效，也能为单个数据符号生成最佳的码字；但存在问题：对于给定的符号集来说，它并非总是生成最有效的码字。

哈夫曼编码能生成理想VLC（即码字的平均长度等于符号集的熵）的唯一情形是，各个符号的出现概率等于2的负整数次幂（即是1/2、1/4或1/8这样的值）。

算术编码算法：将整个输入流转换为一个长度很长的数值，而它的lb表示则与整个输入流真正的熵值很接近。将转换应用到整个源数据上以生成一个输出值，而表示这个输出值所需要的二进制位数比源数据本身少。

Peter Elias首先提出算术编码的概念，IBM的Jorma Rissane给出第一个实现，并申请专利。迫于专利权的保护，区间编码(Range Coding)被提出。

现代主流的文件、音频和视频的压缩格式（如LZMA和BZIP这样的文件格式，JPEG、WebP、WebM和H.264这样的音视频格式），在统计编码步骤上都会使用算术编码压缩方法。

找出正确的数

算术编码的工作原理：将字符串转换为一个数，与字符串相比，表示这个数需要的二进制位数要少一些。

算术编码会根据输入流，通过一系列复杂的步骤计算出那个数。使用改进版的二分查找法来选择这个数。

每个符号都会以递归的方式再次细分取值区间直到读完整个输入流为止。

编码

选择正确的输出值

解码

整个解码的过程，基本上就是在递归的区间内画线，然后再输出在那个时候输入值所在区间对应的符号。

具体实现

对不少实现方法进行修改以适应特定的编码解码器，如JPG和H.264编码解码器所使用的二进制版本（binary only versions）。

ANS

ANS：Asymmetric Numeral Systems，非对称数字系统，Jarek Duda提出，一种精确熵编码方法，所得到的结果可以和最优熵任意接近，它的压缩率与算术编码接近，而性能则与哈夫曼编码相当。

算法原理或步骤：

• 根据符号的出现频率对数值区间进行细分；
• 创建一张表，将子区间与离散的整数值关联起来；
• 每个符号都是通过读取和响应表中的数值来处理的；
• 向输出流中写入可变的二进制位位数。

算法的核心在第2和4步。

备查表，使得从符号转换为数值再从数值转换为符号成为可能。创建这张表时，需要先根据符号出现概率的大小排序，每个符号作为表的一列，从左往右概率依次递减。表里的数值需满足以下条件：

• 表中的每个值都是唯一的
• 每列都按照值从小到大排序
• 每行的值都要比该行的行号大

想要tANS（ANS的一种变体）变成真正的熵编码器，还必须要考虑以下两个性质：

• 在确定每一列值的个数时，需满足该值乘以maxVal后，等于该列符号的出现概率；
• 在确定每一行的值时，需确保该行列选择的值与该列符号的出现概率一致，这样当用该值除以行号，所得商就会（近似）等于该列符号的出现概率。

maxVal的选择直接影响到输出的压缩结果，而压缩结果又直接与编码所允许的整数精度相关。

选择的maxVal应该是一个函数，该函数是所需要的最小二进制位数加上由于精度的需要而额外增加的二进制位数：
$numPrecisionBits=LOG2(numSymbols)+magicExtraBits$，

$maxVal=2^{numPrecisionBits}-1$

magicExtraBits一般取2~8的某个值，或者取任何对于具体数据集来说合适的值。正如稍后会展示的那样，对于magicExtraBits的取值，要综合考虑压缩质量和时间，因为这个值越大，压缩率就越高，但同时压缩需要的时间也会越长。

还需要做一些调整：

• 首先，不再从1行开始，而是将初始状态（行号）选择为maxVal；
• 其次，对从数据流中读取的每个符号：
  • 将目标行设为该符号的列高度；
  • 右移状态值直到它比目标行的值小；
  • 状态值右移的过程中所丢弃的每个二进制位都应该输出到编码后的二进制位流中。

压缩来自于逐位输出(bit wise output)。

因为出现可能性越小的符号其列高越低，有效的行号值离最可能出现的符号也就越远（二进制位距离意义上的远），所以为了得到更小的行号，就需要进行更多次的右移操作，这也意味着每次循环会有更多的二进制位输出到数据流。因此，出现可能性越小的符号，就会输出更多的二进制位到最终的数据流中。

选择

哈夫曼编码有点问题。

算术编码之前有专利限制，算术编码后来得到硬件实现的支持。

ANS后起之秀。ZHuff、LZTurbo、LZA、Oodle和LZNA这些压缩工具已开始使用ANS。

FSE：Finite State Entropy，有限状态熵，更注重性能的ANS变种版本，只使用加法、掩码和移位运算，使ANS对开发人员更具吸引力。性能强大，以至于2015年推出一款名为LZFSE的GZIP变种，作为苹果下一代iOS版本的核心API。