区间编码

维基百科，自由的百科全书

区间编码是一种算术编码形式的数据压缩方法，但是人们认为这种方法不受与算术编码相关的专利约束。正是基于这一点，才激起了人们尤其是开放源码社区对于区间编码的兴趣。但是，人们经常认为区间编码与算术编码之间只有细微的区别，实际上二者是一样的。关于这个问题，需要注意的是 G N N Martin 在 1979 年的论文中定义为“区间编码：去除数字信息中冗余的算法（参见 [1]）”的区间编码尽管本质上与算术编码相同，但是区间编码经常使用基于 Martin 论文的特殊实现方法，根据 Martin 论文的年代，人们通常认为这些实现不受算术编码相关的专利的约束。

[编辑] 区间编码是如何工作的

区间编码概念上要把所有的消息符号都编码成一个数字，这与哈夫曼编码为每个符号赋予一个位组合格式并且将所有这些位组合格式连接到一起不同。这样区间编码能够实现比哈夫曼编码一个符号一位这个上限还要高的压缩率，并且它没有哈夫曼编码处理概率不为 2 的倍数时的效率问题。

区间编码的核心概念是：对于给定的一个范围足够大的整数区间以及符号的概率估计，最初的区间很容易切分成与所表示的符号概率成比例的子区间。将当前区间切分成与下一个待编码符号的概率对应的子区间，通过这种方法就可以对消息中的每个符号进行编码。解码器必须与编码器有同样的概率估计，这种概率估计可以事先发送过去、从已经发送的数据导出或者作为压缩器或者解压器的一部分。

当所有的符号已经编码完成后，仅仅用子区间就可以表示整个信息（当然我们假定解码器提取了整个消息之后通过某种方式得到）。单个的整数实际上已经足够表示子区间，并且可能不需要传输整个的整数；如果有这样一个数字序列，即每个整数的前缀都落在某个子区间，那么前缀本身就已经足够标识字区间并且传输消息。

[编辑] 例子

假设我们打算编码消息“AABA<EOM>”，其中 <EOM> 是消息结束符。对于这个例子来说，假设编码器知道我们打算用十进制数表示，也知道最初的区间是 [0, 100000) 并且频率是 {A: .60; B: .20; <EOM>: .20}，第一个符号将 [0, 100000) 分成三个子区间：

A:     [     0,  60000)
B:     [ 60000,  80000)
<EOM>: [ 80000, 100000)

由于第一符号是 A，所以最初的区间缩减为 [0, 60000)。第二个符号再次将这个区间分成三个子区间，跟在已经编码的 'A' 后面表示：

AA:     [     0,  36000)
AB:     [ 36000,  48000)
A<EOM>: [ 48000,  60000)

两个符号编码之后，区间变成 [000000, 036000)，第三个符号得到下面的结果：

AAA:     [     0,  21600)
AAB:     [ 21600,  28800)
AA<EOM>: [ 28800,  36000)

这一次第二段表示我们要编码的消息，这样区间就变成了 [21600, 28800)。在这种情况下看起来确定子区间变得困难了一些，实际上并非如此：我们可以直接用上限减去下限得到 7200，它最前面的 4320 区间是它的 .60，后面的 1440 区间表示随后的 .20，剩余的 1440 表示剩余的 .20，然后加上下限得到区间：

AABA:     [21600, 25920)
AABB:     [25920, 27360)
AAB<EOM>: [27360, 28800)

最后，区间缩小到 [21600, 25920)，我们还有一个符号要进行编码。与前面一样我们区间进行切分得到：

AABAA:     [21600, 24192)
AABAB:     [24192, 25056)
AABA<EOM>: [25056, 25920)

由于 <EOM> 是最后一个符号，所以最后的区间就是 [25056, 25920)。因为以“251”开头的五位整数都落在最后的区间内，这样任何一个三位前缀在这个范围的整数都能够明确地传达原始信息。存在八个这样的前缀这个事实暗示效率仍然不是最高的，这是由于我们使用十进制而不是二进制整数引起的。

这样看起来主要问题就是我们要选择一个足够大的区间，这样不管需要编码多少符号我们都有足够大的区间使得子区间不为 0。但是，实际上这不是一个问题，因为编码器不是从一个非常大的区间开始不断减小这个区间，编码器在任何时刻都只在一个更小的区间工作。在编码一定熟练的数位之后，最左面的数位不再变化。在这个例子中编码三个符号之后，我们就已经知道结果将以“2”开始。随着更多数位从右侧进来，左侧的数位将不断发送出去。

[编辑] 与算术编码的关系

算术编码与区间编码一模一样，但是它用分数取代了整数。这些分数有一个隐含的-{A|zh-cn:公分母;zh-tw:公分母}-，这样所有的分数都落在 [0,1) 区间。因此，算术编码结果都解释为以一个隐含的“0”开始。由于这是同样的编码方法的不同解释，并且由于算术编码与区间编码的结果相同，所以算术编码器都是与之对应的区间编码器，反之亦然。换句话说就是，算术编码与区间编码是对于同一事物稍微不同的两种理解方法。

但是，实际应用中区间编码器倾向于使用 Martin 论文（参见 [2]）中描述的实现方法，然而算术编码通常也不叫作区间编码。类似的区间编码器经常提及的一个特性是每次正规化（renormalization）一个字节，而不是每次一位。换句话说，区间编码倾向于使用字节而不是位作为编码数码。尽管这会稍微地减小压缩的比率，但是比每次正规化一位的速度要快很多。