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

yeye55的博客

编程就象品一杯清茶,清淡却又深厚。

 
 
 

日志

 
 
关于我

宅男一只,喜欢编程。没事的时候就喜欢抱着电脑看看电影、看看动漫、听听音乐、打打网游、逛逛论坛。清静的时候喜欢专研编程技术,但是发现自己至今仍然只是一只三脚猫。

网易考拉推荐

PPM压缩算法的分析与实现 - 第九章 总结  

2011-11-08 11:05:21|  分类: 数据压缩算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  本论文题目:PPM压缩算法的分析与实现,作者:叶叶,于2011年11月8日在网易博客上发表。页面地址:http://yeye55blog.blog.163.com/blog/static/197241021201110715759577/ 。本论文全文及相关配套程序可以在上述页面中下载。请尊重他人劳动成果,转载或引用时请注明出处。

第九章 总结

9.1 总述

  PPM算法是一种基于概率统计模型的自适应压缩算法。当利用PPM算法编码一个符号的时候。首先需要在当前的上下文中编码这个符号,利用上下文中的统计信息来计算预测概率。如果是匹配则输出符号的预测概率,然后结束编码。如果是逃逸则输出逃逸的预测概率,然后退回到低1阶的上下文中重新开始一轮新的编码。如果符号没有在模型中出现,最终将会退回到-1阶上下文中。在-1阶上下文中所有的符号都有出现,而且频度保持不变。可见,PPM算法涉及到多种阶数上下文之间的相互操作。所以,PPM算法的结构十分复杂。

  PPM算法的实现主要包括了三个方面的内容,分别是统计模型的实现、专用内存管理器的实现和概率编码器的实现。在本文中对于前面两个方面进行了详细的介绍。在PPM算法中,统计模型需要统计在编码过程中出现了哪些上下文,在这些上下文中出现了哪些符号,符号对应的频度又是多少。在进行编码的时候需要根据这些统计信息来计算符号的预测概率。在编码完成一个符号以后还需要对这些统计信息进行更新。在实现的时候,可以使用CT结构来建立整个模型。与传统的Trie结构相比,CT结构更节约内存而且速度更快。在编码和更新的过程中,还可以使用许多优化方案来提高算法的性能。在本文中对于这些优化方案都进行了一一的介绍。在PPM算法实现的时候,CT结构会占用较大的内存。同时在CT结构中还会出现大量的节点,这些节点的内存占用都很零碎。所以,为了提高算法的总体性能,通常需要设计一个专用内存管理器。这个专用内存管理器专门针对CT结构的实现而设计,并且根据PPM算法的特点而进行优化。最后,PPM算法本身并不输出数据。PPM算法只是根据模型中的统计信息计算一个预测概率,然后将这个预测概率交给概率编码器。概率编码器对于输入的预测概率进行编码然后输出。对于概率编码器的说明本文没有涉及,相关的资料请参考我写的另外一篇论文[13]

  此外,在本文中还详细介绍了四种变体方案,分别是LOE方案、SEE方案、II方案和ULC方案。其中,LOE方案利用置信度的大小来抛弃部份的上下文,通过减少逃逸预测概率的输出来提高算法的压缩率。SEE方案利用一个二次模型来计算逃逸的预测概率,通过提高逃逸预测概率的准确性来提高算法的压缩率。II方案利用模型中已有的统计信息来计算符号的初始频度,通过加快模型的稳定来提高算法的压缩率。ULC方案不对模型中上下文的长度进行限制,通过最大阶数的无限增加来提高算法的压缩率。在这些方案中,II方案的性能最好。II方案可以有效的提升算法的压缩率,而且不会增加算法的内存占用,对于算法耗时的影响也非常小。其次是SEE方案。SEE方案也可以有效的提升算法的压缩率,但是使用SEE方案将会增加算法的内存占用和耗时。不过SEE方案的兼容性很好,可以和其它的变体方案一起进行整合使用。接着是LOE方案。LOE方案也可以提高算法的压缩率,但是使用LOE方案将会大幅增加算法的耗时。这个缺点在较高阶数的情况下尤为明显。最后是ULC方案。ULC方案必需与其它方案一起整合使用。整合了ULC方案以后会使算法的内存占用和耗时成倍的增加,所以ULC方案的总体性能最低。上面这四种方案都是可以相互整合的,其中以SEE+II整合方案的性能最为优秀,其它整合方案次之。另外,II+LOE整合方案的性能最差。可见,II方案与LOE方案的兼容性并不好,同时整合这两个方案只会降低算法的压缩率。

  PPM算法的实现是非常复杂的,不仅涉及到大量数据结构的处理,还会涉及到对于各种变体方案的整合。在本文中对于这些内容都进行了详细的介绍。不仅如此,在本文中还给出了各种方案的实现方法以及不同方案之间的对比测试。在本文给出的众多实现方案当中有三种方案的可行性最高,分别是方案4.1(PPMD)、方案7.3(PPM+SEE+II)和方案8.3(PPM+SEE+II+ULC)。如果只希望使用3阶以下的最高阶数对数据进行压缩,那么可以使用方案4.1。方案4.1的算法耗时最小,但是压缩率不是很高。如果希望使用较高的最高阶数对数据进行压缩,那么可以使用方案7.3。方案7.3的算法耗时要比方案4.1更大,但是方案7.3的压缩率较高。另外,方案7.3对于从低阶到高阶的不同最高阶数的适应能力都很好。如果不在乎算法的内存占用和耗时,那么可以使用方案8.3。使用方案8.3虽然有可能提高算法的压缩率,但是算法的内存占用和耗时都会出现成倍的增加。

9.2 常见的PPM算法

  PPM算法一经提出就引起了广大研究人员的兴趣。大量的研究人员经过多年的研究,提出了众多的PPM算法的实现方案。在这里将介绍几种常见的PPM算法的实现方案。

  PPM*算法[5]是由John G. Cleary,W. J. Teahan和Ian H. Witten在1995年提出[5]来的。在PPM*算法中首次使用了CT结构来建立模型,同时PPM*算法也是首次使用ULC方案的PPM算法。在选择上下文的时候,PPM*算法使用的是确定性上下文。即,选择只包含一个符号的上下文。在进行逃逸估计的时候,PPM*算法使用的是方法C,所以这种算法也被称为PPM*C。在这里有一点需要说明,有很多资料声称PPM*算法的性能是非常优秀的,但是在当前这种观点已经是错误的。当初提出PPM*算法的时候,其它的PPM算法一般都是使用Trie结构来建立模型。PPM*算法首次使用了CT结构来建立模型,这使得它与其它PPM算法相比,在性能上得到了很大的提高。但是,并不是只有PPM*算法才能使用CT结构,其它的PPM算法也可以使用CT结构。如果大家都使用CT结构,那么PPM*算法在性能上将没有任何优势。另外,PPM*算法中使用的方法C的压缩率也不是很好。完全可以使用方法D来替换方法C,那么对应的算法可以被称为PPM*D。目前,PPM*算法只存在于资料和教科书中,在现实应用中已经很少使用PPM*算法。不过,在PPM*算法中使用的CT结构却被其它的PPM算法所采纳,并得到了广泛的使用。

  PPMZ算法[6]是由Charles Bloom在1998年提出[6]来的。在PPMZ算法中首次使用了SEE方案来进行逃逸估计。虽然在PPMZ算法中只使用了一个SEE模型,但是对应的SEE方案却是非常复杂的。在进行量化的时候,PPMZ算法对于每个上下文中的信息都生成3个逃逸上下文(Escape Context)。这3个逃逸上下文的位长各不相同,分别为7位的0阶上下文、15位的1阶上下文和16位的2阶上下文。这些逃逸上下文都将各自进行频度统计。在进行逃逸估计的时候,首先根据这3个逃逸上下文的频度来计算对应的熵(Entropy),然后利用熵值来计算各自的权重值,最后通过复杂的运算来进行加权求和,从而得到逃逸的预测概率。在计算时还需要使用到大量的对数运算和浮点运算。可以看出这样的计算是非常复杂的,同时也是十分耗时的。与之相比,在本文中介绍的SEE方案是经过简化的版本。简化后的SEE方案虽然在压缩率上有所降低,但是在总体性能上却有着大幅的提高。PPMZ算法也是一种使用了ULC方案的PPM算法。在选择上下文的时候,PPMZ算法使用的是估计上下文。将MPS-P作为置信度,同时选择置信度最大的上下文。另外,PPMZ算法在建模时使用的是哈希表(Hash Table)结构,而不是常见的CT结构。目前,PPMZ算法已经发展出了第二个版本PPMZ2,其压缩率得到了进一步的提高。不过,PPMZ算法的耗时较大,所以使用的并不是很广泛。PPMZ算法实现程序的源代码以及描述算法原理的论文[6]都可以在其官方网站[7]中下载。

  PPMII(PPMd)算法[8,10]是由Dmitry Shkarin在2001年提出[8]来的。这里需要注意一点,在描述算法原理的论文[8]中,将这个算法命名为PPMII。但是作者在发布程序[10]的时候,却将这个算法命名为PPMd。所以这两个命名属于同一种算法。另外,注意将PPMd与一般实现中的PPMD相区别。在PPMII算法中首次使用了II方案来对符号的初始频度进行计算。实际的应用已经证明II方案的性能是非常优异的。所以,虽然PPMII算法没有使用ULC方案和LOE方案,但是PPMII算法仍然保持了较高的压缩率。除了II方案,在PPMII算法中还使用了简化后的SEE方案。在PPMII算法中一共使用了两个SEE模型,一个供二元上下文使用,另一个供多元上下文使用。特殊的,对于当前开始编码的最高阶上下文。如果这个上下文不是二元上下文,那么就不使用SEE模型,而是使用一种方法D的变体来进行逃逸估计。所以说,在PPMII算法中并没有完全依赖SEE方案来进行逃逸估计。除此之外,PPMII算法还使用了CT结构、定量内存等一系列的方案来提高算法的性能。另外,在描述PPMII算法的论文[8]中,还介绍了一种复杂PPMII(Complicated PPMII,cPPMII)的算法。cPPMII算法的压缩率更高但是耗时更大。目前,PPMII算法已经发展出了PPMdh、PPMdi2、PPMdj1等多种版本。其中以PPMdh算法最为经典。在很多时候,通常以PPMdh算法的性能来代表PPM算法与其它类型的压缩算法进行性能上的对比测试。所以从某种程度上来说,PPMdh算法已经成为PPM算法的代表。不仅如此,在目前主流的压缩软件中,如WinZip、WinRAR和7-Zip等都支持以PPMdh算法为基础的PPM压缩算法的实现。所以PPMdh算法是一种使用非常广泛的PPM算法。PPMII算法实现程序[10]的源代码以及描述算法原理的论文[8]都可以在其官方网站[9]中下载。

  在这里对于上述几种PPM算法的压缩率进行一下汇总。注意一点,PPM*算法和PPMZ系列算法都使用了ULC方案,所以不需要指定最高阶数。对于PPMII算法和cPPMII算法使用8阶的最高阶数来进行压缩。最后的汇总结果如表9.1所示。

文件 PPM* PPMZ PPMZ2 v0.7 PPMII-8 cPPMII-8
bib 1.91 1.744 1.717 1.732 1.694
book1 2.40 2.213 2.195 2.192 2.136
book2 2.02 1.873 1.846 1.838 1.795
geo 4.83 4.033 4.097 4.349 4.163
news 2.42 2.242 2.205 2.205 2.160
obj1 4.00 3.665 3.661 3.536 3.507
obj2 2.43 2.230 2.241 2.206 2.154
paper1 2.37 2.222 2.214 2.194 2.152
paper2 2.36 2.214 2.185 2.181 2.130
pic 0.85 0.790 0.480 0.757 0.721
progc 2.40 2.257 2.258 2.215 2.178
progl 1.67 1.472 1.445 1.470 1.433
progp 1.62 1.477 1.450 1.522 1.489
trans 1.45 1.238 1.214 1.257 1.228
平均 2.34 2.119 2.086 2.118 2.067

表9.1 各种PPM算法的压缩率对比(单位 bpc)

  对于表9.1中的数据需要进行一下说明。其中,PPM*算法的压缩率来自John G. Cleary,W. J. Teahan和Ian H. Witten的论文[5];PPMZ算法的压缩率来自Charles Bloom的论文[6];v0.7版的PPMZ2算法的压缩率来自PPMZ算法的官方网站[7];PPMII算法和cPPMII算法的压缩率来自Dmitry Shkarin的论文[8]

9.3 结束语

  PPM算法的高压缩率和自适应的特点,使得PPM算法成为一种最有效的压缩算法。本文全面介绍了PPM压缩算法的算法结构和实现方法。本文还详细讨论了使用Trie结构和Context Trie结构建立统计模型的方法,并对这两种结构的性能进行了对比分析。同时本文还详细介绍了各种用以提高算法性能的优化方案。另外,本文对于针对PPM算法而设计的专用内存管理器的理论基础和实现方法进行了详细的介绍和说明。本文对于局部阶估计(LOE)方案、二次逃逸估计(SEE)方案、信息继承(II)方案和无限长度上下文(ULC)方案这4种变体方案的理论基础、实现方法和相互整合进行了详细的介绍和说明。最后本文还进行了大量的对比测试和比较分析。并且给出了一个切实可行的应用程序。希望本文能够对PPM压缩算法的研究人员有所帮助。

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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