注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

清风笑

开始,就是未来

 
 
 

日志

 
 

算术编码原理 (转)  

2013-01-08 12:55:16|  分类: 信号处理及算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

原文:http://blog.163.com/sara1124@126/blog/static/1129109702009931105558580/
|字号 订阅

Huffman 编码使用整数个二进制位对符号进行编码,这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为 80%,该字符事实上只需要 -log2(0.8) = 0.322 位编码,但 Huffman 编码一定会为其分配一位 0 或一位 1 的编码。可以想象,整个信息的 80% 在压缩后都几乎相当于理想长度的 3 倍左右,压缩效果可想而知。

难道真的能只输出 0.322 个 0 或 0.322 个 1 吗?是用剪刀把计算机存储器中的二进制位剪开吗?计算机真有这样的特异功能吗?慢着慢着,我们不要被表面现象所迷惑,其实,在这一问题上,我们只要换一换脑筋,从另一个角度……哎呀,还是想不通,怎么能是半个呢?好了,不用费心了,数学家们也不过是在十几年前才想到了算术编码这种神奇的方法,还是让我们虚心地研究一下他们究竟是从哪个角度找到突破口的吧。

输出:一个小数

更神奇的事情发生了,算术编码对整条信息(无论信息有多么长),其输出仅仅是一个数,而且是一个介于 0 和 1 之间的二进制小数。例如算术编码对某条信息的输出为 1010001111,那么它表示小数 0.1010001111,也即十进制数 0.64。

咦?怎么一会儿是表示半个二进制位,一会儿又是输出一个小数,算术编码怎么这么古怪呀?不要着急,我们借助下面一个简单的例子来阐释算术编码的基本原理。为了表示上的清晰,我们暂时使用十进制表示算法中出现的小数,这丝毫不会影响算法的可行性。

考虑某条信息中可能出现的字符仅有 a b c 三种,我们要压缩保存的信息为 bccb。

在没有开始压缩进程之前,假设我们对 a b c 三者在信息中的出现概率一无所知(我们采用的是自适应模型),没办法,我们暂时认为三者的出现概率相等,也就是都为 1/3,我们将 0 - 1 区间按照概率的比例分配给三个字符,即 a 从 0.0000 到 0.3333,b 从 0.3333 到 0.6667,c 从 0.6667 到 1.0000。用图形表示就是:

               +-- 1.0000               |   Pc = 1/3    |               |               +-- 0.6667               |   Pb = 1/3    |               |               +-- 0.3333               |   Pa = 1/3    |               |               +-- 0.0000

现在我们拿到第一个字符 b,让我们把目光投向 b 对应的区间 0.3333 - 0.6667。这时由于多了字符 b,三个字符的概率分布变成:Pa = 1/4,Pb = 2/4,Pc = 1/4。好,让我们按照新的概率分布比例划分 0.3333 - 0.6667 这一区间,划分的结果可以用图形表示为:

               +-- 0.6667   Pc = 1/4    |               +-- 0.5834               |               |   Pb = 2/4    |               |               |               +-- 0.4167   Pa = 1/4    |               +-- 0.3333

接着我们拿到字符 c,我们现在要关注上一步中得到的 c 的区间 0.5834 - 0.6667。新添了 c 以后,三个字符的概率分布变成 Pa = 1/5,Pb = 2/5,Pc = 2/5。我们用这个概率分布划分区间 0.5834 - 0.6667:

               +-- 0.6667               |   Pc = 2/5    |               |               +-- 0.6334               |   Pb = 2/5    |               |               +-- 0.6001   Pa = 1/5    |               +-- 0.5834

现在输入下一个字符 c,三个字符的概率分布为:Pa = 1/6,Pb = 2/6,Pc = 3/6。我们来划分 c 的区间 0.6334 - 0.6667:

               +-- 0.6667               |               |   Pc = 3/6    |               |               |               +-- 0.6501               |   Pb = 2/6    |               |               +-- 0.6390   Pa = 1/6    |               +-- 0.6334

输入最后一个字符 b,因为是最后一个字符,不用再做进一步的划分了,上一步中得到的 b 的区间为 0.6390 - 0.6501,好,让我们在这个区间内随便选择一个容易变成二进制的数,例如 0.64,将它变成二进制 0.1010001111,去掉前面没有太多意义的 0 和小数点,我们可以输出 1010001111,这就是信息被压缩后的结果,我们完成了一次最简单的算术压缩过程。

怎么样,不算很难吧?可如何解压缩呢?那就更简单了。解压缩之前我们仍然假定三个字符的概率相等,并得出上面的第一幅分布图。解压缩时我们面对的是二进制流 1010001111,我们先在前面加上 0 和小数点把它变成小数 0.1010001111,也就是十进制 0.64。这时我们发现 0.64 在分布图中落入字符 b 的区间内,我们立即输出字符 b,并得出三个字符新的概率分布。类似压缩时采用的方法,我们按照新的概率分布划分字符 b 的区间。在新的划分中,我们发现 0.64 落入了字符 c 的区间,我们可以输出字符 c。同理,我们可以继续输出所有的字符,完成全部解压缩过程(注意,为了叙述方便,我们暂时回避了如何判断解压缩结束的问题,实际应用中,这个问题并不难解决)。

现在把教程抛开,仔细回想一下,直到你理解了算术压缩的基本原理,并产生了许多新的问题为止。

真的能接近极限吗?

现在你一定明白了一些东西,也一定有了不少新问题,没有关系,让我们一个一个解决。

首先,我们曾反复强调,算术压缩可以表示小数个二进制位,并由此可以接近无损压缩的熵极限,怎么从上面的描述中没有看出来呢?

算术编码实际上采用了化零为整的思想来表示小数个二进制位,我们确实无法精确表示单个小数位字符,但我们可以将许多字符集中起来表示,仅仅允许在最后一位有些许的误差。

结合上面的简单例子考虑,我们每输入一个符号,都对概率的分布表做一下调整,并将要输出的小数限定在某个越来越小的区间范围内。对输出区间的限定是问题的关键所在,例如,我们输入第一个字符 b 时,输出区间被限定在 0.3333 - 0.6667 之间,我们无法决定输出值得第一位是 3、4、5 还是 6,也就是说,b 的编码长度小于一个十进制位(注意我们用十进制讲解,和二进制不完全相同),那么我们暂时不决定输出信息的任何位,继续输入下面的字符。直到输入了第三个字符 c 以后,我们的输出区间被限定在 0.6334 - 0.6667 之间,我们终于知道输出小数的第一位(十进制)是 6,但仍然无法知道第二位是多少,也即前三个字符的编码长度在 1 和 2 之间。等到我们输入了所有字符之后,我们的输出区间为 0.6390 - 0.6501,我们始终没有得到关于第二位的确切信息,现在我们明白,输出所有的 4 个字符,我们只需要 1 点几个十进制位,我们唯一的选择是输出 2 个十进制位 0.64。这样,我们在误差不超过 1 个十进制位的情况下相当精确地输出了所有信息,很好地接近了熵值(需要注明的是,为了更好地和下面的课程接轨,上面的例子采用的是 0 阶自适应模型,其结果和真正的熵值还有一定的差距)。

小数有多长?

你一定已经想到,如果信息内容特别丰富,我们要输出的小数将会很长很长,我们该如何在内存中表示如此长的小数呢?

其实,没有任何必要在内存中存储要输出的整个小数。我们从上面的例子可以知道,在编码的进行中,我们会不断地得到有关要输出小数的各种信息。具体地讲,当我们将区间限定在 0.6390 - 0.6501 之间时,我们已经知道要输出的小数第一位(十进制)一定是 6,那么我们完全可以将 6 从内存中拿掉,接着在区间 0.390 - 0.501 之间继续我们的压缩进程。内存中始终不会有非常长的小数存在。使用二进制时也是一样的,我们会随着压缩的进行不断决定下一个要输出的二进制位是 0 还是 1,然后输出该位并减小内存中小数的长度。

静态模型如何实现?

我们知道上面的简单例子采用的是自适应模型,那么如何实现静态模型呢?其实很简单。对信息 bccb 我们统计出其中只有两个字符,概率分布为 Pb = 0.5,Pc = 0.5。我们在压缩过程中不必再更新此概率分布,每次对区间的划分都依照此分布即可,对上例也就是每次都平分区间。这样,我们的压缩过程可以简单表示为:

               输出区间的下限      输出区间的上限-------------------------------------------------- 压缩前           0.0                1.0 输入 b           0.0                0.5 输入 c           0.25               0.5 输入 c           0.375              0.5 输入 b           0.375              0.4375

我们看出,最后的输出区间在 0.375 - 0.4375 之间,甚至连一个十进制位都没有确定,也就是说,整个信息根本用不了一个十进制位。如果我们改用二进制来表示上述过程的话,我们会发现我们可以非常接近该信息的熵值(有的读者可能已经算出来了,该信息的熵值为 4 个二进制位)。

为什么用自适应模型?

既然我们使用静态模型可以很好地接近熵值,为什么还要采用自适应模型呢?

要知道,静态模型无法适应信息的多样性,例如,我们上面得出的概率分布没法在所有待压缩信息上使用,为了能正确解压缩,我们必须再消耗一定的空间保存静态模型统计出的概率分布,保存模型所用的空间将使我们重新远离熵值。其次,静态模型需要在压缩前对信息内字符的分布进行统计,这一统计过程将消耗大量的时间,使得本来就比较慢的算术编码压缩更加缓慢。

另外还有最重要的一点,对较长的信息,静态模型统计出的符号概率是该符号在整个信息中的出现概率,而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率,换句话说,自适应模型得到的概率分布将有利于对信息的压缩。

  评论这张
 
阅读(262)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017