数据压缩（5）——上下文转换编码

统计压缩编码基于单个字符，字典编码基于单词；上下文变换基于具有联系的上下文，例如：

RLE编码针对重复字符：AAAABCCC可以记为[A,4]B[C,3]

增量编码针对数值型数据：通过一些运算以减少数值的变化范围，进而可以用更少的二进制位表示，例如：

• [1,3,6,8,10]用第二个数减去第一个数可以得到[1,2,3,2,2]
• [129,130,120,140,121]选择120为基数可以得到[9,10,0,20,1]

【MTF编码】

MTF（Move-To-Front Transfrom）编码，利用数据的空间局部性，也就是最近出现过的字符很可能在接下来的文本附近再次出现。

 对于许多连续的、相同的字符，将被替换为多个0；最近使用过的字符，会被小的index替换；最近很久没有使用过的字符，会被较大的index替换。

编码后文本就可以使用一串数字表示，随后可以再用RLE编码或增量编码

 如果ASCII表中各类字符大部分都在数据集中出现过，那么MTF编码的效果一般。

 MTF的关键在于用小的Index代替字符，移动字符有多种方式：

• 出现了就移动到开头
• 出现N次再移动到开头
• 出现了往前移动N个位置

具体的移动方式可以结合数据集的特征来选择

【BWT编码】

BWT（Burrows Wheeler Transform）编码提供了一种全新的编码思路，其通过打乱字符顺序使得重复的字串聚集在一起，为后续的压缩提供更好的数据流。

可以将BWT的输出作为MTF的输入，再用统计编码

编码

1. 依次将长度为N的字符串右移一位N次，得到N个不同的长度为N的字符串，以BANANA为例
2. 将N个字符串排序
3. 取最后一个字符由上而下组成的字符串为 NNBAAA,原字符串的索引为3（索引从0开始），编码输出为3 NNBAAA

  ///    BANANA   ABANAN
  ///    ABANAN   ANABAN
  ///    NABANA   ANANAB
  ///    ANABAN   BANANA
  ///    NANABA   NABANA
  ///    ANANAB   NANABA

解码

1. 不断的由上而下，从前往后插入输出并排序
2. 取索引为3的字符串 为BANANA

    /// N   A   NA  AB   NAB    ABA     NABA    ABAN    NABAN    ABANA    NABANA    ABANAN      
    /// N   A   NA  AN   NAN    ANA     NANA    ANAB    NANAB    ANABA    NANABA    ANABAN
    /// B   A   BA  AN   BAN    ANA     BANA    ANAN    BANAN    ANANA    BANANA    ANANAB
    /// A   B   AB  BA   ABA    BAN     ABAN    BANA    ABANA    BANAN    ABANAN    BANANA
    /// A   N   AN  NA   ANA    NAB     ANAB    NABA    ANABA    NABAN    ANABAN    NABANA
    /// A   N   AN  NA   ANA    NAN     ANAN    NANA    ANANA    NANAB    ANANAB    NANABA

注意，BWT需要N*N的空间，所以编码的数据集不能过大，对于大的数据集需要分块处理

【PPM编码】

马尔科夫链

上文的上下文编码的上下文关系都是必然的，而PPM（Prediction by Partial Matching，部分预测匹配）编码是基于马尔科夫链的概率联系，具有预测性质的编码。

在变长编码中，根据字符出现的概率分配码字，字符多但概率分布不均，会导致较长的码字；在自适应变长编码中，动态计算概率，动态分配码字，使得长码字出现的更少

基于马尔科夫链来算概率，字符的概率变得更高，使得长码字出现的更少。例如：

在ABACAB中，读取到ABACA时，在其他情况下，下一个出现B时在表中对应的概率0.2（这可以视为0阶马尔可夫链）；在1阶马尔可夫链下，下一个出现B时在表中的概率为0.5

更通俗的例子为：英文小写字母有26个，这是全部的状态值

情况A：在0阶马尔可夫链下，就是什么都不告诉你，给1张纸条，让你猜纸条上写的哪个字母，那么任何一个都可能，你只有1/26的概率猜对

情况B：在1阶马尔可夫链下，给你的第1张纸条上写的l,让你猜第2张纸条上写的是哪个字母，你可能仍然没头绪，你仍只有1/26的概率猜对

情况C：在4阶马尔可夫链下，依次给了你4张纸条，分别写着hell,让你猜第5张纸条上写的是哪个字母，你可能会猜o,你猜对的概率>1/26

情况D：在4阶马尔可夫链下，依次给你发了6张纸条，分别写着hellol,但你手里只能有4张纸条，he要去掉，剩下的是llol,让你猜第7张纸条上写的是哪个字母，那么你猜o的概率比情况B要大

也即在有上文的情况下，我们猜对下文的概率变大。反应在编码上，就是有上文时，下文出现时对应的概率变大，分配的码字变短。

这里N阶马尔可夫链就是N阶上下文，每多一阶，多取一个字符。对每个字符，都需要建立N个表，为了提高性能，通常要采用树结构。

编码

假设二阶上下文，对ABACAB编码：

1. 读取A，没有表,输出A，0阶表记录[A,1]，A的码字为0
2. 读取B，表中没有B，输出B；0阶表记录[A,1],[B,1],AB各出现依次1次，A和B的码字分别为0、1;A的1阶表记录[B,1],B的码字为0，结合之前的输出为A B
3. 读取A，0阶表中有A，输出0；0阶表记录[A,2],[B,1],概率A>B,A和B的码字分别为0、1;B的1阶表记录[A,1],码字为1；A的2阶表记录为[BA,1];,结合之前的输出为A B 0
4. 读取C，0阶表中没有C，输出C；0阶表记录[A,2],[B,1],[C,1],概率A>B=C,码字分别为0，10，11;A的1阶表记录[B,1],[C,1]，BC的码字分别为0、1;A的2阶表记录为[AC,1];A结合之前的输出为A B 0 C
5. 读取A，0阶表中有A，C的1阶表没有A，A的二阶表没有CA，输出0；0阶表记录[A,3],[B,1],[C,1]；C的1阶表记录[A,1];A的2阶表记录为[BA,1],[CA,1];A B 0 C 0
6. 读取B，0阶表中有B，A的1阶段表有B，C的2阶表没有AB，取A的1阶表，输出0；A B 0 C 0 0

解码

1. 读取A，输出A，0阶表记录[A,1]，码字为0
2. 读取B，输出B，0阶表记录[A,1][B,1]，码字分别为0，A的1阶表为[B,1]
3. 读取0，0阶表码字为0对应A，输出A;0阶表记录[A,2][B,1]；B的1阶表为[A,1];A的2阶表为[BA,1]
4. 读取C，输出C，0阶表记录[A,2][B,1][C,1];A的1阶表为[B,1][C,1]；B的2阶表为[AC,1]
5. 读取0，A没有2阶表为C？，C没有1阶表，取0阶表，为A，输出A；0阶表记录[A,3][B,1][C,1]；C的1阶表为[A,1];A的2阶表为[BA,1],[CA,1]
6. 读取0，C没有2阶表，A有1阶段表，且有码字0，对应B，输出B

综合输出为ABACAB

综合考虑，性能、内存、压缩率，一般将N的值设置为5或6

【PAQ编码】

上文的各类编码都基于这样的假设，数据的相邻性与它的最佳编码方式有关。

然而，数据可能和上下文多个地方相关，例如，当前字符可能上文间隔几个字符的地方相关，而不仅仅是邻近的；在图像上，当前像素可能和周围8个像素相关等。

PAQ（Prediction by Adaptive Quadratic estimation）编码利用更多的相关性都使得下一个字符出现的概率变高，码字变短，能获得更好的压缩效果。

PPM是对相关性建模的一种方式，可以进一步优化成自适应PPM，其对于当前字符，有特定的概率计算

我们可以对其他模式做建模，比如取当前字符连续N个间隔8个字符的字符等，根据这个模型，对于当前字符，也有特性的概率计算。

每多一个模型，就多一个概率计算。那么要去哪个模型的结果呢？

典型的如何从多个数据中取一个数据的问题：

可以最简单的独立取值

考虑的模型之前可能具有相关性，可以用最简单的线性混合，

更准确要用逻辑混合， 在逻辑混合中，人类可认知到的相关性是有限的，特定的，不能通用，这时候就需要神经网络来更新权重。

最后，开发应该关注到，增加模型会导致内存增大、性能降低。