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

yeye55的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

PPM压缩算法的分析与实现 - 第二章 一般实现  

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

  下载LOFTER 我的照片书  |

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

第二章 一般实现

2.1 前言

  对于不使用变体方案的PPM算法称为一般PPM(Normal PPM,又称“正常PPM”)。一般PPM算法的实现称为一般实现。PPM算法拥有众多的变体方案,这些变体方案都是以一般实现为基础的。所以掌握一般实现的实现过程对于理解变体方案非常有帮助。另外,即使不使用变体方案,一般实现也可以使用许多优化方案来提高压缩率。而且这些优化方案在变体方案中也同样适用。

  一般PPM算法实现时的主要内容就是如何建立模型,以及如何对模型进行更新。本章将从建模结构开始逐一介绍一般PPM算法的实现过程。同时对更新模型、排除符号、逃逸估计等内容进行介绍。

2.2 建模结构

  PPM算法在实现时需要在内存中建立一个数据结构用以保存上下文的信息。在编码时需要对Zn中的上下文进行遍历,对于每个上下文还要根据符号频度f(a|s)统计出总计频度T(s)。编码完成后还需要对模型进行更新。所以建模的数据结构对于算法性能的影响很大。前面介绍了一个上下文树结构。虽然可以利用这个结构进行建模,但是这个结构的性能很差。使用上下文树结构对上下文中的符号进行操作时,算法会变的很复杂。所以这里使用Trie结构来实现PPM算法。Trie结构也是一种树结构,而且同上下文树结构类似。利用Trie结构也可以表示任意的上下文节点。在Trie结构中我们将s0作为根节点,sD作为叶子节点。这与上下文树结构是一样的。但是,对于sd节点Trie结构与上下文树结构是完全不同的。所以不能将这两种结构相提并论。对于我们在1.4节提出的例子。现在假设使用3阶PPM算法,根据例子中的这份数据可以生成如图2.1所示的Trie结构。

图2.1 使用3阶算法的Trie树

  观察图2.1可以发现。在Trie结构中,对于上下文sd可以按xn-d+1, …, xn-2+1, xn的顺序查找到对应的节点。查找顺序正好与上下文树相反。对于图2.1中的所有叶子节点,按照从左到右的顺序我们可以确定3阶上下文“ABE”、“ACA”、“ADA”、“BEA”、“CAD”、“DAB”和“EAC”。另外,在1阶上下文“A”中出现了3个符号,而这3个符号可以利用“A”的子节点来确定。这样对于上下文“A”进行统计或更新的操作时将会非常的方便。

  需要注意的是。此时Zn中的节点不再是同一分支上的节点,而是分布到了Trie结构的各处。如果要在这个分支上编码,就要频繁的从根节点开始查找上下文节点。有一种解决方案就是在每个节点中都增加一个指针成员,其指向对应的sd-1上下文。利用这个指针成员可以方便的对Zn中的节点进行遍历,从而减少对上下文节点的查找。利用这种方案可以大幅减少算法的耗时。虽然这种方案会增加节点的内存占用,但是从综合性能的角度考虑,这种方案还是可以被采用的。

  在具体实现的时候,上下文中有可能不会出现所有的符号。实际上,在最高阶的上下文中只会出现少数几个符号。所以,在上下文中只记录曾经出现过的符号。如果有新的符号出现,再添加进上下文中。另外,可以将上下文中出现的符号以及符号对应的频度保存成数组的形式。这样对于上下文进行频度统计的操作时将更加的方便。构成Trie结构节点的定义代码如代码2.1所示。

01 type
02     //节点指针
03     PNode = ^TNode;
04
05     //节点项
06     PItem = ^TItem;
07     TItem = packed record
08         Symbol : Byte; //符号值
09         Freq : Byte; //符号频度
10         Link : PNode; //下层节点
11     end;
12
13     //节点项数组
14     PItemAry = ^TItemAry;
15     TItemAry = array [0..0] of TItem;
16
17     //上下文节点
18     TNode = packed record
19         Count : Word; //节点项的个数
20         Items : PItemAry; //节点项数组
21         Lesser : PNode; //指向对应的下一级上下文节点
22     end;

代码2.1 数据结构节点的定义

  一个完整的Trie结构节点是由一个TNode与一个TItemAry两部份构成。之所以这样设计是为了节点更方便更新。在代码2.1的第7行到第11行定义了一个节点项TItem,多个连续的TItem构成了一个节点项数组TItemAry。第18行到第22行定义了一个节点TNode。一个TNode对应于一个上下文。通过其中的Items成员可以访问到当前上下文中所有的符号。Items成员只是一个指针,在其指向的内存中可能包含多个TItem。在Items成员指向的内存中,包含TItem的数量由Count成员指定。如果Count成员为0,那么Items成员为nil,此时的上下文节点被称为空节点。如果要添加一个符号,就需要对Items成员指向的内存进行扩展。扩展内存时有可能会修改指向内存的指针,这时就要对Items成员进行更新。在代码中我们将上下文sd-1称之为下一级上下文。Lesser成员指向的就是当前上下文节点对应的下一级上下文节点。特殊的,0阶上下文s0对应的Lesser成员为nil。对应于图2.1中的1阶上下文“A”,利用代码2.1中的定义保存数据。其上下文节点在内存中的结构分布与指针关系如图2.2所示。

图2.2 节点的结构分布与指针关系

  图2.2虚线框中的两个部份构成了一个完整的Trie结构节点。从图2.2中可以看出,利用TNode和TItemAry之间的关系,可以根据当前上下文sd找到与之对应的高1阶上下文sd+1。如果有一个指向1阶上下文“A”的指针,那么根据对应的TItem.Link成员就可以找到2阶上下文“AB”、“AC”、“AD”。在实现的时候,可以将0阶上下文“^”作为根节点。通过0阶上下文“^”可以找到其它所有的上下文。

  在图2.2中1阶上下文s1对应的是“A”,它的下一级上下文s0是“^”。所以上下文“A”对应的TNode.Lesser成员指向上下文“^”。如果有一个指向D阶上下文sD的指针,那么利用对应的Lesser成员我们可以遍历到sD, sD-1, sD-2, …, s0 , si ∈ Zn各级上下文节点。直到Lesser成员为nil时遍历结束。所以Lesser成员将Zn中的上下文节点连接成了一个单向链表。这样可以大大的简化上下文节点的遍历操作。但是正是由于Lesser成员的存在,使得结构的更新操作变得更加复杂。每当我们添加一个新的上下文节点时,都需要确定对应的下一级上下文。同时还要对Lesser成员进行初始化。另外,当我们已经建立起一个上下文节点的时候,就不能对这个节点进行移动和重新分配。因为这有可能改变节点的内存地址,而在其它上下文节点中也许有许多Lesser成员正指向当前节点。

  在最高阶上下文节点中也有一个TItemAry,此时TItemAry中所有的TItem.Link成员都没有使用。因为不存在比D阶上下文还要高1阶的上下文。根据树结构的规律,叶子节点中TItem的数量总和是最多的。Link成员的空置多少都有些浪费内存。当然我们可以将这些空置的Link成员利用起来从而提高算法的效率。当我们编码完成一个符号时,需要确定下一轮开始的上下文。我们将下一轮开始的最高阶上下文s’D称为当前最高阶上下文sD的兄弟上下文。注意,兄弟上下文在上下文树中对应的节点不一定是兄弟节点。此时,我们可以将最高阶上下文中对应的Link成员指向对应的兄弟上下文节点。这样在确定下一轮开始的上下文时可以避免进行查找操作,从而提高算法效率。对应于图2.1中的3阶上下文“ABE”,其对应的Link成员的指针关系如图2.3所示。

图2.3 最高阶上下文中对应的Link成员指向兄弟上下文

  从图2.3中可以看出,当使用3阶作为最高阶数时。此时3阶上下文“ABE”中出现了符号“A”。与符号“A”对应的TItem.Link成员就指向3阶上下文“BEA”。如果当前的上下文为“ABE”,当前编码的符号为“A”。那么在编码完成符号“A”以后,下一轮开始的上下文为“BEA”。所以“BEA”是上下文“ABE”的兄弟上下文。相对应的,上下文“BEA”中的符号“C”对应的Link成员指向上下文“EAC”。可以看出,利用这种方案可以很方便的根据当前上下文找到相对应的兄弟上下文。

  最后还有一点需要说明。在具体实现的时候,当编码第一个符号时。由于此时没有对应的上下文,我们可以设定一个引导上下文(Priming Context)。引导上下文的长度为当前的最高阶数。所有的数据都是由同一个引导上下文开始的。编码前可以先将引导上下文添加进模型中,再开始编码。解码时也使用相同的引导上下文,就可以正确的解码。引导上下文添加进模型时,可以将对应的符号频度设置为0。这样引导上下文将不会影响到压缩率。

2.3 更新模型

  当编码完一个符号后,需要对模型进行更新。进行一般的更新操作时,需要对Zn中的上下文进行遍历,逐一进行更新。但是,更新时可以使用一种更好的优化方案,这种优化方案被称为排除更新(Update Exclusion)。当使用排除更新方案时,对于较低阶的上下文不进行更新,只对较高阶的上下文进行更新。即,对Zn中的sD, sD-1, …, sd , si ∈ Zn, d = d(a)上下文进行更新,而对于sd-1, sd-2, …, s0 , si ∈ Zn, d = d(a)上下文不进行更新。

  排除更新的方案基于这样一个事实。即,如果符号在较高阶的上下文中出现的频率很高,那么它们在较低阶的上下文中出现的频率通常不高。例如,在英文文本中,空格符号在单词“the”后面出现的频率很高。相对的,空格符号在“he”或“e”后面出现的频率较低。在我们进行编码的时候,都是从最高阶上下文sD开始的。这就意味着,使用排除更新后可以获得更好的高概率预测。同时它又能防止低阶上下文中出现过于平均的概率分布。所以使用这种方案可以有效的提高算法的压缩率。另外,在使用排除更新方案时,我们不必对较低阶的上下文进行更新操作。这样在提高算法压缩率的同时又可以降低算法的耗时。

  在更新时,如果当前符号出现上下文中,那么对应的符号频度需要进行更新。一般情况下更新频度就是将符号的频度加1。当使用排除更新方案时,需要进行符号频度更新操作的上下文就只剩下了匹配上下文s(a)。所以上下文s(a)的更新可以在编码过程中完成。

  在对符号频度进行更新前必需检查更新后的频度是否会超过限定值。与0阶的区间编码算法一样。为了保证编码精度,当频度超过一个限定值时需要进行削减频度(Scaling Freq)。在PPM算法中,一般以符号频度为标准,而不是以总计频度为标准,判断是否需要进行削减频度。一般情况下,削减频度就是将当前上下文中的所有符号的频度都进行减半处理。另外,在区间编码算法中削减频度时,需要防止出现零频的情况。由于PPM算法支持零频符号。所以在削减频度时可以直接减半,允许削减后的频度为0。但是这种做法会使上下文节点中出现频度为0的节点项。由于节点之间复杂的指针关系,我们不能将这些节点项所占用的内存回收。在编码的时候,视零频符号没有出现在当前上下文中。所以在对一个上下文进行频度信息统计的操作时,需要过滤掉可能出现的零频符号。

  当使用排除更新方案时,除了匹配上下文s(a),其它需要更新的上下文分为两种情况。一种情况是符号存在于上下文中,但符号的频度为0。此时只要设置符号频度即可。另一种情况是符号不存在于上下文中。此时需要对TNode.Items成员指向的内存进行扩展,添加新的节点项。同时对TNode.Count成员加1。如果当前上下文不是最高阶上下文,那么在添加完节点项后还要建立一个对应的下层节点。新建的下层节点对应的TNode.Count成员为0是空节点。

  在新建下层节点时需要确定TNode.Lesser成员的值。在一轮更新中,如果按照从高阶到低阶的顺序更新上下文。那么当前新建的下层节点的Lesser成员的值可以根据下次新建的下层节点判断出来。例如,假设在一轮更新中,我们需要对3阶上下文“ABC”、2阶上下文“BC”和1阶上下文“C”三个上下文添加符号“D”。这里假设最高阶数高于3阶。当我们在上下文“ABC”中添加符号“D”时需要新建一个下层节点,即上下文“ABCD”。与上下文“ABCD”对应的下一级上下文可以在下次新建下层节点时确定。当我们在上下文“BC”中添加符号“D”时需要建立上下文“BCD”。此时新建的下层节点“BCD”就是上下文“ABCD”的下一级上下文。相应的,在上下文“C”中添加符号“D”,新建下层节点“CD”。“CD”就是“BCD”的下一级上下文。根据这个规律在新建下层节点时可以比较方便的确定Lesser成员的值。另外,在最高阶上下文中添加符号时也可以利用这个规律来确定相对应的兄弟上下文节点。

2.4 排除符号

  在编码的时候,如果在上下文sd中没有出现当前符号a,那么我们需要退回到低1阶上下文sd-1中。此时我们可以确定一点,在上下文sd中出现的符号都不是当前符号a。那么在对上下文sd-1进行编码的时候,我们可以将上下文sd中出现的符号从上下文sd-1中排除出去。以此类推,如果在上下文sd-1中没有出现当前符号a。那么在对上下文sd-2进行编码的时候,可以将上下文sd与上下文sd-1中出现的所有符号都排除出去。这种优化方案被称为排除符号(Exclude Symbol)。现在让我们来看一个例子。假设使用最高3阶的上下文,已经编码了多个符号,当前的上下文是“ABC”。当前Zn中的上下文,以及对应的符号与频度的数据如表2.1所示。

上下文 s0 s1 s2 s3
“^” “C” “BC” “ABC”
频度表 E 2 E 2 E 3 E 5
F 1 F 2 F 4 esc 1
G 3 G 3 esc 1
H 2 H 6
I 3 esc 1
esc 1

表2.1 3阶上下文频度表

  在表2.1中esc表示逃逸码,这里假设逃逸码的频度固定为1。假设现在编码一个符号a,但是这个符号没有出现在3阶上下文“ABC”中。那么我们退回到2阶上下文“BC”中,此时我们可以发现,当前符号a肯定不是符号“E”。我们可以将符号“E”从上下文“BC”中排除出去。这样符号“F”在上下文“BC”中的预测概率为4/5。上下文“BC”的逃逸码的预测概率为1/5。如果不使用排除符号方案,符号“F”的预测概率为4/8,逃逸码的预测概率为1/8。以此类推,当使用排除符号方案时。在1阶上下文“C”中,符号“G”的预测概率为3/10,符号“H”的预测概率为6/10,逃逸码的预测概率为1/10。相应的,在0阶上下文“^”中,除了符号“I”以外的其它符号都可以被排除。符号“I”在上下文“^”中的预测概率为3/4。

  从上面的例子中可以看出,排除符号方案可以有效的提高算法的压缩率。排除符号后,所有剩余符号的预测概率都得到了改善。所以排除符号是一种非常有效的优化方案。但是它的缺点也很大。使用排除符号方案时,对于每个上下文中的所有符号都要进行筛选。我们将排除符号后的剩余符号的总计频度用T’(s) (T’(s) ≤ T(s))来表示。T’(s)不同于T(s),T(s)只有在模型更新后才会改变,而T’(s)是随时变化的。所以在编码前需要临时计算T’(s)。这些操作都将大大的增加算法的耗时。不过,与压缩率的有效提高相比,算法耗时的增加还是可以容忍的。

  在具体实现的时候,可以建立一张掩码表。掩码表可以是一个包含了M个元素的数组。在掩码表中记录了哪个符号曾经出现过。在编码前需要对掩码表进行清空,每编码一个上下文就要对上下文中的所有符号进行遍历。如果符号在掩码表中就排除符号,如果没有就添加进掩码表。同时对符号频度进行统计。还有一点需要注意,如果一个符号的频度为0,我们视这个符号没有出现在上下文中。所以零频符号不能添加进掩码表中。

2.5 逃逸估计

  每个上下文中都有一个逃逸码,每个逃逸码都有自己的频度。确定逃逸码的频度不像符号频度那样简单。在我们更新模型时,对匹配上下文中的对应符号频度加1即可。在随后的编码过程中可以利用对应的符号频度计算预测概率。但是逃逸码频度不能这样确定。如果一个上下文中只出现了少数的几个符号,每个符号的频度都很小。那么此时逃逸码的频度应该相对较大。因为这种情况下出现逃逸的概率很高。反之,如果一个上下文中出现了大量的符号,或者部份符号的频度非常大。那么此时逃逸码的频度应该相对较小。因为这种情况下出现匹配的概率很高。如果一个上下文中出现了M个符号,那么此时逃逸码的频度应该为0。因为这种情况下不可能出现逃逸。所以说,逃逸码的频度需要根据当前上下文中的相关信息来进行确定。

  根据当前上下文中的信息估计出对应逃逸码的频度,称为逃逸估计(Escape Estimation,EE)。逃逸码的频度必需能够反应出当前上下文中出现逃逸的概率有多大。所以,逃逸估计严重影响着PPM算法的压缩率。正因为如此,“如何估计逃逸码的频度?”这个问题吸引了许许多多的研究人员,同时也提出了各种各样的逃逸估计的方法。对于PPM算法逃逸估计是必需要进行的,所以在算法命名时通常将逃逸估计的方法名添加到名称的末尾。例如,使用方法A(Method A)进行逃逸估计的PPM算法称为PPMA。下面将介绍几种常见的逃逸估计的方法。

  方法A(Method A)是最早提出的同时也是最简单的逃逸估计方法。方法A将逃逸码频度设置为1,并且保持不变。即,f(esc|s) = 1。

  方法C(Method C)最早由Alistair Moffat在1990年提出[2]。方法C将逃逸码的频度设置为m(s)。即,f(esc|s) = m(s)。

  方法X(Method X)最早由Ian H. Witten和Timothy C. Bell在1991年提出[3],后来该方法又出现了多个变体。方法X将逃逸码的频度设置为上下文中频度为1的符号的个数。但是,有可能出现这样的情况,在一个上下文中所有符号的频度都不为1。为了解决这个问题,方法X对所有计算出来的逃逸码频度都加上1。当然,还有其它的解决方法。如果计算出来的逃逸码频度为0,那么就用方法A或者方法C来计算逃逸码频度。这两种估计方法被分别称为方法XA(Method XA)和方法XC(Method XC)。以方法XA为例,先以频度为1的符号的个数作为逃逸码的频度。如果计算出来的逃逸码频度为0,那么就将逃逸码频度设置为1。在这里使用m1(s)来表示上下文s中频度为1的符号的个数。那么方法X系列的三种频度估计方法的计算公式如下。

  方法D(Method D)最早由Paul Glor Howard在1993年提出[4]。方法D与方法C类似,也是将逃逸码的频度设置为m(s)。不过,方法D只给逃逸码频度一半的权值。这相当于将上下文中的符号频度放大一倍。这里需要注意一点,使用方法D时,对于预测概率的计算与其它方法不同。使用方法D时,逃逸码频度以及相关预测概率的计算公式如下。

  具体实现的时候,在计算逃逸码频度和统计相关频度信息时需要注意几点。首先,零频符号视为没有出现在当前上下文中,所以统计m(s)时需要过滤掉零频符号。另外,如果使用了排除符号方案,一般用T’(s)来代替T(s)。即,统计总计频度时忽略已排除符号的频度。还有,无论是否使用排除符号方案,都不影响m(s)的统计。m(s)始终表示上下文s中出现的符号数量。

  现在使用语料库[14]中的18个文件对这6种逃逸估计方法进行测试。测试程序使用了本章介绍的所有优化方案,只有逃逸码估计方法上的不同。测试程序使用最高5阶的上下文来进行压缩。其测试结果如表6.2所示。

文件 PPMA PPMC PPMX PPMXA PPMXC PPMD
bib 1.997 1.916 1.930 1.898 1.901 1.876
book1 2.360 2.339 2.297 2.284 2.291 2.297
book2 2.042 2.005 1.991 1.969 1.975 1.968
geo 6.085 4.716 4.731 4.770 4.764 4.710
news 2.576 2.395 2.407 2.388 2.389 2.364
obj1 4.543 3.745 3.776 3.806 3.804 3.751
obj2 2.758 2.441 2.488 2.463 2.464 2.419
paper1 2.502 2.375 2.404 2.362 2.363 2.337
paper2 2.435 2.358 2.354 2.325 2.330 2.315
paper3 2.745 2.618 2.622 2.597 2.599 2.579
paper4 3.118 2.920 2.943 2.916 2.913 2.892
paper5 3.259 3.016 3.052 3.024 3.022 2.989
paper6 2.610 2.454 2.496 2.447 2.449 2.420
pic 0.880 0.810 0.803 0.816 0.815 0.806
progc 2.610 2.412 2.461 2.418 2.419 2.379
progl 1.784 1.730 1.758 1.711 1.718 1.695
progp 1.840 1.749 1.800 1.742 1.744 1.715
trans 1.609 1.539 1.587 1.529 1.531 1.495
总计 2.221 2.085 2.083 2.067 2.070 2.055

表2.2 逃逸估计方法的测试结果(单位bpc)

  观察表2.2中的测试结果可以发现,方法A的压缩率最差,其它的几种方法略有差别。总体而言,方法D的压缩率最优秀。在方法X系列的三种逃逸估计方法中,方法XA的压缩率最优秀。目前,在PPM算法中使用逃逸估计时,最常用的也是方法D。在本文的后续内容中也将使用方法D作为逃逸估计的方法参与测试。

2.6 解码

  前面一直都在介绍PPM算法的编码过程,实际上PPM算法的解码与编码几乎一样。解码时需要从一个初始模型开始,这个初始模型必需同编码时的相一致。解码的模型更新过程也要同编码时的相一致。编码时使用到的优化方案,在解码时也要使用。这样才可以确保模型的变化过程保持不变。

  解码与编码不同的地方在于,解码时我们输入的是一个估计频度,利用这个估计频度进行查找才可以解码出一个符号。解码时我们可以建立一个临时的M个元素的数组,用以保存累积频度表。在遍历上下文中所有符号的同时,计算对应的累积频度并逐一放入累积频度表中。根据算法的特点,我们可以确定累积频度表是一个升序的已排序数组。这样在累积频度表上查找估计频度时,我们可以使用折半查找法(Binary Search)。

  在编码时所要进行的操作,在解码时都要进行。不仅如此,在解码时还要增加了一个查找操作。所以对于PPM算法来说,解码的耗时要比编码的耗时更大。不过,一般情况下上下文中出现的符号较少,而且我们还使用了折半查找法。所以,解码的耗时只会比编码的耗时略大。

2.7 测试与分析

  在本节中将对PPM算法的一般实现进行测试。由于PPM算法可以使用多种变体方案。所以对于在本文中出现的各种PPM算法的实现方案,本文将按章节进行编号。在本节测试中使用的PPM实现方案的描述如下所示。

方案2.1 使用Trie结构进行建模;使用Delphi 7.0自带的内存管理函数进行内存的分配、扩展和释放;更新时使用排除更新方案;编码时使用排除符号方案;逃逸估计使用方法D(PPMD)。

  目前除PPM算法外,最常用的压缩算法是LZ系列的压缩算法。这里使用LZ系列中最经典的Deflate算法与方案2.1进行对比测试。Delphi 7.0自带了一个ZLib单元。ZLib实际上是一个进行数据压缩的函数库,由Jean-loup Gailly和Mark Adler开发,最初的0.9版在1995年5月1日发表。ZLib使用的就是Deflate算法。Deflate算法将LZ77算法与哈夫曼算法进行了整合。相当于将数据用LZ77算法压缩一遍,然后用哈夫曼算法再压缩一遍。Deflate算法是目前最为常用的一种数据压缩算法。在WinZip中也使用了这种算法。在本节测试中使用Delphi 7.0自带的ZLib单元进行数据压缩。压缩时将压缩等级设置为clMax。

  现在使用语料库[14]中的18个文件进行测试。使用最高5阶的方案2.1与ZLib算法进行压缩率对比测试。测试结果如表2.3所示。

文件 输入大小
(字节)
ZLib算法 方案2.1
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
bib 111261 34924 2.511 26087 1.876
book1 768771 312490 3.252 220762 2.297
book2 610856 206139 2.700 150270 1.968
geo 102400 68365 5.341 60291 4.710
news 377109 144603 3.068 111438 2.364
obj1 21504 10307 3.834 10083 3.751
obj2 246814 81074 2.628 74618 2.419
paper1 53161 18528 2.788 15531 2.337
paper2 82199 29669 2.888 23787 2.315
paper3 46526 18059 3.105 14997 2.579
paper4 13286 5519 3.323 4803 2.892
paper5 11954 4980 3.333 4466 2.989
paper6 38105 13198 2.771 11525 2.420
pic 513216 52369 0.816 51675 0.806
progc 39611 13247 2.675 11779 2.379
progl 71646 16150 1.803 15177 1.695
progp 49379 11172 1.810 10588 1.715
trans 93695 18848 1.609 17512 1.495
总计 3251493 1059641 2.607 835389 2.055

表2.3 压缩率对比测试结果

  从表2.3中的数据中可以看出,PPM算法的压缩率明显要优于LZ系列算法。从总计上看,与ZLib算法相比方案2.1的压缩率提高了21.17%。对于部份文件,如“book1”,方案2.1的压缩率提高了29.37%。PPM压缩算法的压缩率还是很优秀的。这里还只是一般实现,在使用了变体方案后压缩率还可以进一步的提高。

  现在对最高5阶的方案2.1与ZLib算法,进行压缩耗时和解压缩耗时的对比测试。计时的单位使用毫秒(ms)。测试结果如表2.4所示。

文件 ZLib算法 方案2.1
压缩耗时 解压缩耗时 压缩耗时 解压缩耗时
bib 47 0 109 125
book1 359 15 828 844
book2 219 15 593 609
geo 94 0 469 468
news 109 16 531 563
obj1 0 0 63 63
obj2 94 0 406 406
paper1 0 15 78 78
paper2 31 0 94 109
paper3 16 0 63 62
paper4 0 0 15 31
paper5 0 0 16 15
paper6 16 0 46 63
pic 391 16 297 344
progc 16 0 63 47
progl 16 0 62 62
progp 16 0 32 47
trans 16 15 63 63

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

  从表2.4的数据中可以明显的看出,ZLib算法的耗时要优于方案2.1。由于算法的特点,ZLib算法的解压缩耗时与压缩耗时相比显得非常的小。这正是LZ系列算法被广泛使用的原因。与之相反,PPM算法的解压缩耗时会略大于压缩耗时。算法耗时较大已经成为PPM算法的固有缺点之一。对于PPM算法来说,虽然可以通过降低最高阶数的方法来降低算法的耗时。但是这样做会同时降低算法的压缩率。在本文的后续章节中将会介绍结构优化和内存管理的相关方案。这些优化方案可以有效的降低PPM算法的耗时。但是即使使用这些优化方案,PPM算法的耗时仍然较大。不过,随着计算机系统的运算速度越来越快,PPM算法在压缩率方面的优势将会慢慢的显现出来。

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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