【数据压缩入门】字典转换

虽然 VLC 一直都在发挥作用，但它与熵绑定的事实也限制了数据压缩未来的发展。

字典转换(dictionary transforms)
- 考虑的对象不再是单个的符号，而是一组相邻的符号
更确切地说，统计压缩接受我们扔给它处理的任何符号；而字典转换接收的是符号集，并重新定义要使用的符号以减小生成的数据流的熵。
- 一个数据流的预处理阶段，识别出那些经常重复使用的长字符串，而非去替代统计编码

学会分词

怎样才能决定哪些符号是最佳的“单词”？

可以通过被称为分词（tokenization）的过程找出这些“单词”，即分析一组数据并从中找出理想的“单词”。分词这一过程相当复杂，它本身也是信息论领域的一个研究分支。

@ Python jieba 库可以尝试代码分词

向前寻找匹配进行“分词”

搜索缓冲区
- 将数据流分为两部分：search buffer & look ahead buffer
找到匹配
滑动窗口
实际实现过程中，数据流因为其超长长度，难以对所有已处理过的符号进行搜索，因此需要对搜索缓冲区长度加以限制。

有了滑动窗口，查找匹配的性能要求也就有了上限。同样也考虑到了局部性原理，即在给定的数据集中相关的数据很可能分布在相似的局部区域。

一般来说，搜索缓冲区滑动窗口的长度大概为几万个字节，而先行缓冲区的长度则只有几十个字节。

标记匹配
通过偏移量和长度对匹配进行标记
未找到匹配情况
需要对输出的记号进行修改，表明输出的是字面值，这样解码器就能读取并恢复源数据流。不过，怎样构造该记号完全取决于具体的 LZ 算法实现。一种最基本的做法是，将修改后的记号表示为三部分，还是偏移量和长度值，只不过取值都为 0，即 [0,0], 最后一部分则是符号的字面值

以字符串 TOBEORNOTTOBE 为例

这里编码的输出采用其他编码从而进一步编码成二进制，如 ASCII码等

例如上述用例，输出的记号集 [0,0,T] [0,0,O] [0,0,B] [0,0,E] [3,1] [0,0,R] [0,0,N] [3,1] [8,1] [9,4] 分成以下 3 个数据集:

针对数据集的处理：

偏移量集，可知偏移量 $\in [0, X]$ ，永远小于搜索缓冲区长度 $X$ ，可用 $l b (X)$ 位编码，也可统计编码（虽然效果不一定有较大改善）
长度值，长度值的分布取决于输入流的内容以及语言的类型，简单采用统计编码也通常可达较好效果
字面值集，与偏移量集和长度值相比，字面值集好像也没有什么更好的压缩方法。不过，随着输入流增大，由于可能会存在重复的字面值（这是因为有滑动窗口），因此字面值流的熵也会略微变小。

LZ77 基本算法，有时也被称为 LZ1 算法；与前面介绍的唯一区别是，它会将先行缓冲区中下一个符号的字面值作为第三个值输出。

LZ 算法系列的核心算法最早发表于 1977~1978 年，这两种算法有时也被称为 LZ1 算法和LZ2 算法。LZ78 算法的工作原理与前面描述的基本相同，不过它不用距搜索缓冲区结尾的偏移量来指示匹配的位置，而是根据输入流创建字典然后再引用。

LZW（Lempel-Ziv-Welch）算法是由 Terry Welch 于 1984 年提出的，它采用了 LZ78 算法的思想，其工作原理如下。

该算法最适用于那些连续出现重复的数据。