读数据压缩入门笔记07_自适应统计编码

1. 位置对熵的重要性

1.1. 为了计算概率总需要多遍历一次数据集，而在计算出整个数据集中各符号的出现概率后，还要继续处理这些数值

1.1.1. 如果是相对较小的数据集，那么这些就不是什么问题

1.2. 随着要压缩的数据集变大，统计编码的结果与熵的偏差也会越来越大

1.2.1. 数据集的不同部分有着不同的概率特征

1.3. 如果处理的是流数据，比如视频流或音频流，由于整个数据集没有“结尾”，因此就不能“遍历两次”

1.4. 数据中总会存在某种类型的局部偏态（locality-dependent skewing）

1.4.1. 在数据流中，字符Q可能会在前三分之一部分出现很多次，而在后三分之二部分则一次也没有出现

1.5. 如果数据流中存在很多局部偏态的情况的话，将数据流分为N块并且每块都单独压缩，那么得到的结果可能会比将数据流整体压缩得到的结果小

1.6. 局部性很重要（locality matters）

1.6.1. 数据流一般以线性的方式生成，因此数据流中很有可能会出现某一部分的特征与其他部分完全不同的情况

2. "动态”或“自适应”统计编码算法

2.1. 具有适应数据流熵的局部特性能力的统计编码算法

2.3. 自适应统计编码的关键在于其符号码字对应表并非一成不变，相反，可以根据读到的符号动态地生成VLC

3. 自适应VLC编码

3.1. 仅遍历一次数据集，但是过程要更复杂

3.1.1. 符号码字对应表并非必须一成不变，相反，可以根据读到的符号更新它

3.2. VLC表是静态的

3.3. 动态创建VLC表

3.3.1. 每读取一个符号，编码器都会问

3.3.1.1. 这个符号之前出现过吗？

3.3.1.2. 如果出现过，那么输出当前分配的码字，并更新其出现的概率

3.3.1.3. 如果没有，则进行一些特殊处理

3.3.1.3.1. 动态概率表

3.3.1.3.2. 重置

3.3.1.3.3. 字面值

4. 自适应算术编码

4.1. 其编码步骤与概率表之间的交互很简单

4.2. 只要编码器与解码器在更新概率的正确顺序上达成一致，就能根据需要更新概率表

5. 自适应哈夫曼编码

5.1. Faller于1973年提出

5.2. 1985年高德纳又对此算法做出重大改进

5.3. 所有现代的版本都是建立在Vitter于1987年提出的方法之上

5.4. 哈夫曼树结构的处理比较复杂

5.5. 自适应哈夫曼算法没有每次都重新生成完整的树，而是在读取和处理符号时调整现有的树

5.6. 每读取一个符号都必须要做

5.6.1. 更新概率

5.6.2. 对树的大量结点变换位置并重新排序，以使它们与概率的变化同步

5.6.3. 使树的结构满足哈夫曼树的要求

6. 优点

6.1. 有生成符号码字对应表的能力，无须将符号码字对应表显式地存储在数据流中

6.1.1. 数据流变小后，计算性能就能有所提高

6.2. 有实时压缩数据的能力，无须再将整个数据集作为一个整体来处理

6.2.1. 可以有效地处理更大的数据集

6.2.2. 不用事先知道要处理的数据集有多大

6.3. 有适应信息局部性的能力，即邻近的符号会对码字的长度有影响，这可以显著提高压缩率

7. 其他

7.2. 如果处理的是少量的数据，那么简单的静态统计编码算法就可以工作得很好

7.3. 如果处理的是大量的数据或者多媒体数据，而且运行时的性能很重要，那么采用自适应统计编码算法是正确的选择