数据压缩入门

自适应统计编码

｜

73

6.2

　自适应

VLC

编码

下面来看看自适应算法中最简单的一种，了解其基本的工作原理。

一般来说，统计压缩有

3

个步骤

5

：

(1)

遍历数据流并计算各个符号的出现概率；

(2)

根据概率为符号生成

VLC

；

(3)

再次遍历数据流并输出对应的码字。

从上面可以看出，压缩时需要遍历（或者说扫描）数据流两次，并且整个数据集只有一套

VLC

表。这里的问题是，

VLC

表是静态的。

而在

自适应

的压缩算法中，这

3

个步骤简化为仅遍历一次数据集，但是过程要更复杂。关

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

自适应统计编码的关键在于其符号码字对应表并非一成不变，相反，可以根

据读到的符号动态地生成

VLC

。这一过程的动态性质，让我们可以根据需要

对

VLC

表进行修改，比如对其重置。

6.2.1

　动态创建

VLC

表

动态创建

VLC

表的原理如下。

在编码器处理数据流时，每读取一个符号，编码器都会问：

•

这个符号之前出现过吗？

–

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

–

如果没有，则进行一些特殊处理（稍后会讲到这个部分）。

请记住上面的内容。假定你正在处理某个数据流，已经知道了其中的符号及相应的概率期

望。目前已有的

VLC

表如下表所示。

符号 概率 码字

A 0.5 0

B 0.4 10

C 0.1 11

注

5

：

当和那些非常聪明的人谈论数据压缩时，他们通常会认为统计编码只有两个步骤：建模和预测。

John

Brooks

，看到这里，你很高兴吧？

74

｜

第

6

章

接下来，需要从输入流中读取下一个符号，这个符号恰好是 ...