[科普中国]-区间编码

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

简介区间编码是一种基于统计模型的无损压缩算法。G.N.N.Martin在1979年的视频和数据记录会议（Video&Data Recording Conference）上提交了一篇论文：《区间编码：去除数字信息中冗余的算法》（Rangeencoding:analgorithm for removing redundancy from a digitised message.），第一次提出了区间编码算法的思想。区间编码的实现都是基于该论文中描述的方法。尽管从本质上说区间编码与算术编码是相同的，但是根据该论文的发表年代，通常认为区间编码算法不受与算术编码算法相关的专利约束。正是因为如此，越来越多的研究人员将目光转向了区间编码算法。

与经典的哈夫曼编码相比，区间编码可以获得更高的压缩率。因为传统上的哈夫曼编码是以位作为单位为符号分配编码。即使一个符号具有非常高的频度，哈夫曼编码也只能为其分配一个位的编码。这限制了压缩率的进一步提升。与哈夫曼编码不同，区间编码将所有的数据映射到一个整数区间内。然后输出一个属于该区间的整数作为输出编码。这意味着区间编码可以无限的接近数据的熵极限。另外，区间编码由于其特点可以很好的与高阶模型相配合。区间编码已经开始大量的应用。

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

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

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

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

A: [ 0, 60000)

B: [ 60000, 80000)

: [ 80000, 100000)

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

AA: [ 0, 36000)

AB: [ 36000, 48000)

A: [ 48000, 60000)

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

AAA: [ 0, 21600)

AAB: [ 21600, 28800)

AA: [ 28800, 36000)

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

AABA: [21600, 25920)

AABB: [25920, 27360)

AAB: [27360, 28800)

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

AABAA: [21600, 24192)

AABAB: [24192, 25056)

AABA: [25056, 25920)

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

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

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

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

XML动态区间编码方法DCLS(dynamic containment labelingscheme).DCLS 将基于整数的编码泛化到基于向量的编码,扩展了传统静态区间编码方法,有效避免了 XML 文档更新时的重新编码.不论文档更新与否,DCLS 都显示了良好的性能:DCLS 利用基于整数的静态区间编码方法进行初始编码,在文档不更新的环境下,具有较高的存储效率和查询性能;同时,DCLS 将整数视为特殊向量,不仅能够支持文档更新,而且更新效率高;特别是倾斜插入时,DCLS 可以避免编码位长的快速增加.实验结果表明,与已有的动态区间编码方法相比,DCLS 具有更好的性能。

传统的静态区间编码方法中,每个节点都被赋予一对整数,这对整数表达了节点覆盖区域,进而支持了节点间位置关系和结构关系计算.但是使用静态区间编码不能有效处理 XML 文档更新,一旦更新发生,整个树需要重新编码,系统代价高.为解决该问题,一些研究人员提出了动态区间编码方法,包括浮点数区间 、CDBS以及QED等.相比较静态区间编码,这些方法支持文档更新操作,但同时需要更多时空开销,也降低了查询性能.特别在文档不更新或者少更新环境下,效率偏低。

静态区间编码和动态区间编码各有利弊.当文档不更新或者少更新时,静态区间编码无疑是更好的选择;但当 XML 频繁更新时,静态区间编码性能急剧下降,而动态区间编码则显示出优势.通常情况下,人们很难事先判断文档更新频率,进而不易选择合适的编码方法.这个意义下,开发出有效的动态编码,满足文档更新与否情况下都具有良好性能显得尤为重要.基于此,本文3提出了新的动态区间编码方法——DCLS(dynamic containmentlabeling scheme),DCLS 直接在静态区间编码基础上进行扩展,可以有效地支持 XML 动态更新,同时又确保了文档不更新环境下的良好性能。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所