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

yeye55的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

PPM压缩算法的分析与实现 - 第七章 信息继承  

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

  下载LOFTER 我的照片书  |

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

第七章 信息继承

7.1 前言

  在PPM模型中,如果一个上下文出现了逃逸。那么在更新PPM模型时,需要将当前符号添加到这个上下文中。当一个符号被添加到一个上下文中时,这个符号需要设置一个初始频度(Initial Freq)。在一般情况下,符号的初始频度都是设置为1。当符号的初始频度为1时,需要经过一段时间的编码,才能让符号的频度稳定下来,从而反应出这个符号的概率统计特征。通过对PPM模型的观察我们可以发现,一个符号在当前上下文中的频度信息与这个符号在父上下文中的频度信息具有一定的相关性。这就意味着,当我们把一个符号添加到当前上下文中时,可以使用这个符号在父上下文中的频度信息,来计算这个符号在当前上下文中的初始频度。即,符号在当前上下文中的初始频度继承了来自父上下文中的频度信息。这就是本章将要介绍的信息继承(Information Inheritance,II)方案。II方案最早是由Dmitry Shkarin在2001年提出[8],并且应用在了PPMII(PPMd)算法[8,10]中。使用II方案可以让模型中的符号频度更快的稳定下来,从而有效的提高算法的压缩率。不仅如此,在使用II方案时,只有当符号被添加到上下文中时才需要计算初始频度。所以,II方案对于算法耗时的影响不会很大。

  本章将会介绍如何利用父上下文中的频度信息来计算符号的初始频度。本章除了会给出一个在方案4.1上整合II方案的实现方案,还会讨论将II方案与SEE方案和LOE方案进行整合的实现方案。

7.2 计算初始频度

  先来看一个例子,假设我们从4阶上下文“ABCD”开始编码一个符号“E”。在上下文“ABCD”和上下文“BCD”中都没有找到符号“E”,最后在上下文“CD”中找到了符号“E”。那么2阶上下文“CD”就是匹配上下文。更新时我们需要在上下文“ABCD”和上下文“BCD”中添加符号“E”,符号“E”在这两个上下文中的初始频度可以根据符号“E”在上下文“CD”中的频度来进行计算,这就是II方案。

  在实现II方案时,首先要确定一个计算初始频度的公式。为了更好的描述计算公式,我们需要约定一些公式变量和表达式。设si为当前上下文,那么我们可以用sk (k < i, k = d(a))来表示与si同一分支的匹配上下文。我们需要在当前上下文中添加一个符号,我们用f0(a|si)来表示符号a在当前上下文si中的初始频度。注意一点,在计算f0(a|si)的时候,f0(a|si)的值是没有包含在T(si)中的。另外,上下文sk有可能是上下文si的父上下文,也有可能是上下文si的祖先一类上下文。在使用II方案的时候,f0(a|si)的值就是根据上下文sk中的频度信息来进行计算的。一种比较简单的计算方法就是让符号a在上下文si中的频度比例与符号a在上下文sk中的频度比例保持完全一致。其对应的计算公式如公式1所示。

  公式1过于简单,除了频度比例我们还有许多其它需要考虑的信息。其中一个就是符号数量。在我们的模型中,上下文sk中的符号数量肯定会大于等于上下文si中的符号数量。符号数量也会影响到频度的比例关系。所以在计算初始频度的时候,应该将上下文中的符号数量考虑进来。另外,上下文sk有可能是上下文si的祖先一类上下文。在当前分支上,上下文si与上下文sk之间可能还会出现多个上下文。如果上下文sk是上下文si的比较久远的祖先上下文,那么计算初始频度的风险也比较大。所以,在上下文si与上下文sk之间出现的上下文的频度信息也应该加入到初始频度的计算公式中来。例如在本节开始的例子中,在4阶上下文“ABCD”中添加符号“E”时,符号“E”的初始频度就是根据2阶上下文“CD”中的频度信息来进行计算的。这当中间隔着3阶上下文“BCD”,那么上下文“BCD”中的频度信息也应该被考虑进来。结合上述几点,我们对公式1进行修改,其修改后的结果如公式2所示。

  在公式2中,表示了在上下文si与上下文sk之间出现的所有上下文的总计频度的总和。我们称为累积总计频度。当上下文sk是上下文si的父上下文时,则。如果上下文sk是上下文si的越久远的祖先上下文时,那么的值就越大。的计算公式如公式3所示。

  公式2综合考虑了频度比例、符号数量、累积总计频度等各种信息。只要对公式2进行变换,我们就可以得到计算初始频度f0(a|si)的公式。不过,这里还有一种情况需要进行考虑。在CT结构中进行扩展上下文的操作时,需要新建上下文节点。新建的上下文是一个二元上下文,二元上下文中仅有符号的初始频度也是需要进行计算的。此时,新建的二元上下文中没有任何的频度信息可供参考。即,T(si) = 0同时m(si) = 0。不仅如此,扩展上下文时新建的所有上下文都位于同一分支,这意味着对于任何一个新建的上下文都会有。在这种情况下计算初始频度就需要对公式2进行适当的调整。现在,我们对公式2进行变换,然后在变换后的公式中增加一个对于T(si) = 0情况的处理。那么我们就可以得到初始频度f0(a|si)的计算公式,最终的计算公式如公式4所示。

  注意一点,在公式4中增加了一个参数2。测试表明,增加这个参数可以有效的改善算法的压缩率。对于公式4可以满足两种情况下的初始频度的计算。第一种情况就是在进行扩展上下文的操作时,对于新建的二元上下文中仅有符号的初始频度的计算。此时T(si) = 0。这种情况只有在进行扩展上下文的操作时才会出现。另一种情况就是将一个符号添加到一个上下文中时,对于添加符号的初始频度的计算。此时T(si) ≠ 0。这种情况只有在更新模型时才会出现。除此之外还有另外的两种情况,在这两种情况下我们不需要使用公式4来进行初始频度的计算。第一种情况就是当上下文sk是一个二元上下文时,即m(sk) = 1。此时上下文si肯定也是一个二元上下文。那么符号a在上下文si中的初始频度直接复制于符号a在上下文sk中的频度,即f0(a|si) = f(a|sk)。这种情况只有在进行扩展上下文的操作时才会出现。另一种情况就是符号a是在当前模型中的第一次出现。此时符号a只有在-1阶上下文中才能得到匹配。在这种情况下,在当前模型中没有任何相关的频度信息可供参考。所以,此时我们只能将符号a的初始频度设置为1。这种情况只有在更新模型时才会出现。

  另外,在使用公式4计算符号的初始频度时,得到的计算结果可能会比较大。使用较大的初始频度可能会对上下文中的其它符号的预测概率带来不利的影响。所以,在计算符号的初始频度时,通常对初始频度的最大值进行限制。在本文的实现程序中,将初始频度的最大值限制到7。除了需要限制初始频度的最大值,还需要防止初始频度为0。在我们当前使用的模型中不允许出现零频的符号。所以如果计算得到的初始频度为0,那么就把初始频度设置为1。

  最后说明一点,计算初始频度的公式并不是一成不变的。可以根据数据的特征,对计算初始频度的公式进行适当的调整和修改。另外,本文介绍的计算初始频度的公式同Dmitry Shkarin论文[8]中的公式,在细节上有所不同。感兴趣的读者可以参阅对应的论文[8]

7.3 方案实现

  当使用了II方案以后,需要对实现过程中的一些细节进行修改。首先就是在更新符号频度时的增量。一般情况下,在更新符号频度的时候都是将符号的频度加1。在使用了II方案以后,由于考虑到计算得到的初始频度不一定会非常的准确。所以,在更新符号频度的时候,将符号频度的增量设置为4。即,每次更新符号频度时将符号的频度加4。这样做还有另外一个好处。在使用II方案时,符号的初始频度是根据父上下文中的频度信息来进行计算的。每当我们进行削减频度操作的时候,低频符号的频度比例都会被降低。如果增加更新符号频度时的增量,就可以减慢频度比例的降低程度。这样在计算初始频度时,对于父上下文中的频度信息的收集将更加的有利。

  使用II方案时仍然需要进行逃逸估计。与方案4.1类似,这里使用方法D来作为逃逸估计的方法。由于我们将更新符号频度时的增量设置为4,这就相当于将所有符号的频度都放大了4倍。所以,这时就需要对逃逸码频度的计算方法进行适当的调整。以方法D为基础进行适当的调整,那么我们就可以确定逃逸码频度以及相关预测概率的计算公式。其相关的计算公式如下所示。

  在实现II方案的时候,我们需要统计累积总计频度的值。累积总计频度将会在计算初始频度时使用。统计累积总计频度可以在编码过程中完成。在一个上下文中完成编码以后,如果这个上下文不是匹配上下文,那么就可以将这个上下文中的总计频度统计到累积总计频度中来。在统计时需要注意几点。首先,统计时使用的是上下文中的总计频度,不能使用排除符号后的总计频度。另外,在编码时我们会跳过符号数相同的上下文,这些上下文中的总计频度也要被统计进来。

  总的来说,实现II方案还是比较简单的。在方案4.1上整合II方案所需要进行的修改也是比较少的。不仅如此,II方案的性能也是非常不错的。使用II方案不会增加太多的算法耗时,但是却可以有效的提高算法的压缩率。

7.4 方案整合II+LOE

  从算法结构上来说,II方案和LOE方案并不冲突,可以把这两个方案整合在一起。在整合时需要进行的修改也不多。不过有一点需要注意。在实现LOE方案的时候,我们将MPS对应的节点项放置在节点项数组的最前面。在更新模型添加符号的时候,如果不使用II方案,那么符号的初始频度都是1。在这种情况下,新增符号不可能成为MPS。但是,如果使用了II方案,那么符号的初始频度就是计算得到的。在这种情况下,新增符号将有可能成为MPS。所以,在整合II方案后,每次添加符号时需要对符号的初始频度进行检查。如果新增符号是MPS,那么就要把这个符号移动到节点项数组的最前面。

  虽然从算法结构上来说,II方案和LOE方案并不冲突。但是这两个方案整合后的实际性能却并不理想。这一点可以从后面的测试与分析中看出来。这说明,II方案与LOE方案相互之间的兼容性并不好。

7.5 方案整合SEE+II

  II方案同样可以与SEE方案进行整合。整合后仍然使用两个SEE模型,一个供二元上下文使用,另一个供多元上下文使用。当然在整合的时候需要对量化策略进行适当的调整。在对量化策略进行调整的时候,必需注意一点。在使用II方案时,我们将更新符号频度时的增量设置为4。所以在进行相关量化操作的时候,需要对量化数值的范围进行调整。除此之外,量化的策略和SEE上下文的结构与6.2节中的描述基本一致。量化生成的两种SEE上下文的结构如图7.1和图7.2所示。对应的量化代码请参考本文的配套项目,这里不再给出。

图7.1 由二元上下文量化生成的SEE上下文的结构

图7.2 由多元上下文量化生成的SEE上下文的结构

7.6 方案整合SEE+II+LOE

  整合变体方案的数量是没有限制的。只要这些变体方案在算法结构上没有冲突,那么就可以把它们全部都整合到一起。当然整合后的性能是否优异,那就是另外一回事了。这里将SEE方案、II方案和LOE方案全部都整合到一起。在整合的过程中,上面两小节中提到的内容都需要值得注意。第一,每次更新模型添加符号的时候,都需要对符号的初始频度进行检查。如果新增符号是MPS,那么就需要把这个符号移动到节点项数组的最前面。第二,在进行相关量化操作的时候,需要对量化数值的范围进行调整。

  在本节的这个整合方案中仍然需要使用两个SEE模型,一个供估计上下文使用,另一个供多元上下文使用。其中SEE模型的量化策略和SEE上下文的结构与6.4节中的描述完全相同,只不过在量化数值的范围上有所不同。所以,其细节部份可以去参考6.4节中的描述。另外,对应的量化代码请参考本文的配套项目,这里不再给出。

7.7 测试与分析

  现在我们以方案4.1(PPMD)为基础整合II方案,并以此确定一套新的实现方案。这套方案命名为方案7.1(PPMD+II)。然后,我们以方案7.1为基础整合LOE方案,并以此确定一套新的实现方案。这套方案命名为方案7.2(PPMD+II+LOE)。接着,我们以方案6.1(PPM+SEE)为基础整合II方案,并以此确定一套新的实现方案。这套方案命名为方案7.3(PPM+SEE+II)。同时,我们以方案7.3为基础整合LOE方案,并以此确定一套新的实现方案。这套方案命名为方案7.4(PPM+SEE+II+LOE)。对于方案7.1、方案7.2、方案7.3和方案7.4这四种方案的描述如下所示。

方案7.1 以方案4.1(PPMD)为基础,整合II方案;使用II方案时,利用公式来计算符号的初始频度,并对方法D进行适当的调整;其它描述与方案4.1相同(PPMD+II)。
方案7.2 以方案7.1(PPMD+II)为基础,整合LOE方案;使用LOE方案选择上下文时,以MPS-P作为置信度,并选择置信度最大的上下文作为估计上下文;其它描述与方案7.1相同(PPMD+II+LOE)。
方案7.3 以方案6.1(PPM+SEE)为基础,整合II方案;使用II方案时,利用公式来计算符号的初始频度;其它描述与方案6.1相同(PPM+SEE+II)。
方案7.4 以方案7.3(PPM+SEE+II)为基础,整合LOE方案;使用SEE方案时,建立两个SEE模型,一个供估计上下文使用,一个供多元上下文使用;使用LOE方案选择上下文时,以MPS-P作为置信度,并选择置信度最大的上下文作为估计上下文;其它描述与方案7.3相同(PPM+SEE+II+LOE)。

  现在我们对方案4.1(PPMD)、方案5.1(PPMD+LOE)和方案7.1(PPMD+II)这三套方案进行压缩率的对比测试,测试时使用5阶的最高阶数对语料库[14]中的18个文件进行压缩。其测试结果如表7.1所示。

文件 输入大小
(字节)
方案4.1 方案5.1 方案7.1
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
bib 111261 26089 1.876 25614 1.842 25068 1.802
book1 768771 220763 2.297 218996 2.279 215362 2.241
book2 610856 150272 1.968 149213 1.954 145982 1.912
geo 102400 60303 4.711 60240 4.706 58448 4.566
news 377109 111441 2.364 110504 2.344 108491 2.302
obj1 21504 10081 3.750 10194 3.792 9815 3.651
obj2 246814 74620 2.419 74506 2.415 71861 2.329
paper1 53161 15533 2.338 15363 2.312 15011 2.259
paper2 82199 23789 2.315 23521 2.289 22976 2.236
paper3 46526 14999 2.579 14844 2.552 14524 2.497
paper4 13286 4805 2.893 4755 2.863 4672 2.813
paper5 11954 4468 2.990 4429 2.964 4348 2.910
paper6 38105 11527 2.420 11410 2.395 11135 2.338
pic 513216 51682 0.806 51447 0.802 51391 0.801
progc 39611 11781 2.379 11673 2.358 11354 2.293
progl 71646 15179 1.695 14989 1.674 14582 1.628
progp 49379 10590 1.716 10382 1.682 10096 1.636
trans 93695 17512 1.495 17398 1.486 16708 1.427
总计 3251493 835434 2.056 829478 2.041 811824 1.997

表7.1 压缩率对比测试结果

  从表7.1的数据中可以看出,使用II方案可以有效的改善算法的压缩率。在使用最高5阶进行压缩时,从总计上看方案7.1(PPMD+II)的压缩率比方案4.1(PPMD)提高了2.87%。不仅如此,方案7.1的压缩率也比方案5.1(PPMD+LOE)更为优秀。

  现在我们对方案4.1(PPMD)、方案5.1(PPMD+LOE)和方案7.1(PPMD+II)这三套方案进行测试,测试时分别使用从3阶到20阶的不同最高阶数对语料库[14]中的18个文件进行压缩。每次压缩后记录其总计的压缩率,最后将这些压缩率绘制成两条曲线。其结果如图7.3所示。

图7.3 使用不同阶数的压缩率对比

  从图7.3中我们可以看出,使用不同的最高阶数进行压缩,方案7.1(PPMD+II)的压缩率都会优于方案4.1(PPMD)和方案5.1(PPMD+LOE)。类似的,在方案7.1中不断提高最高阶数,同样也会出现压缩率逐步降低的情况。在对于方案7.1的测试中可以发现,与方案5.1相同。当使用最高6阶进行压缩时,方案7.1压缩率最好。如果再提高最高阶数,压缩率就会出现逐步降低的情况。不过,压缩率降低的幅度非常的小。其降低的幅度基本等同于方案5.1。这意味着,II方案对于不同的最高阶数的适应能力也非常的好。

  现在我们对方案7.2(PPMD+II+LOE)、方案7.3(PPM+SEE+II)和方案7.4(PPM+SEE+II+LOE)这三套方案进行压缩率的对比测试,测试时使用5阶的最高阶数对语料库[14]中的18个文件进行压缩。其测试结果如表7.2所示。

文件 输入大小
(字节)
方案7.2 方案7.3 方案7.4
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
bib 111261 25313 1.820 24600 1.769 25053 1.801
book1 768771 215758 2.245 212040 2.207 213159 2.218
book2 610856 146802 1.923 144152 1.888 145701 1.908
geo 102400 59268 4.630 55654 4.348 57978 4.530
news 377109 109001 2.312 106988 2.270 107729 2.285
obj1 21504 10016 3.726 9694 3.606 9984 3.714
obj2 246814 72953 2.365 71116 2.305 72418 2.347
paper1 53161 15143 2.279 14810 2.229 14968 2.252
paper2 82199 23088 2.247 22594 2.199 22797 2.219
paper3 46526 14616 2.513 14301 2.459 14428 2.481
paper4 13286 4684 2.820 4601 2.770 4625 2.785
paper5 11954 4377 2.929 4299 2.877 4345 2.908
paper6 38105 11235 2.359 10983 2.306 11111 2.333
pic 513216 51306 0.800 50369 0.785 50269 0.784
progc 39611 11462 2.315 11214 2.265 11366 2.296
progl 71646 14762 1.648 14293 1.596 14482 1.617
progp 49379 10213 1.655 9919 1.607 10061 1.630
trans 93695 17083 1.459 16094 1.374 16547 1.413
总计 3251493 817080 2.010 797721 1.963 807021 1.986

表7.2 压缩率对比测试结果

  从表7.2的数据中可以看出,方案7.2(PPMD+II+LOE)的压缩率并不是很理想。虽然,与表7.1中方案5.1(PPMD+LOE)的压缩率相比,方案7.2的压缩率得到了改善。但是,与表7.1中方案7.1(PPMD+II)的压缩率相比,方案7.2的压缩率反而出现了下降。这证明II方案与LOE方案的兼容性并不好,同时整合这两个方案只会降低算法的压缩率。从表7.2中方案7.4(PPM+SEE+II+LOE)的压缩率中可以看出,即使整合了SEE方案也挽救不了II方案和LOE方案这对冤家。方案7.4的压缩率明显要比方案7.3(PPM+SEE+II)来得更低。

  现在我们对方案7.2(PPMD+II+LOE)、方案7.3(PPM+SEE+II)和方案7.4(PPM+SEE+II+LOE)这三套方案进行测试,测试时分别使用从3阶到20阶的不同最高阶数对语料库[14]中的18个文件进行压缩。每次压缩后记录其总计的压缩率,最后将这些压缩率绘制成两条曲线。其结果如图7.4所示。

图7.4 使用不同阶数的压缩率对比

  从图7.4中我们可以看出,方案7.3(PPM+SEE+II)的压缩率是最优秀的。不仅如此,在使用不同的最高阶数对方案7.3的测试中我们可以发现,方案7.3的压缩率是随着最高阶数的提高而不断提高的。这意味着,既使不使用LOE方案,将SEE方案与II方案整合也可以做到让算法的压缩率随着最高阶数的提高而提高。另外,方案7.4(PPM+SEE+II+LOE)虽然也可以做到这一点。但是从图7.4中可以看出,方案7.4的压缩率始终低于方案7.3。

  现在我们对方案4.1(PPMD)、方案5.1(PPMD+LOE)和方案7.1(PPMD+II)这三套方案进行压缩耗时和解压缩耗时的对比测试,测试时使用最高5阶来进行压缩。其测试结果如表7.3所示。

文件 方案4.1 方案5.1 方案7.1
压缩耗时 解压缩耗时 压缩耗时 解压缩耗时 压缩耗时 解压缩耗时
bib 47 47 78 63 47 47
book1 500 516 734 750 500 563
book2 328 344 500 516 328 375
geo 172 187 157 172 171 187
news 234 265 329 360 250 265
obj1 15 31 15 31 31 32
obj2 172 172 234 219 156 188
paper1 16 31 31 31 16 31
paper2 31 47 63 47 31 31
paper3 32 16 31 32 31 32
paper4 0 15 0 15 0 0
paper5 0 15 15 0 16 0
paper6 16 16 16 16 16 15
pic 109 125 188 203 109 140
progc 16 15 31 16 31 16
progl 16 31 32 47 32 31
progp 15 15 31 15 15 31
trans 15 31 47 47 31 32

表7.3 算法耗时对比测试结果(单位毫秒)

  从表7.3的数据中可以看出,使用II方案对于算法的耗时影响不大。使用II方案时,虽然需要通过复杂的运算来得到符号的初始频度,但是只有当符号被添加到上下文中时才需要计算初始频度。在刚刚开始编码的时候,需要大量的向模型中添加符号。但是,当编码了部份数据以后,模型就会稳定下来。此时,添加符号的操作也会大幅减少。所以就总体而言,使用II方案对于算法的耗时影响不会很大。与之相比,使用LOE方案则会大幅增加算法的耗时。考虑到II方案和LOE方案一样,与SEE方案整合后都可以让算法的压缩率随着最高阶数的提高而提高。那么II方案明显要比LOE方案更加优秀。

  现在我们对方案7.2(PPMD+II+LOE)、方案7.3(PPM+SEE+II)和方案7.4(PPM+SEE+II+LOE)这三套方案进行压缩耗时和解压缩耗时的对比测试,测试时使用最高5阶来进行压缩。其测试结果如表7.4所示。

文件 方案7.2 方案7.3 方案7.4
压缩耗时 解压缩耗时 压缩耗时 解压缩耗时 压缩耗时 解压缩耗时
bib 79 78 63 78 188 172
book1 750 781 657 719 1406 1391
book2 500 532 406 469 1047 1016
geo 172 187 187 219 218 218
news 343 359 313 344 656 672
obj1 16 15 15 15 31 31
obj2 234 234 203 219 438 438
paper1 31 47 31 32 78 79
paper2 62 63 62 63 140 141
paper3 31 47 31 47 78 78
paper4 0 0 0 0 16 32
paper5 16 0 16 15 31 16
paper6 31 31 31 31 62 63
pic 203 219 141 172 531 515
progc 31 31 15 15 63 63
progl 32 31 31 47 94 94
progp 32 31 15 31 63 62
trans 47 63 32 31 125 125

表7.4 算法耗时对比测试结果(单位毫秒)

  从表7.4的数据中可以看出,在这3种方案中方案7.3(PPM+SEE+II)的算法耗时最少,方案7.4(PPM+SEE+II+LOE)的算法耗时最多。对于方案7.3来说,使用SEE方案和II方案都不会增加太多的算法耗时。所以从总体上说,方案7.3的算法耗时最优秀。方案7.4则相反,LOE方案会占用大量的算法耗时。LOE方案与其它方案整合后,算法耗时还会进一步的增加。

  通过上面的测试我们可以发现。II方案与LOE方案并不兼容。整合了II方案以后,如果再整合LOE方案,那么算法的压缩率将出现下降。而且,这样的整合方案还会大幅增加算法的耗时。与之相反,SEE方案与II方案的整合就非常的优秀。SEE方案与II方案整合后不仅可以做到让算法的压缩率随着最高阶数的提高而提高,而且整合后的算法耗时也不会增加太多。所以说,方案7.3(PPM+SEE+II)是最具有可行性的一个实现方案。

  不过我们需要注意一点,II方案与LOE方案的不兼容主要集中在置信度和初始频度的计算上。很明显,当II方案使用一个公式计算符号的初始频度以后,使得符号自身的频度以及符号在上下文中的频度比例都发生了非常大的变化。这种变化明显影响到了MPS-P的计算。此时再以MPS-P作为置信度已经不再合适。从算法的结构上来说,II方案与LOE方案并不冲突。LOE方案是根据一定的标准抛弃部份的上下文来提高算法的压缩率。而II方案是根据一个拟定的公式来计算符号的初始频度从而提高算法的压缩率。现在的问题是,是否可以拟定一个新的置信度的计算方法或者是一个新的判断标准,用来选择估计上下文。从而提高LOE方案与II方案的兼容性,并将这两个方案的优点合并起来。实际上这个问题是非常难解决的。退一步说,即使解决了这个问题也很有可能会使算法的耗时进一步的增加。当然,在这个问题上本人的研究不深,感兴趣的读者可以花点时间自行研究一下。

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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