数据压缩入门

97

第 8 章

上下文数据转换

在开始本章内容前，我们先花一些时间回顾一下前面的内容。

统计编码算法工作时会为每个符号分配一个长度可变的码字，压缩主要来自于为越频繁

出现的符号分配越短的码字。而字典转换的分词过程会识别出数据集中最长且最频繁出

现的那些符号。实际上，只有分词过程找出了那些最适合的符号，编码的效率才能提高。

从技术上来说，我们完全可以通过分词过程识别出那些最适合编码的符号，然后再将所

得结果交给统计编码算法处理以得到压缩的效果。然而，

LZ

算法的真正威力体现在我们

没有那样去做，而是用熵值较低的记号二元组来表示匹配的信息，然后再去压缩这些记

号二元组。

除了字典变换之外，还有一整套其他的变换都是按照同样的原理工作的：给定一组相邻的

符号集，对它们进行某种方式的变换使其更容易压缩。我们通常称这样的变换为“上下文

变换”（

contextual transform

），因为在思考数据的理想编码方式时，这些方法考虑到了邻近

符号的影响。

这些变换的目标是一致的，即通过对这些信息进行某种方式的变换，使统计编码算法对其

进行压缩时更高效。

变换数据的方法有很多种，但其中有

3

种对现代的数据压缩来说最为重要，即

行程编码

（

run-length encoding

，

RLE

）、

增量编码

（

delta coding

）和

伯罗斯

–

惠勒变换

（

Burrows-Wheeler

transform

，

BWT

）。

下面分别介绍这

3

种方法。