自适应统计编码
- 为何需要“自适应”？
- 统计编码算法需要遍历数据以计算概率分布，再编码相当于二次处理，不适合大数据集或流数据（如视频流，数据集无“结尾”）
- 数据中存在某种类型的局部偏态 (locality-dependent skewing)，某些符号只常出现在某个子区间
如果数据流存在较多局部偏态，则分块编码可能比整体压缩效果好得多
- 难点
找到最佳方式分割数据流
思路：如果“期望”的熵与“实际的符号平均二进制位数”之间出现显著差异，那么统计编码算法会重置概率表，并使用重置后的概率表进行编码。
动态创建 VLC 表
编（解）码：
- 从输入流中读取符号（码字）
- 输出该符号（码字）对应的码字（符号）到输出流中
- 更新符号的出现概率并重新生成码字
字面值
- 解决的问题：
- 在开始编码前，最初的 VLC 表是什么样子？
- 在解码过程中，如果读到一个 VLC 表中不存在的符号该怎么办？
- 字面值词条（literal tokens），相当于一个假字符，用以标识说明出现了未遇到过的符号
- 具体做法
- 编码其遇到新符号时：
- 将 LITERAL 对应码字写入输出流
- 读到的新符号添加到字面值流中
- 解码读到 LITERAL 时：
- 从字面值流中读取下一个字面值
- 将该字面值写入输出流并更新 VLC 表
【例】对输入字符串AAAAABCABC编码
- 编码其遇到新符号时：
重置
然而实际场景中，没有人使用这种简版的自适应 VLC 算法（静态 VLC 算法也是）。现代压缩工具通常采用自适应 Huffman 编码与自适应算术编码