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

yeye55的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

PPM压缩算法的分析与实现 - 第一章 绪论  

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

  下载LOFTER 我的照片书  |

声明

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

  论文全文下载(点这里

  项目文件下载(点这里

目录

  第一章 绪论... 3

  1.1 前言... 3

  1.2 算法简述... 4

  1.3 本文约定... 5

  1.4 一个例子... 6

  1.5 开发与测试... 6

  第二章 一般实现... 7

  2.1 前言... 7

  2.2 建模结构... 7

  2.3 更新模型... 11

  2.4 排除符号... 12

  2.5 逃逸估计... 13

  2.6 解码... 15

  2.7 测试与分析... 15

  第三章 结构优化... 17

  3.1 前言... 17

  3.2 区分削减... 18

  3.3 内存共用... 18

  3.4 上下文Trie. 20

  3.5 模型的规律... 27

  第四章 内存管理... 28

  4.1 前言... 28

  4.2 定量内存... 29

  4.3 预分配... 31

  4.4 回收池... 33

  4.5 碎片整理... 35

  4.6 测试与分析... 37

  第五章 局部阶估计... 43

  5.1 前言... 43

  5.2 确定性上下文... 46

  5.3 估计上下文... 47

  5.4 方案实现... 47

  5.5 测试与分析... 48

  第六章 二次逃逸估计... 50

  6.1 前言... 50

  6.2 量化... 51

  6.3 建模... 56

  6.4 方案整合SEE+LOE. 58

  6.5 测试与分析... 59

  第七章 信息继承... 63

  7.1 前言... 63

  7.2 计算初始频度... 64

  7.3 方案实现... 66

  7.4 方案整合II+LOE. 67

  7.5 方案整合SEE+II 67

  7.6 方案整合SEE+II+LOE. 68

  7.7 测试与分析... 68

  第八章 无限长度上下文... 73

  8.1 前言... 73

  8.2 方案实现... 74

  8.3 方案整合... 76

  8.4 测试与分析... 76

  第九章 总结... 84

  9.1 总述... 84

  9.2 常见的PPM算法... 85

  9.3 结束语... 87

  附录A 查询表的生成... 88

  附录B 方案汇总... 92

  B.1 基本方案... 92

  B.2 实现方案... 95

  附录C 项目说明... 96

  C.1 程序项目... 96

  C.2 MemoryManager.pas文件... 97

  C.3 MemoryManager_Debug.pas文件... 98

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

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

  参考文献... 102

PPM压缩算法的分析与实现

作者:叶叶(网名:yeye55)

  摘要:全面介绍了PPM压缩算法的算法结构和实现方法。详细讨论了使用Trie结构和Context Trie结构建立统计模型的方法,并对这两种结构的性能进行了对比分析。详细介绍了各种用以提高算法性能的优化方案。对于针对PPM算法而设计的专用内存管理器的理论基础和实现方法进行了详细的介绍和说明。对于局部阶估计(LOE)方案、二次逃逸估计(SEE)方案、信息继承(II)方案和无限长度上下文(ULC)方案这4种变体方案的理论基础、实现方法和相互整合进行了详细的介绍和说明。同时还进行了大量的对比测试和比较分析。并且给出了一个切实可行的应用程序。

  关键字:PPM;逃逸估计;Trie;Context Trie;内存管理;局部阶估计;二次逃逸估计;信息继承;无限长度上下文;Delphi

  中图分类号:TP301.6

第一章 绪论

1.1 前言

  1984年John G. Cleary和Ian H. Witten提出了PPM算法[1]。该算法一经提出,立刻引起了广大研究人员的兴趣。PPM算法的高压缩率和自适应的特点,使得PPM算法成为一种最有效的压缩算法。自从PPM算法诞生以来,许许多多的研究人员围绕着PPM算法展开了大量的研究工作。这使得PPM算法出现了大量的变体方案,这也使得PPM算法越来越接近压缩率的极限。

  准确的说,PPM算法并不是一种压缩算法,而是一种建模算法。PPM的全称是部分匹配预测(Prediction by Partial Matching,PPM)。PPM算法通过建立一个数学模型对即将编码的符号的概率进行预测。预测的概率将交给基于概率统计的编码器进行编码,如区间编码算法[12]的编码器。由于PPM算法需要在编码过程中建立一个数学模型,并对这个模型进行更新和维护。这使得PPM算法具有算法结构复杂、算法耗时长、内存占用大等缺点。不过随着计算机系统越来越先进,这些缺点也会被慢慢的淡化。

  目前,PPM算法已经被大量的使用。主流的压缩软件都支持PPM算法的压缩。由于PPM算法是一种预测模型。PPM算法还被大量的应用在网络攻击检测、访问预测、股市预测等方面。

  本文将会对PPM算法进行全面的介绍。本文的第一章将会对PPM算法进行整体上的简述;第二章将会介绍PPM算法的一般实现;第三章将会介绍PPM算法的建模结构的优化;第四章将会介绍与PPM算法相关的内存管理器的实现;第五章将会介绍局部阶估计(LOE)方案的实现与整合;第六章将会介绍二次逃逸估计(SEE)方案的实现与整合;第七章将会介绍信息继承(II)方案的实现与整合;第八章将会介绍无限长度上下文(ULC)方案的实现与整合;第九章将会对全文进行总结,并介绍几种常见的PPM算法;另外,在本文配套的项目文件中将会给出一个利用Delphi 7.0开发的切实可行的应用程序。在这个应用程序中将会给出本文介绍的各种方案的具体实现。

1.2 算法简述

  PPM算法是一种基于概率统计模型的自适应压缩算法。PPM算法中使用的模型被称为PPM模型(PPM Model)。对于概率统计模型,在实现的时候必需遵循两个原则。第一个原则是预测的概率必需与编码过符号的概率相符合。例如,前面已经编码过10个符号,其中符号“A”出现了5次。如果现在要编码符号“A”,那么就以5/10的概率进行预测。这样才可以保证用最少的位来表示概率最高的符号。第二个原则是尽可能的避免概率的均匀分布。概率分布越均匀压缩率越低。例如,压缩字节数据时。如果每个符号都以1/256的概率进行预测。那么压缩后输出的数据,将与输入的数据一样大小。高概率可以获得高压缩率。如果一个模型可以找到一个符号不均匀分布的概率,那么就可以从中获得较高的压缩率。当然第二原则不能与第一原则相冲突。

  一般的基于概率统计模型的自适应压缩算法,如区间编码,都是根据已编码符号的频度统计信息来预测当前符号的概率。PPM算法也是如此,只不过PPM算法是根据当前符号在不同的前缀符号串中的频度统计信息来预测当前符号的概率。当前符号的前缀符号串被称为上下文(Context),前缀符号串的长度被称为阶(Order)。如果对最高阶数进行限制,这种情况被称为有限上下文(Finite Context,FC)。反之如果不限制最高阶数,则称为无限长度上下文(Unbounded Length Contexts,ULC)。

  相对而言,一般的区间编码算法可以被称为0阶算法。而PPM算法可以被称为高阶算法。熟悉0阶算法的人都知道,在模型初始化时需要将所有符号的频度都设为1。因为在预测时不能出现零频符号。但是PPM算法是高阶算法,需要处理不同阶数的多个上下文。如果在高阶模型中,将每个上下文中所有符号的频度都设为1,那么整个模型将占用大量的内存。因为许多上下文中可能只出现少量的几个符号,但是却要为所有的符号分配内存。另外,在使用高阶模型时符号的频度计数会分散到每个上下文中。这会使得频度值较小,从而造成概率分布均匀。如果所有符号的频度都设为1,已出现符号的频度要很大,才会产生高概率。在实际应用中这会严重影响压缩率。所以PPM算法建模时必需支持零频符号,这就是PPM算法的零频问题(Zero Frequency Problem)。解决零频问题的方法是在每个上下文中都添加一个逃逸码(Escape Code,又称“转义码”)。逃逸码也有自己的频度,并同其它符号一起编码。如果一个符号不在当前上下文中时,它的频度为零。此时PPM算法输出逃逸码的预测概率,并退回到低1阶的上下文中。这种情况被称为逃逸(Escape)。反之,如果符号出现在当前上下文中,就直接输出这个符号的预测概率。这种情况被称为匹配(Match)。如果符号在所有的上下文中都没有出现,那么PPM算法最终会退回到-1阶上下文中。在-1阶上下文中,所有的符号都有出现。而且符号的频度始终为1,不进行更新。解决了零频问题后,在PPM算法的高阶模型中只要记录已出现符号在不同上下文中的频度即可。这样就可以大大的节约内存,同时提高算法的压缩率。

  实际上PPM算法只进行概率预测,预测出来的概率由区间编码算法[12]的编码器进行编码。区间编码算法编码一个符号时需要接收三个数据,符号的累积频度、符号的频度、所有符号的总计频度(包含逃逸码频度)。PPM算法根据上下文中记录的符号的频度统计信息,计算出上述三个数据交给区间编码算法的编码器进行编码输出。

  一般的PPM算法的编码过程是这样的:首先从最高阶的上下文开始。如果匹配则输出符号的预测概率,同时编码结束。如果逃逸则输出逃逸码的预测概率,并且退回到低1阶的上下文中。然后从低1阶的上下文中重新开始一轮新的编码。循环这个过程,直到找到匹配的上下文或者退回到-1阶的上下文。编码结束后还要对模型进行更新。对于匹配的上下文需要将对应的符号频度加1。对于逃逸的上下文需要将符号添加到上下文中。解码的过程也是如此,这里就不再重复。

1.3 本文约定

  从上一节的内容中可以看出,PPM算法的实现是比较复杂的。PPM算法在实现时将涉及到多个上下文的操作。为了更好的说明算法,本文将约定一些公式变量和表达式。

  设A是由M (M ≥ 2)个不同的符号组成的符号集。符号串xn = x1, x2, …, xn , xi ∈ A是一份数据的前n个符号。当前的符号为xn+1 = a , a ∈ A。那么当前符号a对应的上下文为sd = xn-d+1, …, xn-2+1, xn , xi ∈ A, 0 ≤d ≤ D。其中d为上下文的阶数,D为上下文的最高阶数。我们称sd为d阶上下文。特殊的,0阶上下文s0为一个空串。我们将s0作为根节点,sd-1作为sd的父节点,sd+1作为sd的子节点,sD作为叶子节点。那么我们可以用一棵度为M、深度为D的树来描述所有可能的上下文。这棵树被称为上下文树(Context Tree),所有可能的上下文都可以表示为这棵树上的一个节点。上下文sd描述了从树的根节点到当前节点之间的路径。

  设Zn为上下文sd所在分支的所有节点的集合,即Zn = {sD, …, sd, …, s0}。符号a在不同的上下文s中的频度也是不同的。我们用f(a|s)来表示符号a在上下文s中的频度。每一个上下文中都有一个逃逸码,每个逃逸码都有自己的频度。我们用f(esc|s)来表示上下文s中逃逸码的频度。用A(s)来表示上下文s中出现的不同符号的集合,即A(s) = {a : f(a|s) > 0}。用m(s)来表示上下文s中出现的不同符号的个数。用T(s)来表示上下文s中出现的所有符号的总计频度,即。注意,T(s)中不包含逃逸码的频度f(esc|s)。

  通常情况下,符号a的真实概率是未知的。但是,符号a的预测概率可以根据当前上下文s中的符号频度f(a|s)、逃逸码频度f(esc|s)、总计频度T(s)来进行计算。即,符号a在上下文s中的预测概率为。对应的,上下文s中逃逸码的预测概率为。如果上下文s中出现了符号a,此时f(a|s) > 0。那么我们称当前的上下文s为匹配上下文,并用s(a)来表示当前的上下文s。同时用d(a)来表示s(a)对应的阶数。特殊的,如果s(a)没有出现在Zn中,那么d(a) = -1。此时,符号a在-1阶上下文s-1中的预测概率固定为

  PPM算法的编码实现过程,实际上就是对Zn中的上下文从sD遍历到s0,逐一计算预测概率q并输出。直到找到s(a)或者出现d(a) = -1。所以符号a的总体预测概率q*等于每个输出预测概率q的连乘。对于任意符号a在PPM算法中的总体预测概率q*可以使用如下公式进行表示。

1.4 一个例子

  现在我们来看一个例子,假设输入了一份数据“ABEACADABEA”。在这份数据中一共出现了“A”、“B”、“C”、“D”、“E”、5个符号。我们使用“^”来表示0阶上下文s0。现在假设使用3阶PPM算法,根据这份数据可以生成如图1.1所示的上下文树。

图1.1 使用3阶算法的上下文树

  观察图1.1可以发现。在上下文树结构中,对于上下文sd可以按xn, xn-2+1, …, xn-d+1的顺序查找到对应的节点。对于图1.1中的所有叶子节点,按照从左到右的顺序我们可以确定3阶上下文“ACA”、“ADA”、“BEA”、“DAB”、“EAC”、“CAD”和“ABE”。对于最左边的分支,我们可以发现s3 = “ACA”是s2 = “CA”的子节点。而s2 = “CA”是s1 = “A”的子节点。而s1 = “A”是s0 = “^”的子节点。此时的Zn = {“ACA”,“CA”,“A”,“^”}。如果要在这个分支上编码,这就是我们要遍历的节点。

  分析数据与图1.1可以发现,在1阶上下文“A”中出现了3个符号,分别为符号“B”、符号“C”和符号“D”。其中符号“B”出现了2次。所以A(“A”) = {“B”,“C”,“D”};m(“A”) = 3;T(“A”) = 4;f(“B”|“A”) = 2。

  经过观察我们同时可以发现,上下文树结构不利于算法的实现。例如我要统计1阶上下文“A”中的频度信息,那么我就要对上下文树上1至2层中的所有节点进行遍历。这对模型的维护更新十分不利。所以在算法实现的时候,通常不使用上下文树结构。上下文树结构仅仅作为算法说明的理论结构而存在。本文的第二章将会介绍一个可行的建模数据结构,并且在第三章中对这个结构进行优化。

1.5 开发与测试

  PPM算法需要一个概率编码器对输出的预测概率进行编码。这个概率编码器即可以采用算术编码算法[11],也可以采用区间编码算法[12]。大部份PPM算法的实现都是使用算术编码算法的概率编码器。但是算术编码算法带有版权限制。所以本文实现的PPM算法全部使用区间编码算法的概率编码器。至于这个概率编码器是如何实现的,本文将不进行介绍。详细的理论说明与实现方法请参考我写的另外一篇论文[13]

  本文的配套项目在Delphi 7.0下开发,编译通过并且调试正常。测试程序的计算机使用Intel 2.66GHz单核CPU,DDR400 512MB内存,Windows XP SP3操作系统。测试程序压缩文件的时候,将文件全部读入内存进行压缩。压缩后的数据再写入到文件中。解压缩的过程也是如此。算法计时的时候,读写文件的时间并没有计算在内。只计算单纯算法的耗时。另外,程序中使用API函数GetTickCount进行计时。按照微软官方的说法,该函数有15毫秒的误差。

  本文对于PPM算法的各种实现方案都有给出对应的实现程序。这些程序都是在上述计算机中进行编写和测试的。在后续章节中给出测试数据时,将不再对测试平台进行说明。另外,为了可以更方便的进行各种实现方案之间的性能对比。在对实现方案进行测试的时候,将统一使用卡尔加里语料库(The Calgary Corpus[14],以下简称“语料库”)中的18个文件作为测试语料。并且统一使用bpc(bit per char,位每字符)作为单位来表示算法的压缩率。bpc的值越小表示压缩率越大,如果bpc的值出现了降低,那么证明压缩率得到了提高。对于没有进行任何压缩的单纯的数据拷贝,对应的压缩率为8.000bpc。目前公认的,通用数据压缩算法的平均压缩率的极限在2.000bpc左右。在本文中bpc的值将使用如下公式进行计算。

  评论这张
 
阅读(2166)| 评论(7)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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