分类： C/C++
2008-10-09 14:44:08
算术编码
早在1948年，香农就提出将信源符号依其出现的概率降序排序，用符号序列累计概率的二进值作为对芯源的编码，并从理论上论证了它的优越性。1960年， Peter Elias发现无需排序，只要编、解码端使用相同的符号顺序即可，提出了算术编码的概念。Elias没有公布他的发现，因为他知道算术编码在数学上虽然成 立，但不可能在实际中实现。1976年，R. Pasco和J. Rissanen分别用定长的寄存器实现了有限精度的算术编码。1979年Rissanen和G. G. Langdon一起将算术编码系统化，并于1981年实现了二进制编码。1987年Witten等人发表了一个实用的算术编码程序，即CACM87（后用 于ITU-T的H.263视频压缩标准）。同期，IBM公司发表了著名的Q-编码器（后用于JPEG和JBIG图像压缩标准）。从此，算术编码迅速得到了 广泛的注意。
算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔（Interval），消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。
算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。
给定事件序列的算术编码步骤如下：
（1）编码器在开始时将“当前间隔” [ L， H) 设置为[0，1)。
（2）对每一事件，编码器按步骤（a）和（b）进行处理
（a）编码器将“当前间隔”分为子间隔，每一个事件一个。
（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。
（3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。
设Low和High分别表示“当前间隔”的下边界和上边界，CodeRange为编码间隔的长度，LowRange(symbol)和HighRange(symbol)分别代表为了事件symbol分配的初始间隔下边界和上边界。上述过程的实现可用伪代码描述如下：
set Low to 0
set High to 1
while there are input symbols do
take a symbol
CodeRange = High – Low
High = Low + CodeRange *HighRange(symbol)
Low = Low + CodeRange * LowRange(symbol)
end of while
output Low
算术码解码过程用伪代码描述如下：
get encoded number
do
find symbol whose range straddles the encoded number
output the symbol
range = symbo.LowValue – symbol.HighValue
substracti symbol.LowValue from encoded number
divide encoded number by range
until no more symbols
算术编码器的编码解码过程可用例子演示和解释。
例1：假设信源符号为{A， B， C， D}，这些符号的概率分别为{ 0.1， 0.4， 0.2，0.3 }，根据这些概率可把间隔[0， 1]分成4个子间隔：[0， 0.1]， [0.1， 0.5]， [0.5， 0.7]， [0.7， 1]，其中[x，y]表示半开放间隔，即包含x不包含y。上面的信息可综合在表03-04-1中。
表03-04-1 信源符号，概率和初始编码间隔
符号
A
B
C
D
概率
0.1
0.4
0.2
0.3
初始编码间隔
[0， 0.1)
[0.1， 0.5)
[0.5， 0.7)
[0.7， 1]
如果二进制消息序列的输入为：C A D A C D B。编码时首先输入的符号是C，找到它的编码范围是[0.5，0.7]。由于消息中第二个符号A的编码范围是[0， 0.1]，因此它的间隔就取[0.5， 0.7]的第一个十分之一作为新间隔[0.5，0.52]。依此类推，编码第3个符号D时取新间隔为[0.514， 0.52]，编码第4个符号A时，取新间隔为[0.514， 0.5146]，…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图03-04-1所示。
图03-04-1 算术编码过程举例
这个例子的编码和译码的全过程分别表示在表03-04-2和表03-04-3中。
表03-04-2 编码过程
步骤
输入符号
编码间隔
编码判决
1
C
[0.5， 0.7]
符号的间隔范围[0.5， 0.7]
2
A
[0.5， 0.52]
[0.5， 0.7]间隔的第一个1/10
3
D
[0.514， 0.52]
[0.5， 0.52]间隔的最后一个1/10
4
A
[0.514， 0.5146]
[0.514， 0.52]间隔的第一个1/10
5
C
[0.5143， 0.51442]
[0.514， 0.5146]间隔的第五个1/10开始，二个1/10
6
D
[0.514384， 0.51442]
[0.5143， 0.51442]间隔的最后3个1/10
7
B
[0.5143836， 0.514402]
[0.514384，0.51442]间隔的4个1/10，从第1个1/10开始
8
从[0.5143876， 0.514402]中选择一个数作为输出：0.5143876
表03-04-3 译码过程
步骤
间隔
译码符号
译码判决
1
[0.5， 0.7]
C
0.51439在间隔 [0.5， 0.7)
2
[0.5， 0.52]
A
0.51439在间隔 [0.5， 0.7)的第1个1/10
3
[0.514， 0.52]
D
0.51439在间隔[0.5， 0.52)的第7个1/10
4
[0.514， 0.5146]
A
0.51439在间隔[0.514， 0.52]的第1个1/10
5
[0.5143， 0.51442]
C
0.51439在间隔[0.514， 0.5146]的第5个1/10
6
[0.514384， 0.51442]
D
0.51439在间隔[0.5143， 0.51442]的第7个1/10
7
[0.51439， 0.5143948]
B
0.51439在间隔[0.51439，0.5143948]的第1个1/10
8
译码的消息：C A D A C D B
在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。
在算术编码中有几个问题需要注意：
· 由于实际的计算机的精度不可能无限长，一个明显的问题是运算中出现溢出，但多数机器都有16、32或者64位的精度，因此这个问题可使用比例缩放方法解决。
· 算术编码器对整个消息只产生一个码字，这个码字是在间隔[0，1]中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。
· 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。
算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地 进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开发动态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息 时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。
此外，在算术编码的使用中还存在版权问题。JPEG标准说明的算术编码的一些变体方案属于IBM， AT&T和Mitsubishi拥有的专利。要合法地使用JPEG算术编码必须得到这些公司的许可。
