vc00352 多阶自适应算术编码原理分析与实现

摘    要

算术编码是一种无损的压缩编码算法，因此可以用于数据压缩。算术编码压缩效率高，大约比传统的霍夫曼编码高出10%左右。目前算术编码逐渐在实际中得到了应用。静止图像压缩标准JPEG2000和视频编码标准H.264和视频编码标准H.264均将算术编码选为其中的主要熵编码手段。多阶的自适应二进制编码考虑了不同长度的符号，并使符号出现的概率动态变化，比基本的算术编码更接近香农极限。

本文通过对算术编码原理的研究，阐明其强大的生命力和独特优势。本文介绍了算术编码的基本原理和几种主流的改进算法，并实现了一种多阶（基于上下文）自适应二进制算术编码。最后，本文用不同种类的文件对其性能做了测试，并将结果与主流压缩软件比较，发现算术编码与其中占优势的软件性能不相上下，取得了非常好的压缩效果。

关键词：算术编码；自适应模式；上下文；压缩率

引言

数据压缩就是用更少的符号来表示相同的信号。数据之所以可以被压缩，本质上是因为存在冗余——数据所用的符号长度多余所包含的信息量。数据的压缩是有限度的，不可能无限制地进行压缩，这个限制就是该数据所包含的信息量，即香农极限。

数据的冗余分为很多种。例如，在一份文件中，某些符号会重复出现，某些符号比另一些符号出现的更加频繁，或某些符号总是在一些有规律的位置出现，这些就是该文件的冗余。再如，相邻数据之间往往存在相关性，图片的均匀背景就是一个典型的例子。图像是一种典型的压缩对象，对图像进行分析，有多种冗余：

空间冗余。图像之所以能被人欣赏，必须服从大面积着色原理，在背景中，这一点尤为突出。一大片的颜色都是差不多的，这在空间上可以进行预测编码。

视觉冗余。人眼对亮度敏感而对色度不敏感。这些规律可以用来做有损压缩编码。^[2]

时域的冗余。人眼对低频敏感而高频不敏感，经过变换，保留主要的低频成分，去除无关紧要的高频成分，可以大大降低码率。

算术编码是熵编码的一种，因此属于无损压缩编码。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0 ≤ n < 1.0)的小数n。基本的算术编码最后的编码结果是一个浮点数。算术编码的改进包括很多方面，可以处理更复杂的情况，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。

1.2 国内外研究现状

熵编码包含的编码种类多种多样。哈夫曼编码是一种常用的数据压缩编码方法，是哈夫曼于1952年为压缩文本文件提出的一种变长编码方法。它的基本思想是对出现概率大的符号分配短字长的二进制代码，对出现概率小的符号则分配长字长的二进制代码，从而最终得到每个符号码字平均码长最短的码。[11]因此对每一个输入符号都对应一个码字，而且该输入符号的出现概率必须是2的整数次幂，对应的码字字长必须是整数比特。

1968 年前后， P. Elias[2] 发展了 Shannon 和 Fano 的编码方法，构造出从数学角度看来更为完美的 Shannon-Fano-Elias 编码。沿着这一编码方法的思路， 1976 年， J. Rissanen[3] 提出了一种可以成功地逼近信息熵极限的编码方法——算术编码(Arithmetic Coding)。1982 年， Rissanen 和 G. G. Langdon[4] 一起改进了算术编码。之后，人们又将算术编码与 J. G. Cleary 和 I. H. Witten[5] 于 1984 年提出的部分匹配预测模型（ PPM ）相结合，开发出了压缩效果近乎完美的算法。今天，那些名为 PPMC 、 PPMD  或 PPMZ 并号称压缩效果天下第一的通用压缩算法，实际上全都是这一思路的具体实现。算术编码是利用信源统计特性对码率进行无损压缩的一种编码方式，属于熵编码范畴，实现算术编码首先需要知道信源发出每个符号的概率大小，然后再扫描符号序列，依次分割相应的区间，最终得到符号序列所对应的码字。整个编码需要两个过程，即概率模型建立过程和扫描编码过程。其编码的目的是为了最大程度的降低符号间冗余度，从而获得尽可能高的压缩效率。早在上个世纪60年代，Abralnson就根据信息论中信源序列积累概率的概念提出了算术编码的基本思想，虽然它的编码效率非常理想，接近于最佳的编码效率，但由于计算精度的问题，直到70年代中期算术编码一直停留在理论阶段。此后Rubin Guazsanen和Langd等人对算术编码做出了不断改进，算术编码进入实用阶段，1987年IanH.witen等人公布了现代多符号算术编码的第一个纯软件版本，算术编码才逐渐得以比较广泛应用。[1]目前在不少的数据压缩领域都在应用算术编码，例如英文文件编码(领域)、活动图像和目前最新的H.264视频压缩编译码标准和静止图像(JPEG2000) 压缩编码领域。下面简要的说明其编码原理，并与目前广泛应用的Huffman编码做全面的比较，以此来说明算术编码的先进性，优越性。设计具体的压缩算法时，设计者首先要做的是寻找一种能尽量精确地统计或估计信息中符号出现概率的方法，然后还要设计一套用最短的代码描述每个符号的编码规则。统计学知识对于前一项工作相当有效，迄今为止，人们已经陆续实现了静态模型、半静态模型、自适应模型、Markov模型、部分匹配预测模型等概率统计模型。

犹太人 J. Ziv 和 A. Lempel脱离 Huffman 及算术编码的设计思路，创造出了一系列比 Huffman 编码更有效，比算术编码更快捷的压缩算法。这些算法统称为 LZ 系列算法，如： LZ77 算法， LZ78 的压缩算法，以及LZW 算法。该系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们只是用一种极为巧妙的方式将字典技术应用于通用数据压缩领域。这种基于字典模型的思路在表面上虽然和 Shannon 、 Huffman 等人开创的统计学方法大相径庭，但在效果上一样可以逼近信息熵的极限。而且LZ 系列算法在本质上符合信息熵的基本规律。 LZ 系列算法的优越性使得使用该算法的压缩软件数量呈爆炸式增长。今天，我们熟悉的 PKZIP 、 WinZIP 、 WinRAR 、Gzip 等压缩工具以及 ZIP、GIF、PNG 等文件格式都是 LZ 系列算法的受益者。

在图像压缩领域，著名的 JPEG 标准是有损压缩算法中的经典。 JPEG 标准由静态图像联合专家组（ Joint Photographic Experts Group ， JPEG ）于 1986 年开始制定，1994 年后成为国际标准。 JPEG 以离散余弦变换（ DCT ）为核心算法，通过调整质量系数控制图像的精度和大小。

    1994年， M. Burrows 和 D. J. Wheeler 共同提出了一种全新的通用数据压缩算法。这种算法的核心思想是对字符串轮转后得到的字符矩阵进行排序和变换，类似的变换算法被称为 Burrows-Wheeler 变换，简称 BWT。分形压缩技术是图像压缩领域近几年来的一个热点。这一技术起源于 B. Mandelbrot 于 1977 年创建的分形几何学。 M. Barnsley 在 20 世纪 80 年代后期为分形压缩奠定了理论基础。从 20 世纪 90 年代开始， A. Jacquin 等人陆续提出了许多实验性的分形压缩算法。

1.3 本文主要研究内容

本文先介绍了算术编码的基本原理，并分析了几种算术编码的改进算法。在原有算术编码方法的基础上，实现了一种改进的算术编码方法，使得编码效率得到提高。本文的结构安排如下：

第一章  绪论。介绍了算术编码的背景、意义以及国内外研究现状，并说明了本文的主要研究内容和结构安排。

第二章  算术编码的原理。介绍了基本算术编码的原理，并将其霍夫曼编码做比较。

第三章  多阶自适应二进制算术编码。介绍几种常见的改进的算术编码，详细描述了多阶的自适应二进制算术编码原理。

第四章  改进算术编码的实现。在Visual Studio 2005 中实现改进的算术编码，并通过实验与主流文件压缩软件比较性能。

第五章  总结与展望。对本文的工作进行了总结并提出了未来工作研究的方向。