(资料图片)

1.压缩算法可归为两类

1.1.统计压缩（即VLC）

1.2.字典压缩（如LZ78）

1.3.从不同的角度利用了给定数据流中存在的统计冗余信息

2.上下文变换

2.1.contextual transform

2.2.给定一组相邻的符号集，对它们进行某种方式的变换使其更容易压缩

3.行程编码

3.1.run-length encoding，RLE

3.2.过去40多年来看似很简单、实则很高效的编码技术

3.3.单字符上下文模型

3.3.1.对任何给定的符号，在编码时我们都只考虑它的前一个符号

3.3.1.1.如果这两个符号是相同的，那么行程继续

3.3.1.2.如果不相同，那么当前行程终止

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

3.5.将最短码字分配给最大的值（因为它表示的是最长的行程）

3.5.1.如果我们从绝对值的角度理解每个行程的开始，那么长度值表示的是数据流中符号变化之间的距离

3.6.最适用于大多数符号都连续重复出现的数据集

3.6.1.如果要处理的数据集没有这样的性质，那么RLE算法并不适用

3.6.2.会将最短的编码分配给那些连续重复出现的符号

3.7.示例

3.7.1.AAAABBBBBBBBCCCCCCCC

3.7.2.[A,4][B,8][C,8]

3.8.编码工作就是找到一个符号并向前扫描看看其行程有多长

3.9.解码工作则相反，给定某个符号值及其长度值的二元组，只需要将正确个数的符号添加到输出流之后就行了

3.10.短行程是RLE作为一种算法面临的大问题

3.10.1.存储短行程的开销极大地影响了数据压缩后的大小

3.11.数据流中交错出现字面值是会出问题的

3.11.1.在数据集中增加一个二进制位流，来表示某个给定的符号流中各个符号是否连续重复出现

3.12.对干扰符号十分敏感

4.从压缩角度来说，数值型数据算是最令人讨厌的数据类型之一

4.1.GPS的坐标信息

4.2.搜索引擎的倒排索引信息

4.3.返回的用户ID

4.4.因为大多数时候，我们找不到可以利用的统计信息

5.增量编码

5.1.delta coding

5.2.将一组数据转换为各个相邻数据之间的相对差值（即增量）的过程

5.3.思想

5.3.1.给定一组数据，相关的或相似的数据往往会集中在一起。如果这样，有了两个相邻值之间的差，就可以用其中一个值以及该差值来表示另外一个值

5.3.2.它依靠的是相邻性

5.4.在数值型数据这样普遍而其熵值又如此偏高的情况下，增量编码提供了一种不依靠统计的转换

5.5.目的就是缩小数据集的变化范围

5.5.1.为了减少表示数据集中的每个值所需要的二进制位数

5.5.2.当相邻数值之间的差相对较小时，增量编码最有效

5.5.3.如果差值变大，情况就会变糟

5.6.最适用于处理时间序列数据以及音频和图像数据这类多媒体数据

5.6.1.比如每10秒检测一次温度的传感器所产生的数据

5.6.2.这类数据中邻近的数据之间存在着时间上的关联

5.7.减法增量编码算法的问题是，结果中可能会出现负数，进而产生各种问题

5.7.1.负数不仅在存储的时候需要额外的二进制位，此外还可能会增大数据的变化范围

5.8.如果增量编码能做到以下两点，那么我们就可以认为它生成的数据更容易压缩

5.8.1.将数据集中的最大值变小，因此缩小了数值的变化范围

5.8.2.生成了许多重复值，可以让统计压缩的效率更高

6.XOR增量编码

6.1.通过使用按位异或运算（bitwise exclusive OR，XOR）代替减法运算

6.2.完全绕开了负数出现的问题，因为整数之间的XOR根本不可能产生负数

7.参照系增量编码

7.1.参照系方法通过让其他数减去最小的数

7.2.“参照系”（frame of reference，FOR）中那个“参照数”（frame）的选取，与将转换恰当地应用到数据集上有关

7.2.1.因此需要将数据集细分为更小的数据组

7.3.FOR最初的设计目的是，尽可能地将更多数值匹配到单个整数的空间之内（通常是32位或者128位的整数

7.3.1.使数值在运行时更容易处理（因为计算机处理经过字节对齐，是 2的幂的那些数值会更容易），同时还可以将它当作一种漂亮的内存压缩表示

7.3.2.提供了一种非常简单的压缩方法。将 10个整数压缩到32个二进制位的空间内，这样的压缩效果可以说很好了，其结果是产生了一种性能很强的方法，可以在一秒内解码数十亿个整数值，代价则是那些没有充分利用空间的整数需要额外的开销

7.4.修正的参照系增量编码

7.4.1.Patched Frame of Reference Delta Coding，PFOR

7.4.2.Zukowski等人提出

8.前移编码

8.1.move-to-front coding，MTF

8.2.最简单的动态统计转换形式之一

8.3.数据的排列次序中包含着一些有助于编码未来符号的信息

8.4.MTF是局部自适应的

8.4.1.会根据输入流中局部区域符号的出现频次进行调整

8.4.2.符号在短时间内重复出现时，MTF会重新分配一个较小的值

8.5.对干扰符号这类问题不敏感

8.6.问题

8.6.1.一些捣乱的符号会打乱前面存在的符号流

8.6.1.1.真实数据中普遍存在

8.7.解决方法

8.7.1.不是一读到某个符号就将它移到最前面，而是采取一些探索式方法慢慢地将它移到最前面

9.伯罗斯–惠勒变换

9.1.Burrows-Wheeler transform，BWT

9.1.1.1994年

9.1.2.Burrows与Wheeler合作

9.2.工作原理

9.2.1.通过打乱数据流次序来让重复的子串聚集在一起

9.2.2.这一操作本身不能压缩数据，却可以为后续的压缩系统提供转换好的数据流，方便压缩

9.3.顺序很重要

9.3.1.熵作为度量单位，它的一个问题是没有考虑符号之间的顺序

9.3.1.1.事实上符号之间的顺序很重要

9.3.2.通过转换数据流中符号之间的顺序，可以让数据流更容易压缩

9.3.3.在对数据排序后，如果没有更多额外的信息指明它是如何变化的，我们无法让数据重新回到未排序的状态

9.3.4.字典序排列

9.3.4.1.lexicographical permutation

9.3.4.2.BWT会打乱数据流中符号的顺序，并试图让相同的符号簇彼此靠近

9.3.4.3.找出原始数据集的一种排列，根据其顺序，该排列可能更容易压缩

9.3.5.通过BWT，在编码与解码时无须增加太多的额外信息

9.4.示例

9.4.1.BANANA

9.4.2.在接下来的每一行，我们都会对该字符串进行一次循环右移一位操作

9.4.3.BANANA

ABANANNABANAANABANNANABAANANABBANANA

9.4.4.对表中的每一行按字典顺序排序

9.4.5.ABANAN

ANABANANANABBANANANABANANANABA

9.4.6.每个字符串的最后一个字符，从上到下

9.4.7.NNBAAA

9.4.7.1.与BANANA相比更好地将相同的字符聚集在了一起

9.4.8.0 ABANAN

1 ANABAN2 ANANAB3 BANANA4 NABANA5 NANABA

9.4.9.行索引3就是源字符串

9.5.最引人注目的特点在于只需要极小的数据开销，它所进行的变换操作就是可逆的（reversible）

9.6.对DNA来说是一种理想的变换，可以使其更容易压缩、查询和检索

9.7.具体实现

9.7.1.将整个文件分为许多1 MB大小的数据块，然后在每个数据块上分别应用该算法

9.8.最常见的用法

9.8.1.将BWT的输出作为MTF的输入，经过处理后接着用统计编码算法处理

9.8.1.1.BZIP2的内部工作原理

标签：