0%

[笔记] 数据压缩入门（Understanding Compression）

发表于 更新于

数据压缩入门

并非无趣的一章

适合游戏数据的压缩：

  1. 无损：去掉重复数据（lz）；熵压缩（Huffman，算术编码）
  2. 有损：降精度，图像视频压缩，音频压缩

Compressor Head - Youtube

5类压缩算法：变长编码，统计压缩，字典编码，上下文模型，多上下文模型

压缩数据的两个思路：

  1. 减少符号数量（字母表尽可能小）
  2. 用更少的位数对更常见的符号进行编码

The web back in 1996-1997

BWT是压缩dna信息最有效的格式

突破熵

Rosetta Code

一组符号的香农熵是表示一个符号最小的位数

通过利用真实数据的两个性质，很可能把数据压缩得比熵小

突破熵：改变数据的表示形式

增量编码

字典编码器

排列（无重复）通常很难压缩

通过消除编码法压缩排列

数据压缩的艺术，就在于将数据转换为熵值更小的新的表现形式

对压缩进行评价时熵不是一个好指标（除了统计压缩）

柯尔莫戈洛夫复杂度（Kolmogorov complexity），为了准确地生成数据，需要的生成程序的大小。如果生成程序很小，可以用它代替数据本身。逻辑综合（logic synthesis），程序综合（program synthesis）

VLC

给定一组符号，将最短的编码分配给最常见的符号

编码需满足前缀性质

整数转为VLC的方法称为通用编码（universal codes）。越小的数字编码越短。还有唯一可译码（uniquely decodable codes）与非奇异码（nonsingular codes）

一元码：编码N为N个1加1个0。

Elias Gamma编码：

  1. x= 2^N + L
  2. 用一元码编码N
  3. 用固定长度二进制码编码L

Elias delta

Elias omega

VLC的问题：

  1. 不按字节对齐
  2. 大整数的长度超过固定编码
  3. 按位解码慢

variant算法：Google用在LevelDB中的按字节vlc

避免压缩整数（escaping for compressed integers）

统计编码

通过数据集中符号出现的概率确定唯一的新的变长编码，有时被称为熵编码

哈夫曼编码，总是将码表放在数据流前面一起传输，避免解码时创建码表

TED: The math and magic of origami

哈夫曼编码的问题：单个符号的编码长度总是整数，当符号出现概率不是2的负整数幂时达不到最优

算术编码：将整个输入流转换为长度很长的数值

区间编码：绕开算术编码的专利限制

算术编码过程：

  1. 初始区间为[0, 1)
  2. 将当前区间按各符号概率进行分割
  3. 读入一个符号，选择对应的字区间，更新当前区间
  4. 重复

最终输出最后一个区间中任意一个数（二进制位数最少的）

ANS（asymmetric numeral systems）是新编码算法，压缩率和算术编码接近，性能和哈夫曼编码接近

The Use of Asymmetric Numeral Systems as an Accurate Replacement for Huffman Coding

  1. 创建转换表，每个符号一列，按概率自左向右排列
  2. 填入数值，满足：
    1. 唯一
    2. 每列升序
    3. 大于该行行号（从1开始）
    4. 每列值的个数满足乘以maxVal后等于该符号的出现概率
    5. 每个cell的值除以行号近似等于该符号的出现概率
  3. 实际使用时从maxVal开始

变种：有限状态熵（finite state entropy）

自适应统计编码

前一章的统计编码需要先遍历数据计算符号的概率，有两个问题：

  1. 不同部分的符号概率不同（局部偏态），数据量大的话偏差增大。
  2. 流数据没办法先遍历。

局部性很重要（locality matters）。

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

通常统计压缩的步骤：

  1. 遍历数据流并计算概率。
  2. 根据概率生成VLC。
  3. 再次遍历数据流真正压缩。

动态VLC编码：

  1. 读取符号。
  2. 输出对应码字。
  3. 更新符号的概率和码字。

解码：

  1. 读取码字。
  2. 输出符号。
  3. 更新符号的概率和码字。

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

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

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

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

自适应Huffman编码（参见Design and Analysis of Dynamic Huffman Codes）。

字典转换

统计压缩接受任何符号；字典转换接收的是符号集，并重新定义要使用的符号以减少生成的数据流的熵。

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

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

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

  1. 数据流前半部分新单词很多，后半部分匹配的概率大。
  2. 向前匹配可以找出最长的匹配词。

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

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

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

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

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

上下文数据转换

上下文转换：给定一组相邻的符号集，对其进行变换以易于压缩。

最重要的3种转换方法：

  1. 行程编码（run-length coding，RLE）
  2. 增量编码（delta coding）
  3. Burrows-Wheeler transform，BWT

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）：

  1. 选择位宽b
  2. 用b位对每个值编码
  3. 当遇到的值位数超过b时，将这个值单独存起来

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

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

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

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

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

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

  1. 向前K个位置。最常见的K为1。
  2. 出现C次再前移。

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

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

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

  1. 表中加入原始流。
  2. 依次将原始流向右rotate1位，加入表，直到操作完一轮。
  3. 按字典序排序表。
  4. 依次输出每行最后一个字符，即组成原始流的一种新排列，且通常有更好的聚集性。

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

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

恢复过程：

  1. 将NNBAAA排序为AAABNN。
  2. 与NNBAAA配对组合为NA/NA/BA/AB/AN/AN，再次排序
  3. 重复以上过程，直到每个子串长度达到6，此时原始流就在它的索引位置。

应用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（一种上下文混合算法）包含模型：

  1. n元语法（n-grams），指之前的n个字符。
  2. 整词n元语法（whole-word n-grams），忽略大小写和非字母字符。
  3. 稀疏上下文，由前面的8位或16位字节的高字节位组成（对多媒体文件很有用）。
  4. 二维上下文（对图像、表、电子表格很有用），行的长度由找出的重复字节模式的步长决定。
  5. 只针对特定文件类型的特殊模型。

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

  1. 线性混合（linear mixing），将各个模型的预测值加权平均。权重是静态的。
  2. 逻辑混合，使用神经网络来更新权重，缺点是内存占用大，运算复杂。

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

换个话题

大多数多媒体数据压缩都是有损压缩算法。

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

评价数据压缩

ZPAQ：文本压缩率高，但内存占用和运算量大。

LZMA：内存占用高。

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

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

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

压缩图像数据

大多数人分辨不出图片质量75和90的区别，前者文件大小只有后者的一半，适合作为默认上传值。75以下会影响体验。

量化（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。

序列化数据

二进制序列化格式相比JSON/XML等可读格式的真正优点是可以产生更好的压缩效果，有时后续还可以用GZIP等通用压缩算法进一步处理。

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

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

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