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

yeye55的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

PPM压缩算法的分析与实现 - 附录及参考文献  

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

  下载LOFTER 我的照片书  |

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

附录A 查询表的生成

  内存管理中所使用到的查询表由两个常量数组组成。常量数组MMCountToId负责根据节点项的个数查询对应的内存块编号,常量数组MMIdToCount负责根据内存块的编号查询对应的节点项个数。查询表中的内容可以根据两个常量MM_SEED和MM_MAX_INDEX的值计算得到。根据这两个常量可以确定如何划分内存块。内存块的划分必需满足一定的要求,不能随意划分。具体的介绍请参考本文的第四章,这里不再重复。不能随意划分,意味着常量MM_SEED和MM_MAX_INDEX的值不能是任意值,必需经过精心的计算。MM_SEED和MM_MAX_INDEX的值必需相互对应。查找可用的MM_SEED和MM_MAX_INDEX的组合值的代码如代码A.1所示。

01 //查找可用的MM_SEED和MM_MAX_INDEX的组合值。
02 function Fun1: String;
03 var
04     Seed,n,i : Integer;
05     Index : array [0..256] of Integer;
06 begin
07     Result:='MM_SEED MM_MAX_INDEX'+#13#10;
08
09     for Seed:=1 to 256 do
10     begin
11         n:=2;
12         for i:=0 to Seed do
13         begin
14             Index[i]:=n; Inc(n,2);
15         end;
16
17         n:=0;
18         for i:=Seed+1 to 256 do
19         begin
20             Index[i]:=Index[i-1]+Index[n]; Inc(n);
21
22             if Index[i]=256 then
23             begin
24                 Result:=Format('%s   %3d    %3d'+#13#10,[Result,Seed,i]);
25                 break;
26             end;
27
28             if Index[i]>256 then break;
29         end;
30     end;
31
32     //完成
33 end;

代码A.1 查找可用的MM_SEED和MM_MAX_INDEX的组合值

  代码A.1中的函数Fun1可以输出可用的MM_SEED和MM_MAX_INDEX的组合值。根据这样的MM_SEED和MM_MAX_INDEX的值生成的查询表,将可以满足内存划分的要求。函数Fun1输出的数据如下所示。

MM_SEED MM_MAX_INDEX
    22     36
    36     49
    49     61
    61     72
    72     82
    82     91
    91     99
    99    106
   106    112
   112    117
   117    121
   121    124
   124    126
   126    127

  常量MM_MAX_INDEX反应出内存块会被划分到多少个等级。36意味着0到36,即,37个等级。从代码A.1中可以看出,MM_MAX_INDEX主要根据MM_SEED计算得到。在实现的时候使用太大的MM_SEED没有意义。所以本文的配套程序中使用22与36的组合。根据这样的组合生成查询表常量定义代码的代码如代码A.2所示。

01 //根据MM_SEED和MM_MAX_INDEX的值生成查询表常量定义代码。
02 function Fun2: String;
03 const
04     MM_SEED = 22;
05     MM_MAX_INDEX = 36;
06 var
07     i,m,n : Integer;
08     CountToId : array [2..256] of Byte; //个数转索引
09     IdToCount : array [0..MM_MAX_INDEX] of Word; //索引转个数
10 begin
11     //生成转换表
12     IdToCount[0]:=2;
13     m:=2;
14     for i:=1 to MM_SEED do
15     begin
16         Inc(m,2); IdToCount[i]:=m;
17     end;
18
19     n:=2;
20     for i:=MM_SEED+1 to MM_MAX_INDEX do
21     begin
22         Inc(m,n); IdToCount[i]:=m; Inc(n,2);
23     end;
24
25     m:=0;
26     for i:=2 to 256 do
27     begin
28         CountToId[i]:=m;
29
30         if i=IdToCount[m] then Inc(m);
31     end;
32
33     //生成常量定义代码
34     Result:='    //根据节点项的个数查询对应的内存块编号'+#13#10
35            +'    MMCountToId : array [2..256] of Byte = ('+#13#10
36            +'        ';
37
38     n:=0;
39     for i:=2 to 256 do
40     begin
41         Result:=Format('%s%2d, ',[Result,CountToId[i]]);
42
43         Inc(n);
44         if n=16 then
45         begin
46             n:=0; Result:=Result+#13#10+'        ';
47         end;
48     end;
49
50     i:=Length(Result);
51     Result[i-1]:=')';
52     Result[i  ]:=';';
53
54     Result:=Result+#13#10#13#10
55            +'    //根据内存块的编号查询对应的节点项个数'+#13#10
56            +'    MMIdToCount : array [0..MM_MAX_INDEX] of Word = ('+#13#10
57            +'        ';
58
59     n:=0;
60     for i:=0 to MM_MAX_INDEX do
61     begin
62         Result:=Format('%s%3d, ',[Result,IdToCount[i]]);
63
64         Inc(n);
65         if n=16 then
66         begin
67             n:=0; Result:=Result+#13#10+'        ';
68         end;
69     end;
70
71     i:=Length(Result);
72     Result[i-1]:=')';
73     Result[i  ]:=';';
74
75     //完成
76 end;

代码A.2 根据MM_SEED和MM_MAX_INDEX的值生成查询表常量定义代码

  代码A.2中的函数Fun2可以生成查询表的常量定义代码。内存管理程序在执行的时候需要频繁的查询这些常量数组。函数Fun2生成的代码如代码A.3所示。

01     //根据节点项的个数查询对应的内存块编号
02     MMCountToId : array [2..256] of Byte = (
03          0,  1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,
04          8,  9,  9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16,
05         16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24,
06         24, 24, 24, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26,
07         26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28,
08         28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29,
09         29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
10         30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31,
11         31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32,
12         32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 33, 33, 33, 33,
13         33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33,
14         33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
15         34, 34, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35,
16         35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35,
17         35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
18         36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36);
19
20     //根据内存块的编号查询对应的节点项个数
21     MMIdToCount : array [0..MM_MAX_INDEX] of Word = (
22           2,   4,   6,   8,  10, 12, 14, 16, 18, 20, 22, 24, 26,  28,  30,  32,
23          34,  36,  38,  40,  42, 44, 46, 48, 52, 58, 66, 76, 88, 102, 118, 136,
24         156, 178, 202, 228, 256);

代码A.3 函数Fun2生成的代码

  代码A.3中的内容就是最后生成的查询表常量数组的定义代码。查询这两个表中的数据就可以判断出内存块是如何划分的。本文第四章中表4.2中的数据就是根据代码A.3计算得到的。另外声明一点,本人不保证这样的划分策略是最优秀的。读者感兴趣的话可以自己进行研究,也许可以设计出一套更为优秀的划分策略。

附录B 方案汇总

B.1 基本方案

  基本方案是指PPM算法中使用的各种优化方案和变体方案。PPM算法拥有数量众多的基本方案。不仅如此,这些基本方案还可以相互整合。这也造就了众多的实现方案。在本节中,将对与PPM算法相关的基本方案进行汇总,以方便读者的查阅。另外,对于内存管理器中的一些方案,如预分配、碎片整理等。由于这些方案对于PPM算法来说是“透明”的,所以在本节中不对这些方案进行汇总。关于这些方案的内容请参考本文的第四章。现在对于本文中出现的基本方案汇总如下。

  ·Trie结构

  Trie结构是建模数据结构的实现方案。Trie结构是一种树结构。在Trie结构中我们将s0作为根节点,sD作为叶子节点。对于一个上下文,我们根据构成上下文的从左到右的符号将这个上下文放置到Trie结构中。Trie结构便于上下文的查找。详见2.2节。

  ·排除更新(Update Exclusion

  排除更新方案在更新模型的时候使用。当使用排除更新方案时,对于较低阶的上下文不进行更新,只对较高阶的上下文进行更新。使用排除更新方案以后,可以只更新一部份的上下文。这有助于降低算法耗时。另外,它又能防止低阶上下文中出现过于平均的概率分布。详见2.3节。

  ·削减频度(Scaling Freq

  对一个上下文中的符号频度进行更新的时候,如果符号频度超过了一个限定值,就需要进行削减频度。削减频度时,对当前上下文中的所有符号的频度都进行减半处理。在一般实现中,可以允许削减后出现零频符号。详见2.3节。

  ·排除符号(Exclude Symbol

  在进行编码的时候,将已经编码过的上下文中的符号从当前的上下文中排除出去。这就是排除符号方案。排除符号方案可以有效的提升算法的压缩率。排除符号后,所有剩余符号的预测概率都得到了改善。但是,排除符号方案会增加算法的耗时。详见2.4节。

  ·逃逸估计(Escape Estimation,EE

  根据当前上下文中的信息估计出对应逃逸码的频度,称为逃逸估计。在PPM算法中,所有的上下文都需要进行逃逸估计。逃逸估计的方法有很多种,对于逃逸估计方法的选择将会严重的影响到算法的压缩率。详见2.5节。

  ·方法A(Method A

  方法A是逃逸估计方法中的一种。一般将使用方法A的PPM算法称为PPMA。方法A将逃逸码频度设置为1,并且保持不变。这种方案的压缩率最低。详见2.5节。

  ·方法C(Method C

  方法C是逃逸估计方法中的一种。一般将使用方法C的PPM算法称为PPMC。方法C将逃逸码的频度设置为m(s)。详见2.5节。

  ·方法X(Method X

  方法X是逃逸估计方法中的一种。一般将使用方法X的PPM算法称为PPMX。方法X将逃逸码的频度设置为上下文中频度为1的符号的个数再加上1。详见2.5节。

  ·方法XA(Method XA

  方法XA是逃逸估计方法中的一种。一般将使用方法XA的PPM算法称为PPMXA。方法XA将逃逸码的频度设置为上下文中频度为1的符号的个数。如果上下文中所有符号的频度都不为1,那么就将逃逸码频度设置为1。详见2.5节。

  ·方法XC(Method XC

  方法XC是逃逸估计方法中的一种。一般将使用方法XC的PPM算法称为PPMXC。方法XC将逃逸码的频度设置为上下文中频度为1的符号的个数。如果上下文中所有符号的频度都不为1,那么就将逃逸码频度设置为m(s)。详见2.5节。

  ·方法D(Method D

  方法D是逃逸估计方法中的一种。一般将使用方法D的PPM算法称为PPMD。方法D与方法C类似,也是将逃逸码的频度设置为m(s)。不过,方法D只给逃逸码频度一半的权值。这相当于将上下文中的符号频度放大一倍。在本文介绍的几种逃逸估计方法中,方法D的压缩率最高。详见2.5节。

  ·区分削减

  区分削减方案在需要对一个上下文进行削减频度时使用。使用区分削减方案后,在非最高阶上下文中削减频度时不允许出现零频符号。在最高阶上下文中削减频度时允许出现零频符号。如果出现零频符号,就将该符号从当前上下文中删除。区分削减方案可以有效的提高算法效率。另外,区分削减方案只会轻微的影响到算法的压缩率。详见3.2节。

  ·内存共用

  对于二元上下文,将仅有的TItem保存在对应的TNode中,这就是内存共用方案。使用内存共用方案后,每个上下文节点都会增加2个字节。但是测试表明,内存共用方案可以有效的节约内存的使用量。详见3.3节。

  ·上下文Trie(Context Trie,CT

  CT结构是建模数据结构的实现方案。CT结构是以Trie结构为基础,忽略部份的上下文节点,并且增加一个符号列表。使用CT结构后,模型中的上下文节点数量大幅减少。使用CT结构不但可以节约内存,而且有助于降低算法的耗时。详见3.4节。

  ·定量内存(Ration Memory

  在编码前指定一个定量,在初始化模型前根据这个定量的大小来分配一块内存。这块内存就被称为定量内存。在随后建立模型的过程中,只能从定量内存中分配内存。如果定量内存出现溢出,那么就对模型进行重置,重置后的模型将返回到初始状态。使用定量内存方案可以大幅的降低算法的耗时。详见4.2节。

  ·局部阶估计(Local Order Estimation,LOE

  当使用LOE方案时,从当前分支的sH, sH-1, ..., s0 , si ∈ Zn上下文中按照一定的标准选择一个上下文。首先在选择的上下文中进行编码。如果选择的上下文不是匹配上下文,那么就从比选择上下文更低1阶的上下文开始,像正常算法那样进行编码。当使用较高的最高阶数进行压缩时,LOE方案有助于提高压缩率。但是,LOE方案的耗时较大。详见第五章。

  ·确定性上下文(Deterministic Contexts,Det-Context

  在使用LOE方案的时候,如果我们需要从当前分支中选择一个上下文,那么我们可以选择一个最低阶的只包含一个符号的上下文。我们称这样的上下文为确定性上下文。确定性上下文方案的性能不高。详见5.2节。

  ·估计上下文(Estimation Contexts,Est-Context

  在使用LOE方案的时候,如果我们需要从当前分支中选择一个上下文,那么我们可以对当前分支中的所有上下文,都各自计算一个称之为置信度的值。然后选择一个置信度最大的上下文。我们称这样的上下文为估计上下文。实现时一般使用MPS-P作为置信度。详见5.3节。

  ·二次逃逸估计(Secondary Escape Estimation,SEE

  按照一个量化策略,根据上下文中的相关信息量化生成一个SEE上下文。根据SEE上下文建立一个SEE模型。编码一个符号的时候。首先根据SEE模型中的统计信息输出逃逸的或者是匹配的预测概率。如果是匹配,那么再根据PPM模型中的统计信息输出符号的预测概率。编码完一个符号后,对于SEE模型和PPM模型都需要进行更新。SEE方案可以有效的提高算法的压缩率。而且,SEE方案同其它变体方案的兼容性也很好。详见第六章。

  ·信息继承(Information Inheritance,II

  当我们把一个符号添加到当前上下文中时,可以使用这个符号在父上下文中的频度信息,来计算这个符号在当前上下文中的初始频度。即,符号在当前上下文中的初始频度继承了来自父上下文中的频度信息。II方案可以有效的提高算法的压缩率。同时,II方案对于算法耗时的影响不会很大。详见第七章。

  ·无限长度上下文(Unbounded Length Contexts,ULC

  不对最高阶数进行限制,同时让模型能够处理无限长度的上下文,这就是ULC方案。从理论上来说,使用ULC方案可以获得最优秀的压缩率。但是使用ULC方案会使模型的内存占用以及算法的耗时大幅增加。所以从总体性能的角度来讲,ULC方案的性能并不是很好。详见第八章。

B.2 实现方案

  由于PPM算法的实现方案很复杂,所以在本文中对于出现的实现方案都按照章节号进行编号。在本文配套的项目程序中,一个实现方案对应于一个pas文件。pas文件按照方案的编号进行命名。在本文中出现的所有实现方案如下所示。

方案2.1
PPM21.pas
使用Trie结构进行建模;使用Delphi 7.0自带的内存管理函数进行内存的分配、扩展和释放;更新时使用排除更新方案;编码时使用排除符号方案;逃逸估计使用方法D(PPMD)。详见2.7节。
方案4.1
PPM41.pas
使用CT结构(Context Trie)进行建模;使用定量内存,并使用自行设计的专用内存管理器对定量内存进行管理;构建模型时使用内存共用方案;削减频度时使用区分削减方案;更新时使用排除更新方案;编码时使用排除符号方案;逃逸估计使用方法D(PPMD)。详见4.6节。
方案5.1
PPM51.pas
以方案4.1(PPMD)为基础,整合LOE方案;使用LOE方案选择上下文时,以MPS-P作为置信度,并选择置信度最大的上下文作为估计上下文;其它描述与方案4.1相同(PPMD+LOE)。详见5.5节。
方案6.1
PPM61.pas
以方案4.1(PPMD)为基础,不再使用方法D,并整合SEE方案;使用SEE方案时,建立两个SEE模型,一个供二元上下文使用,一个供多元上下文使用;初始化时使用一份数据表来对SEE模型进行初始化;其它描述与方案4.1相同(PPM+SEE)。详见6.5节。
方案6.2
PPM62.pas
以方案6.1(PPM+SEE)为基础,整合LOE方案;使用SEE方案时,建立两个SEE模型,一个供估计上下文使用,一个供多元上下文使用;使用LOE方案选择上下文时,以MPS-P作为置信度,并选择置信度最大的上下文作为估计上下文;其它描述与方案6.1相同(PPM+SEE+LOE)。详见6.5节。
方案7.1
PPM71.pas
以方案4.1(PPMD)为基础,整合II方案;使用II方案时,利用公式来计算符号的初始频度,并对方法D进行适当的调整;其它描述与方案4.1相同(PPMD+II)。详见7.7节。
方案7.2
PPM72.pas
以方案7.1(PPMD+II)为基础,整合LOE方案;使用LOE方案选择上下文时,以MPS-P作为置信度,并选择置信度最大的上下文作为估计上下文;其它描述与方案7.1相同(PPMD+II+LOE)。详见7.7节。
方案7.3
PPM73.pas
以方案6.1(PPM+SEE)为基础,整合II方案;使用II方案时,利用公式来计算符号的初始频度;其它描述与方案6.1相同(PPM+SEE+II)。详见7.7节。
方案7.4
PPM74.pas
以方案7.3(PPM+SEE+II)为基础,整合LOE方案;使用SEE方案时,建立两个SEE模型,一个供估计上下文使用,一个供多元上下文使用;使用LOE方案选择上下文时,以MPS-P作为置信度,并选择置信度最大的上下文作为估计上下文;其它描述与方案7.3相同(PPM+SEE+II+LOE)。详见7.7节。
方案8.1
PPM81.pas
以方案4.1(PPMD)为基础,整合ULC方案;使用ULC方案时,对CT结构进行适当的调整,同时不再使用区分削减方案,削减频度时不允许出现零频符号;其它描述与方案4.1相同(PPMD+ULC)。详见8.4节。
方案8.2
PPM82.pas
以方案6.2(PPM+SEE+LOE)为基础,整合ULC方案;使用ULC方案时,对CT结构进行适当的调整,同时不再使用区分削减方案,削减频度时不允许出现零频符号;其它描述与方案6.2相同(PPM+SEE+LOE+ULC)。详见8.4节。
方案8.3
PPM83.pas
以方案7.3(PPM+SEE+II)为基础,整合ULC方案;使用ULC方案时,对CT结构进行适当的调整,同时不再使用区分削减方案,削减频度时不允许出现零频符号;其它描述与方案7.3相同(PPM+SEE+II+ULC)。详见8.4节。

附录C 项目说明

C.1 程序项目

  该程序项目是本文的配套程序。该程序项目同时作为免费开源程序进行发布。该程序项目中的代码无需任何授权或许可即可用于个人和商业目的。使用者一切后果自负。

  该程序项目是在Delphi 7.0下开发,编译通过并且调试正常。该程序项目提供了一个文件到文件的,PPM算法的压缩程序。该程序项目中还提供了相关的测试代码,以分析PPM算法的内存占用。在该程序项目中,有部分文件来自于我写的另外两篇论文[13,15]。该程序项目中的主要文件及相关说明如表C.1所示。

文件 说明
Project1.dpr 项目主文件
Project1.exe 项目可执行文件
Unit1.pas 主窗口单元文件
Unit1.dfm 主窗口窗体文件
MemoryBuffer.pas 内存缓冲区管理单元文件
RangeCoding.pas 区间编码算法实现单元文件
MemoryManager.pas 专用内存管理器实现单元文件
MemoryManager_Debug.pas 带测试信息实现的单元文件
PPM??.pas PPM算法实现的系列单元文件
PPM??_Debug.pas 带测试信息实现的系列单元文件

表C.1 项目主要文件说明

  在程序项目中,MemoryBuffer.pas文件[15]用于内存缓冲区的管理,RangeCoding.pas文件[13]用于区间编码算法的实现。这两个文件的详细说明请参考相关论文[13,15]中对应的项目说明。MemoryManager.pas文件用于专用内存管理器的实现,该内存管理器专用针对PPM算法而设计,其理论基础和实现方法请参考本文的第四章。另外,PPM??.pas指的是一系列的单元文件,一共有12个这样的单元文件,一个这样的单元文件对应于本文的一个实现方案。详细的文件名以及对应方案的详细说明请参考本文的附录B。在PPM??.pas系列文件中是对于PPM算法的统计模型的实现。它需要使用MemoryManager.pas文件中的程序来进行内存管理。同时,它还需要使用RangeCoding.pas文件中的程序来输出预测概率。所以这些文件需要放在一起使用。

C.2 MemoryManager.pas文件

  在该单元文件中编写了专用内存管理器的实现代码。在该单元文件中只定义了一个被称为内存分配器的类TMMAllocator。TMMAllocator类实现了对一个定量内存的管理,并支持内存块的分配与回收。注意一点,TMMAllocator类分配的内存块大小是以节点项的个数为单位的,一个节点项的大小为6个字节。TMMAllocator类最少分配2个单位长度的内存块,即12个字节。最多分配256个单位长度的内存块,即1536字节。对于TMMAllocator类中的方法说明如下。

  InitAlloc方法用于初始化。在调用其它的所有方法之前必需先调用这个方法,以便对内存分配器进行初始化。InitAlloc方法有一个参数Ration,这个参数指定了内存分配器使用的定量内存的大小。在调用完InitAlloc方法之后,在开始分配内存块之前还需要调用Restart方法,才能完成全部的初始化操作。

  Restart方法用于重置内存分配器。调用Restart方法将会回收所有分配过的内存块,同时将内存分配器恢复到初始状态。一般在定量内存出现溢出后,调用Restart方法来进行定量内存的重置。

  PutBlock方法将一个指定的内存块放入到回收池中。如果指定的内存块不是完整的,那么PutBlock方法将对这个内存块进行分割,使其成为两个完整的内存块。PutBlock方法有两个参数Block和Count。Block参数指向需要回收的内存块,Count参数指定了内存块的大小。

  GlueBlock方法用于碎片整理。调用时,GlueBlock方法会把当前回收池中的所有内存块全部取出,然后将连续的内存块合并在一起,最后再将这些内存块放回到回收池中。关于碎片整理的详细说明请参考本文的4.5节。

  IncSymPos方法用于将符号列表的指针位置下移一个字节。如果IncSymPos方法返回False,说明定量内存的空间已经用完,需要进行定量内存重置。

  AllocBlock方法用于分配一个内存块。调用AllocBlock方法时,如果在回收池中有合适的内存块就从回收池中分配,如果没有就从定量内存中分配。同样的,如果AllocBlock方法返回False,说明定量内存的空间已经用完,需要进行定量内存重置。

  FreeItems方法用于释放一个节点项数组。调用FreeItems方法后,对应的内存块将会被放入到回收池中。FreeItems方法不会检查内存块的合法性,所以调用前必需确定对应的内存块是由当前的内存分配器分配的,而且相关的参数都是正确无误的。

  ExpandItems方法用于扩展一个节点项数组。根据PPM算法中统计模型的特点,每次扩展节点项数组时都是只扩展一个元素。所以在调用ExpandItems方法后只会对原数组增加一个元素。ExpandItems方法会先检查新旧内存块是否被划分到了同一个范围内。如果是就直接返回,如果不是再分配新内存块拷贝数据,同时释放旧内存块。另外,如果ExpandItems方法返回False,说明定量内存的空间已经用完,需要进行定量内存重置。

  ShrinkItems方法用于收缩一个节点项数组。在调用时,ShrinkItems方法会先检查收缩前后的内存块是否被划分到了同一个范围内。如果是就直接返回,如果不是那么ShrinkItems方法将会对原内存块进行分割,回收多余的部份。所以,调用ShrinkItems方法始终是成功的,不会出现内存用完的情况。

  在该单元文件中还有两个非常重要的常量数组MMCountToId和MMIdToCount。通过这两个常量数组可以查询到当前内存块的划分情况。如果两个内存块的编号相同,那么这两个内存块就是划分在同一个范围内,它们实际分配的内存大小也是一样的。在分配的过程中需要频繁的访问这两个常量数组,而这两个常量数组中的数据将会严重的影响内存分配器的性能。所以,这两个常量数组中的数据不能随意修改。生成这两个常量数组的程序代码请参考本文的附录A,其相关的理论基础和实现方法请参考本文的4.3节。

C.3 MemoryManager_Debug.pas文件

  该单元文件是在MemoryManager.pas文件的基础上添加了测试代码而得到的。该单元文件中的基本功能与MemoryManager.pas文件中的完全相同。除此之外,在该单元文件中还会对程序运行过程中的重置内存分配器的次数、碎片整理的次数、分配的小内存块大小、分配的大内存块大小、空占内存的大小等数据进行记录。另外,在该单元文件的TMMAllocator类中还增加了一个OutDebug方法。OutDebug方法会统计模型的内存占用情况和相关的比例,并且将这些数据通过Unit1.pas文件中的Form1.Memo1输出。正是由于如此,该单元文件必需与Unit1.pas文件一同使用。

C.4 PPM??.pas系列文件

  该系列文件由12个单元文件组成,一个单元文件对应于本文的一个实现方案。在这些单元文件中编写了不同实现方案的PPM算法的实现代码。这些单元文件在大体结构上是相同的,但是在细节处理上却有所不同。在这些单元文件中都定义有两个类TPPMCoder类和TPPMCoding类。TPPMCoder类实现了PPM算法,但是TPPMCoder类并不输出数据。在编码过程中TPPMCoder类向TRCCoder类输出预测概率。TRCCoder类在RangeCoding.pas文件[13]中定义。另外,TPPMCoding类提供了对TPPMCoder类和TRCCoder类的简单封装。对应于不同的实现方案,TPPMCoder类中的成员和方法也是不同的。对于TPPMCoder类中的方法说明如下。

  ChooseContext方法用于从当前分支中选择一个MPS-P最大的上下文。只有使用了LOE方案的实现方案才会有这个方法。ChooseContext方法根据FHiContext成员来判断当前分支中最高阶的上下文,并对当前分支中的所有上下文进行遍历,逐一计算MPS-P。在计算MPS-P时使用的是浮点运算,所以使用Extended类型的变量来保存MPS-P。在选择完成后,ChooseContext方法会设置FLoContext成员和FLoOrder成员用于指定估计上下文。另外,对于使用了SEE+LOE整合方案的实现方案,ChooseContext方法会变得更加复杂。在计算MPS-P时,需要对每个上下文逐一进行量化。在选择完成后还需要把估计上下文对应的SEE上下文保存到FSEEContext成员中。对于估计上下文的详细说明请参考本文的5.3节。

  SearchBranch方法用于搜索当前分支查找当前符号。只有使用了LOE方案的实现方案才会有这个方法。并且,只有当估计上下文匹配时才会调用这个方法。SearchBranch方法从当前分支中的最高阶上下文搜索到估计上下文,以查找比估计上下文更高阶的上下文中是否有匹配上下文。同时,在SearchBranch方法中还会对当前符号的频度进行更新操作。

  BinQuantize方法用于对二元上下文进行量化。只有使用了SEE方案的实现方案才会有这个方法。但是,对于使用了SEE+LOE整合方案的实现方案没有这个方法。因为,对于任意上下文的量化合并到了ChooseContext方法中完成。BinQuantize方法利用FLoContext成员来确定当前的上下文,并返回一个15位的SEE上下文。对于量化方式的详细说明请参考本文的6.2节。

  MulQuantize方法用于对多元上下文进行量化。只有使用了SEE方案的实现方案才会有这个方法。MulQuantize方法利用FLoContext成员来确定当前的上下文,并返回一个15位的SEE上下文。MulQuantize方法有一个参数SymTotal,SymTotal参数对应于在当前上下文中排除符号后的总计频度。MulQuantize方法需要利用这个值来进行量化。对于量化方式的详细说明请参考本文的6.2节。

  SymEncode方法用于在当前上下文中编码一个符号。只有在方案2.1的实现方案中才会有这个方法。因为在一般实现下,不用区分二元上下文和多元上下文。SymEncode方法会对当前上下文中的频度信息进行统计,计算并输出预测概率。如果出现匹配,SymEncode方法还会对当前符号的频度进行更新,并且设置FFindItem成员指向对应的节点项。

  SymDecode方法用于在当前上下文中进行解码。只有在方案2.1的实现方案中才会有这个方法。SymDecode方法会对当前上下文中的频度信息进行统计,并生成一个累积频度表。然后输入一个预测概率,并在累积频度表中进行查找。如果出现匹配,SymDecode方法还会对当前符号的频度进行更新,并且设置FFindItem成员指向对应的节点项。

  BinEncode方法用于在二元上下文中编码一个符号。在二元上下文中的预测概率可以直接判断出来,不需要进行统计。所以,在BinEncode方法中的代码很简单。BinEncode方法会输出一个预测概率。如果出现匹配,BinEncode方法还会对当前符号的频度进行更新,并且设置FFindItem成员指向对应的节点项。

  BinDecode方法用于在二元上下文中进行解码。BinDecode方法会输入一个预测概率,并用于解码。如果出现匹配,BinDecode方法还会对当前符号的频度进行更新,并且设置FFindItem成员指向对应的节点项。

  MulEncode方法用于在多元上下文中编码一个符号。MulEncode方法同SymEncode方法类似。

  MulDecode方法用于在多元上下文中进行解码。MulDecode方法同SymDecode方法类似。

  EstEncode方法用于在估计上下文中编码一个符号。只有使用了LOE方案的实现方案才会有这个方法,同时BinEncode方法将会被取消。估计上下文有可能是一个二元上下文,也有可能是一个多元上下文。所以,EstEncode方法中的代码比较复杂,相当于合并了BinEncode方法和MulEncode方法中的代码。

  EstDecode方法用于在估计上下文中进行解码。只有使用了LOE方案的实现方案才会有这个方法,同时BinDecode方法将会被取消。EstDecode方法中的代码比较复杂,相当于合并了BinDecode方法和MulDecode方法中的代码。

  对于上述的6个用于编解码的方法BinEncode方法、BinDecode方法、MulEncode方法、MulDecode方法、EstEncode方法和EstDecode方法,这里有一点需要说明。在使用了SEE方案的实现方案中,这些编解码方法不仅需要完成相关的编解码操作,还需要对SEE模型进行相关的操作。对于当前上下文需要进行量化以获得对应的SEE上下文。特殊的,对于EstEncode方法和EstDecode方法可以直接从FSEEContext成员中获得估计上下文对应的SEE上下文。在编解码完成以后,不管是出现逃逸还是出现匹配都需要对SEE模型进行更新。

  ExtendContext方法用于扩展上下文。调用ExtendContext方法时,从当前分支的当前上下文开始遍历到根节点,逐一扩展上下文节点。如果遇到已经扩展过的上下文,那么扩展操作将会提前结束。在进行扩展操作的时候需要新建上下文节点,所以有可能出现定量内存溢出的情况。如果出现这样的情况,那么ExtendContext方法将停止操作并退出,同时返回False。反之,如果所有的操作都顺利完成,那么ExtendContext方法将返回True。

  ScalingFreq方法用于削减频度。在每次更新符号的频度之前,都需要检查符号频度是否已经达到了上限。如果达到就需要调用ScalingFreq方法来进行削减频度的操作。在一般实现的方案2.1以及其它使用了ULC方案的实现方案中,在削减频度时不允许出现零频的符号。所以,对应的ScalingFreq方法相对比较简单。对于其它使用了区分削减方案的实现方案,对应的ScalingFreq方法就比较复杂。使用区分削减方案后,在削减频度时。首先要判断当前上下文是否是最高阶上下文。在非最高阶上下文中削减频度,不允许出现零频符号。在最高阶上下文中削减频度,允许出现零频符号。如果出现零频符号,就需要将零频符号的数据移去,并且释放多余的内存。对于区分削减方案的详细说明请参考本文的3.3节。

  RestartModel方法用于重置当前模型。每次进行新建上下文节点、扩展节点项数组、移动符号列表指针位置这些操作的时候,都需要检查定量内存是否出现溢出。如果出现溢出就需要调用RestartModel方法来对模型进行重置。在调用了RestartModel方法以后,当前的模型就会被恢复到初始状态。如果使用了SEE方案,那么对应的SEE模型也会被恢复到初始状态。

  UpdateModel方法用于更新当前模型。在当前分支中完成编解码操作的时候,就需要调用UpdateModel方法来对当前模型进行更新。特殊的,如果符号出现在最高阶上下文中,那么可以不用调用UpdateModel方法来更新模型。调用UpdateModel方法时,从当前分支的最高阶上下文开始遍历到当前上下文,逐一添加对应的节点项。另外,UpdateModel方法还会将当前的符号列表的指针位置下移一个字节。UpdateModel方法进行的这些更新操作,都有可能会出现定量内存溢出的情况。如果出现这样的情况,那么UpdateModel方法将停止操作并退出,同时返回False。反之,如果所有的操作都顺利完成,那么UpdateModel方法将返回True。

  FreeNode方法用于释放所有曾经分配过的上下文节点和节点项数组。只有在方案2.1的实现方案中才会有这个方法。其它的实现方案都使用了定量内存,所以没有这个方法。FreeNode方法会对当前Trie结构中的所有节点进行遍历,对于其中分配过的每一个内存块逐一进行释放。

  InitCoder方法用于初始化当前的编解码器。在调用其它的所有方法之前必需先调用这个方法,以便对编解码器进行初始化。InitCoder方法有3个参数Coder、Order和Ration。对于不同的实现方案,InitCoder方法拥有的参数也是不同的。Coder参数用于指定一个区间编码算法编解码器。在编码的时候,将利用这个编解码器来输出预测概率。Order参数用于指定当前模型的最高阶数。使用了ULC方案的实现方案没有这个参数,因为ULC方案不对最高阶数进行限制。Ration参数用于指定当前模型使用的定量内存的大小,单位是字节。一般实现的方案2.1没有这个参数,因为方案2.1不使用定量内存。最后注意一点,如果是为了进行解码而调用InitCoder方法,那么调用时的参数必需和编码时的完全一致。

  Encode方法用于在当前模型中编码一个符号。Encode方法实际上是一个调度程序,它通过调用其它的方法来完成整个操作。Encode方法根据FHiContext成员来判断当前分支中最高阶的上下文,并对当前分支中的上下文进行遍历,以查找匹配上下文。对于遍历到的上下文,Encode方法会调用相关的编码方法,同时过滤掉相同符号数的上下文。如果符号没有出现在当前模型中,那么Encode方法将在-1阶上下文中完成编码。如果找到匹配上下文,那么Encode方法将根据需要调用ExtendContext方法来对当前上下文进行扩展。在编码完成后,Encode方法还会根据需要调用UpdateModel方法来完成对于模型的更新。在操作过程中,Encode方法将会时刻检查定量内存是否出现溢出,如果出现溢出就调用RestartModel方法来对模型进行重置。

  Decode方法用于从当前模型中解码出一个符号。在代码结构上Decode方法与Encode方法是完成一样的。只不过Encode方法调用的是相关的编码方法,而Decode方法调用的是相关的解码方法。在最后退出的时候,Decode方法将会把解码出来的符号返回。

  FinishCoder方法用于结束编解码器的操作。当所有的数据都处理完成,不再需要调用方法来进行操作的时候,可以调用FinishCoder方法来进行收尾操作。在调用完FinishCoder方法以后,如果想再使用编解码器,那么必需先调用InitCoder方法。另外注意一点,在进行收尾操作的时候,FinishCoder方法不会调用对应的TRCCoder.FinishEncode方法或者是TRCCoder.FinishDecode方法。这两个方法由编解码器的使用者自行调用。关于这两个方法的详细说明请参考相关的项目说明[13]

C.5 PPM??_Debug.pas系列文件

  该系列文件由3个单元文件组成,分别是PPM21_Debug.pas文件、PPM41_Debug.pas文件和PPM81_Debug.pas文件。这3个单元文件是在对应的单元文件的基础上添加了测试代码而得到的。这3个单元文件中的基本功能与对应的单元文件中的完全相同。对于这3个单元文件分别介绍如下。

  PPM21_Debug.pas文件对应于PPM21.pas文件。该单元文件会对程序运行过程中的分配上下节点个数、分配节点项个数等数据进行记录。在该单元文件的TPPMCoder.FreeNode方法中增加了测试代码。在释放内存的同时,对模型的内存占用情况和相关比例以及释放操作的耗时进行统计,然后将这些测试数据输出。另外,在该单元文件中可以选择使用不同的逃逸估计方法来进行压缩。只要修改对应的预编译指令中的定义,然后重新编译运行,即可实现。在本文的2.5节中表2.2中的测试数据,就是通过这样的方法测试得到的。

  PPM41_Debug.pas文件对应于PPM41.pas文件。该单元文件会对程序运行过程中的符号列表长度、分配上下节点个数、二元上下节点个数、分配节点项个数等数据进行记录。该单元文件通过调用MemoryManager_Debug.pas文件中的内存分配器来进行内存管理。在该单元文件的TPPMCoder.FinishCoder方法中增加了测试代码,调用TMMAllocator.OutDebug方法来统计和输出测试数据。另外,在该单元文件中会建立一个匹配计数表。并在程序运行的过程中,对于不同阶数上下文的匹配情况进行记录和统计。最后还会将统计得到的匹配计数表输出。

  PPM81_Debug.pas文件对应于PPM81.pas文件。该单元文件会对程序运行过程中的出现的最大阶数、符号列表长度、分配上下节点个数、二元上下节点个数、分配节点项个数等数据进行记录。该单元文件通过调用MemoryManager_Debug.pas文件中的内存分配器来进行内存管理。在该单元文件的TPPMCoder.FinishCoder方法中增加了测试代码,通过调用TMMAllocator.OutDebug方法来统计和输出测试数据。

  在这3个单元文件中得到的测试数据都会通过Unit1.pas文件中的Form1.Memo1输出。正是由于如此,这3个单元文件必需与Unit1.pas文件一同使用。

参考文献

[1] John G. Cleary, Ian H. Witten, Data Compression Using Adaptive Coding and Partial String Matching, IEEE Transactions on Communications, 1984, 32(4), 396-402.
[2] Alistair Moffat, Implementing the PPM Data Compression Scheme, IEEE Transactions on Communications, 1990, 38(11), 1917-1921.
[3] Ian H. Witten, Timothy C. Bell, The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression, IEEE Transactions on Informaton Theory, 1991, 37(4), 1085-1094.
[4] Paul Glor Howard, The Design and Analysis of Efficient Lossless Data Compression Systems, Brown University, Department of Computer Science, 1993, Technical Report No: CS-93-28.
[5] John G. Cleary, W. J. Teahan, Ian H. Witten, Unbounded length contexts for PPM, IEEE Data Compression Conference (DCC), 1995, 52-61.
[6] Charles Bloom, Solving the Problems of Context Modeling, 1998, http://www.cbloom.com/papers/ppmz.zip .
[7] Charles Bloom, PPMZ -- High Compression Markov Predictive Coder, 1999, http://www.cbloom.com/src/ppmz.html .
[8] Dmitry Shkarin, PPM: one step to practicality, IEEE Data Compression Conference (DCC), 2002, 202-211, http://compression.graphicon.ru/download/articles/ppm/shkarin_2002dcc_ppmii_pdf.rar .
[9] Dmitry Shkarin, All about data compression, image and video, 1999, http://compression.graphicon.ru/ds/ .
[10] Dmitry Shkarin, PPMd -- fast PPM compressor for textual data, 2001, http://compression.graphicon.ru/ds/ppmdh.rar .
[11] Ian H. Witten, Radford M. Neal, John G. Cleary, Arithmetic Coding for Data Compression, Communications of the ACM, 1987, 30(6), 520-541.
[12] G. N. N. Martin, Range encoding: an algorithm for removing redundancy from a digitised message, Video & Data Recording Conference, Southampton, 1979, July 24-27.
[13] 叶叶, 区间编码算法的分析与实现, 编程论坛, 2010, http://yeye55blog.blog.163.com/blog/static/197241021201110613847165/ .
[14] The Canterbury Corpus, http://corpus.canterbury.ac.nz/descriptions/ .
[15] 叶叶, 范式哈夫曼算法的分析与实现, 编程论坛, 2010, http://yeye55blog.blog.163.com/blog/static/197241021201110575844440/ .
[16] Mark Nelson, Arithmetic Coding + Statistical Modeling = Data Compression, Data Compression, 1991, February 1st, http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/ .

叶叶

2011年10月25日

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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