读数据压缩入门笔记06_上下文转换-全球今亮点
博客园 2023-06-17 07:06:23
(资料图片仅供参考)
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
