上下文数据转换

上下文数据转换（contextual transform）类似字典变换，对符号集进行某种方式变换使其更易压缩

行程编码（RLE）

行程编码（run-length encoding，RLE）主要针对的是连续出现的相同符号聚类的现象，它会用包含符号值及其重复出现次数的元组，来替换某个符号一段连续的“行程”（run）。

短行程问题

根据现有的计算机科学课程及维基百科，RLE 通常不会用上面这样成对的记号来表示，而是将 A4B1C4 这样的符号值及其长度放在一起来表示。然而，由于符号与数值会交替出现，因此实际上没有人会使用这种形式的 RLE，介绍这种形式纯属浪费时间。

【解决方式】
辨别出那些用 RLE 算法编码后反而变大的符号，对这类符号，可能需要将它们单独留在数据流中。例如，可以只对那些行程长度大于 2 的符号编码。

但这样解码时可能出现歧义，需要有一种方法来区分哪些字符编码后是二元组哪些字符不是——>行程控制位流

压缩

压缩 RLE 算法输出的结果需要一些技巧。首先，需要将数据集分成两部分：字面值流和行程长度流。

• 对于字面值流，可按情况选择编码器

应用 LZ 算法很有趣，因为这样就可以看到符号行程重复的频率。

• 对行程长度流，采用统计编码或自适应统计编码可能得到较好的结果。

有时将 RLE 中的长度当成一种增量编码值是有帮助的。如果我们从绝对值的角度理解每个行程的开始，那么长度值表示的是数据流中符号变化之间的距离。

RLE 在现代压缩工具中用得并不多，但还是有人在研究更高效的 RLE。

增量编码

从压缩角度来说，数值型数据算是最令人讨厌的数据类型之一，这是因为大多数时候，我们找不到可以利用的统计信息。

• 增量编码，其实就是将一组数据转换为各个相邻数据之间的相对差值（即增量）的过程。增量编码提供了一种不依靠统计的转换。它依靠的是相邻性，所以最适用于处理时间序列数据（比如每 10 秒检测一次温度的传感器所产生的数据），以及音频和图像数据这类多媒体数据，因为这类数据中邻近的数据之间存在着时间上的关联。
• 增量编码的目的就是缩小数据集的变化范围
  如数组 [1,3,6,8,10] 增量编码后为 [1,2,3,2,2]
  但对某些数据集有增益，对某些数据集也会有负增益如 [1,3,10,8,6]——>[1,2,7,–2,–2]

改进增量编码

XOR增量编码

使用按位异或运算（bitwise exclusive OR，XOR）代替减法运算绕开了负数出现的问题。

参照系增量编码

“参照系”（frame of reference，FOR）中那个“参照数”（frame）的选取，与将转换恰当地应用到数据集上有关，需要将数据集细分为更小的数据组。

• 例如编码[107,108,110,115,120,125,132,132,131,135]
  拆分得到 [107,108,110,115,120] 和 [125,132,132,131,135] ，使用参照系增量编码处理之后，得到：[107,0,1,3,8,13] 和 [125,0,7,7,6,10]
  相比原始增量编码得到的 [0,1,3,8,13,18,25,25,24,28]，数值的变化范围缩小了
• 遗憾的是，离群值还是可能造成很多问题。（比如 [1,2,10,256] 中的 256）

修正的参照系增量编码（PFOR）

Zukowski 等人针对离群值问题提出了一种补救的方法，称为修正的参照系增量编码（Patched Frame of Reference Delta Coding，PFOR）。
【工作原理】

1. 选择一个位宽度 $b$。
2. 遍历数据并用 $b$ 位对每个值编码。
3. 当遇到的值所需的编码位数大于 $b$ 时，将这样的离群值存储在单独的位置。

如 [1,1,8,246] ——>[1,1,8][246][3]

【主要问题&解决方式】

• 如何选择 $b$？
  目标即选择一个合适的 $b$ 值，使大多数值在编码时需要的位数不超过 $b$，并且可以通过它识别出那些离群值。通常可以逐步做到这一点。可以从 $b=1$ 开始试验，看看数据集中有多少数小于 $2^1$ ，如果数据集中 90% 的数小于 2，那么就将 $b$ 设置为 1。否则，令 $b$ 的值为 2，以此类推。

• 如何处理离群值？

  • 离群值数据集变化范围很大，通常很难直接压缩
  • 原始论文 Super-Scalar RAM-CPU Cache Compression 的叙述中，PFOR 没有将整个的离群值原样扔进一个新的列表中，而是将最低的 $b$ 位留在源数据流中，并将剩下的部分存储在离群值列表中。
  • 例如考虑数组 [101 0010, 000 1010, 000 1100, 000 1011]，一眼能看出只有第一个值才是需要关注的离群值。结果是得到了如下的三组新数据：
    • 原始数据的最低 4 位：[0010,1010,1100,1011]
    • 离群值所在的位置：[0]
    • 离群值的实际异常位:：[101]

压缩增量编码后的数据

如果增量编码能做到以下两点，那么我们就可以认为它生成的数据更容易压缩：
• 将数据集中的最大值变小，因此缩小了数值的变化范围
• 生成了许多重复值，可以让统计压缩的效率更高

对于文本数据，增量压缩得到的数据中会出现很多正负数交替的情况。另外，对于英语文本，像 LZ 这样的算法可能会做得更好。

前移编码（MTF）

前移编码（move-to-front coding，MTF）利用数据的排列次序中包含着一些有助于编码未来符号的信息，但与 RLE 和字典编码器 只考虑直接相邻的符号不同，MTF 考虑更多的是在较短的窗口内某个特定符号很有可能会出现多次，或者至少短时间内会成为常见的符号。

工作流程

【例】假定数据中的符号都是小写的 ASCII 字符，输入字符串为 banana，初始状态下 SortedArray 中的字符是按字母顺序排列的。

1. 读取字母 b。
2. b 在 SortedArray 中的索引为 1，因此将 1 写入输出流。
3. 将 b 移动到 SortedArray 的最前面。
4. 读取字母 a，由于其现在的索引为 1，因此输出 1，同时将 a 重新移到最前面。
5. 对其余的字母，按照顺序重复上面的过程，具体如下表所示。

消除捣乱符号的影响

MTF 存在的一个问题是，有一些偶尔出现的捣乱符号会打乱前面存在的符号流。

【解决方法】

• 向前移动 $k$个位置
  采用这种方法，那么与当前符号匹配的元素就不再是直接移到 SortedArray 的最前面，而是将它前移 $k$ 个位置。通常选取 $k=1$

  关于直接移动到开头还是前移一位，可详见@ 列表模型对该问题的数学讨论

• 出现 $c$ 次再移动
  SortedArray 中的元素只有在输入流中出现过 c 次之后（并非必须连续出现），才会移动到最前面。SortedArray 中的每个元素都有一个计数器，记录该元素出现的次数。

压缩 MTF

MTF 生成的输出流中有很多的 0 和 1，因此简单的统计编码算法就可以工作得很好。

伯罗斯-惠勒编码（BWT）

BWT 的工作原理并非如统计压缩（即 VLC）和字典压缩（如 LZ78）。相反，它通过打乱数据流次序来让重复的子串聚集在一起。这一操作本身不能压缩数据，却可以为后续的压缩系统提供转换好的数据流，方便压缩。

工作原理

• 通过转换数据流中符号之间的顺序，可以让数据流更容易压缩。关键问题在于，通过较少的额外信息便能在编解码时排序与还原。
• BWT 最引人注目的特点并不在于它能生成更易压缩的输出（普通排序也能做到这一点），而在于只需要极小的数据开销，它所进行的变换操作就是可逆的（reversible）。

变换流程

【例】编码输入流 BANANA

1. 创建一张表，其中包含输入流的所有移位排列。
2. 对表中每行按字典顺序排序
3. 输出最后一列字符组成的排列与原始字符串的索引，与源字符串相比，能更好地将相同的字符聚集起来

NNBAAA 与序号 3 就是字符串 BANANA 经 BWT 后输出的结果。

逆变换操作

1. 将输出字符串写入表中，即表示每一行的最后一个字符
2. 对这一列排序，其结果与原来的排序后表格的第一列相同（因为循环位移不改变符号集）

3. 将上述两列合并并排序
4. 将原始的输出字符串（NNBAAA）按顺序添加每行字符串的最前面（每行添加 1 个字符）

5. 再次对每行字符串按字典顺序按列排序，继续将原始字符串按顺序添加到每行字符串的最前面并按列排序，直到整个输出矩阵的宽度等于输出字符串的长度

6. 从矩阵中取出生成的索引号对应的行

最后的矩阵与在编码器中生成的排序后的置换矩阵完全相同，因此利用例子中 BWT 生成的索引号 3 便可恢复源输入字符串

压缩BWT后的数据

最常见的算法是将 BWT 的输出作为 MTF 的输入，经过处理后接着用统计编码算法处理。这基本上就是 BZIP2 的内部工作原理。

Q: 为何不用 RLE？
RLE 对干扰符号十分敏感，而 BWT不能生成足够长的连续行程以确保 RLE 始终处于理想状态。
Q: 为什么不使用 LZ 算法？
当字符串中出现较长的重复子串时，LZ 算法才工作得最好。比如 LZ 算法在 TOBEORNOTTOBE 字符串上工作的较好，但经 BWT 处理后为 OBTTTTTTOOEER，并不一定适合 LZ

© 2024 LiQ :) 由 Obsidian&Github 强力驱动