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

yeye55的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

PPM压缩算法的分析与实现 - 第五章 局部阶估计  

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

  下载LOFTER 我的照片书  |

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

第五章 局部阶估计

5.1 前言

  在开始本章的内容之前,我们需要先进行一系列的测试。在方案4.1中,当我们需要编码一个符号的时候,需要从当前开始的上下文sH搜索到0阶上下文s0,从中查找匹配上下文。匹配上下文有可能是从H阶到0阶的任意一个上下文。现在我们来进行一个测试,我们使用一张计数表。每次编码一个符号的时候,如果能找到对应的匹配上下文。那么根据匹配上下文的阶数将计数表中的对应元素加1。当编码完成时,计数表中的每个元素就可以反应出对应阶数上下文中的匹配次数。我们将这张计数表称为匹配计数表。现在使用方案4.1进行测试。测试时分别使用从2阶到10阶的不同最高阶数对语料库[14]中的文件“book1”进行压缩。每次压缩时统计并输出匹配计数表。最后的汇总结果如表5.1所示。

  2阶 3阶 4阶 5阶 6阶 7阶 8阶 9阶 10阶
0阶 1745 1745 1745 1745 1745 1745 1745 1745 1745
1阶 14362 11472 11472 11472 11472 11472 11472 11472 11472
2阶 752583 37850 36662 36662 36662 36662 36662 36662 36662
3阶 717623 74462 74164 74164 74164 74164 74164 74164
4阶 644349 103956 103874 103874 103874 103874 103874
5阶 540691 113924 113908 113908 113908 113908
6阶 426849 108527 108524 108524 108524
7阶 318338 91554 91552 91552
8阶 226787 70803 70802
9阶 155986 52059
10阶 103928

表5.1 使用不同阶数压缩book1的匹配计数表(单位次)

  从匹配计数表中可以看出,编码一份数据的时候,匹配上下文主要集中哪些阶数中。从表5.1的数据中可以看出。当使用较低的最高阶数进行压缩的时候,匹配上下文主要集中在最高阶数中。但是,随着最高阶数越来越大,匹配上下文开始集中在某一阶数附近,不再集中在最高阶数中。比如在表5.1中,当使用最高10阶压缩文件“book1”时,可以明显的看出匹配上下文集中在5阶附近,而不是最高阶10阶中。另外,观察不同的最高阶数可以发现,这种匹配上下文的集中情况非常的稳定。提高最高阶数不会改变较低阶上下文中的匹配次数。这意味着,随着最高阶数越来越大,最高阶上下文中的匹配次数会变得越来越小。现在我们使用最高32阶的方案4.1对文件“book1”进行压缩。我们将压缩后输出的匹配计数表绘制成一条曲线,其结果如图5.1所示。

图5.1 使用32阶压缩book1的匹配计数表曲线

  从图5.1中我们可以明显的看到一个峰值。当使用最高32阶压缩文件“book1”时,匹配上下文主要集中在5阶附近。较高阶上下文中的匹配次数非常的少,这就引出了一个问题。在编码的时候,如果在较高阶的上下文中没有找到符号,那么我们就需要一级一级的退回到较低阶的上下文中。每退回一级都需要输出逃逸码预测概率。如果匹配上下文集中在较低阶的上下文中,那么我们使用较高的阶数进行压缩,不但不会提高压缩率反而会使压缩率降低。现在我们再次使用方案4.1进行测试,测试时分别使用从1阶到32阶的不同最高阶数对文件“book1”进行压缩。同时记录每次压缩后的压缩率,最后将这些压缩率绘制成一条曲线。其结果如图5.2所示。

图5.2 使用不同阶数压缩book1的压缩率曲线

  经测试表明,使用最高4阶压缩文件“book1”时,可以获得最好的压缩率。但是,如果继续提高阶数,那么压缩率将逐步下降。从12阶开始压缩率逐步稳定,从25阶开始压缩率保持不变。此时再提高最高阶数将没有任何意义。这种情况并不是只有文件“book1”才会出现,对于其它文件也会出现类似的情况。现在使用方案4.1进行测试,测试时分别使用从1阶到10阶的不同最高阶数对语料库[14]中的18个文件进行压缩。其压缩率如表5.2所示。

文件 1阶 2阶 3阶 4阶 5阶 6阶 7阶 8阶 9阶 10阶
bib 3.460 2.634 2.087 1.904 1.876 1.887 1.905 1.924 1.940 1.955
book1 3.610 2.902 2.456 2.297 2.297 2.341 2.391 2.429 2.455 2.472
book2 3.738 2.867 2.252 2.013 1.968 1.979 2.006 2.034 2.059 2.079
geo 4.622 4.546 4.657 4.712 4.711 4.712 4.709 4.708 4.707 4.707
news 4.131 3.243 2.631 2.401 2.364 2.374 2.391 2.406 2.417 2.426
obj1 4.463 3.880 3.770 3.746 3.750 3.758 3.763 3.768 3.771 3.775
obj2 3.957 3.035 2.694 2.486 2.419 2.408 2.404 2.389 2.392 2.398
paper1 3.803 2.903 2.456 2.337 2.338 2.356 2.372 2.385 2.397 2.406
paper2 3.612 2.857 2.423 2.312 2.315 2.344 2.372 2.392 2.405 2.415
paper3 3.706 3.078 2.673 2.573 2.579 2.606 2.626 2.640 2.649 2.655
paper4 3.843 3.221 2.915 2.876 2.893 2.916 2.931 2.940 2.944 2.948
paper5 3.997 3.305 3.017 2.973 2.990 3.000 3.011 3.015 3.023 3.026
paper6 3.825 2.943 2.511 2.415 2.420 2.434 2.452 2.464 2.477 2.485
pic 0.841 0.817 0.816 0.815 0.806 0.806 0.809 0.807 0.810 0.813
progc 3.825 2.875 2.475 2.382 2.379 2.386 2.399 2.411 2.422 2.428
progl 3.264 2.384 1.886 1.742 1.695 1.674 1.664 1.660 1.668 1.679
progp 3.331 2.254 1.812 1.730 1.716 1.714 1.722 1.724 1.731 1.739
trans 3.446 2.345 1.744 1.545 1.495 1.472 1.461 1.465 1.469 1.479
总计 3.312 2.632 2.227 2.078 2.056 2.069 2.090 2.107 2.121 2.133

表5.2 方案4.1下使用不同阶数的压缩率(单位 bpc)

  从表5.2的数据中可以看出,不同的文件使用不同的最高阶数可以获得最好的压缩率。比如文件“bib”使用最高5阶可以获得最好的压缩率,而文件“obj2”使用最高8阶可以获得最好的压缩率。总体而言,使用最高5阶获得的压缩率最好,再提高阶数只会降低压缩率。这意味着,如果不采取其它措施那么在PPM算法实现的时候将会有阶数上的限制。

  PPM算法在实现的时候可以指定一个最高阶数。这个最高阶数将影响到算法的压缩率和耗时。从上面一系列的测试中我们可以发现。当我们使用较高的最高阶数进行压缩时,我们将面临相互矛盾的两个方面。一方面,如果符号能够在越高阶的上下文中得到匹配,那么这个符号的预测概率就越好。越高阶的上下文出现的次数越少,其中符号的概率也越突出。这样算法的压缩率也会越高。这一点可以从图5.2中看出来。从1阶到4阶,越着阶数的提高压缩率也在大幅提高。与之相反的另一方面,如果符号无法在高阶上下文中得到匹配,那么就需要输出一系列的逃逸码预测概率。如果匹配上下文的阶数与当前开始上下文的阶数相差越大,那么输出的逃逸码概率也就越多。从而影响到算法的压缩率,使得压缩率出现下降。这一点也可以从图5.2中看出来。从5阶到12阶,越着阶数的提高压缩率也在逐步的降低。算法最后表现出来的压缩率就是上面两个方面博弈的结果。如果符号在高阶上下文中匹配所获得的压缩率的收益,能够超过大量输出逃逸码概率所出现的压缩率的损失,那么总体的压缩率将得到改善。

  本章将要介绍的局部阶估计(Local Order Estimation,LOE)方案就是为了解决上述问题而被提出来的。当使用LOE方案时,从当前分支的sH, sH-1, ..., s0 , si ∈ Zn上下文中按照一定的标准选择一个上下文。首先在选择的上下文中进行编码。如果选择的上下文不是匹配上下文,那么就从比选择上下文更低1阶的上下文开始,像正常算法那样进行编码。从对LOE方案的描述中可以看出,LOE方案实际上是有意抛弃了一些上下文来提高算法的压缩率。如果这些被抛弃的上下文成为匹配上下文的可能性很低,那么LOE方案就可以减少逃逸码预测概率的输出,从而提高算法的压缩率。所以,对于LOE方案来说,最核心的问题就是如何选择一个上下文。如果选择的上下文过于高阶。虽然有可能获得更好的符号预测概率,但是也有可能输出更多的逃逸码概率。反之,如果选择的上下文过于低阶。虽然可以减少逃逸码概率的输出,但是对于符号概率的预测却会变得更糟糕。所以如何选择一个上下文将会严重的影响LOE方案的性能。

  本章将会介绍两种选择上下文的方案。同时还会给出一个在方案4.1上整合LOE方案的实现方案。然后将这个新的实现方案与方案4.1进行对比测试。

5.2 确定性上下文

  在使用LOE方案时,如果我们需要从当前分支中选择一个上下文,那么我们可以选择一个最低阶的只包含一个符号的上下文。我们称这样的上下文为确定性上下文(Deterministic Contexts,Det-Context)。可以发现确定性上下文就是一个二元上下文。在选择确定性上下文的时候,如果在当前分支中无法找到确定性上下文,那么我们就从最高阶上下文开始,像正常算法那样进行编码。如果可以找到,那么就先在确定性上下文中进行编码。如果确定性上下文不是匹配上下文,那么就从比确定性上下文低1阶的上下文开始,像正常算法那样进行编码。确定性上下文的方案最早是由John G. Cleary,W. J. Teahan和Ian H. Witten在1995年提出[5]来的,并且应用在了PPM*算法[5]中。

  但是,在本文的实现方案中决定不采用确定性上下文的方案。原因有两点。第一点,根据模型的特点,越高阶上下文中出现的符号越少。当我们使用较高的最高阶数时,二元上下文将会集中在较高阶的上下文中。如果此时我们使用确定性上下文的方案,那么每次选择都会倾向于较高阶的上下文。这将会降低算法的压缩率。第二点,在方案4.1中无法使用确定性上下文的方案。回顾3.5节中归纳的模型的规律。根据规律二,同一分支中高1阶上下文中出现的符号数总是小于等于当前上下文中出现的符号数,即,m(sd+1) ≤ m(sd) , si ∈ Zn。那么在方案4.1的模型中,二元上下文只会出现在较高阶的上下文中。这意味着,在方案4.1中使用确定性上下文的方案将没有任何效果。综上两种原因,本文将放弃使用确定性上下文的方案,转而使用另外一种选择上下文的方案。

5.3 估计上下文

  另外一种选择上下文的方案,就是对当前分支中的所有上下文,都各自计算一个称之为置信度(Confidence Rating)的值。然后选择一个置信度最大的上下文。我们称这样的上下文为估计上下文(Estimation Contexts,Est-Context)。选择完成之后,我们先在估计上下文中进行编码。如果估计上下文不是匹配上下文,那么就从比估计上下文低1阶的上下文开始,像正常算法那样进行编码。估计上下文的方案最早是由Charles Bloom在1998年提出[6]来的,并且应用在了PPMZ算法[6]中。

  接下来的一个问题就是如何计算置信度。置信度必需可以反应出一个上下文成为匹配上下文的可能性有多大。在保证这一点的前提下,最好是越高阶的上下文置信度越大。置信度决定了我们将会选择哪一个上下文。所以如何计算置信度将会严重影响算法的压缩率。

  在一个上下文中有可能会出现多个符号,我们将频度最大的那个符号称之为最有可能的符号(The Most Probable Symbol,MPS)。MPS对应的预测概率称之为最有可能的符号的概率(The Most Probable Symbol's Probability,MPS-P)。MPS就是一个上下文中最有可能被匹配到的符号。MPS-P越大说明一个上下文成为匹配上下文的可能性也越高。另外,越高阶的上下文中出现符号的数量越少,与之相对应的MPS-P就会越大。所以我们可以将MPS-P作为置信度,用于上下文的选择。当然,置信度的计算方法还有很多,但是性能都不及MPS-P。所以这里不再对这些方法进行介绍。感兴趣的读者可以自行参考相关的论文[6]

5.4 方案实现

  在实现的时候,我们需要对当前分支中的所有上下文逐一计算MPS-P。计算后还要相互比较,从中选择出一个MPS-P最大的上下文。MPS-P可以使用如下公式进行计算。

  从上面的公式中可以看出。在计算MPS-P的时候,我们需要大量的访问MPS的频度。那么我们可以将MPS对应的节点项放置在节点项数组的最前面。这样对于TNode.Items成员,使用Items[0].Freq成员就可以访问到MPS的频度。另外,使用TNode.Total成员可以访问到T(s)。这样计算MPS-P就可以更加的方便。不过,在更新符号频度的时候,操作会变得更加复杂。每次更新完一个符号的频度之后,都必需检查这个符号是否是MPS。如果这个符号是MPS,那么就需要将它移动到节点项数组的最前面。从而确保节点项数组的第一个元素始终为MPS。

  另外,MPS-P是一个小于1的小数。MPS-P的精度对于上下文的选择影响很大。所以在实现的时候一般使用浮点类型的变量来保存MPS-P。这就意味着,对于上面公式的计算就必需使用浮点运算来进行。如果使用较高的最高阶数,那么在一个分支中出现的上下文的数量也较多。对于每个上下文都要进行一定的浮点运算,这将会增加算法的耗时。

  还有一点,在更新模型的时候还需要注意一个问题。如果估计上下文没有命中,即,估计上下文不是匹配上下文。那么我们可以确定比估计上下文更高阶的上下文都不是匹配上下文。但是,如果估计上下文命中,那么比估计上下文更高阶的上下文中将有可能出现匹配上下文。所以,如果出现估计上下文命中的情况。那么在更新模型前,我们需要对所有比估计上下文更高阶的上下文进行查找。如果在更高阶的上下文中找到匹配上下文,那么在更新模型时就按照这个上下文来进行更新。

5.5 测试与分析

  现在我们以方案4.1(PPMD)为基础整合LOE方案,并以此确定一套新的实现方案。这套方案命名为方案5.1(PPMD+LOE)。对于方案5.1的描述如下所示。

方案5.1 以方案4.1(PPMD)为基础,整合LOE方案;使用LOE方案选择上下文时,以MPS-P作为置信度,并选择置信度最大的上下文作为估计上下文;其它描述与方案4.1相同(PPMD+LOE)。

  现在我们对方案5.1(PPMD+LOE)的压缩率进行测试,测试时分别使用从1阶到10阶的不同最高阶数对语料库[14]中的18个文件进行压缩。其压缩率如表5.3所示。

文件 1阶 2阶 3阶 4阶 5阶 6阶 7阶 8阶 9阶 10阶
bib 3.461 2.635 2.088 1.892 1.842 1.833 1.832 1.832 1.832 1.832
book1 3.610 2.902 2.456 2.294 2.279 2.300 2.325 2.344 2.355 2.362
book2 3.738 2.902 2.257 2.015 1.954 1.943 1.946 1.950 1.955 1.959
geo 4.753 4.756 4.684 4.708 4.706 4.706 4.704 4.704 4.704 4.704
news 4.131 3.244 2.636 2.399 2.344 2.335 2.335 2.336 2.337 2.337
obj1 4.472 3.920 3.818 3.792 3.792 3.794 3.794 3.798 3.797 3.798
obj2 3.959 3.057 2.712 2.491 2.415 2.390 2.373 2.346 2.339 2.336
paper1 3.803 2.923 2.463 2.334 2.312 2.309 2.310 2.311 2.314 2.314
paper2 3.612 2.864 2.427 2.307 2.289 2.294 2.303 2.308 2.311 2.314
paper3 3.706 3.095 2.685 2.567 2.552 2.561 2.568 2.571 2.574 2.575
paper4 3.843 3.230 2.919 2.867 2.863 2.870 2.874 2.876 2.876 2.878
paper5 3.997 3.316 3.027 2.967 2.964 2.963 2.965 2.961 2.964 2.965
paper6 3.825 2.974 2.524 2.412 2.395 2.390 2.390 2.389 2.390 2.391
pic 0.842 0.817 0.815 0.812 0.802 0.803 0.804 0.800 0.801 0.803
progc 3.826 2.879 2.495 2.381 2.358 2.344 2.341 2.339 2.339 2.337
progl 3.265 2.389 1.892 1.737 1.674 1.637 1.611 1.594 1.588 1.585
progp 3.332 2.264 1.820 1.718 1.682 1.665 1.654 1.634 1.625 1.621
trans 3.446 2.389 1.768 1.554 1.486 1.442 1.411 1.401 1.391 1.389
总计 3.316 2.650 2.232 2.077 2.041 2.038 2.042 2.044 2.047 2.049

表5.3 方案5.1下使用不同阶数的压缩率(单位 bpc)

  虽然LOE方案是为了解决PPM算法的阶数限制问题而被提出来的,但是从测试数据中我们可以看出LOE方案的效果并不理想。在表5.3的数据中,从总计上看使用最高6阶获得的压缩率最好。如果再提高最高阶数,压缩率同样会出现逐步降低的情况。不过降低的幅度比方案4.1(PPMD)有所减小。

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

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

  从图5.3中我们的可以看出。尽管在方案5.1(PPMD+LOE)中不断提高最高阶数,同样也会出现压缩率逐步降低的情况。但是在方案5.1中压缩率降低的幅度显示要比方案4.1(PPMD)来的更低。不仅如此,虽然对于最低的1阶、2阶和3阶,方案5.1的压缩率要比方案4.1来的略低。但是从最高4阶开始,方案5.1的压缩率明显超过了方案4.1。而且随着最高阶数的提高,这种趋势变得更加的明显。所以说,总体而言方案5.1的压缩率要比方案4.1来的更优秀。

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

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

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

  从表5.4的数据中可以看出。就总体而言,方案5.1(PPMD+LOE)的耗时比方案4.1(PPMD)增加了大约40%左右。在使用LOE方案的时候,我们需要进行浮点运算。浮点运算量随着分支中上下文的数量的增多而增多。即使在编程中使用一些技巧来替换浮点运算,这些运算仍然会对算法的耗时产生很大的影响。测试表明,当使用的最高阶数逐步提高时,方案5.1的耗时会大幅增加。这就是使用LOE方案的最大缺点。

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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