算术编码

摘??? 要 算术编码是一种熵编码算法，比传统的霍夫曼编码更接近香农极限，因此具有更高的压缩比。算术编码目前已被广泛接受，如在静止图像压缩标准JPEG2000和视频编码标准H.264中被选用为其中的主要熵编码手段。尽管如此，基本算术编码仍然有很大的提高空间。自适应算术编码和多阶算术编码的编码效率比基本算术编码得到了显著的提高。 本文首先介绍了算术编码的基本原理和几种主流的改进算法，并实现了一种多阶（基于上下文）自适应二进制算术编码，最后对其性能做了测试。该算法考虑了编码符号序列之间的相关性，用符号序列的大概率值代替单个符号的小概率值。本文所做的试验表明，这种算法的压缩性能比基本算术编码有了明显提高，且与主流压缩软件不相上下。 关键词：算术编码；自适应模式；阶；压缩率 ?引言 数据压缩就是用更少的符号来表示相同的信号。数据之所以可以被压缩，本质上是因为存在冗余——数据所用的符号长度多余所包含的信息量。数据的压缩是有限度的，不可能无限制地进行压缩，这个限制就是该数据所包含的信息量，即香农极限。 数据的冗余分为很多种。例如，在一份计算机文件中，某些符号会重复出现，某些符号比另一些符号出现的更加频繁，或某些符号总是在一些有规律的位置出现，这些就是该文件的冗余。再如，相邻数据之间往往存在相关性，图片的均匀背景就是一个典型的例子。图像是一种典型的压缩对象，对图像进行分析，有多种冗余： 空间冗余。图像之所以能被人欣赏，必须服从大面积着色原理，在背景中，这一点尤为突出。一大片的颜色都是差不多的，这在空间上可以进行预测编码。 视觉冗余。人眼对亮度敏感而对色度不敏感。这些规律可以用来做有损压缩编码。[2] 时域的冗余。人眼对低频敏感而高频不敏感，经过变换，保留主要的低频成分，去除无关紧要的高频成分，可以大大降低码率。 算术编码是熵编码的一种，因此属于无损压缩编码。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0 ≤ n < 1.0)的小数n。基本的算术编码最后的编码结果是一个浮点数。算术编码的改进包括很多方面，可以处理更复杂的情况，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。 1.2 ?国内外研究现状 哈夫曼编码是一种常用的数据压缩编码方法，是哈夫曼于1952年为压缩文本文件提出的一种变长编码方法。它的基本思想是对出现概率大的符号分配短字长的二进制代码，对出现概率小的符号则分配长字长的二进制代码，从而最终得到每个符号码字平均码长最短的码。[11]因此对每一个输入符号都对应一个码字，而且该输入符号的出现概率必须是2的整数次幂，对应的码字字长必须是整数比特。 算术编码 (Arithmetic Coding)是利用信源统计特性对码率进行无损压缩的一种编码方式，属于熵编码范畴，实现算术编码首先需要知道信源发出每个符号的概率大小，然后再扫描符号序列，依次分割相应的区间，最终得到符号序列所对应的码字。整个编码需要两个过程，即概率模型建立过程和扫描编码过程。其编码的目的是为了最大程度的降低符号间冗余度，从而获得尽可能高的压缩效率。早在上个世纪60年代，Abralnson就根据信息论中信源序列积累概率的概念提出了算术编码的基本思想，虽然它的编码效率非常理想，接近于最佳的编码效率，但由于计算精度的问题，直到70年代中期算术编码一直停留在理论阶段。此后Rubin Guazsanen和Langd等人对算术编码做出了不断改进，算术编码进入实用阶段，1987年IanH.witen等人公布了现代多符号算术编码的第一个纯软件版本，算术编码才逐渐得以比较广泛应用。[1]目前在不少的数据压缩领域都在应用算术编码，例如英文文件编码(领域)、活动图像和目前最新的H.264视频压缩编译码标准和静止图像(JPEG2000) 压缩编码领域。下面简要的说明其编码原理，并与目前广泛应用的Huffman编码做全面的比较，以此来说明算术编码的先进性，优越性。 1.3? 本文主要研究内容 本文先介绍了算术编码的基本原理，并分析了几种算术编码的改进算法。在原有算术编码方法的基础上，实现了一种改进的算术编码方法，使得编码效率得到提高。本文的结构安排如下： 第一章? 绪论。介绍了算术编码的背景、意义以及国内外研究现状，并说明了本文的主要研究内容和结构安排。 第二章? 基本算术编码。介绍了基本算术编码的原理，并将其霍夫曼编码做比较。 第三章? 算术编码的改进。介绍几种常见的改进的算术编码，详细描述了多阶的自适应二进制算术编码原理。 第四章? 改进算术编码的实现。在Visual Studio 2005 中实现改进的算术编码，并比较性能。 第五章? 总结与展望。对本文的工作进行了总结并提出了未来工作研究的方向。