资源描述：
《算术编码工作原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、算术编码工作原理在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。例:对一个简单的信号源进行观察，得到的统计模型如下：·60%的机会出现符号中性·20%的机会出现符号阳性·10%的机会出现符号阴性·10%的机会出现符号数据结束符.(出现这个符号的意思是该信号源'内部中止'，在进行数据压缩时这样的情况是很常见的。当第一次也是唯一的一次看到这个符号时，解码器就知道整个信号流都被解码完成了。)算术编码可以处理的例子不
2、止是这种只有四种符号的情况，更复杂的情况也可以处理，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。一个简单的例子以下用一个符号串行怎样被编码来作一个例子：假如有一个以A、B、C三个出现机会均等的符
3、号组成的串行。若以简单的分组编码会十分浪费地用2bits来表示一个符号：其中一个符号是可以不用传的(下面可以见到符号B正是如此)。为此，这个串行可以三进制的0和2之间的有理数表示，而且每位数表示一个符号。例如，“ABBCAB”这个串行可以变成0.011201(base3)(即0为A,1为B,2为C)。用一个定点二进制数字去对这个数编码使之在恢复符号表示时有足够的精度，譬如0.001011001(base2)–只用了9个bit，比起简单的分组编码少(1–9/12)x100%=25%。这对于长串行是可行的因为有高效的、适当的算法去精确地转换
4、任意进制的数字。编码过程的每一步，除了最后一步，都是相同的。编码器通常需要考虑下面三种数据：·下一个要编码的符号·当前的区间(在编第一个符号之前，这个区间是[0,1),但是之后每次编码区间都会变化)·模型中在这一步可能出现的各个符号的概率分布(像前面提到的一样，高阶或者自适应的模型中，每一步的概率并不必须一样)编码其将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为在下一步编码中的初始区间。例:对于前面提出的4符号模型:·中性对应的区间是[0,0.6)·阳性对应的区
5、间是[0.6,0.8)·阴性对应的区间是[0.8,0.9)·数据结束符对应的区间是[0.9,1)当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号串行。任何人使用该区间和使用的模型参数即可以解码重建得到该符号串行。实际上我们并不需要传输最后的结果区间，实际上，我们只需要传输该区间中的一个小数即可。在实用中，只要传输足够的该小数足够的位数(不论几进制)，以保证以这些位数开头的所有小数都位于结果区间就可以了。例:下面对使用前面提到的4符号模型进行编码的一段信息进行解码。编码的结果是0.538(为了容易理解，这里使用十进制而
6、不是二进制；我们也假设我们得到的结果的位数恰好够我们解码。下面会讨论这两个问题)。像编码器所作的那样我们从区间[0,1)开始，使用相同的模型，我们将它分成编码器所必需的四个子区间。分数0.538落在NEUTRAL坐在的子区间[0,0.6)；这向我们提示编码器所读的第一个符号必然是NEUTRAL，这样我们就可以将它作为消息的第一个符号记下来。然后我们将区间[0,0.6)分成子区间：·中性的区间是[0,0.36)--[0,0.6)的60%·阳性的区间是[0.36,0.48)--[0,0.6)的20%·阴性的区间是[0.48,0.54)--[
7、0,0.6)的10%·数据结束符的区间是[0.54,0.6).--[0,0.6)的10%我们的分数.538在[0.48,0.54)区间；所以消息的第二个符号一定是NEGATIVE。我们再一次将当前区间划分成子区间：·中性的区间是[0.48,0.516)·阳性的区间是[0.516,0.528)·阴性的区间是[0.528,0.534)·数据结束符的区间是[0.534,0.540).我们的分数.538落在符号END-OF-DATA的区间；所以，这一定是下一个符号。由于它也是内部的结束符号，这也就意味着编码已经结束。（如果数据流没有内部结束，我
8、们需要从其它的途径知道数据流在何处结束——否则我们将永远将解码进行下去，错误地将不属于实际编码生成的数据读进来。）同样的消息能够使用同样短的分数来编码实现如.534、.535、.536、.537或者是.53
