虚拟主机怎么上传网站,在线优化seo,建设银行临夏分行网站,海口模板建站定制向极限挑战#xff1a;算术编码
(转) http://blog.csdn.net/hhf383530895/archive/2009/08/24/4478605.aspx
我们在上一章中已经明白#xff0c;Huffman 编码使用整数个二进制位对符号进行编码#xff0c;这种方法在许多情况下无法得到最优的压缩 效果。假设某个字符的出…向极限挑战算术编码
(转) http://blog.csdn.net/hhf383530895/archive/2009/08/24/4478605.aspx
我们在上一章中已经明白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.3333b 从 0.3333 到 0.6667c 从 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/4Pb 2/4Pc 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/5Pb 2/5Pc 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/6Pb 2/6Pc 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.5Pc 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 个二进制位。
为什么用自适应模型
既然我们使用静态模型可以很好地接近熵值为什么还要采用自适应模型呢
要知道静态模型无法适应信息的多样性例如我们上面得出的概率分布没法在所有待压缩信息上使用为了能正确解压缩我们必须再消耗一定的空间保存静态模型统计出的概率分布保存模型所用的空间将使我们重新远离熵值。其次静态模型需要在压缩前对信息内字符的分布进行统计这一统计过程将消耗大量的时间使得本来就比较慢的算术编码压缩更加缓慢。
另外还有最重要的一点对较长的信息静态模型统计出的符号概率是该符号在整个信息中的出现概率而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率换句话说自适应模型得到的概率分布将有利于对信息的压缩可以说结合上下文的自适应模型的信息熵建立在更高的概率层次上其总熵值更小好的基于上下文的自适应模型得到的压缩结果将远远超过静态模型。
自适应模型的阶
我们通常用“阶”(order)这一术语区分不同的自适应模型。本章开头的例子中采用的是 0 阶自适应模型也就是说该例子中统计的是符号在已输入信息中的出现概率没有考虑任何上下文信息。
如果我们将模型变成统计符号在某个特定符号后的出现概率那么模型就成为了 1 阶上下文自适应模型。举例来说我们要对一篇英文文本进行编码我们已经编码了 10000 个英文字符刚刚编码的字符是 t下一个要编码的字符是 h。我们在前面的编码过程中已经统计出前 10000 个字符中出现了 113 次字母 t其中有 47 个 t 后面跟着字母 h。我们得出字符 h 在字符 t 后的出现频率是 47/113我们使用这一频率对字符 h 进行编码需要 -log2 (47/113) 1.266 位。
对比 0 阶自适应模型如果前 10000 个字符中 h 的出现次数为 82 次则字符 h 的概率是 82/10000我们用此概率对 h 进行编码需要 -log2 (82/10000) 6.930 位。考虑上下文因素的优势显而易见。
我们还可以进一步扩大这一优势例如要编码字符 h 的前两个字符是 gt而在已经编码的文本中 gt 后面出现 h 的概率是 80%那么我们只需要 0.322 位就可以编码输出字符 h。此时我们使用的模型叫做 2 阶上下文自适应模型。
最理想的情况是采用 3 阶自适应模型。此时如果结合算术编码对信息的压缩效果将达到惊人的程度。采用更高阶的模型需要消耗的系统 空间和时间至少在目前还无法让人接受使用算术压缩的应用程序 大多数采用 2 阶或 3 阶的自适应模型。
转义码的作用
使用自适应模型的算术编码算法必须考虑如何为从未出现过的上下文编码。例如在 1 阶上下文模型中需要统计出现概率的上下文可能有 256 * 256 65536 种因为 0 - 255 的所有字符都有可能出现在 0 - 255 个字符中任何一个之后。当我们面对一个从未出现过的上下文时比如刚编码过字符 b要编码字符 d而在此之前d 从未出现在 b 的后面该怎样确定字符的概率呢
比较简单的办法是在压缩开始之前为所有可能的上下文分配计数为 1 的出现次数如果在压缩中碰到从未出现的 bd 组合我们认为 d 出现在 b 之后的次数为 1并可由此得到概率进行正确的编码。使用这种方法的问题是在压缩开始之前在某上下文中的字符已经具有了一个比较小的频率。例如对 1 阶上下文模型压缩前任意字符的频率都被人为地设定为 1/65536按照这个频率压缩开始时每个字符要用 16 位编码只有随着压缩的进行出现较频繁的字符在频率分布图上占据了较大的空间后压缩效果才会逐渐好起来。对于 2 阶或 3 阶上下文模型情况就更糟糕我们要为几乎从不出现的大多数上下文浪费大量的空间。
我们通过引入“转义码”来解决这一问题。“转义码”是混在压缩数据流中的特殊的记号用于通知解压缩程序下一个上下文在此之前从未出现过需要使用低阶的上下文进行编码。
举例来讲在 3 阶上下文模型中我们刚编码过 ght下一个要编码的字符是 a而在此之前ght 后面从未出现过字符 a这时压缩程序输出转义码然后检查 2 阶的上下文表看在此之前 ht 后面出现 a 的次数如果 ht 后面曾经出现过 a那么就使用 2 阶上下文表中的概率为 a 编码否则再输出转义码检查 1 阶上下文表如果仍未能查到则输出转义码转入最低的 0 阶上下文表看以前是否出现过字符 a如果以前根本没有出现过 a那么我们转到一个特殊的“转义”上下文表该表内包含 0 - 255 所有符号每个符号的计数都为 1并且永远不会被更新任何在高阶上下文中没有出现的符号都可以退到这里按照 1/256 的频率进行编码。
“转义码”的引入使我们摆脱了从未出现过的上下文的困扰可以使模型根据输入数据的变化快速 调整到最佳位置并迅速减少对高概率符号编码所需要的位数。
存储空间问题
在算术编码高阶上下文模型的实现中对内存的需求量是一个十分棘手的问题。因为我们必须保持对已出现的上下文的计数而高阶上下文模型中可能出现的上下文种类又是如此之多数据结构的设计将直接影响到算法实现的成功与否。
在 1 阶上下文模型中使用数组来进行出现次数的统计是可行的但对于 2 阶或 3 阶上下文模型数组大小将依照指数规律增长现有计算机的内存满足不了我们的要求。
比较聪明的办法是采用树结构存储所有出现过的上下文。利用高阶上下文总是建立在低阶上下文的基础上这一规律我们将 0 阶上下文表存储在数组中每个数组元素包含了指向相应的 1 阶上下文表的指针1 阶上下文表中又包含了指向 2 阶上下文表的指针……由此构成整个上下文树。树中只有出现过的上下文才拥有已分配的节点没有出现过的上下文不必占用内存空间。在每个上下文表中也无需保存所有 256 个字符的计数只有在该上下文后面出现过的字符才拥有计数值。由此我们可以最大限度地减少空间消耗。
资源
关于算术压缩具体的设计和实现请参考下面给出的示例程序。
程序 Arith-N 由 League for Programming Freedom 的 Mark Nelson 提供由王笨笨在 Visual C 5.0 环境下编译、调试 通过。
Arith-N 包含 Visual C 工程 ArithN.dsp 和 ArithNExpand.dsp分别对应了压缩和解压缩程序 an.exe 与 ane.exe。
Arith-N 是可以在命令行指定阶数的 N 阶上下文自适应算术编码通用压缩、解压缩程序由于是用作教程示例为清晰起见在某些地方并没有刻意进行效率 上的优化 。
所有源程序包装在文件 .NET /wangyg/tech/benben/src/Arith-N.zipArith-N.zip 中。 本文来自CSDN博客转载请标明出处http://blog.csdn.net/pyramide/archive/2010/01/12/5172334.aspx
