数据压缩入门汇总
读书笔记——数据压缩入门（柯尔特·麦克安利斯）上
读书笔记——数据压缩入门（柯尔特·麦克安利斯）中
读书笔记——数据压缩入门（柯尔特·麦克安利斯）下
第九章 数据建模
多上下文编码算法背后的基本概念，可以用下面的例子解释：
例如，在“典型”的英语文本中，字母“h”平均的出现概率大约是5%。然而，如果当前字母是“t”，那么下一个字母是“h”的概率就会高很多，其出现概率大约为30%，这是因为“th”这样的字母组合在英语中很常见。类似地，字母“u”平均的出现概率大约是2%。而如果当前字母是“q”，那么下一个字母是“u”的可能性则会超过99%。在这个例子中，通过当前字母是“q”，我们就能预测到下一个字母会是“u”，因此可以分配给它更少的二进制位数。这种基于统计观察的相邻关系，通常也被称作“预测”编码器，大多数正式的压缩文献中都会出现；
9.1 马尔科夫链
马尔可夫链是一种离散的随机过程，其未来的状态只取决于现在，而与过去的历史无关；假定有一个学生已经完成了中学三年级的课程，而我们想知道他在中学四年级的数学课上得A的概率。一般来说，通常我们会认为这样的预测会取决于他在中学一年级、二年级和三年级的数学课上所取得的成绩。然而，如果只有三年级（即当前）的成绩会对结果产生影响，而前两年的成绩完全可以忽略不计，那么就可以认为这是一个马尔可夫过程。
二阶上下文（second-order context），即我们有两组数据并利用它们来定义某个活动的发生概率；比如周二我看电影的概率为20%，星期作为第一阶，活动作为第二阶；同理，三阶就可以这样，周二我看完电影再做家务的概率为25%；
可以做出一个树状图，这个跟条件概率、博弈那些很相近，人工智能这门课程学的内容；
马尔可夫链这一概念能很好地融入现有的模型，因为可以认为统计编码算法就是一阶马尔可夫链。利用马尔科夫压缩比较复杂，并且我认为作者在这一块的叙述存在很多疑问点没有解释清楚，同时，没有人真正地使用马尔可夫链来压缩数据，至少不会用文中提到的方法来压缩；所以，这里我也不加了，马尔科夫链是为了引出后文的部分匹配预测算法PPM和上下文混合算法；
这只是对数据源的建模，或者说是一种编码方式，那么如何对之后的概率模型进行压缩呢？这里有个例子应该会帮助理解：
这是用符号表树表示的二阶马尔可夫链，那么“周一，洞穴探险；周二，在泳池边躺着”编码后的结果为0 1 10 1110，总共8个二进制位。相比之下，如果想将10个状态都遍历一次，那么编码同样的数据最终需要的二进制位数肯定会超过12。从技术角度来看，为压缩而建立的马尔可夫链遵循的许多规则与前面介绍的自适应统计编码（参见第2章）相同，比如读取符号之后再动态更新频率表，等等；
以字符串“TOTOTO”创建马尔可夫链为例来说明整个编码过程：
解码过程如下：
9.2 部分匹配预测算法PPM
要使马尔可夫链算法变得实用，就必须要解决内存消耗问题与计算性能问题，即使用最佳链来编码。John Cleary与和Ian Witten于1984年提出了马尔可夫链算法的一种具体实现，并称之为部分匹配预测算法（prediction by partial matching，PPM），该算法在内存消耗与计算性能方面表现都还不错。与马尔可夫链类似，PPM算法同样通过前N个符号的上下文来决定第N+1个符号最有效的编码方式。
给定输入流中的当前符号，PPM算法会向前扫描N个符号，并根据前N个符号的上下文来决定当前符号的出现概率。如果在N个符号的上下文中，当前符号的出现概率为0，PPM算法就会将上下文符号的个数减少为N-1。如果没有在任何上下文中发现匹配，就会做出固定的预测。
说白了，三阶、二阶指的就是当前字符前面第3个、2个字符，从他们开始找匹配的；
9.2.1 单词查找树
要实现PPM算法，我们遇到的首要问题是如何创建一种数据结构，可以将从输入流中读取的每个字符的所有上下文（[0-N]阶）存储起来，并且在需要时能快速定位到。在简单的情况下，可以通过一种被称为单词查找树（trie）的特殊树结构来实现这样的需求，这种树的每个分支都表示一种上下文。
创建这样的查找树是有用的，给定当前的状态，我们很快就能将N减X阶上下文查找出来。例如，假定当前字符是“C”，那么它的二阶上下文是“BA”，一阶上下文是“A”。这与实际完全符合，因为它表示的就是编码“ABAC”时在“C”之前的一个和两个符号的滑动窗口。
在限定二阶上下文的情况下，可以用这棵查找树来表示输入字符串的所有子字符串：B、BA、BAC、C、A、AB、AC和ABA。
9.2.2 字符的压缩
除了能提供高效的存储以及快速提取子字符串外，单词查找树的每一层都会记录字符出现的次数。有了这些数据，统计编码算法就能构建出字符出现的概率表，并根据概率表为每个字符分配相应的码字;
实际上，对树的每一层，只需要考虑这一层的兄弟节点并将出现次数归一化就能得到相应的概率。例如，一阶上下文中节点[B,1]、[C,1] 和[A,2] 中出现次数对应的概率分别为25%、25% 和50%。
此外，注意因为在二阶上下文中编码每个字符都只用了1个二进制位，所以每个字符都节省了1个二进制位。
9.2.3 选择一个合理的N值
PPM算法会选择一个N值，然后再根据这样的上下文长度去寻找匹配。如果没有找到匹配，就会选择更短的上下文继续寻找。这样看来，似乎上下文越长（也就是N的取值越大），预测的效果越好。然而，大多数PPM算法的实现在综合考虑所需内存、处理速度以及压缩率后，将N的值设定为5或者6；也有一些PPM算法的变体，例如PPM*，尝试着使N的取值变大，并且是变得非常大。这样做，不仅需要一种新的查找树结构，而且需要的计算资源也远比PPM多，但其结果则比PPM算法好，能多节省约6% 的存储空间；
简单地说，N值大小直接与内存消耗挂钩；
9.2.4 处理未知的符号
PPM算法（模型）的大部分优化工作是在处理输入流中那些之前没有出现过的字符。显而易见的处理方法是通过创建“从没见过”的符号来触发转义序列（escape sequence），但是那些没有见过的符号应该赋什么样的概率值呢？这通常被称为零频问题（zero-frequency problem）。
有一种PPM算法的变体使用拉普拉斯估计（Laplace estimator），赋给所有“从没见过”的符号相同的伪计数值1。还有一种被称为PPMD的变体是这样处理这一问题的，“从没见过”的符号每使用一次，伪计数值就加1。（换句话说，PPMD算法是这样估算新出现符号的概率的，即新符号的概率等于不同符号的个数与观察到的所有符号的出现次数之比。）
PPMZ算法刚开始时它的处理方式与PPM* 相同，都试图在N阶上下文下找出当前符号的匹配。当找不到这样的匹配时，它就会换上完全不同的算法，即局部阶估计法（Local-Order-Estimator），而使用的还是基本的PPM模型，只不过预测的算法完全不同。
9.3 上下文混合算法
对PPM算法的改进，让我们有了新的数据压缩算法，PAQ 系列算法。特别是在PPMZ算法中，对于符号如何去响应匹配，人们尝试了多种类型的上下文；
重点中的重点，如何优化paq算法；
随着时间的推移，这一概念逐渐被称为上下文混合算法（context mixing），即为了找出给定符号的最佳编码，我们会使用两个或者更多的统计模型。例如，通过一个统计模型来预测在所有的经常性活动（比如营救小猫之类）中你去健身房的概率有多大，用另外一个统计模型来预测吃了太多意大利面后的12个小时内你去健身房的概率。在面对“现在你要去健身房的概率有多大”这样的问题时，每个模型会给出不同的概率。由于通常情况下你去健身房的概率为20%，而且离你吃完意大利面已经有6个小时了，因此现在去健身房的概率很可能是50%。上下文混合算法就是综合去利用这些概率。
对于数据压缩，上下文混合算法带来两个有意思的问题：①应该使用什么样的模型；②怎样结合模型；
9.3.1 模型的类型
对数据压缩来说，相邻性是一个很重要的课题。LZ、RLE、增量编码以及BWT这些算法都是基于这样的假设：数据的相邻性与它的最佳编码方式有关。
总的来说，相邻性和局部性都只是上下文的最简单形式，而绝不是唯一的形式。实际上，模型可以有很多种，需要处理的数据类型不同，模型也会不同。
例如，图像数据更多地关注二维的局部性，也就是说一个像素的颜色通常与上下左右四个方向相邻像素的颜色有关，可以利用这一信息对图像进行压缩。然而，这一模型不适用于文本，在文本中通常找不出这样的规律，即一个字符与其上一行或下一行同样位置的字符无关；
比如，在编程中，当把高级的指令编译为字节码后，就会呈现出完全不同的模型。一个字节可以描述指令，后面跟着长度不等的字节描述函数的输入。由于代码往往有相同的模式，因此你完全可以按照下面的方式建模：当看到“跳转到此指令”命令后，你极有可能会看到附近出现"将变量压入调用栈"之类的命令。因此，在这种情况下，相邻的字节不重要，重要的是命令本身。
音乐是另外一种完全不同的数据，你可以建立模型来表示低音旋律或者吉他即兴重复，并考虑其中涉及的音阶或者变奏过渡的长度。关键在于，你如果对数据足够了解并且能正确地提问，就会有成千上万种建模的方法。因此，在某些情况下问题的难度就增加了，因为现在讨论的不再是通用算法，而更多的是提问：“你是否对数据了解得足够多，可以正确地对其进行建模？”
作为上下文混合算法的先驱压缩器之一，PAQ包含以下模型：
PAQ不是小打小闹，它在大文本压缩基准测试（Large Text Compression Benchmark）中经常排名靠前，它的最新版本之一ZPAQ在压缩人类DNA信息的比赛中获得了第二名；
9.3.2 混合的类型
幸运的是，统计学已经基本上帮我们解决了这个问题。将不同模型的输出结合起来有以下两种方法：
一种是线性混合（linear mixing），它是将各个模型的预测值加权平均的过程，最终的值则取决于权重。
在前面举的例子中，我们想知道的是你现在去健身房的概率，而给定的值是你多久去一次健身房以及吃一次意大利面。这两个给定的值有不同的证据权重，其中的一个值由于有更多的试验数据或者说样本数据，因而更可信。例如，如果你是在人的一生这个时间层面考虑意大利面如何影响你去健身房，那么就会有更多的样本数据，因此相应的取值也就比你上周去健身房的次数更可信。因此，对这样的值我们会在混合模型中给予更高的权重，因为它更可信。
另一种则是逻辑混合，它要复杂很多。我们知道，在线性混合中，没有反馈回路来说明在预测如何压缩数据时我们赋给一个模型的权重是否正确；因此，当输入数据流变化时，模型的权重保持不变，最终得到的结果不但没有压缩，反而比原来需要的空间还大。
为了解决这个问题，逻辑混合使用了神经网络来更新权重，而更新的依据则是哪个模型在过去给出了最准确的预测。这里的关键是修改当前的权重，其实就是加入惩罚函数，从而对权重进行修正；假定根据当前的权重，我们选择了模型A编码某个符号，编码后的长度为12个二进制位，而模型B其实才是正确的选择，它只需要8个二进制位。那么，编码器会输出12个二进制位，并修改模型的权重，这样当下次所有的模型输出结果相同时，模型B有更大的机会被选中。
逻辑混合的缺点是，在进行数据压缩时，它需要消耗大量的内存，同时运行的时间也较长。如果看一些在LTCB上运行的ZPAQ，你会发现压缩1 G的文件需要14 G的内存。这些压缩的中间数据都需要空间去存储。
9.4 下一代技术
由于需要大量的内存和运行时间，这就使得上下文混合算法很难适用于移动设备（至少在本书写作时如此）。然而实际情况是，这时的数据目标与前面的完全不同。如果你想处理的只是1~50 MB的数据，那么即使用了上下文混合算法，所得的结果也会和很多其他的算法差不多。只有当需要处理的数据量很大、数据很复杂并且一直在变化时，上下文混合算法才能真正发挥作用；
对数据压缩来说，同样没有银弹。无论是哪个数据集，都需要有思考的过程，对信息的定义和处理进行分析。即使是上下文建模，虽然它建立的目的是适应数据的变化，但也同样依赖于人们所建的信息模型。
第十章 一些点
之前主要关注特定的数据压缩算法以及它们通常是怎样工作的，虽然这些内容中包含的信息很多，但除非你打算自己实现一个有突破性的数据压缩工具，否则这些内容的主要目的还是帮助你理解数据及其压缩； 现在，我们想换个话题，谈谈数据压缩应用中的一些点，以及它们如何与你、你开发的项目以及眼前的世界关联；
当前压缩可以分为两类，即多媒体数据压缩（media-specific compression）与通用压缩（generalpurpose compression）；
10.1 多媒体数据压缩
多媒体数据压缩工具是专门设计用来压缩图像、音频、视频等多媒体数据的；一张1024×1024的RGB色彩模式的图片，其大小就有3 MB，如果用ASCII码来表示字母的话，同样的空间能用来表示3145728个字母，相比而言，有名的《霍比特人》一书只有95022个单词，如果假定平均每个单词由5个字母组成，那么这本书大约有475 110个字母。也就是说，一张1024×1024的图片所占用的空间，可以用来存放约6本《霍比特人》这样篇幅的书；
有损压缩指的是为了使数据压缩得更小，可以牺牲多媒体的质量这样的数据转换；例如，一张1024×1024的图片，如果使用8个二进制位来表示红绿蓝这3种颜色通道，那么每个像素就需要24个二进制位，因此整个图片的大小为3 MB。然而，如果每个颜色通道只用4个二进制位表示，那么每个像素就只需要12个二进制位，整个图片占用的空间也就只有1.5 MB，但同时也降低了图片的色彩质量。
有损数据转换的种类特别多，每一种都针对特定的多媒体文件（针对图像文件的就不太适用于音频文件）和内容类型（灰度图像与全彩图像使用的压缩算法同样不同）；在内容转换为更容易压缩的状态后，你可以继续应用所有标准转换，例如LZ、BWT、RLE以及增量压缩，甚至可以使用哈夫曼编码、算术编码和ANS。
关键在于，针对某种数据类型找出最佳的转换方法，以获得最好的结果；
10.2 通用压缩
相比而言，通用压缩工具是设计用来压缩除多媒体数据以外的其他数据。像DEFLATE、GZIP、BZIP2、LZMA和PAQ这些算法，都是将各种无损转换结合起来，用来压缩诸如文本、源代码、序列化数据以及二进制内容等其他不能使用有损压缩工具压缩的非多媒体文件；
大文本压缩基准测试，有很多通用压缩工具会参与这项压缩大文本的比赛，以比较这些工具的各种性能指标。新的算法还在不断出现。谷歌对GZIP算法的改进已产生了一系列的压缩工具，如Snappy、Zopfli、Gipfeli以及Brotli，这些工具努力的方向是为了实现更好的压缩率、更小的内存需求和更快的解压速度，但是每个的侧重点不同；
不妨看看最近那些很成功的压缩工具（Brotli、LZHAM、LZFSE、ZSTD），我们发现有以下趋势：研究主题的变化很小。它们都是在现有的转换上使用一些技巧或是进行一些改变，然后再应用到现有的压缩算法上，以获得某些小的提升，而且获得边际提升需要的资源越来越多；
通过观察各种各样的基准测试，我们发现30%~50% 这样比例的突破已经不存在了，更多的是经过大量努力后，只能在现有算法的基础上提高2%到10%；
第十一章 评价数据压缩
11.1 使用场景
讨论数据是在哪里压缩、存储和解压的。理解数据是从哪里来的、到哪里去之所以很重要，是因为编码器与解码器之间的相互作用很重要；
线下压缩，客户端解压
在第一个场景中，数据在某个与客户端无关的地方压缩，然后分发到客户端，并在客户端解压以供使用。
这一场景对打包的应用程序或者电子游戏来说很常见，并且相应的资源文件中常常包含大量的图片、视频和音乐；即原始的作品都是使用高分辨率、高保真的工具制作的，然后再输出并压缩以供分发；这里压缩的目的是使多媒体文件尽可能地小。
需要权衡取舍的是多媒体文件的品质；
客户端压缩，云端解压
大多数现代社交媒体应用程序会在客户端产生很多内容，然后将它们推到云端进行处理并分发给其他社交用户。在这些场景中，通常会在客户端进行初步压缩，以节省出站通信的流量费用。例如，在获取一组社交数据后，我们会先使用二进制序列化格式将这组数据序列化，然后在发送到服务器之前再用GZIP对它进行压缩。
这里的主要目的是减少用户的费用。虽然很多北美的用户（仍然）使用的是无限量数据套餐服务，但是世界上很多地方的用户不能享受这样的服务，因此大多数用户使用的是按照流量付费的套餐。也就是说，这些用户上传到服务器上的每个二进制位都要自己付费。
这里的权衡取舍是，对于移动设备，需要消耗电池的电量去压缩数据；
云端压缩，客户端解压
放到云端压缩的数据大致可以分类两类：
1.由云端资源生成的动态数据
与用户将数据上传到云端相反，这些数据来源于云端并由用户下载到本地。例如，在客户端请求数据库操作的结果，或者服务器发送了动态布局的数据，而客户端在等待内容生成的时候，服务器生成并压缩数据所需的时间就变得非常重要。因为如果需要的时间比较长的话，客户端就会明显地感受到网络延迟。这里最重要的是平衡压缩后的大小与所需要的时间。值得指出的是，在某些高延迟的环境下，用户可能会更愿意多等一些时间，使文件变得更小。这里，压缩的目的就是让通过网络传输的内容变得更小。
这里需要权衡取舍的是时间。
2.为提高计算效率而传输到云端的大量数据
这一场景的重要性往往是因为需要确保手边的媒体文件尽量地小。例如，设想你有2GB的PNG文件需要转换为10种不同分辨率的WebP图片，或者是你有长度为1200个小时的视频文件需要在播放前转换为H.264格式。需要记住的是，由云端传输出去的每个二进制位都需要所有者付费，实际上，客户端也需要为从云端获取的每个二进制位付费。因此，这是使用云端计算资源的理想场景，我们可以用计算效率最高的方式让数据的二进制位数变得最小。
这里的目标就是高效地将大量的数据压缩为最少的二进制位数，这里需要权衡取舍的是成本和效率（也就是计算资源的价格）；
客户端压缩，客户端解压
还有很多客户端应用程序相互之间需要通信，它们之间可能会相互发送对等网络包、图片或者GPS信息这样的内容；
在这些情况下，客户端会生成数据并压缩它，然后再发送给其他客户端去解压。这里的难点是，客户端通常是移动设备，没有优化转换和压缩数据所需要的大量资源。然而，这些设备通常会有专用的图形硬件，因此可以用来压缩像JPG和H.264这样格式的文件，也就是可以用来处理图片和视频。至于其他类型的数据，因为只有这样的硬件配置，所以数据压缩的质量会比较低（没有什么时间去优化），同时解压缩的过程也会比较慢（移动设备的电量有限）。因此，处理客户端之间互相通信的算法通常选择固定二进制位率的压缩，例如手动打包序列化结构而不是对它进行压缩。
如此一来，这里就不存在取舍，相反，这里更多的是需要权衡设备的功能、压缩和解压需要的时间以及需要数据的迫切性
11.2 数据压缩的需求
作为开发人员，为每种类型的数据匹配正确的算法，对最大限度地压缩数据至关重要，当然在这中间需要做出一些权衡取舍。永远不会有银弹，做出正确的选择需要我们：
- 了解要处理的数据——要了解的不仅是数据的类型，还要了解它的内部结构，特别是它的使用方式；•了解算法的各项指标，这样才能从中选出正确的算法系列;
- 最重要的是，了解在给定的情况下你需要的是什么，因为有些算法能节省特别多的空间。
比如，与全屏显示的图片相比，缩略图对图片质量的要求就会比较低。因此，缩略图可以使用有损的JPEG编码压缩，而对质量有更高要求的图片则应该使用无损的WebP编解码器编码；
11.3 压缩率
压缩率，也就是内容压缩后的大小与压缩前大小之比，通常是评价压缩效果时最重要的指标；
当性能或者内存更重要的时候，你可能愿意接受压缩节省的空间变小；当然，对那些在线下或者云端进行压缩的服务来说，压缩率就是最重要的考虑因素之一，这里我们有资源、有时间将数据压缩得最小，同时这样做还能减少传输数据所需的费用。
11.4 压缩性能
压缩性能，指的是将数据转换为压缩后的形式需要多长时间。在对网络延迟要求很高的情况下，无论是客户端负责数据压缩还是客户端在等待服务器正在压缩的数据，压缩性能都至关重要。
在这个方面通常有两个评价指标：CPU速度和内存。编码系统的CPU速度之所以重要，是因为它决定了数据可以压缩得多快。而可用内存的数量之所以重要，是因为它十分有限，特别是对移动设备来说。
11.5 解压性能
对所有重点关注性能的环境来说，解压速度的重要性超过其他所有指标。在现代应用程序的开发中，解压通常是在客户端设备中进行，与服务器端相比，客户端通常存在能量不足的问题。那些能将文件压缩得最小的算法，通常也需要花最长的时间去解压，因此对需要将数据传输到移动设备上处理的应用程序来说，这些算法并不适用。
因此，有时我们必须做出取舍：选择压缩算法主要是根据该算法的解压性能而不是压缩后文件的大小。例如，ZPAQ可以说是一种非常高效的压缩算法，它使用神经网络作为编解码器，因此解压时需要运行大量的资源。这样的资源需求使得它注定与只拥有较少的CPU和电池资源的移动设备无缘。
实际上，GZIP之所以成为当前世界上使用较多的通用文档压缩算法，解码性能是其中最主要的原因之一。GZIP算法生成的压缩文件大小合适且解压速度很快，这使得它适用于各种类型的嵌入式设备和非嵌入式设备。从诞生到现在的20多年里，GZIP算法一直在改进，其解压性能不断提高到新水平。
11.6 解码流的能力
数据流通常是解压时容易被忽略的一个方面。我们通常认为解压算法处理的是“完整的数据包”，也就是说解码前所有的数据都必须在内存中。
然而这样的想法远非事实。想象一下，一次去听一部歌剧或者观看Kenneth Branagh的《哈姆雷特》，通常你会认为这样做一下子接受的内容太多了，最好能一次只听一两个章节或只看一两幕。幸运的是，一些通用压缩算法如GZIP、BZIP2以及大多数多媒体压缩算法像H.264能在流模式下工作。数据以分块的形式发送到客户端，一到客户端就开始解码（即分块解码）。对许多客户端应用程序来说，这种能力正是它们需要的。想象一下，一位用户想要从头浏览某个社交视频流，而在他能解码“我终于在巨石阵趴街了”这一内容前，必须要先去下载过去10年里“今天早晨我准备吃什么”这样的内容，这真是令人难以接受。
11.7 比较压缩算法
前面提到的大文本压缩基准测试会定期比较各种算法压缩1GB文本数据时的各方面表现。Squash压缩基准测试则会测试各种算法在压缩XML、文本、图像以及其他数据格式时的表现。此外Squeeze Chart则会比较算法在压缩各种文本、音频以及位图时的表现。
总之一句话，不同的算法和不同的设置，都会影响到开发的应用程序的压缩质量。在任何情况下，你都需要根据当前的条件和目标，试着对候选的算法进行测试，从而挑出最适合的那一个。
魏斯曼教授设计了一种度量数据压缩性能的方法，用数据集的压缩率除以其编码速度作为衡量标准。其目的是通过已知的现有编码器（如GZIP），归一化新压缩算法的压缩率与其编码速度之商，来测试新算法的性能。通过归一化，我们就有了将某个算法与通用标准压缩工具相比较的能力，这有助于评估对于某种数据类型，哪个算法最合适。制片人以它的提出者为这种新的度量标准命名，称之为魏斯曼评分（Weissman Score），但目前还没人使用这一评分；
第十二章 压缩图像数据
图像压缩是一个非常棘手的问题，包含在压缩工具中的每个有损压缩算法都很复杂（最乐观地看），还是不要接触的好。不过也不要放弃希望，虽然这些压缩工具大多数情况下被当作黑盒系统，你的开发团队仍然可以做很多事情来影响图像内容的大小，使它变得更小；
12.1 图片质量与文件大小
通常来说，图像压缩工具会提供一个整数参数，让你来决定图像的质量；随着这个值变小，图像的大小也会变小，当然质量也会变差。
更差的质量就意味着有更多的颜色被丢弃，或者是有更多的边缘信息被忽略，所有这些都是为随后的统计编码阶段生成更多的重复符号；
选定这样一个值，可以说是一项重大的、关键的、耗时的决定。如果这个值选得过小，就会造成图像伪影，用户也可能抱怨图像质量差；如果这个值选得过大，那么发送的图像就比需要的大得多，相应的费用也会增加不少
对正常的JPEG图片来说，当压缩级别在75~100时，只会出现非常小的、几乎不可见的“明显”质量变化，但文件大小之间的差别比较大。这意味着当质量值为75时对普通用户来说很多图片看着挺好，但是其文件大小只有质量值为95时的一半。当质量值低于75时，图片看起来就变差很多，并且节省的空间也在逐渐递减；
什么降低了图像质量
在看图像时，人类的眼睛对很多事物很敏感，其中包括边缘和渐变；任何时候，当两个已知值之间的边缘出错，或者出现了与大脑认为的平滑颜色不一致的搭配，都会很容易察觉；
量化（quantization）和区块化（blocking）是导致图像压缩出现视觉问题的最常见的两种形式。大多数图像压缩算法将图像数据先切分为像素块，然后再量化，以减少图像中不同的颜色数量，再在此基础上基于图像的局部性进行修改。
例如，JPG会将图像的像素切分为8×8的小块，然后试着找出与此区域相似的颜色。这种方法之所以可行，是因为图像数据局部区域之间存在关联。也就是说，在一幅真正随机的图像中，两个相邻的像素之间并不会存在相关性；然而在一张照片中，两个相邻的像素之间往往是渐变的，颜色相似。这种区块化过程造成的结果是，相邻区块之间的颜色可能不太相同，区块之间的边缘因此也就变得很明显，如图所示：
度量图像质量
人们通常使用相互之间有些竞争的两个指标来评价图像数据：峰值信噪比（peak signal-to-noise ratio，PSNR）和结构相似性（structural similarity index，SSIM）；
PSNR通常表示一个信号的最大可能功率与影响它的表示精度的破坏性噪声功率的比值(以对数分贝为单位）。这一度量的基础是压缩图片的均方误差（mean-square error，MSE），换句话说，原始图像的值与压缩后的值差别有多大。PSNR与MSE之间，存在着反比关系。当误差的数量较少时，图片的质量就比较高(PSNR同样如此），反之亦然。这里唯一需要注意的是，如果你试着去计算两张一样的图像的均方误差值，其结果会为0，那么对应的PSNR会是未定义的（除以0）。
SSIM这个概念的提出就是为了解决PSNR的问题，在比较图像的压缩质量时考虑了人眼的感知情况。它是通过比较源图像与压缩后图像的边缘相似性来实现的。SSIM看上去是一个更好的质量度量标准，但是其计算也更复杂。
SSIM取值范围为[0,1]，当其取值为1时表示的是压缩后的图像与源图像完全相同，而取值为0则表示压缩后的图像与源图像完全不同。
12.2 图像的尺寸
更小的屏幕会使用更小的物理像素显示图像，因为它拥有的物理像素就少，那么应该在什么地方调整大小呢？
将全分辨率的图像发送到设备上，在渲染前再调整大小，对开发人员来说，这样做肯定最省事，但缺点也很明显，我们将用户不需要（也不会看）的数据发给了他们。这样做，其实是把钱往水里扔，还听不到一个响
更好的方法是直接在云端调整图像的大小，或者在某处缓存调整大小后的图像，这样就能向小屏幕发送小尺寸的图像。这并非遥不可及。很有可能，我们已经有了同一幅图像的不同分辨率的多个版本（见图12-5）：低分辨率的缩略图、高分辨率的全屏版本，也许还有介于两者之间的预览版本。
发送合适大小的图像给用户有以下好处。
- 发送的数据量更少了，这会更快，也会节省用户的套餐费用。
- 可以节省用户的设备空间。
- 无须再调整图像的大小。（是的，我们知道 GPU可以帮我们去做这件事，但是如果要在 GPU中处理 4 MB大小的图像，而渲染的时候只是缩略图，是不是很浪费资源？）
- 解码会更快，加载会更快，显示也会更快……你都明白了吧。
12.3 正确的图像格式
PNG
便携式网络图像格式（Portable Network Graphics format，PNG），是一种无损图像格式，它使用GZIP这样的压缩工具使数据量变小。由于是一种无损的图像格式，因此压缩后的图像质量与源图像相同。这正是它的优点，既能保证图像的高质量又能压缩数据量，当然压缩的程度不像有损压缩那么大；
PNG格式最吸引人的地方在于它对透明度的支持。除了红、绿和蓝这3种颜色通道外，它还支持alpha通道，可以定义渲染时哪些像素是透明混合的。
事实上，PNG格式的这种无损性质是一把双刃剑。从图像质量的角度来看，相对源图像我们可以获得完美的像素结果，但是从文件大小的角度来看，复杂的图像不会包含很多颜色相似的像素，因此压缩就会不太理想。如果真的需要使用PNG格式，比如Android应用程序打包或是网页上需要使用透明的图像这样的场景，我们可以在图像保存为PNG格式之前，进行一些有损的预处理，来提高图像的压缩率。
JPG
JPG是一种用于摄影图像的格式，它不支持alpha透明度。它包含一个功能强大的有损压缩工具，我们可以通过一个质量值来控制它，以达成对文件大小与图像质量的权衡取舍。
JPG这种压缩格式的基础是分块编码。如图12-6所示，一幅图像会被分成8×8的小块，然后在每块上应用各种不同的变换，再将变换之后的小块组合起来交给统计编码算法处理。
GIF
GIF是另外一种支持透明度的格式，此外它还支持动画（这也是cats on the internet thing的直接原因）。GIF格式文件的生成包含两个压缩步骤，第一步是有损的色彩数量压缩，将整个图像的颜色数量减少到只有256种，第二步则是无损的LZW压缩。将图像颜色的数量减少到256种会极大地降低图像的质量，而好处则是文件压缩得更小，这也会使LZW算法的压缩效果更好。网站对GIF有很好的支持，然而在本地平台上它没有得到统一的支持。
WebP
WebP格式为用户提供了介于PNG和JPG之间的中间地带。WebP既支持无损模式和透明度，同时也支持有损模式。总的来说，你可以从JPG和PNG各自的优点之间进行选择。虽然听起来好像WebP就是最好的图像格式，但是它也存在一些问题，最主要的是，浏览器不是100% 支持它。同时，在开发移动应用程序时，为了使用它还需要包含相应的库(安卓平台除外，因为它本身就支持WebP）。除此之外，在有损压缩模式下的高压缩率，也就意味着在解压时它要比JPG或者PNG格式慢一些。
12.4 GPU纹理格式
计算机不能直接利用压缩格式的数据绘制图像，而是需要先将压缩的数据加载到内存中，然后再解压为系统可以直接渲染的格式。默认情况下，图像会被解压为每像素32位的格式，其中红绿蓝三种颜色通道以及alpha通道都是8位（也就是RGBA_8888这种表现形式）。然后，图像会被当作纹理传输到GPU中，也就是说你生成的每一个位图都会同时需要CPU和GPU内存。结果就是，不论图像在网络上的压缩质量如何，当在设备上显示时，它就会占用大量的内存。好消息是，GPU能直接渲染的像素压缩格式是存在的，因此你可以利用这一点，将从网络中传输过来的数据解压为这些压缩格式之一，这样GPU就可以直接渲染，而无须解压这一步骤
12.5 矢量格式
通常来说，图像是通过二维网格中的像素来显示的，这些像素表示的是图像本身的颜色。当从远处观察图像时，像素之间的边缘就会消失，这样人的眼睛（被欺骗了）看到的就是平滑的颜色渐变。这种类型的图像通常被称为光栅格式图像（raster format image），它可以(比较直接地）在屏幕上渲染。
同一幅图像的光栅格式表示和矢量格式表示，从中可以看出取舍很明显。
矢量格式有一些很有趣的优点。例如，对某些类型的复杂图像来说，比如主要是由线组成的技术图纸，列出其中的点并描述如何连接这些点就要比传输每个像素有效得多。（这也是一种形式的压缩。）此外，矢量图像能精确地放大缩小，当需要在不同的设备上显示同一图像的缩略图、图标和全屏形式时，这一性质相当有用。当然，付出的代价就是加载的时间。因为需要通过执行指令来为GPU生成光栅化的图像，所以，这一格式就是在用客户端的速度换文件的大小。虽然它可以使需要传输的数据变小，但在渲染时由于需要重新生成图像，因而加大客户端的时间开销。
总的来说，矢量格式适用于标志、技术图纸以及简单的图像样式，而光栅格式则适用于相片以及其他信息密集的图像。
第十三章 序列化数据
序列化就是将高级数据对象转化为二进制字符串的过程（与之相反的过程则称为反序列化）；这一转换可以应用到很多不同的数据类型上，但用它来描述将内存中的结构体或者类转化为能通过网络传输的文件或者内存二进制大对象的过程是最准确的；
虽然从文件大小上来看图像是数据压缩的主要对象，但是序列化内容被压缩的次数要更多。
这就意味着，压缩的性能对序列化速度、反序列化速度，以及需要发送给数百万用户的结果文件大小来说至关重要。为了让你有更多的了解，下面来看看两种最常见的序列化文件格式XML和JSON，并讨论一些能让这些文件变得更小的技术；
13.1 使用场景
服务器动态生成的数据
客户端通常会向服务器发出查询请求，可能请求的是数据库操作的结果，服务器计算出结果，将其内容序列化后再发送给客户端，由客户端进行反序列化。在这个过程中，HTTP协议栈通常会对序列化数据进行进一步的压缩（例如使用GZIP），从而使文件变得更小。考虑到节省的空间相当可观，因此客户端付出的解压时间开销是值得的。
服务器拥有的静态数据
虽然动态生成的数据很常见，但是应用程序同样也有静态的序列化内容，例如，向客户端发送最新的配置文件。开发者会在服务器上不定期地更新这些文件，而且通常是离线进行的。这样，服务器就可以认为这些文件是静态的，并在客户端请求时将其发送过去。同样，这些文件也会被HTTP协议栈进一步压缩。
客户端动态生成的数据
在很多情况下，客户端也会向服务器发送信息，其中就有客户端本身生成序列化信息的情形。这就意味着序列化操作以及数据压缩过程的所有开销都完全由客户端设备来承担。对便携式计算机或台式计算机来说，这可能不是问题，但对移动电话、平板计算机和可穿戴设备来说，久而久之可能就会造成大麻烦。此外，由于这些设备往往电量有限，因此一般不倾向于将客户端的资源花在要上传的数据的压缩上。这就形成了一种独特的平衡行为，即开发人员需要解决他的应用程序面临的此类问题。
客户端拥有的静态数据
最后，还有一类存储在本地且客户端一直在使用的数据，例如，布局信息就是一次编写然后被多次加载，而且也没有什么变化。这样的信息很容易压缩，而且通常是在应用程序的构造期间，此时有额外的电源可用。客户端唯一需要做的，就是保持数据驻留（或者永久地存储起来）并在需要时将其加载到内存中。
13.2 序列化格式
两种最常见的序列化格式就是JSON和XML；
JSON和XML这两种格式最吸引人的地方在于，它们（或多或少）是可读的。也就是说，如果用文本编辑器打开序列化后的文件，就可以读取全部内容，如下随机选取的JSON代码片段所示。
它通过将文件表示为一组字符串值，并用标记拼凑在一起，来定义事物是如何关联的。
优点在于格式十分灵活（绝大多数数据结构可以找到序列化为这种格式的方法），但缺点也很明显，为了保证可读性，其中包含了大量的冗余信息。其中包含了大量的空格、换行符和双引号。因此，需要编码的文件比实际需要的要大。当有数值时，这个问题更严重。例如，如果序列化的文件中含有“3.141592653589793”这个值，那它会至少需要17个字节（由于编码格式的不同，因此占用的字节数可能会更多）。考虑到用浮点数来表示这个值只需要8个字节（或者64个二进制位），这是很大的浪费：人类可读的表示方法需要的空间比二进制方法的两倍还多。
需要注意的是，这样的文本格式在解码时常常会需要很长时间。其原因是多方面的：一是字符串的输入必须经过强力操作才能转化为内存对象（例如将ASCII符号转换为整数就不那么容易）；二是在加载期间将数据保存在临时内存里并非总是高效的；三是对旧格式的兼容也会使得编码和解码变慢。由此带来的另外的问题是，像XML和JSON这样的格式都倾向于有较长的加载时间，以便客户端能正确地反序列化。事实上，存在不少XML和JSON编码器专注于减少特定组织的文件类型的加载时间。
13.3 更小的序列化数据
① 使用二进制序列化格式
最简单有效的方法就是将XML和JSON格式扔到一边，找出一种二进制序列化格式来代替它们。虽然二进制格式不再具备XML和JSON的可读性，但是能保证数据用紧凑和高效的二进制形式编码。这样，文件就会变小，加载速度也会变快。
像BSON和MSGPACK这些格式虽然保留了JSON的模式，但在编码时能提供二进制的大小。这可以让你得到更小的文件，而无须改动大量的代码。
这些二进制格式的真正优点在于，与人类可读格式相比，它们可以产生更好的压缩效果，并且在某些情况下，实际上还可以使用通用编码工具如GZIP对它进行进一步压缩。
② 重构列表以获得更好的压缩
下面这点很有意思：当你对数据进行序列化时，其实大多数时间，你所做的只是将数据内容映射为内存对象形式。我们来看看下面这段代码，想想左边的结构体是怎样序列化为右边的JSON代码的。
首先，由于JSON对象（可以随便选一个观察一分钟）是由键值对组成的，由于该结构体的每个实例中都包含相同的属性，因此对整个文件来说包含大量的冗余信息。在下面这个包含人名及国籍的列表中，对每个人都必须重复“name”和“country”这两个关键字。
像GZIP这样的编码工具在最初的转换步骤中使用的是LZ算法，这就意味着如果能在搜索窗口中发现重复的数据模式的话，LZ算法就能充分发挥作用；
只需要简单地对列表内容重新排序，你就能解决属性的重复和相似属性值之间的距离这两个问题。如下面的示例所示，你可以将前面的数组结构[插图]（array structure）转换为某个给定属性的所有值都包含在一个数组中，并紧密地放在一起。
组织数据以便高效获取
客户端对需要显示的数据掌握的信息越多，效率就越高。应用程序决定缓存或者删除哪些数据，例如，怎样在新数据达到时使布局无效。移动客户端要比简单的HTML渲染器更强大，你完全可以将比较好的结构化数据交给它来处理。
第十四章 有损压缩算法
有损压缩工具通常会被首先应用，以减少数据的动态变化范围，从而为进一步的无损压缩做准备。
必须要清楚：有损压缩工具其实有无限多种，选择哪一种取决于需要处理的数据类型、你的需求以及用户愿意容忍多大范围的失真。
实际上，它才是数据压缩领域内最富饶的土地，因而能做的事情还有很多。
作者在另一本书中会详细讲有损压缩；
第十五章 数据压缩与生活
当涉及你以及你的公司时，通常是钱的问题。数据压缩与公司的盈利是如此紧密地交织在一起，以至于拥有这方面技术的公司能节省如下费用：
- 用户获取与保持
- 运行成本
- 提前规划
用户获取与保持
统计数据显示，如果移动页面加载超过4秒钟，那么平均每4个用户中就会有一个用户放弃浏览该页面。这样的测试也值得你的网页去做，因为这意味着仅仅从网页加载方面就能对公司的盈利产生巨大的影响。如果你需要更具说服力的证据，可以看看下面这些真实的故事。
亚马逊的数据显示，网页的加载速度每慢 100毫秒，其收入就会下降 1%。或者，换一个角度来看，对像亚马逊这样的商业巨头来说，如果网页加载速度慢了 1秒，其收入就会减少 16亿美元。反过来看就是，亚马逊的网页加载速度每快 100毫秒，其收入就会增加 1%。
沃尔玛的最新报告显示，其页面加载速度每加快 1秒，它的客户转化率就增加 2%。网页加载速度每提升 100毫秒，公司的收入就会增加 1%。
运行成本
网站上的大量内容必须存储在某个地方，通常来说其实就是云服务器上大量的硬盘。硬盘要花钱，向云端传输和下载数据也要花钱，租用（或建立并运营）数据中心和带宽还是要花钱。即使云技术已经标准化且其费用在大幅下降，带宽和存储仍然是大公司面临的重要财务挑战。
同样在2015年，Facebook公布了其提供图像预览服务的细节，每幅图像的预览只有200字节。考虑到社交媒体网络每天传输的图像的数量，这对他们来说是一个很大的成功，特别是对使用2G设备的用户来说；
提前规划
网页之所以一直在变大，其中一个原因是它们包含的图像越来越多，同时每幅图像也变得越来越大。此外，由于网页变得越来越复杂，因此网页中包含的代码也越来越多。对2G用户来说，这一问题正变得越来越突出。为了解决这一问题，谷歌这样的大公司推出了移动页面加速（Accelerated MobilePages，AMP）这一全新的框架，专门用来减小站点加载时依赖的图形、图像文件的大小，在带宽有限的情况下为用户提供更精简、加载速度更快的内容。
移动设备已成为现代生活中很重要的一部分。想到用户的体验是如此严重地依赖于商品目录的图像是以多快的速度从服务器端传输到用户端，真让人感慨。
当我们试图降低出站流量的成本时，用户也在想着降低入站流量的成本。我们必须清楚：一切都是需要用户支付费用的。他们中的大多数人要为数据付费，以兆字节为单位，并且付费惊人。
我们不仅要考虑金钱成本，还要考虑电池的开销。连接速度较慢的用户在下载同样的内容时需要的时间也较长，这就意味着使用电池的时间也要比连接速度快的用户长。结果就是，连接较慢时，用户消耗电池电量的速度变快了。
数据压缩与这两个问题都直接相关。在连接速度同样慢的情况下，文件越小就意味着下载需要的时间会越短，消耗的电量也会越少。最终的结果就是，用户能快速看到商品的图像。
下一步技术
过去10年移动计算技术的快速发展告诉我们，下一个10亿用户将第一次主要是通过移动电话，而不是台式计算机或便携式计算机接入网络。
在非洲已有超过6.5亿的手机用户，而在亚洲手机用户的数量已接近30亿。他们中大多数人使用的是只有基本功能——电话和短信——的手机，这主要因为他们所在国家的数据服务费用十分昂贵，即使是那些买得起具有网络功能的手机或智能手机的人，也负担不起数据服务的费用。这种状况将来肯定会改变，一旦这种改变发生，这些人就会深深受益于智能手机革命。
简而言之，移动网络的速度仍然会继续提高，尽管提高的速度会比较慢，在各地也不均衡，而且花费巨大。如果你期待移动网络突然变得更快，很可能就需要找一把舒适的椅子慢慢坐着等待。例如，2G网络的传输速度大约为0.021 MB/s，而GZIP的压缩速度则可达61 MB/s，即使GZIP的压缩速度降为原来的十分之一，压缩1 MB的速度仍然比通过网络传输要快。本书作者柯尔特对这些数据的分析表明，与投入数百万美元升级网络硬件相比，投资更好的压缩解压编解码器要划算得多。
作为开发人员，你既不能真正控制网络，也不能控制硬件。你唯一能控制的只有数据，你可以做大量工作，以确保数据被压缩得很小，这样它们就能以较高的质量、较快的速度传输给用户，从而让用户获得正常的计算体验，并且一直是你的应用程序的忠实用户。
