局部性很重要（locality matters）。

最优方式分割数据流是NP完全问题，因此我们要做的是自动重置统计编码：如果期望的熵与实际编码位数出现显著差异，则重置概率表。

通常统计压缩的步骤：

动态VLC编码：

编解码过程中遇到第一次出现的符号时，使用一个特殊的LITERAL符号对应的码字，后面再跟着这个符号的原始编码。

初始概率表只有LITERAL，概率为100%。

监视平均位数，如果与熵值的差别超过阈值，表明数据模式发生了变化，需要重置。

自适应算术编码可以使用类似方法。

字典转换实际是一个数据流的预处理，之后数据流会更小，压缩率更高。之后还可以做统计编码。

字典转换的中心问题是分词。

LZ算法向前查找当前单词是否出现过，因此：

当前位置左边叫搜索缓冲区（search buffer），是已经处理过的符号；右边叫先行缓冲区（look ahead buffer）。

匹配过程类似于字符串查找的bm算法。

考虑到性能和局部性，需要有滑动窗口，search buffer通常有几万B，look ahead buffer通常只有几十B。

匹配完成后算法输出<offset, len>。或者<offset, len, C>，其中C是原始符号，表示匹配失败。

LZ将数据流转换为了记号流，之后可以继续使用统计编码，如把offset/len/C分成三组再分别编码。

最重要的3种转换方法：

RLE主要针对连续出现的相同符号聚类的现象。它会用包含符号值和重复次数的tuple替换单个符号连续的“行程”。编码就是找到一个符号，向前看看行程有多长。

1

AAAABCCCC -> [A,4][B,1][C,4]

B是短行程，因此直接输出字面值B。为了区分字面值后有没有次数，在整个输出流前面加上一个bitmap，长度为符号数，1表示有次数，0表示无次数。

一般来说数据流中交错出现字面值是会出问题的。

压缩时字面值和次数分开压缩，解码时根据bitmap选择。

通常认为RLE是单字符上下文模型。一种新的RLE：TurboRLE。

增量编码是将数据转换为delta的过程。

减法增量编码可能出现负数，影响效率。可以用XOR代替，保证没有负数，但不一定会缩小delta的范围。

参照系（frame of reference，FOR）增量编码，即找一个参照值，将所有值减去参照值，从而缩小范围。

为了处理离群值，使用修正的参照系增量编码（Patched Frame of Reference Delta Coding，PFOR）：

为了还原，需要存离群值的位置。可以将离群值的低b位留在原数据流中，只存储其余位，这样可以进一步压缩离群值。

编码后可以进一步用统计编码压缩。

前移编码（move-to-front coding，MTF）更多考虑在较短的窗口内某个特定符号的出现次数。

预期：每出现一个符号，短时间内它可能还会出现很多次。

MTF是局部自适应的。它维护一个SortedArray，保存所有出现过的符号。每遇到一个符号，输出它在Array中的索引，并将它移到Array最前面（索引0）。

为了避免离群符号打乱Array，可以：

MTF是最简单的动态统计转换形式之一。它会输出很多0和1，因此很适合配合统计编码或RLE。

BWT通过打乱数据流次序来让重复的子串聚集，从而利于后续压缩方法。

BWT需要维护一张表，保存输入流的所有移位排列，之后：

如BANANA转换为NNBAAA。另一个重要数据是原始流在排序后的索引值，如3。

BWT的优点是可逆，且开销极小。

恢复过程：

应用BWT时需要先对数据分块，如1MB。BWT压缩文本的性能不如gzip，但非常适合压缩DNA数据。

最常见的组合是BWT输出给MTF，再用统计编码。

不用RLE的原因是RLE对干扰敏感，而MTF不敏感。

可以认为统计编码算法就是一阶马尔可夫链。

通过为每个前面出现过的符号增加一张符号码字对应表，可以创建二阶马尔可夫链。

应用马尔可夫链编码和解码时，随着读取输入流，动态调整一阶和二阶表。可以组合之前的自适应编码方法。

实际不会用原始的马尔可夫链来压缩，一个问题是高阶马尔可夫表需要的内存和计算太多。

值得注意的衍生算法：部分匹配预测算法（prediction by partial matching，PPM）和上下文混合算法（context mixing）。

PPM的一种构造方法：使用trie记录原始串的所有子串和出现次数。之后依次为每个节点生成概率表。匹配时先按N阶上下文匹配，如果发现概率为0则用N-1阶重试。如果N减为0，则遇到了不认识的新子串，输出转义码。对转义码的不同处理产生了不同的PPM算法。

大多数PPM算法的N为5或6。

上下文混合算法，即为了找出给定符号的最佳编码，使用两个或更多的统计模型。

对数据压缩来说，相邻性很重要，LZ、RLE、Delta Encoding、BWT都是基于假设：数据的相邻性与最佳编码方式有关。

但相邻性和局部性都只是上下文的最简单方式，不是唯一的方式。

模型是用来识别和描述符号之间的关系。需要处理的数据类型不同，模型也会不同。

PAQ（一种上下文混合算法）包含模型：

将不同模型的输出结合的方法：

移动设备很难应用上下文混合算法。只有当数据量很大时它才能发挥作用。

通用压缩是用来处理除多媒体数据之外的数据的。

LZMA：内存占用高。

JPG、Ｈ.264在大多数客户端都有硬件支持。GZIP有专用芯片。

WebP的压缩率和图片质量都好于JPEG，但最初版本解码时间长，现在改善了。

GZIP流行的一个主要原因是大小合适，解码快。

量化（quantization）和区块化（blocking）是导致图像压缩出现视觉问题的最常见形式。

评价图像质量的指标：峰值信噪比（peak signal-to-noise ratio，PSNR）和结构相似性（structural similarity index，SSIM）。

PSNR计算的是去噪之后经过均方处理的原始值与压缩后的值的误差

SSIM考虑了人眼的感知情况，比较了源图像与压缩后图像的边缘相似性，计算更复杂。

PNG：无损（使用GZIP等算法），支持透明度、元数据块（对用户无用）。

JPEG：有损，不支持透明度，支持元数据块。有广泛的硬件支持。

GIF：有损，支持透明度、动画。第一步将图像颜色数降到256，第二步使用LZW无损压缩。

WebP：介于PNG和JPEG之间，支持有损或无损、透明度。

GPU可以直接渲染以下格式而无需解压：DXT、ETC、PVR。它们适合用于游戏中。

矢量格式：描述如何生成图像，能精准缩放，不适合高质量图像。SVG。

对于大的序列化文件，将结构的数组转换为数组的结构极为重要。

组织数据以便高效获取。服务端返回的数据不需要客户端重新组合。

将数据切分为适当的压缩形式。