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

yeye55的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

PPM压缩算法的分析与实现 - 第八章 无限长度上下文  

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

  下载LOFTER 我的照片书  |

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

第八章 无限长度上下文

8.1 前言

  如果PPM算法的压缩率可以随着最高阶数的提高而提高。那么我们自然而然的可以想到,如果我们不限制最高阶数那么就可以获得最优秀的压缩率。不对最高阶数进行限制,同时让模型能够处理无限长度的上下文,这就是本章将要介绍的无限长度上下文(Unbounded Length Contexts,ULC)方案。ULC方案最早是由John G. Cleary、W. J. Teahan和Ian H. Witten在1995年提出[5],并且应用在了PPM*算法[5]中。从理论上来说,使用ULC方案可以获得最优秀的压缩率。但是使用ULC方案会使模型的内存占用以及算法的耗时大幅增加。所以从总体性能的角度来讲,ULC方案的性能并不是很好。与ULC情况相对应,如果我们限制模型的最高阶数,那么这种情况被称为有限上下文(Finite Context,FC)。可见,本文前面介绍的几种实现方案都属于FC情况。在FC情况下,模型的内存占用和算法耗时都不会太大。所以FC情况比ULC情况更具有可行性。

  本章将会介绍ULC方案是如何实现的。本章除了会给出一个在方案4.1上整合ULC方案的实现方案,还会讨论分别以方案6.2(PPM+SEE+LOE)和方案7.3(PPM+SEE+II)为基础整合ULC方案的实现方案。

8.2 方案实现

  首先让我们来回顾一下3.4节,在3.4节中介绍了CT结构的详细实现。当初提出CT结构就是为了解决ULC方案中的建模问题。那就是,既要让模型能够处理无限长度的上下文,又要让模型不至于占用太大的内存。CT结构就可以很好的解决这个问题。不过,在3.4节中介绍的CT结构是针对FC情况而设计的。所以,当我们把它应用到ULC方案中时需要对其进行适当的调整。

  首先在3.4节介绍的CT结构中,符号在最高阶上下文中对应的TItem.Link成员指向对应的兄弟上下文。所以,在进行扩展上下文的操作时,对于最高阶上下文将不进行扩展操作。不过,在ULC情况下没有限制最高阶数,所以也不存在最高阶上下文。当使用ULC方案时,需要对所有的上下文进行扩展,不存在“符号的Link成员指向兄弟上下文”的这种情况。这也就意味着在ULC情况下,CT结构中Trie树的高度会越来越大不断增加。

  另外,在ULC情况下将不能使用区分削减方案。区分削减方案就是在最高阶上下文中削减频度时允许出现零频符号。如果出现零频符号,那么就将该符号从当前上下文中删除。在ULC情况下没有最高阶上下文,所以不能使用区分削减方案。这样,在进行削减频度操作的时候,所有的符号都不能出现零频。这意味着,一旦一个符号被添加到上下文中,那么这个符号将会一直存在不会被删除。所以,在ULC情况下将不存在需要收缩节点项数组这样的情况。

  还有一点,在FC情况下当符号出现在最高阶上下文中时,这个符号可以不用追加到符号列表中。但是,在使用了ULC方案之后将不再有最高阶上下文。所以,所有的符号都需要被添加到符号列表中。这就意味着,如果在编码过程中没有出现定量内存重置,那么在编码结束时,最终的符号列表将会成为输入数据的一份拷贝。

  根据上面的这个特点,可以提出一种改进方案。使用这种改进方案时,将不再使用符号列表。而是在内存中建立一个数据缓冲区,在编码前将整份数据读入到数据缓冲区中。在编码过程中,对应的TItem.Link成员如果不是指向上下文节点,那么就是直接指向数据缓冲区中的相应位置。通过指向数据缓冲区的指针和数据缓冲区的大小来判断Link成员是指向上下文节点还是指向数据缓冲区。这种改进方案速度更快,可以不用考虑符号列表的更新。但是,这种方案只能处理数据块(Data Block)而不能处理数据流(Data Stream)。所以,在本文的实现方案中将不使用这种改进方案。

  现在,我们使用与3.4节中相同的例子,在ULC情况下编码数据“ABEACADABEA”。在编码过程中,CT结构的变化过程基本与3.4节中的一致。所以这里就不再进行详细的说明。在ULC情况下,编码完成数据“ABEACADABEA”以后,模型的数据结构如图8.1所示。

图8.1 编码完数据“ABEACADABEA”后的模型结构

  将图8.1与3.4节中的图3.2 12)相比,我们可以发现ULC情况下CT结构的一些特点。在图3.2 12)中,在FC情况下的CT结构生成了9个上下文节点,符号列表的长度为10个符号。而在图8.1中,在ULC情况下的CT结构生成了10个上下文节点,符号列表的长度为11个符号。很明显,使用ULC方案会增加模型中上下文节点的数量。上面例子中的这份数据的数据量较小,所以仅增加了一个上下文节点。测试表明,在数据量较大的情况下,使用ULC方案会使模型中的上下文节点的数量成倍增加。另外,在编码结束时,最终的符号列表将会成为输入数据的一份拷贝。这一点也可以从图8.1中看出来。上述的这些特点表明,使用ULC方案会显著的增加模型的内存占用。另外,由于上下文节点数量的大幅增加,使得相关的操作变得更加的繁重,从而还会造成算法耗时的大幅增加。

  另外,从图8.1中我们还可以看出一个特点。ULC方案虽然被称为无限长度上下文,但是在编码过程中上下文的长度并不会达到无限。在上面的例子中,出现的最长的上下文是“ABEA”。也就是说,在编码过程中出现的最大阶数为4阶。仔细观察模型的结构以及编码的过程,我们可以得到这样的一个结论:在编码过程中出现的最大阶数,为输入数据中可重叠最长重复子串(Longest Repeated Substring Can Be Overlapping)的长度。在上面的例子中,数据“ABEACADABEA”的可重叠最长重复子串就是“ABEA”。子串“ABEA”的长度为4,所以在编码过程中出现的最大阶数为4阶。这相当于我们限制最高阶数为4阶来进行数据的压缩。在最极端的情况下,例如输入的数据完全是由同一个符号重复而成的。那么在编码过程中出现的最大阶数就是输入数据的长度减1。假设对一份长度为101个符号的数据来进行压缩。如果在这份数据中只出现了一种符号,那么这就相当于使用最高100阶来对这份数据进行压缩。我们知道,最高阶数越高模型占用的内存也越大,算法的耗时也越长。这就意味着,使用ULC方案会使算法的性能出现较大的波动。如果一份数据的可重叠最长重复子串的长度较短,那么压缩时模型占用的内存和算法的耗时都不会太大。但是,如果一份数据的可重叠最长重复子串的长度较长,那么压缩时模型占用的内存和算法的耗时都会大幅增加。

8.3 方案整合

  在本文的5.1节中我们进行了一系列的测试。这些测试的结果都可以证明,对于一般的PPM算法的实现,如果不断的提高最高阶数那么算法的压缩率将会出现逐步的下降。这就意味着,如果我们单独整合ULC方案,那么在算法的性能上将得不到任何好处。算法的内存占用和算法的耗时都会大幅的增加,而算法的压缩率反而会出现下降。所以说,ULC方案必需和其它的变体方案一起整合使用。在整合ULC方案之前,必需保证其它的变体方案可以让算法的压缩率随着最高阶数的提高而提高。在本文前面介绍的众多的整合方案中,只有3种整合方案可以满足这样的要求。这就是方案6.2(PPM+SEE+LOE)、方案7.3(PPM+SEE+II)和方案7.4(PPM+SEE+II+LOE)。以这3个整合方案为基础,在其之上整合ULC方案,才可以保证算法的压缩率不会出现下降。在整合ULC方案的时候,主要是对CT结构进行适当的调整,而对于已经整合的其它变体方案就不需要再进行调整了。所以在整合ULC方案的实现方案中,对于II方案中的初始频度的计算、LOE方案中的置信度的计算、SEE方案中的量化策略和模型的建立,都不需要进行调整可以直接使用。另外,在7.7节的测试中已经可以证明,方案7.4的各方面性能都不如方案7.3。所以在拟定整合方案的时候,我们放弃在方案7.4上整合ULC方案的实现方案。

8.4 测试与分析

  现在我们以方案4.1(PPMD)为基础整合ULC方案,并以此确定一套新的实现方案。这套方案命名为方案8.1(PPMD+ULC)。然后,我们以方案6.2(PPM+SEE+LOE)为基础整合ULC方案,并以此确定一套新的实现方案。这套方案命名为方案8.2(PPM+SEE+LOE+ULC)。接着,我们以方案7.3(PPM+SEE+II)为基础整合ULC方案,并以此确定一套新的实现方案。这套方案命名为方案8.3(PPM+SEE+II+ULC)。对于方案8.1、方案8.2和方案8.3这三种方案的描述如下所示。

方案8.1 以方案4.1(PPMD)为基础,整合ULC方案;使用ULC方案时,对CT结构进行适当的调整,同时不再使用区分削减方案,削减频度时不允许出现零频符号;其它描述与方案4.1相同(PPMD+ULC)。
方案8.2 以方案6.2(PPM+SEE+LOE)为基础,整合ULC方案;使用ULC方案时,对CT结构进行适当的调整,同时不再使用区分削减方案,削减频度时不允许出现零频符号;其它描述与方案6.2相同(PPM+SEE+LOE+ULC)。
方案8.3 以方案7.3(PPM+SEE+II)为基础,整合ULC方案;使用ULC方案时,对CT结构进行适当的调整,同时不再使用区分削减方案,削减频度时不允许出现零频符号;其它描述与方案7.3相同(PPM+SEE+II+ULC)。

  在进行测试之前有一点需要说明一下。在前面的所有测试中,在设置定量内存大小的时候,都可以保证在压缩语料库[14]中的18个文件时,不会出现定量内存重置的情况。这一点在本节的测试中将得不到保证。在前面的测试中,当使用最高5阶进行压缩时,我们将定量内存的大小设置为4兆字节(MB)。但是,由于使用ULC方案会大幅的增加模型的内存占用。所以在本节的测试中,将定量内存的大小设置为50兆字节(MB)。使用这个定量值可以保证在压缩语料库[14]中的除了文件“pic”以外的17个文件时,不会出现定量内存重置的情况。使用ULC方案压缩文件“pic”时,需要使用数百兆大小的定量内存才可以保证不会出现定量内存的重置。所以,在本节的测试中决定不使用这么大的定量内存。在使用方案8.1压缩文件“pic”的时候,如果将定量内存的大小设置为50兆字节(MB),那么在压缩的过程中将会出现3次的定量内存重置。这对于最终的测试数据将会有一定的影响。

  现在我们首先对方案4.1(PPMD)和方案8.1(PPMD+ULC)在压缩过程中的内存使用情况进行对比测试,测试方案4.1时使用5阶的最高阶数对语料库[14]中的18个文件进行压缩。通过前面的介绍我们知道,使用了ULC方案以后肯定会使模型的内存占用大幅增加。所以,在测试时我们将会统计在编码结束后定量内存的使用量以及模型中生成的节点数量。另外,在使用了ULC方案以后,在编码过程中出现的最大阶数为输入数据中的可重叠最长重复子串的长度。这意味着,使用ULC方案压缩不同的文件出现的最大阶数也是不同的。所以,在测试时我们将会统计在编码结束后模型中出现的最大阶数。对于定量内存使用量和符号列表长度的测试结果如表8.1所示。对于节点项个数和上下文节点个数以及最大阶数的测试结果如表8.2所示。

文件 方案4.1 方案8.1 增加倍数
定量内存
使用量
(字节)
符号列表
长度
(字节)
定量内存
使用量
(字节)
符号列表
长度
(字节)
定量内存
使用量
(倍)
符号列表
长度
(倍)
bib 704580 35148 5007021 111261 6.11 2.17
book1 3375661 175261 17062035 768771 4.05 3.39
book2 2659380 137376 19562792 610856 6.36 3.45
geo 1390240 95116 1547092 102400 0.11 0.08
news 2743617 144369 43576797 377109 14.88 1.61
obj1 217743 14043 430620 21504 0.98 0.53
obj2 1908140 99332 27228094 246814 13.27 1.48
paper1 496884 24636 2157241 53161 3.34 1.16
paper2 657680 33836 2319023 82199 2.53 1.43
paper3 471465 24417 1197110 46526 1.54 0.91
paper4 170456 8564 365810 13286 1.15 0.55
paper5 157005 7809 333686 11954 1.13 0.53
paper6 380402 18566 2099429 38105 4.52 1.05
pic 860810 56702 - - - -
progc 383637 18969 1717835 39611 3.48 1.09
progl 430033 19609 10519818 71646 23.46 2.65
progp 330027 14307 24871043 49379 74.36 2.45
trans 535694 21206 43199495 93695 79.64 3.42

表8.1 内存使用对比测试结果

文件 方案4.1 方案8.1 增加倍数 最大阶数
(阶)
节点项
个数
(个)
上下文
节点个数
(个)
节点项
个数
(个)
上下文
节点个数
(个)
节点项
个数
(倍)
上下文
节点个数
(倍)
bib 50884 28298 171070 316182 2.36 10.17 156
book1 298820 104994 1154049 735192 2.86 6.00 104
book2 216665 93067 935377 1076504 3.32 10.57 246
geo 119264 44670 130105 51437 0.09 0.15 61
news 210357 103064 572986 3293327 1.72 30.95 1029
obj1 17956 7366 27541 19218 0.53 1.61 1011
obj2 136646 77197 380166 2046183 1.78 25.51 607
paper1 35964 19912 82183 131292 1.29 5.59 104
paper2 51214 24257 125408 118945 1.45 3.90 115
paper3 36064 17655 70443 57891 0.95 2.28 48
paper4 12363 6781 20156 18538 0.63 1.73 36
paper5 11237 6332 18174 17033 0.62 1.69 52
paper6 26994 15587 59184 140205 1.19 7.99 214
pic 77358 25421 756502 15412713 8.78 605.30 36315
progc 27059 15748 60778 107419 1.25 5.82 156
progl 28651 18684 118134 808190 3.12 42.26 560
progp 20523 15183 82444 2024974 3.02 132.37 1631
trans 30046 26643 160083 3508069 4.33 130.67 1706

表8.2 节点数量对比测试结果

  在分析表8.1和表8.2中的数据之前有一点需要留意。文件“pic”在压缩过程中出现了3次的定量内存重置,所以它的一些测试数据缺失。不仅如此,这也会影响到其它相关的测试数据的结果。

  从表8.1的数据中可以看出,与方案4.1(PPMD)相比方案8.1(PPMD+ULC)的内存占用出现了成倍的增加。除了文件“pic”以外,最高的就是文件“trans”。使用方案8.1压缩文件“trans”时的定量内存使用量与使用方案4.1时的相比,增加了79.64倍。不仅如此,使用方案8.1压缩不同的文件时,模型占用内存的情况波动性很大。不管文件有多少大,压缩一些文件时模型占用了大量的内存,而压缩另外一些文件时模型却占用了相对较小的内存。比如文件“trans”的大小要比文件“book1”小很多,但是压缩文件“trans”时定量内存的使用量却是压缩文件“book1”时的2.53倍。另外,在使用方案8.1压缩文件时,如果没有出现定量内存重置,那么最终的符号列表就是输入文件的一份拷贝。这当然也会增加模型的内存占用。对于数据量较大的文件来说,这一点尤为明显。

  现在再让我们来看表8.2中的数据,与方案4.1(PPMD)相比方案8.1(PPMD+ULC)的节点数量也是出现了成倍的增加。仔细比较之后我们可以发现,虽然节点项个数和上下文节点个数都出现了成倍的增加,但是上下文节点个数的增加倍数是最大的。这其中最高的就是文件“pic”。使用方案8.1压缩文件“pic”时的上下文节点个数与使用方案4.1时的相比,增加了605.30倍。这还要考虑到文件“pic”出现了3次定量内存重置,如果我们继续增加定量内存的大小,那么上下文节点的个数还会进一步的成倍增加。这也是压缩文件“pic”时需要使用大量内存的原因。由此可见,当使用方案8.1的时候,在模型成倍增加的内存占用之中,上下文节点个数的增加占有很大的比例。将上下文节点个数的增加倍数与模型中出现的最大阶数相比较我们可以发现,从总体上来说最大阶数越大上下文节点个数的增加倍数也越大。比如文件“pic”的最大阶数达到了36315阶,所以它的上下文节点个数的增加倍数也是最大的。可以看出,模型中生成的上下文节点的个数与模型中出现的最大阶数是息息相关的。而最大阶数又是根据输入数据中的结构分布特点而定的。所以,使用方案8.1压缩不同的文件时,模型占用内存的情况波动性会很大。这一点也可以从表8.1的数据中看出来。

  综合分析表8.1和表8.2中的数据可以看出,从总体上来说在编码结束时模型中出现的最大阶数越大,在编码过程中模型占用的内存也越大。不过对于具体的内存占用情况还要视输入数据中的结构分布特点而定。比如对于文件“obj1”来说,虽然它的最大阶数达到了1011阶,但是它的定量内存使用量相对来说并不是很大。但是就总体而言,模型在ULC情况下的内存占用肯定会比在FC情况下的更高。

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

文件 输入大小
(字节)
方案4.1 方案8.1 压缩率
提高比例
(%)
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
bib 111261 26089 1.876 28487 2.048 -9.17
book1 768771 220763 2.297 239934 2.497 -8.71
book2 610856 150272 1.968 164158 2.150 -9.25
geo 102400 60303 4.711 60280 4.709 0.04
news 377109 111441 2.364 117890 2.501 -5.80
obj1 21504 10081 3.750 10552 3.926 -4.69
obj2 246814 74620 2.419 75723 2.454 -1.45
paper1 53161 15533 2.338 16248 2.445 -4.58
paper2 82199 23789 2.315 25074 2.440 -5.40
paper3 46526 14999 2.579 15512 2.667 -3.41
paper4 13286 4805 2.893 4910 2.956 -2.18
paper5 11954 4468 2.990 4536 3.036 -1.54
paper6 38105 11527 2.420 11993 2.518 -4.05
pic 513216 51682 0.806 88122 1.374 -70.47
progc 39611 11781 2.379 12219 2.468 -3.74
progl 71646 15179 1.695 16472 1.839 -8.50
progp 49379 10590 1.716 11407 1.848 -7.69
trans 93695 17512 1.495 20177 1.723 -15.25
总计 3251493 835434 2.056 923694 2.273 -10.55

表8.3 压缩率对比测试结果

  从表8.3的数据中可以看出,方案8.1(PPMD+ULC)的压缩率不如方案4.1(PPMD)。其中,除了文件“geo”的压缩率有略微的提高以外,其它文件的压缩率都出现了明显的下降。很明显,单独整合ULC方案不会提高算法的压缩率。使用了ULC方案以后,模型中出现的最大阶数通常会比较大,所以在编码过程中将会出现大量输出逃逸码预测概率的情况。这也就意味着,最大阶数越大算法的压缩率有可能会越低。我们在5.1节中所做的测试也可以证明这一点。所以说,ULC方案必需同其它变体方案一起配合使用,才可以保证最终压缩率的提高。

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

文件 输入大小
(字节)
方案6.2 方案8.2 压缩率
提高比例
(%)
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
bib 111261 24874 1.789 24122 1.734 3.07
book1 768771 213122 2.218 215353 2.241 -1.04
book2 610856 145875 1.910 143434 1.878 1.68
geo 102400 57173 4.467 57118 4.462 0.11
news 377109 108082 2.293 105921 2.247 2.01
obj1 21504 10035 3.733 10174 3.785 -1.39
obj2 246814 73340 2.377 69064 2.239 5.81
paper1 53161 15011 2.259 14821 2.230 1.28
paper2 82199 22838 2.223 22738 2.213 0.45
paper3 46526 14471 2.488 14470 2.488 0.00
paper4 13286 4636 2.792 4629 2.787 0.18
paper5 11954 4351 2.912 4329 2.897 0.52
paper6 38105 11135 2.338 10984 2.306 1.37
pic 513216 50345 0.785 51215 0.798 -1.66
progc 39611 11424 2.307 11196 2.261 1.99
progl 71646 14501 1.619 13105 1.463 9.64
progp 49379 10067 1.631 9116 1.477 9.44
trans 93695 16554 1.413 14622 1.248 11.68
总计 3251493 807834 1.988 796411 1.959 1.46

表8.4 压缩率对比测试结果

  从表8.4的数据中可以看出,与方案6.2(PPM+SEE+LOE)相比方案8.2(PPM+SEE+LOE+ULC)的压缩率有所提高。虽然有3个文件的压缩率出现了降低,但是就总体而言压缩率还是有所提高的。方案8.2的压缩率不仅比方案8.1(PPMD+ULC)来的更优秀,而且比方案4.1(PPMD)也来的更优秀。不过,从压缩率提高比例的角度来看,方案8.2的压缩率却出现了很大的波动性。其中,压缩率提高比例最大的是文件“trans”,使用方案8.2压缩文件“trans”时的压缩率比使用方案6.2时的提高了11.68%。但是对于文件“paper3”来说,使用方案8.2压缩时的输出大小仅仅比使用方案6.2时的减少了1个字节。更不用说还有3个文件出现了压缩率的下降。可见,使用了ULC方案以后不仅会在内存占用方面出现波动性,在压缩率方面同样也会出现波动性。

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

文件 输入大小
(字节)
方案7.3 方案8.3 压缩率
提高比例
(%)
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
bib 111261 24600 1.769 24041 1.729 2.26
book1 768771 212040 2.207 214329 2.230 -1.04
book2 610856 144152 1.888 141796 1.857 1.64
geo 102400 55654 4.348 55523 4.338 0.23
news 377109 106988 2.270 104938 2.226 1.94
obj1 21504 9694 3.606 9682 3.602 0.11
obj2 246814 71116 2.305 66989 2.171 5.81
paper1 53161 14810 2.229 14644 2.204 1.12
paper2 82199 22594 2.199 22536 2.193 0.27
paper3 46526 14301 2.459 14306 2.460 -0.04
paper4 13286 4601 2.770 4601 2.770 0.00
paper5 11954 4299 2.877 4279 2.864 0.45
paper6 38105 10983 2.306 10837 2.275 1.34
pic 513216 50369 0.785 47358 0.738 5.99
progc 39611 11214 2.265 10979 2.217 2.12
progl 71646 14293 1.596 12957 1.447 9.34
progp 49379 9919 1.607 8963 1.452 9.65
trans 93695 16094 1.374 14302 1.221 11.14
总计 3251493 797721 1.963 783060 1.927 1.83

表8.5 压缩率对比测试结果

  从表8.5的数据中可以看出,与方案7.3(PPM+SEE+II)相比方案8.3(PPM+SEE+II+ULC)的压缩率有所提高。同时,与方案8.2(PPM+SEE+LOE+ULC)相比方案8.3的压缩率也有所提高。从这里可以看出,II方案要比LOE方案更为优秀。另外从压缩率提高比例的角度来看,方案8.3与方案8.2类似,也出现了大幅的波动。而且波动的比例与方案8.2也十分的相近。可见,整合ULC方案是出现这种波动的主要原因。

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

 
文件
方案4.1 方案8.1
压缩耗时 解压缩耗时 压缩耗时 解压缩耗时
bib 47 47 78 78
book1 500 516 719 750
book2 328 344 469 500
geo 172 187 172 187
news 234 265 375 422
obj1 15 31 31 16
obj2 172 172 250 281
paper1 16 31 47 31
paper2 31 47 47 62
paper3 32 16 31 31
paper4 0 15 16 0
paper5 0 15 0 15
paper6 16 16 31 15
pic 109 125 515 563
progc 16 15 31 31
progl 16 31 62 63
progp 15 15 78 93
trans 15 31 156 172

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

  从表8.6的数据中可以看出,与方案4.1(PPMD)相比方案8.1(PPMD+ULC)的算法耗时是大幅的增加了。其中的两个文件“pic”和“trans”,它们的算法耗时是成倍的增加。使用了ULC方案以后,算法的结构没有出现太大的变化,但是模型中的节点数量却出现了成倍的增加。所以,在使用了ULC方案以后所增加的算法耗时,主要集中在对于多增加节点的处理操作上。观察表8.1中的数据,文件“pic”需要进行3次的定量内存重置才可以完成压缩。而文件“trans”的定量内存使用量与方案4.1相比增加了79.64倍。这两个文件的节点数量都出现了成倍的增加,这就造成了它们的算法耗时也随着大幅的增加。所以说,使用ULC方案不仅会大幅增加算法的内存占用,还会大幅增加算法的耗时。

  现在我们对方案6.2(PPM+SEE+LOE)和方案8.2(PPM+SEE+LOE+ULC)进行压缩耗时和解压缩耗时的对比测试,测试方案6.2时使用最高5阶来进行压缩。其测试结果如表8.7所示。

文件 方案6.2 方案8.2
压缩耗时 解压缩耗时 压缩耗时 解压缩耗时
bib 156 156 234 266
book1 1313 1360 1922 2031
book2 953 1000 1531 1609
geo 203 204 219 219
news 594 625 1063 1141
obj1 32 32 109 109
obj2 406 406 703 719
paper1 78 78 93 109
paper2 125 141 172 172
paper3 63 79 79 94
paper4 16 32 15 15
paper5 16 15 15 16
paper6 62 47 78 78
pic 453 484 58547 58844
progc 63 46 78 78
progl 78 110 219 219
progp 63 62 266 266
trans 110 125 468 468

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

  在表8.7的数据中,方案8.2(PPM+SEE+LOE+ULC)的测试结果可谓令人惊叹。其中,文件“pic”的压缩耗时达到了58547毫秒,将近1分钟的耗时让人无语。究其原因,问题主要集中在LOE方案上。在使用LOE方案的时候,每次编码一个符号时,都需要对当前分支中的所有上下文进行遍历,逐一计算MPS-P。在使用了ULC方案以后,文件“pic”中出现的最大阶数为36315阶。这就意味着在一个分支中,有可能出现36316个上下文。对于这些上下文需要逐一计算MPS-P,而且在计算时使用的还是浮点运算。在这样的情况下,算法的耗时可想而知。算法耗时较大本来就是LOE方案的固有缺点,整合ULC方案无异于会再次放大这个缺点,从而造成算法耗时的大幅增加。

  现在我们对方案7.3(PPM+SEE+II)和方案8.3(PPM+SEE+II+ULC)进行压缩耗时和解压缩耗时的对比测试,测试方案7.3时使用最高5阶来进行压缩。其测试结果如表8.8所示。

文件 方案7.3 方案8.3
压缩耗时 解压缩耗时 压缩耗时 解压缩耗时
bib 63 78 93 109
book1 657 719 906 969
book2 406 469 625 657
geo 187 219 188 203
news 313 344 469 531
obj1 15 15 32 31
obj2 203 219 312 329
paper1 31 32 47 62
paper2 62 63 78 94
paper3 31 47 32 47
paper4 0 0 0 16
paper5 16 15 16 16
paper6 31 31 32 47
pic 141 172 641 672
progc 15 15 31 47
progl 31 47 78 78
progp 15 31 109 125
trans 32 31 187 187

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

  从表8.8的数据中可以看出,与方案7.3(PPM+SEE+II)相比方案8.3(PPM+SEE+II+ULC)的算法耗时是大幅的增加了。不过,与方案8.2(PPM+SEE+LOE+ULC)相比方案8.3的算法耗时还算是比较优秀的。方案8.3相对于方案7.3的算法耗时的增量与方案8.1(PPMD+ULC)相对于方案4.1(PPMD)的算法耗时的增量大体相近。可见,II方案对于算法耗时的影响相对较小。另外,方案8.3无论是在压缩率方面还是在算法耗时方面都要比方案8.2更优秀,所以方案8.3的可行性最好。

  通过上面一系列的测试我们可以发现,使用ULC方案的确可以提高算法的压缩率。不过使用了ULC方案以后,算法的内存占用和算法的耗时都会出现大幅的增加,而且算法的总体性能也会出现很大的波动。在使用ULC方案的时候。输入数据中的结构分布特点将决定着模型中出现的最大阶数、模型的内存占用、算法的耗时和算法的压缩率。对于不同的输入数据其结构分布特点也有很大的不同,这就造成了算法性能的大幅波动。如果在一份输入数据中出现了大量的重复数据块,如果这些重复数据块的长度较长。那么压缩这样的输入数据将可以获得较大的压缩率。但是相应的,模型的内存占用和算法的耗时都将大幅的增加。反之,如果在一份输入数据中只出现了少量的重复数据块,或者是重复数据块的长度较短。那么压缩这样的输入数据获得的压缩率将不会太高。相应的,模型的内存占用和算法的耗时也会相对较少。从理论上来说,ULC方案的这种特点恰恰可以证明使用ULC方案可以获得最好的压缩率。根据输入数据中的结构分布特点,让模型进行无限制的扩展,从而将PPM算法中压缩率的极限发挥出来。但是从实际应用的结果来看,当模型进行无限制扩展的时候,模型的内存占用和算法的耗时都会出现成倍的增加。另一方面,ULC方案对于压缩率的提升受限于其它相关的整合方案。单独整合ULC方案只会降低算法的压缩率,ULC方案必需和其它变体方案一起整合使用。而且在整合ULC方案之前必需保证其它相关的整合方案可以做到让算法的压缩率随着阶数的提高而提高。从前面的表8.5中可以看出,在测试中表现最好的是SEE+II的整合方案。即便如此,在此之上整合了ULC方案之后文件“book1”的压缩率还是下降了1.04%,输出大小增加了2289字节。可见,对于任何一种输入数据,在较大阶数的情况下,要做到让压缩率随着阶数的提高而提高是很困难的。另外,在6.5节和7.7节中对于方案6.2(PPM+SEE+LOE)和方案7.3(PPM+SEE+II)的测试分析中我们可以看出,当阶数较大时压缩率的提升空间是有限的。那么为了获得少量的压缩率的提升,从而付出成倍增加的内存占用和算法耗时,这样做是否值得还是需要商榷的。所以说,整合ULC方案虽然有可能提高算法的压缩率,但是却会降低算法的总体性能。

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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