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

yeye55的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

PPM压缩算法的分析与实现 - 第六章 二次逃逸估计  

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

  下载LOFTER 我的照片书  |

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

第六章 二次逃逸估计

6.1 前言

  在一个上下文中编码一个符号的时候,我们需要进行逃逸估计。逃逸估计就是要估算出在当前的上下文中出现逃逸的可能性有多大。在前面介绍的方法D中,使用了上下文中的符号数量这一个方面的信息来估算逃逸码的预测概率。但是,不仅仅是这一个方面的信息,我们还可以使用其它方面的信息来作为逃逸估计的参考。例如,在5.1节的测试中我们可以发现,某一阶的上下文成为匹配上下文的可能性非常大。那么上下文的阶数信息也可以作为逃逸估计的参考。对于一个上下文来说,可以用来作为逃逸估计的参考信息有很多。比如说,这个上下文中的总计频度是多少、符号数量是多少、上下文的阶数是多少等等。甚至还可以包括父上下文和子上下文中的信息。在进行逃逸估计的时候,如果我们能够将上下文中的各种信息都考虑进来,那么预测出来的逃逸码概率将会变得更加准确。

  本章将要介绍的二次逃逸估计(Secondary Escape Estimation,SEE)方案就是这样的一个方案。SEE方案最早是由Charles Bloom在1998年提出[6],并且应用在了PPMZ算法[6]中。在使用SEE方案的时候。首先,需要根据一个量化策略对每个上下文中的相关信息进行量化(Quantize)。量化后可以得到一个量化值,我们把这个量化值称为SEE上下文(SEE Context)。接着,我们为SEE上下文建立一个二次模型(Secondary Model)。我们将这个二次模型称为SEE模型(SEE Model)。SEE模型也是一个概率统计模型,并且独立于当前的PPM模型。在SEE模型中将会统计每个SEE上下文对应的上下文的匹配频度和逃逸频度。在进行逃逸估计的时候,就可以根据SEE模型中的统计信息来预测逃逸的概率。

  本章将会介绍量化生成SEE上下文的方法,以及如何建立SEE模型。本章除了会给出一个在方案4.1上整合SEE方案的实现方案,还会讨论将SEE方案与LOE方案进行整合的实现方案。另外说明一点,在PPMZ算法[6]中,使用了一种非常复杂的SEE方案。本章不对这个SEE方案进行介绍,感兴趣的读者可以自行参考相关的论文[6]。本章介绍的SEE方案经过了一定的简化处理。

6.2 量化

  在进行逃逸估计的时候,在一个上下文中可以用来进行参考的信息有很多。一个信息就是一个数值,如果我们直接根据这些数值来建立SEE模型,那么这个模型将占用大量的内存。例如,我们根据符号数量和阶数两个方面的信息来建立SEE模型。假设使用最高5阶的上下文,那么就有1275种信息。每一种信息都对应于一个匹配频度和一个逃逸频度。如果我们继续增加参考的信息,那么模型占用的内存将会大幅增长。解决这个问题的方法是进行量化。量化时将每个相关信息的数值都量化成数个二进制位,然后再将这些二进制位彼此连接起来从而构成一个固定位长的SEE上下文。通过使用适当的量化策略,我们可以控制SEE上下文的位长。这时再利用SEE上下文来建立SEE模型,我们就可以控制模型占用的内存。

  在SEE模型中必需可以预测出一个上下文出现逃逸的可能性有多大。当我们使用量化方案的时候,两个不同的上下文有可能会生成相同的SEE上下文。这时量化策略就显得非常的重要。假设一个上下文出现逃逸的可能性很大,而另一个上下文则很小。如果量化后这两个上下文生成相同的SEE上下文,那么这将会降低算法的压缩率。量化的策略是SEE方案中最灵活多变的部份。不同类型的数据适合的量化策略也不同。要拟定一个对所有类型的数据都很优秀的量化策略是非常困难的。所以本文介绍的量化策略只能说对于一般类型的数据都还不错。

  从前面几章的内容中我们知道,在PPM模型中二元上下文占有较大的比例。而且在进行逃逸估计的时候,二元上下文拥有的许多特点使它区别于多元上下文。因此在使用SEE方案的时候,我们可以使用两个SEE模型。这两个SEE模型使用不同的量化策略。一个SEE模型供二元上下文使用,另一个SEE模型供多元上下文使用。这样的区别对待可以有效的改善算法的压缩率。针对二元上下文的量化策略的描述如下。

  1)在一份数据中通常有一些符号起到分隔的作用。比如文本数据中的标点符号,或者是图像数据中的色块边沿。收集这些符号的信息有助于我们进行逃逸估计。对于当前符号之前的数个符号,取每个符号的最高2位,从而构成了一个上下文的特征。这里将上下文的特征量化到6位。在实现的时候,收集上下文的特征可以在编码完成一个符号之后进行。上下文特征的定义和更新如代码6.1所示。

01 var
02     ContextChar : Cardinal; //上下文的特征
03
04 procedure Encode(Symbol : Byte);
05 begin
06     //省略部份代码……
07
08     //更新上下文特征
09     ContextChar:=(ContextChar shl 2)+((Symbol and $C0) shr 6);
10 end;

代码6.1 上下文特征的定义和更新

  2)在二元上下文中只包含了一个符号,这个符号的特征同样对逃逸估计有利。与1)类似,我们取这个符号的最高2位。于是,这个符号的符号值可以量化到2位。

  3)如果当前上下文不是匹配上下文,那么我们就需要退回到下一级上下文中。下一级上下文中的信息也有助于我们进行逃逸估计。于是,这里收集下一级上下文中的总计频度的信息,并将其量化到2位。

  4)与3)相同的理由,不仅是总计频度,符号数量也很重要。在我们的模型结构中,下一级上下文的符号数量肯定会大于等于当前上下文的符号数量。于是,这里将下一级上下文中的符号数减去当前上下文中的符号数,并将其计算结果量化到2位。

  5)二元上下文中仅有符号的频度最为重要。这个频度值的大小很大程度上影响了当前上下文成为匹配上下文的可能性。于是,这里将仅有符号的频度量化到3位。

  根据上述的策略,我们可以根据一个二元上下文中的信息来生成一个15位长的SEE上下文。这个SEE上下文由5个部份组成,其结构如图6.1所示。量化生成这个SEE上下文的代码如代码6.2所示。

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

01 var
02     Root : PPPMNode; //根节点
03     Context : PPPMNode; //当前上下文
04
05 //对二元上下文进行量化,返回一个15位的SEE上下文。
06 function BinQuantize: Cardinal;
07 var
08     NextCount : Integer; //下一级上下文的符号数
09     NextTotal : Cardinal; //下一级上下文的总计频度
10 begin
11     //提取下一级上下文的信息
12     if Context=Root then
13     begin
14         NextCount:=256;
15         NextTotal:=256;
16     end
17     else with Context.Lesser^ do
18     begin
19         NextCount:=Count;
20         if Count=1 then NextTotal:=OnlyItem.Freq
21         else            NextTotal:=Total;
22     end;
23
24     //(1)、当前上下文特征,量化到6位
25     Result:=ContextChar and $3F;
26
27     with Context.OnlyItem do
28     begin
29         //(2)、仅有符号的符号值,量化到2位
30         Inc(Result,Symbol and $C0);
31
32         //(3)、下一级上下文的总计频度,量化到2位
33         case NextTotal-1 of
34             0    : Inc(Result,0 shl 8); //1
35             1..2 : Inc(Result,1 shl 8); //2
36             3..6 : Inc(Result,2 shl 8); //4
37             else   Inc(Result,3 shl 8);
38         end;
39
40         //(4)、下一级上下文的符号数与当前符号数的差,量化到2位
41         case NextCount-1 of
42             0    : Inc(Result,0 shl 10); //1
43             1    : Inc(Result,1 shl 10); //1
44             2..3 : Inc(Result,2 shl 10); //2
45             else   Inc(Result,3 shl 10);
46         end;
47
48         //(5)、仅有符号的频度,量化到3位
49         case Freq-1 of
50              0      : Inc(Result,0 shl 12); // 1
51              1..  2 : Inc(Result,1 shl 12); // 2
52              3..  6 : Inc(Result,2 shl 12); // 4
53              7.. 14 : Inc(Result,3 shl 12); // 8
54             15.. 30 : Inc(Result,4 shl 12); //16
55             31.. 62 : Inc(Result,5 shl 12); //32
56             63..126 : Inc(Result,6 shl 12); //64
57             else      Inc(Result,7 shl 12);
58         end;
59     end;
60
61     //完成
62 end;

代码6.2 二元上下文的量化

  在进行量化的时候需要考虑到信息数值的特点。不仅如此,在量化时还要尽可能的满足一个原则。那就是有可能出现的高匹配预测的信息要与高逃逸预测的信息量化到两个不同的数值中。这样才能有助于改善算法的压缩率。实际上要做到这点很难,但是在拟定量化策略的时候应该尽可能的做到这一点。例如在代码6.2中的第49行到第58行,这10行的代码将仅有符号的频度量化到了3个二进制位。符号的频度值有255种可能,而3个二进制位只能表示8个值。最简单的方法当然就是平均分配,但是这种方法的效果并不理想。根据模型的特点我们可以发现,仅有符号的频度较小的情况出现的次数较多。反之,频度较大的情况出现次数较少。不仅如此,频度越大出现匹配的可能性也越大。反之,在频度很小的时候出现逃逸的可能性就很大。于是在进行量化的时候,较小的频度量化到较多的量化值,而较大的频度集中量化到一个量化值中。这样就可以让高匹配预测的信息集中起来,从而改善算法的压缩率。

  观察代码6.2我们可以发现,在代码中大量使用了case语句来进行量化。case语句的性能并不是很高。另外,我们可以发现量化的数值相对较少。那么我们可以使用常量数组来替换case语句。这样的修改有助于提高程序的运行性能。改进后的量化函数BinQuantize如代码6.3所示。

01 //对二元上下文进行量化,返回一个15位的SEE上下文。
02 function BinQuantize: Cardinal;
03 const
04     QUANT_3 : array [0..6] of Byte = (
05         0, 1, 1, 2, 2, 2, 2);
06
07     QUANT_4 : array [0..3] of Byte = (
08         0, 1, 2, 2);
09
10     QUANT_5 : array [0..126] of Byte = (
11         0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4,
12         4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5,
13         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
14         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6,
15         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
16         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
17         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
18         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6);
19
20 var
21     n : Cardinal;
22 begin
23     //(1)、当前上下文特征,量化到6位
24     Result:=ContextChar and $3F;
25
26     //量化下一级上下文
27     if Context=Root then Inc(Result,$F shl 8)
28     else with Context.Lesser^ do
29     begin
30         //(3)、下一级上下文的总计频度,量化到2位
31         if Count=1 then n:=OnlyItem.Freq-1
32         else            n:=Total-1;
33
34         if n<=6 then Inc(Result,QUANT_3[n] shl 8)
35         else         Inc(Result,3 shl 8);
36
37         //(4)、下一级上下文的符号数与当前符号数的差,量化到2位
38         n:=Count-1;
39         if n<=3 then Inc(Result,QUANT_4[n] shl 10)
40         else         Inc(Result,3 shl 10);
41     end;
42
43     //量化当前上下文
44     with Context.OnlyItem do
45     begin
46         //(2)、仅有符号的符号值,量化到2位
47         Inc(Result,Symbol and $C0);
48
49         //(5)、仅有符号的频度,量化到3位
50         n:=Freq-1;
51         if n<=126 then Inc(Result,QUANT_5[n] shl 12)
52         else           Inc(Result,7 shl 12);
53     end;
54
55     //完成
56 end;

代码6.3 改进后的二元上下文的量化

  除了二元上下文以外,剩下的就是多元上下文。对于多元上下文的量化与二元上下文类似。针对多元上下文的量化策略的描述如下。

  1)类似的,在多元上下文中我们同样需要收集上下文的特征信息。这里将上下文的特征量化到6位。

  2)对于多元上下文来说,下一级上下文中的信息同样重要。这里将下一级上下文中的总计频度量化到2位。

  3)同样的,这里将下一级上下文中的符号数减去当前上下文中的符号数,并将其计算结果量化到2位。

  4)在多元上下文中,上下文中的符号数量也非常重要。一般情况下符号数量越多,当前上下文成为匹配上下文的可能性也越大。这里将当前上下文中的符号数量化到2位。

  5)除了符号数量,上下文中的总计频度也很重要。所以我们也要收集总计频度的信息。但是注意一点,在我们实现的方案中,我们使用了排除符号方案。所以我们对排除符号后的剩余符号的总计频度进行量化。这里将排除符号后的总计频度量化到3位。

  根据上述的策略,我们可以根据一个多元上下文中的信息来生成一个15位长的SEE上下文。这个SEE上下文由5个部份组成,其结构如图6.2所示。对应的量化代码请参考本文的配套项目,这里不再给出。

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

  在本文中介绍的量化策略并不是唯一的量化策略,量化策略是灵活多变的。如果压缩程序需要针对某一类型的数据进行设计,那么可以调整量化策略来适应这一类型的数据。不仅如此,如果将SEE方案同其它变体方案进行整合,也需要对量化策略进行适当的调整。在拟定或者是调整量化策略的时候,需要根据数据在概率统计上的特点来进行。每一份的数据都有各自的特点,即使是对于同一类型的数据也是如此。所以,要拟定一个对所有数据都很优秀的量化策略是非常困难的。正因为如此,在拟定量化策略的时候,需要对样本数据进行大量的调试工作。所以最后声明一点,本文介绍的量化策略未必是最优秀的。

6.3 建模

  根据一个上下文中的信息我们可以生成一个SEE上下文,我们利用SEE上下文来建立SEE模型。在SEE模型中,对于每个SEE上下文都需要统计匹配频度和逃逸频度两个数据。那么在实现SEE模型的时候,我们可以使用两个数组来实现其数据结构。一个SEE上下文对应于数组中的一个元素,一个数组用来保存匹配频度,另一个数组用来保存逃逸频度。在我们当前使用的模型中,一共使用了两个SEE模型,对应的SEE上下文都是15位长。那么我们可以据此给出SEE模型结构的定义。这两个SEE模型的数据结构的定义如代码6.4所示。

01 var
02     //供二元上下文(Bin)使用的SEE模型
03     BinEscape : array [0..$7FFF] of Word; //逃逸频度
04     BinMatch  : array [0..$7FFF] of Word; //匹配频度
05
06     //供多元上下文(Mul)使用的SEE模型
07     MulEscape : array [0..$7FFF] of Word; //逃逸频度
08     MulMatch  : array [0..$7FFF] of Word; //匹配频度

代码6.4 SEE模型的数据结构定义

  从上面的描述中可以看出,SEE模型实际上就是一个0阶的概率统计模型。与一般的概率统计模型一样,SEE模型也需要避免出现零频的SEE上下文。于是在编码前必需对SEE模型进行初始化。概率统计模型都是根据模型中累积的频度信息来进行预测的。一般情况下,在编码前无法知道一份数据中的概率分布。所以,一般的概率统计模型在初始化时都是将所有的频度设置为1。不过对于SEE模型来说,情况却有一些不同。

  回顾上一节的内容,以多元上下文为例。生成的SEE上下文的最高3位是由排除符号后的总计频度量化得到的,接下来紧邻的2位是由当前上下文中的符号数量化得到的。根据模型的特点我们可以发现。随着总计频度越来越大,上下文出现匹配的可能性也越来越大。同样的,随着符号数越来越大,上下文出现匹配的可能性也同样的越来越大。如果统合考虑这两点,当总计频度越来越大而符号数越来越小时,上下文出现匹配的可能性将大幅增长,反之亦然。模型的这些特点意味着,我们在编码前就可以大体的预测出SEE模型中的匹配与逃逸的比例关系。那么我们就可以根据这些比例关系来拟定一份初始化数据表。然后使用这份数据表来初始化代码6.4中的数组。

  一般的概率统计模型将频度初始化为1。这就需要一个较长的过程,通过频度累积来使模型稳定下来。我们使用一份事先拟定好的数据表来初始化SEE模型,这样就可以让SEE模型更快的稳定下来,从而获得更好的预测概率。初始化数据表的拟定必需和量化策略相配合,并且与数据的概率特点相适应。在本文实现的方案中,根据SEE上下文的最高5位来拟定初始化数据表,并使用这份数据表来初始化SEE模型。其相关的实现代码请参考本文的配套项目,这里不再详述。

  在使用了SEE方案以后,就可以不再使用一般的逃逸估计方法。当使用SEE方案在一个上下文中编码一个符号时。首先,我们需要根据当前上下文中的信息量化生成一个SEE上下文。对于当前上下文s,我们使用w(s)来表示对应的SEE上下文。SEE上下文对应的匹配频度使用f(mat|w(s))来表示,对应的逃逸频度使用f(esc|w(s))来表示。在我们当前使用的SEE模型中,使用一个SEE上下文就可以从代码6.4的数组中查询到对应的匹配频度和逃逸频度。现在,我们需要判断当前上下文是否匹配。如果匹配则输出匹配的预测概率,如果逃逸则输出逃逸的预测概率。不管是匹配还是逃逸,预测概率都是根据SEE模型中的统计数据来进行计算的。在SEE模型中,逃逸的预测概率的计算公式如下所示。

  如果当前上下文逃逸,那么只要输出逃逸的预测概率即可。然后我们就可以退回到下一级上下文中,开始新一轮的编码。但是,如果当前上下文匹配,那么我们不仅要输出匹配的预测概率,还要根据PPM模型中的统计数据来输出当前符号的预测概率。对于当前符号a在当前上下文s中的预测概率的计算公式如下所示。

  从上面的公式中我们可以看出,对于匹配上下文需要输出两个预测概率。首先输出根据SEE模型计算得到的匹配预测概率,然后再输出根据PPM模型计算得到的符号预测概率。对于符号预测概率,这里需要注意一点。和前面几章介绍的内容相比,这里的符号预测概率不再需要考虑逃逸码的频度。逃逸估计已经完全由SEE模型来负责。这一点可以从上面的公式中看出来。这也就意味着,如果当前上下文是二元上下文同时又是匹配上下文,那么符号预测概率可以不用输出。因为此时的符号预测概率为1。

  在一个上下文中编码完成一个符号的时候,无论是匹配还是逃逸都需要对SEE模型进行更新。更新SEE模型实际上很简单,只需要根据当前的SEE上下文修改相关的数组元素即可。但是,有几点需要说明一下。对于一般的概率统计模型,在更新模型时都是对相关的频度加1。不过对于SEE模型来说情况却有一些不同。实际测试表明,适当的加大更新时频度的增量,可以有效的改善算法的压缩率。所以,每次更新SEE模型时,通常将相关的频度增加10至20左右。另外一点,与一般的概率统计模型类似,当频度超过一个固定的阀值时,需要进行削减频度。一个SEE上下文对应的频度都是成对的,即一个匹配频度和一个逃逸频度。在削减频度时,只需要对这两频度进行减半处理即可。没必要对整个SEE模型进行削减。另外,SEE模型不支持零频,所以在削减频度时必需避免出现零频的SEE上下文。

  就总体而言SEE模型还是比较简单的。SEE模型综合考虑了一个上下文中的多种信息,并由此进行逃逸估计。与一般的逃逸估计方法相比,SEE方案肯定可以获得更好的压缩率。虽然使用SEE模型时会增加整个算法的内存占用。比如对于代码6.4中定义的两个SEE模型,就占用了256KB的内存。但是虑到SEE方案可以有效的提高压缩率,这些内存占用的增加还是可以接受的。

6.4 方案整合SEE+LOE

  在PPM算法中,各种变体方案都是可以整合在一起的,当然在整合的时候需要对方案中细节进行调整。不过需要注意一点,并不是说整合的变体方案越多算法的性能就越好。一般情况下,整合的变体方案越多算法的耗时也越大。每一种变体方案都需要增加操作才可以完成,这些操作都会增加算法的耗时。另外,一些变体方案彼此之间的兼容性很差。如果将这些变体方案整合在一起,反而会降低算法的压缩率。下面就来介绍将SEE方案与LOE方案整合在一起的实现方案。

  SEE方案与LOE方案并不冲突。在使用LOE方案时,需要对当前分支中的所有上下文进行遍历并逐一计算MPS-P。计算MPS-P时将会涉及到逃逸估计,那么这就由SEE模型来负责。在前面介绍的SEE方案中,我们使用了两个SEE模型。一个供二元上下文使用,另一个供多元上下文使用。计算MPS-P时进行的逃逸估计与二元上下文中或者是多元上下文中进行的逃逸估计又不太一样。计算MPS-P时是针对任意一个上下文进行的,这个上下文有可能是一个二元上下文,也有可能是一个多元上下文。MPS-P的计算值将会严重影响LOE方案的性能,而SEE模型的逃逸估计又会严重影响MPS-P的计算值。所以,为了与LOE方案相配合,我们专门使用一个SEE模型用于MPS-P的计算。当使用LOE方案选择了一个估计上下文之后,在这个估计上下文中进行编码的时候也使用这个SEE模型来进行。当然这个SEE模型的量化策略需要重新拟定。针对任意一个上下文的量化策略的描述如下。

  1)类似的,在任意一个上下文中我们同样需要收集上下文的特征信息。这里将上下文的特征量化到6位。

  2)对一个上下文sd来说,有紧密相关的两个上下文。下一级上下文sd-1(父上下文)和上一级上下文sd+1(子上下文)。上下文sd与sd-1和sd+1之间的相互关系也会影响到逃逸估计的进行。所以,这里将上下文sd中的总计频度与sd-1和sd+1中的总计频度进行大小比较,并将比较的结果量化到2位。

  3)与2)类似,这里将上下文sd中的符号数与sd-1和sd+1中的符号数进行比较,看看这些符号数是否一致。然后再将比较的结果量化到2位。

  4)与上一节中的量化策略类似,这里将当前上下文中的符号数量化到2位。注意一点,当前上下文有可能是二元上下文,也有可能是多元上下文。

  5)当前的量化策略将会被用于MPS-P的计算,计算MPS-P时我们不能进行排除符号。所以,这里对总计频度的信息进行量化。考虑到总计频度的特点,这里将当前上下文中的总计频度减去当前上下文中的符号数,然后再将计算结果量化到3位。

  根据上述的策略,我们可以根据任意一个上下文中的信息来生成一个15位长的SEE上下文。这个SEE上下文由5个部份组成,其结构如图6.3所示。对应的量化代码请参考本文的配套项目,这里不再给出。

图6.3 由任意一个上下文量化生成的SEE上下文的结构

  使用LOE方案选择一个估计上下文以后,如果估计上下文没有命中,那么仍然需要退回到下一级上下文中。从模型的特点中我们知道,退回后开始编码的下一级上下文肯定不是二元上下文,而是一个多元上下文。在这个多元上下文中进行编码,同样需要一个SEE模型。于是在当前的整合方案中,我们一共使用两个SEE模型。一个供估计上下文使用,另一个供多元上下文使用。供多元上下文使用的SEE模型的量化策略与6.2节中论述的多元上下文的量化策略一致,这里就不再重复说明。

  总得来说,变体方案的整合还是比较简单的。各种变体方案各司其职,SEE方案负责进行逃逸估计,LOE方案负责选择估计上下文。整合时就是将各种变体方案的操作合并到同一个算法中,相互配合共同完成任务。

6.5 测试与分析

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

方案6.1 以方案4.1(PPMD)为基础,不再使用方法D,并整合SEE方案;使用SEE方案时,建立两个SEE模型,一个供二元上下文使用,一个供多元上下文使用;初始化时使用一份数据表来对SEE模型进行初始化;其它描述与方案4.1相同(PPM+SEE)。
方案6.2 以方案6.1(PPM+SEE)为基础,整合LOE方案;使用SEE方案时,建立两个SEE模型,一个供估计上下文使用,一个供多元上下文使用;使用LOE方案选择上下文时,以MPS-P作为置信度,并选择置信度最大的上下文作为估计上下文;其它描述与方案6.1相同(PPM+SEE+LOE)。

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

文件 输入大小
(字节)
方案4.1 方案6.1 方案6.2
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
bib 111261 26089 1.876 24869 1.788 24874 1.789
book1 768771 220763 2.297 214126 2.228 213122 2.218
book2 610856 150272 1.968 145752 1.909 145875 1.910
geo 102400 60303 4.711 56242 4.394 57173 4.467
news 377109 111441 2.364 108253 2.296 108082 2.293
obj1 21504 10081 3.750 9916 3.689 10035 3.733
obj2 246814 74620 2.419 72867 2.362 73340 2.377
paper1 53161 15533 2.338 14995 2.257 15011 2.259
paper2 82199 23789 2.315 22912 2.230 22838 2.223
paper3 46526 14999 2.579 14499 2.493 14471 2.488
paper4 13286 4805 2.893 4658 2.805 4636 2.792
paper5 11954 4468 2.990 4344 2.907 4351 2.912
paper6 38105 11527 2.420 11129 2.336 11135 2.338
pic 513216 51682 0.806 50835 0.792 50345 0.785
progc 39611 11781 2.379 11376 2.298 11424 2.307
progl 71646 15179 1.695 14464 1.615 14501 1.619
progp 49379 10590 1.716 10034 1.626 10067 1.631
trans 93695 17512 1.495 16320 1.393 16554 1.413
总计 3251493 835434 2.056 807591 1.987 807834 1.988

表6.1 压缩率对比测试结果

  从表6.1的数据中可以看出,使用SEE方案后压缩率得到明显的改善。在使用最高5阶进行压缩时,从总计上看方案6.1(PPM+SEE)的压缩率比方案4.1(PPMD)提高了3.36%。不仅如此,SEE方案对于不同的最高阶数的适应能力都很好。

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

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

  从图6.4中我们可以看出,使用不同的最高阶数进行压缩,方案6.1(PPM+SEE)的压缩率都会优于方案4.1(PPMD)。与方案4.1类似,在方案6.1中不断提高最高阶数,同样也会出现压缩率逐步降低的情况。在对方案6.1的测试中我们可以发现。当使用最高6阶进行压缩时,方案6.1压缩率最好。但是,如果再提高最高阶数,压缩率就会出现逐步降低的情况。不过,从图6.4中可以看出,压缩率降低的幅度非常的小。这证明SEE方案要比一般的逃逸估计方法优秀很多,对于不同的最高阶数的适应能力也很好。

  SEE方案不仅优秀,与其它变体方案的兼容能力也很好。现在我们对方案5.1(PPMD+LOE)和方案6.2(PPM+SEE+LOE)进行测试,测试时分别使用从3阶到20阶的不同最高阶数对语料库[14]中的18个文件进行压缩。每次压缩后记录其总计的压缩率,最后将这些压缩率绘制成两条曲线。其结果如图6.5所示。

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

  从图6.5中我们可以看出,将方案5.1(PPMD+LOE)与方案6.2(PPM+SEE+LOE)相比,方案6.2的压缩率同样的更优秀。不仅如此,在使用不同的最高阶数对方案6.2的测试中我们可以发现,方案6.2的压缩率是随着最高阶数的提高而不断提高的。这正是LOE方案所希望达到的目的。虽然方案5.1没有达到这个目的,但是在整合SEE方案后方案6.2达到了这个目的。不过,在测试中我们还会发现。将方案6.1(PPM+SEE)与方案6.2相比,只有从最高9阶开始,方案6.2的压缩率才会高于方案6.1。在此之前的最高阶数,方案6.2的压缩率都是低于方案6.1的。比如使用最高5阶压缩,从表6.1中可以看出方案6.2的压缩率低于方案6.1。这说明方案6.2需要在较高的最高阶数中使用,才能获得较好的压缩率。另外从图6.5中我们可以看出。虽然使用方案6.2时压缩率会随着最高阶数的提高而不断提高。但是当最高阶数超过11阶时,压缩率提高的幅度变得非常的有限。大幅提高最高阶数,仅仅能获得0.001bpc的压缩率的提升。这意味着即便使用方案6.2,大幅提高最高阶数也无法给算法的性能带来多少好处。

  使用SEE方案不仅会增加整个模型的内存占用,当然也会增加算法的耗时。现在我们对方案4.1(PPMD)、方案6.1(PPM+SEE)和方案6.2(PPM+SEE+LOE)这三套方案进行压缩耗时和解压缩耗时的对比测试,测试时使用最高5阶来进行压缩。其测试结果如表6.2所示。

文件 方案4.1 方案6.1 方案6.2
压缩耗时 解压缩耗时 压缩耗时 解压缩耗时 压缩耗时 解压缩耗时
bib 47 47 62 78 156 156
book1 500 516 672 719 1313 1360
book2 328 344 437 484 953 1000
geo 172 187 172 203 203 204
news 234 265 297 343 594 625
obj1 15 31 31 15 32 32
obj2 172 172 204 219 406 406
paper1 16 31 46 31 78 78
paper2 31 47 62 63 125 141
paper3 32 16 31 31 63 79
paper4 0 15 0 16 16 32
paper5 0 15 16 0 16 15
paper6 16 16 16 31 62 47
pic 109 125 141 172 453 484
progc 16 15 32 16 63 46
progl 16 31 31 31 78 110
progp 15 15 31 15 63 62
trans 15 31 47 46 110 125

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

  使用SEE方案后所增加的耗时主要集中在两个方面。一方面是SEE模型量化与维护的耗时。从SEE模型中查找匹配频度和逃逸频度时,需要使用量化生成的SEE上下文。输出预测概率后,还要对SEE模型进行更新。这些操作都会增加算法的耗时。另一方面在使用SEE方案时,对于每一个匹配上下文都需要输出两个预测概率。一个匹配预测概率和一个符号预测概率。使用一般的逃逸估计方法时,逃逸码频度包含在符号预测概率中。所以只需要输出一个符号预测概率即可。而使用SEE方案时,则需要多输出一个匹配预测概率。多输出的预测概率会增加底层概率编码器的工作量,从而增加算法的耗时。不过从表6.2的数据中我们可以看出,方案6.1(PPM+SEE)所增加的算法耗时并不是很大。究其原因,SEE模型的结构并不是很复杂,所以查询和维护起来也比较简单。另外,在输出匹配预测概率之后,只有多元上下文需要再输出符号预测概率,二元上下文可以忽略符号预测概率。而且在匹配上下文中,二元上下文占了大量的比例。所以总的来说,使用SEE方案不会增加太多的算法耗时。

  与方案6.1(PPM+SEE)相比,方案6.2(PPM+SEE+LOE)的算法耗时多少有些惨不忍睹。即使与表5.4中的方案5.1(PPMD+LOE)的算法耗时相比,方案6.2的算法耗时也出现了大幅的增加。除了使用SEE方案本身会增加的一些耗时以外,主要增加的算法耗时都集中在估计上下文的选择上。在当前分支中选择一个估计上下文时,需要对当前分支中的所有上下文逐一进行量化,逐一计算MPS-P。而且计算MPS-P时使用的是浮点运算。使用了SEE方案以后,计算MPS-P的浮点运算会变得更加复杂。这些原因导致了方案6.2的算法耗时的大幅增加。SEE方案与LOE方案的整合,虽然可以做到让压缩率随着最高阶数的提高而不断提高。但是整合了SEE方案使得LOE方案的缺点也更加的明显与突出。测试表明,当继续提高算法的最高阶数时,方案6.2的算法耗时也会随着大幅增加。而且增加的幅度远远的超过了方案5.1。

  评论这张
 
阅读(999)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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