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

yeye55的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

高阶哈夫曼算法的分析与实现  

2011-11-06 09:44:45|  分类: 数据压缩算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

声明

  本论文题目:高阶哈夫曼算法的分析与实现,作者:叶叶,于2010年10月15日在编程论坛上发表。页面地址:http://programbbs.com/bbs/view12-29344-1.htm 。本论文全文及相关配套程序可以在上述页面中下载。请尊重他人劳动成果,转载或引用时请注明出处。

  论文全文下载(点这里

  项目文件下载(点这里

目录

  1 前言... 2

  2 统计模型分析... 2

  3 统计模型实现... 4

  4 码表保存... 7

  4.1 码表分析... 7

  4.2 元组压缩... 8

  5 测试与分析... 10

  6 结束语... 13

  参考文献... 13

  附录:项目说明... 13

  1 程序项目... 13

  2 HOCanHuffman.pas文件... 14

  3 HOCH_Debug.pas文件... 15

  4 OOCanHuffman.pas文件... 17

高阶哈夫曼算法的分析与实现

作者:叶叶(网名:yeye55)

  摘要:介绍了高阶哈夫曼算法的实现原理。详细讨论了高阶建模、码表保存等技术的理论基础和实现方式。并给出了一个切实可行的应用程序。

  关键词:哈夫曼;高阶哈夫曼;Trie;双数组Trie;Delphi

  中图分类号:TP301.6

1 前言

  一般的,哈夫曼算法是根据符号的频度分配编码进行压缩的。即:出现次数较多的符号分配较短的编码,出现次数较少的符号分配较长的编码。高阶哈夫曼算法是依据前面出现的符号来统计当前符号的频度,然后再根据这样的频度分配编码。前面出现的符号称为上下文(Context),依据上下文的长度称为阶(Order)。假如:依据前面出现的3个符号的上下文,称为3阶哈夫曼算法。相应的,一般哈夫曼算法可以称为0阶哈夫曼算法。因为一般哈夫曼算法只考虑当前符号的频度,不考虑当前符号前面的符号。

  高阶哈夫曼算法需要建立一个复杂的统计模型。保存压缩数据时也需要导出一个异常复杂的码表,以便解码程序重建统计模型。这些问题使得高阶哈夫曼算法速度较慢,而且压缩性能不稳定。但是,对于部分数据高阶哈夫曼算法可以获得比0阶哈夫曼算法高的多的压缩率。

2 统计模型分析

  哈夫曼算法需要扫描一遍数据统计符号的频度,建立符号的统计模型。这个过程被称为建模。0阶哈夫曼算法的建模过程非常简单,只需要建立一个同符号容量一样大小的数组计算频度即可。高阶哈夫曼算法的建模过程(以下简称“高阶建模”)比较复杂,由于涉及到上下文的查找,所以使用Trie结构比较合适。Trie的概念最早由Donald E. Knuth在1972年提出[1],它是Retrieval的缩写。Trie是一种搜索树,从根节点开始根据关键词中的符号进行查找,从而由一层节点进入到下一层节点。每次下移一层都消耗掉关键词中的一个符号。当移动到一个终止节点或终止符号时完成一次成功的查找。

  高阶建模中使用的Trie与一般的Trie略有不同。一般Trie需要有一个终止节点或终止符号来判断关键词的结束,高阶建模中的Trie则不需要。因为阶数是固定的,所有关键词的长度都一样而且是不变的。这意味着Trie中的终止节点都在同一层,而且是最下一层。在查找中到达这一层就表示查找结束。

  现在来看一个例子:“ABABACABABADBABC”。这份数据的长度是16,共出现了4种符号。假设对这份数据进行3阶哈夫曼算法压缩。让我们来分析一下高阶建模的过程。

  首先,设定所有数据都是由同一个引导上下文开始的。在3阶的情况下我们设定引导上下文为“###”。注意,“###”是什么符号并不重要。甚至于“###”三个符号是否相同也不重要。重要的是编码程序和解码程序必需要使用相同的引导上下文,这样才可以正常的编解码。在数据的开头添加了引导上下文之后就可以开始建模了。建模时,从原数据的第一个符号开始扫描数据。根据符号前的3个符号确定上下文。在我们的例子里,上下文依次是“###”、“##A”、“#AB”、“ABA”、“BAB”……。如果对应上下文中的符号没有在Trie中,就插入符号并设置频度为1。如果有在Trie中,就增加对应的频度。最后,建立完成的模型如图2.1所示。

图2.1 3阶上下文统计模型

  在建立完统计模型后,就可以为符号分配编码。分配时以上下文为单位,不同上下文中的符号分配不同的编码。分配共分为三种情况:第一种情况,上下文中只出现了一种符号。这种情况称为单叶子节点。在我们的例子里出现了很多单叶子节点。例如,上下文“###”后只出现“A”,上下文“ACA”后只出现“B”。对于单叶子节点不分配编码,因为单叶子节点的符号可以根据上下文直接判断出来。当进行编码的时候遇到单叶子节点可以直接跳过。例如在编码的时候,当前的上下文为“ACA”现在要编码“B”,那么什么都不输出直接开始编码下一个符号。例如在解码的时候,当前的上下文为“ACA”现在要解码一个符号,那么什么都不输入直接判断出符号“B”。因此,单叶子节点不需要分配编码。

  第二种情况,上下文中出现了两种符号。这种情况称为双叶子节点。在我们的例子里上下文“BAB”就是双叶子节点。在上下文“BAB”后出现了两中符号“A”和“C”。双叶子节点分配编码比较简单。这时可以忽略符号频度,直接按照符号值的大小分配编码。“A”可以分配编码“0”,“C”可以分配编码“1”。

  第三种情况,上下文中出现了三种或者三种以上的符号。这种情况称为多叶子节点。在我们的例子里上下文“ABA”就是多叶子节点。在上下文“ABA”后出现了三中符号“B”、“C”、“D”。多叶子节点可以像一般的哈夫曼算法一样分配编码。“ABA”一共出现了4次,其中有2次后面出现“B”,各有1次后面出现“C”和“D”。可以根据这些频度信息为符号“B”、“C”、“D”分配编码。我在实现的时候使用了范式哈夫曼算法分配编码。我在一篇论文[3]中已经详细的描述了范式哈夫曼算法,这里不再重复。

  为符号分配编码的时候需要对Trie遍历一遍,找出所有存在的上下文,为上下文中的符号分配编码。编码全部分配完成后还要对数据再扫描一遍输出编码。3阶范示哈夫曼的编码表如表2.1所示。作为对比,在我们的例子中,如果用0阶范式哈夫曼算法进行编码。那么生成的编码表如表2.2所示。

上下文 符号 频度 位长 编码
### A 1 0 -
##A B 1 0 -
#AB A 1 0 -
ABA B 2 1 0
C 1 2 10
D 1 2 11
ACA B 1 0 -
ADB A 1 0 -
BAB A 2 1 0
C 1 1 1
BAC A 1 0 -
BAD B 1 0 -
CAB A 1 0 -
DBA B 1 0 -

表2.1 3阶范式哈夫曼编码表

符号 频度 位长 编码
A 7 1 0
B 6 2 10
C 2 3 110
D 1 3 111

表2.2 0阶范式哈夫曼编码表

  现在我们可以比较一下。在不计算码表输出大小的情况下,3阶算法最后输出的数据只有9位。而0阶算法最后输出的数据有28位。很明显的3阶算法极大的提高了压缩率。但是,我们同时也注意到:3阶算法要输出一个比0阶算法大得多的码表。而庞大的码表会严重的拖累压缩率。

3 统计模型实现

  统计模型的具体实现问题主要集中在Trie结构的实现上。Trie是一种树结构,一种实现方式是每个节点都保存一个同符号容量一样大小的数组。例如,对于字节数据,符号容量为256。那么每个节点都保存一个256大小的数组,每个数组元素都保存一个指向其子树的指针。但这种方式会占用大量的存储空间,不适合在内存中使用。另一种实现方式是兄弟-儿子方式。即:每个节点都保存两个指针,一个指向兄弟节点,一个指向子节点。另外还要增加一个域保存符号值。这种方式可以节约存储空间,但是查找速度很慢。第三种方式在上述两种方式上取得了一个折中。这就是双数组Trie(DoubleArray Trie)。Jun-IchiAoe在1989年提出了这种数据结构[2]。双数组Trie是一种很高效的方法,尤其是查询速度,非常的快。

  双数组Trie将Trie看成是一种DFA(Deterministic Finite Automation,确定有限自动机)。在树结构中,每个节点看成是一个DFA状态。从树的一层节点移动到下一层节点看成是DFA状态转换的有向边。双数组Trie将一个DFA保存到两个数组Base和Check中。Base中的每个单元对应于Trie中的一个节点。Base中每个单元保存对应节点的子节点的起始索引。Check与Base平行的工作,Check中每个单元保存对应节点的父节点的索引。双数组Trie可以将不同父的节点交叉存放在一起,利用Check中的信息来区别彼此。在查找时,利用Base中的起始索引加上符号值来完成一次状态转换。利用Check中的索引来验证这次转换是否成功。

  双数组Trie的插入操作较为复杂。插入时先要查找关键词,当出现状态转换失败时才可以插入。出现状态转换失败后,根据当前Base中的起始索引计算出插入单元的索引。如果该单元空闲那么可以直接插入,如果没有空闲那么将出现冲突。解决冲突的方法是:首先,根据当前Base中的起始索引找到所有的子节点。然后,在Base中查找空闲单元,空闲单元的位置必需足够容纳所有的子节点。如果没有足够的空闲单元就扩展数组。接着,将子节点移动到新的位置,并更新Base中的起始索引。最后,如果子节点不是叶子节点,那么遍历所有子节点的下级节点,更新Check中对应父节点的索引。可以发现,当插入出现冲突的时候操作会变得非常复杂,这也是双数组Trie所有操作中最耗时的部分。

  在双数组Trie实现的时候,可以利用Base和Check中的空闲单元建立一个双向循环链表。利用该链表将空闲单元连接起来,这样可以加快冲突解决时空闲单元的查找速度。将Check中的空闲单元设置为负数,这样就可以将空闲单元和非空闲单元区分开来。一般情况下,空闲单元在链表中按照单元的位置排序。位于数组前面的空闲单元放置在链表的前面。这样这些空闲单元将优先分配。这种做法可以减少数据的稀疏,降低内存的占用。但是,这种做法速度较慢。一方面,当一个单元被释放,放入链表的时候。需要在链表中查找,以确定插入位置。另一方面,数据稀疏减少意味着冲突次数的增多。而冲突的解决是最耗时的操作。高阶建模时需要临时建立双数组Trie,所以速度也很关键。这里有一个简单的改进方案:对链表不做排序,使用无序链表。当一个单元被释放的时候,直接将该单元放入链表开头。扩展数组时新增的单元也放入链表开头,优先分配。这样做会增加内存的使用,但可以提高速度。利用卡尔加里语料库(The Calgary Corpus[4])中的18个文件对两种方案进行比较测试。其结果如表3.1所示。

文件名 使用
个数
原方案 改进方案
单元
个数
空置
冲突
次数
耗时 单元
个数
空置
冲突
次数
耗时
bib 28863 36864 21% 15536 406ms 57600 49% 10005 125ms
book1 65169 92672 29% 37634 3063ms 157184 58% 21395 719ms
book2 73201 97024 24% 40208 2719ms 172032 57% 22931 562ms
geo 125421 201728 37% 41155 7750ms 499200 74% 16181 625ms
news 101138 136960 26% 53912 4718ms 239872 57% 30161 578ms
obj1 25791 33792 23% 8132 203ms 96000 73% 3214 78ms
obj2 108270 148480 27% 43408 2922ms 364032 70% 18640 547ms
paper1 20657 26368 21% 10417 187ms 42240 51% 6803 62ms
paper2 22110 28928 23% 11703 250ms 46080 52% 7561 78ms
paper3 18762 24576 23% 9870 188ms 37120 49% 6464 63ms
paper4 9243 11264 17% 4395 62ms 17152 46% 3112 31ms
paper5 9328 11776 20% 4220 47ms 17408 46% 2808 31ms
paper6 17304 20992 17% 8414 141ms 34816 50% 5231 47ms
pic 56780 78336 27% 29013 1469ms 241920 76% 11611 250ms
progc 19025 24064 20% 8884 156ms 40448 52% 5497 62ms
progl 16623 21248 21% 8519 140ms 32768 49% 5495 63ms
progp 14923 18944 21% 6908 110ms 29952 50% 4308 47ms
trans  21959 28160 22% 10293 204ms 45312 51% 6447 78ms

表3.1 双数组Trie测试

  以上测试所使用计算机的配置见本论文第5节。在本次测试中使用3阶哈夫曼算法进行压缩。其中的耗时是压缩完成后所使用的时间。在压缩过程中是以字节(8位符号)为单位进行压缩。数组空间不足时,每次扩展一个符号容量大小,即:256个单元。单元个数是指建模完成后双数组Trie总共占用的单元个数。使用个数是指所有单元中实际使用单元的个数。原方案使用排序链表,而改进方案进行无序链表。

  现在,可以比较一下测试结果。原方案的空置率明显很低,大约在20%到30%左右。这证明数据稀疏较小。但是,冲突次数和耗时明显比较高。改进方案的空置率在40%到50%左右,也就说有一半左右的单元是空闲的。对于部分文件,空间占用“恶化”的比较利害。例如“obj1”、“obj2”等文件,空置率高达70%左右。在改进方案中,双数组Trie的内存占用在数MB左右。但是,它的耗时比原方案快很多。所以说,从总体而言,改进方案还是可以接受的。

  最后,除了上述的改进方案外,还有一些可以改进的地方。前面已经讲过,高阶建模中使用的Trie与一般的Trie略有不同。对于双数组Trie也是如此。一般情况下,Base中的终止节点用负数来表示,其它的节点用正数表示。但是在高阶建模中我们不需要终止状态,查找何时终止可以用阶数判断出来。那么Base中的非终止节点也可以用负数来表示,这就意味着Base中保存的起始索引可以为负数。那么在分配子节点的时候可以将子节点尽可能的往数组前方放置,这样可以减少数据稀疏。另外,最后终止节点对应的Base单元(以下简称“最终单元”)将不再使用,当然可以利用最终单元来保存其它信息。

  在编码的时候,最终单元对应于上下文中的一个符号。在建模期间可以利用最终单元来保存符号的频度。在分配编码的时候,可以建立一张编码表保存所有上下文中符号的编码及其位长。然后利用最终单元保存指向编码表的索引。其结构如图3.1 1)所示。对于不分配编码的单叶子节点可以将最终单元设置为-1以示区别。在解码的时候,可以确定当前上下文,但是无法确定上下文后的符号。所以Trie结构比编码的时候要少一层,其最终单元对应于一个上下文。解码的时候,每个上下文都对应一张解码表和一张符号列表。可以将这些数据分别保存在同一个数组中。利用最终单元保存指向数组的索引。其结构如图3.1 2)所示。由于单双叶子节点的解码方式不太一样,所以可以将对应解码表中的位长一栏设为0以示区别。对于图3.1 2)中的解码表的使用,我在另一篇论文[3]中已经进行了详细分析。这里不再重复。另外,如果为每个上下文都建立一张快表,将会占用大量的内存空间。同时,由于上下文中的符号一般不是很多,所以我在解码实现的时候没有使用快表。

图3.1 编解码时数据结构

4 码表保存

4.1 码表分析

  一般的哈夫曼算法都需要保存一份码表数据,以便解码程序可以建立相关的解码结构。高阶哈夫曼算法也不例外。保存高阶建模产生的Trie结构,第一映像就是保存所有的节点。然后在解码的时候重建整个Trie结构。这需要输出大量的数据。但是,仔细观察图2.1中的Trie树我们可以发现,所有的上下文都是有规律的。由于我们在建模的时候是顺序的扫描数据。一个上下文后的符号形成下一个上下文。例如:在我们的例子中,位于数据开始的上下文“ABA”后面出现“B”。那么下一个上下文将是“BAB”。这意味着,可以根据一个上下文推导出其它上下文。例如:在上下文“ABA”后出现了“B”、“C”、“D”,那么我们可以推导出在Trie中还出现了“BAB”、“BAC”、“BAD”三个上下文。根据这三个上下文又可以推导出其它上下文。由于我们建模时的上下文都是由一个引导上下文“###”开始的,从导引上下文“###”开始可以推导出所有的上下文。利用这种方法可以遍历Trie中的所有上下文,同时逐一输出上下文对应的符号。这就意味着在保存码表的时候,只需要保存图2.1中最末端的叶子节点。上方的分支节点可以不用保存。另外,由于分配编码的时候也需要遍历Trie,那么可以将分配编码和保存码表的操作合并起来。这样只需要遍历一次Trie。

  在实现的时候可以设定一个上下文栈。首先,将引导上下文“###”入栈。然后,从栈中弹出一个上下文,查找该上下文中的所有符号,为这些符号分配编码。并按一定的格式将符号个数、符号值以及编码位长输出。同时将推导出来的上下文压入栈中。接着,再从栈中弹出一个上下文,按照上述方法操作。直到栈空。在解码的时候,由于可以确定引导上下文。所以,先将引导上下文“###”添加进Trie中,并且入栈。然后,从栈中弹出一个上下文,按照一定的格式输入符号个数、符号值以及编码位长。同时将推导出来的上下文添加进Trie中,并且入栈。接着,再从栈中弹出一个上下文,按照上述方法操作。直到栈空。

  这里还有两个问题需要注意。第一,推导出来的上下文可能会发生重复。例如:上下文“ABA”中出现“B”,可以推导出上下文“BAB”。而上下文“DBA”中也出现“B”,也可以推导出上下文“BAB”。对于重复出现的上下文需要排除。在将一个上下文入栈的时候,要判断该上下文是否已经入栈或者已经处理过了。第二,末尾上下文可能没有出现在Trie中。在我们的例子里最后出现的上下文是“BAB”,后面是“C”。根据这个上下文可以推导出上下文“ABC”。“ABC”就是末尾上下文。由于符号“C”之后就没有数据了,所以“ABC”没有被添加到Trie中。另外,如果最后一个符号不是“C”而是“A”,那么末尾上下文就是“ABA”。而这个上下文存在于Trie中。所以说遍历的时候需要注意,有一个推导出来的上下文可能不存在于Trie中。而且,如果末尾上下文不存在,那么需要将末尾上下文同码表一起输出。以便让解码程序知道,有一个推导出来的上下文不存在。

  在实际操作中,在将上下文入栈之前,可以先对上下文进行查找。如果上下文不存在则跳过,如果存在则入栈。入栈前先将查找上下文时最后状态转换对应的Check单元设为-1,这样对应的上下文将无法再次被找到。这就可以保证栈中的上下文都是需要处理的上下文。由于Check被破坏,在编码期间将不能利用Check查找上下文。不过编码期间也不需要利用Check查找上下文。编码期间是第二次扫描数据,可以断定相关上下文已经在Trie中。所以编码期间直接利用Base查找,不进行Check检查。在解码的时候,在将上下文入栈之前,也可以先对上下文进行查找。如果上下文存在则跳过,如果不存在则添加进Trie中,并且入栈。另外,如果有一个不存在的末尾上下文,可以事先将该上下文添加进Trie中。这不会影响到解码。

4.2 元组压缩

  每个上下文都需要按照一定的格式输出符号个数、符号值以及编码位长。输出数据格式是如下所示的一个元组。

[Num, Sym0, Bit0, …,  SymNum-1, BitNum-1]

  其中,Num表示符号个数,Sym表示符号值,Bit表示编码位长。由于使用了范式哈夫曼算法,所以只要保存编码位长就可以重建解码表。不过,上面这个元组还是可以简化一下的。在我们分配编码的时候,单叶子节点不分配编码,双叶子节点按符号值分配编码。只有多叶子节点按一般的范式哈夫曼算法分配编码。所以,对于单双叶子节点可以不需要保存Bit元素。元组格式可以简化,并分为三种情况,如下所示。

(1)
(2)
(3)
[Num, Sym]
[Num, Sym0, Sym1]
[Num, Sym0, Bit0, …,  SymNum-1, BitNum-1]
(Num = 1)
(Num = 2)
(Num > 2)

  一份码表会输出很多元组,所以在输出的时候需要对元组进行压缩。可以看出,元组是由Num、Sym、Bit三个元素构成。在这里可以采用分组压缩的方式,使用三个0阶范式哈夫曼编码器分别对三个元素进行压缩。所产生的二次码表,再使用指数哥伦布编码进行压缩。即:我在另一篇论文[3]中提到的G方案。

  另外,对于Sym元素的保存有两种方案。第一种方案(以下简称“方案一”)就是直接对符号值进行压缩保存。第二种方案(以下简称“方案二”)是保存符号的差值。先将符号按值的大小,从小到大排序。第一个符号值直接压缩保存,其它符号则计算与前一个符号的差值。然后对差值进行压缩保存。对于一份数据,如果上下文中的符号无规律分散,那么使用方案一会取得比较好的效果。如果上下文中的符号集中在一定的区间内变化,那么使用方案二会取得比较好的效果。现在使用卡尔加里语料库[4]中的18个文件对这两种方案进行比较测试。其结果如表4.1所示。

   

文件名 方案一 方案二 差值
bib 154917 152376 -2541
book1 432834 401310 -31524
book2 445468 428166 -17302
geo 624747 513556 -111191
news 599748 580986 -18762
obj1 96620 94899 -1721
obj2 530443 501337 -29106
paper1 * 100810 103661 2851
paper2 * 116594 118411 1817
paper3 * 94062 97481 3419
paper4 * 38716 41769 3053
paper5 * 37653 40446 2793
paper6 * 81222 84042 2820
pic * 282302 302177 19875
progc * 87624 90497 2873
progl * 80729 84635 3906
progp * 66915 70264 3349
trans * 101910 103918 2008

表4.1 压缩方案比较

  以上测试中使用3阶哈夫曼算法压缩数据,表中的数据为输出码表的大小,单位是位。差值为方案二测试结果减去方案一测试结果。两套方案都使用三个0阶范式哈夫曼编码器分别对三个元素进行压缩。唯一不同的是,方案一保存Sym的符号值,方案二保存Sym的符号差值。

  现在,可以对测试数据进行一下比较。测试文件中有11个文件其方案一要优于方案二。见表4.1中带星号的文件。而对于其它文件方案二要优于方案一。这说明了一个问题,两套方案对于不同的数据其压缩效果也不同。对于一份数据方案一要优于方案二,而对于另一份数据可能恰恰相反。在压缩前很难判断当前数据适合用哪套方案,不过可以在压缩的时候比较两套方案的压缩效率。实现时,对元组进行扫描的时候,两套方案都进行统计频度和分配编码的操作。然后,根据频度和编码位长分别计算出两套方案压缩后的大小。比较这两个值就可以判断出应该用哪套方案。

5 测试与分析

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

  我编写的这个高阶哈夫曼算法的实现程序可以设定阶数。最低限制在1阶。通过使用不同的阶数进行压缩,可以发现高阶哈夫曼算法的一些特点。现在对卡尔加里语料库[4]中的“book1”文件进行不同阶数的压缩测试。从1阶到10阶,测试结果如表5.1所示。

码表大小 数据大小 总计大小 bpc 耗时
1 12817 2785455 2798272 3.640 63ms
2 102424 2222419 2324843 3.024 125ms
3 401310 1790969 2192279 2.852 641ms
4 967888 1455563 2423451 3.152 1500ms
5 1620512 1153822 2774334 3.609 3140ms
6 2250919 880170 3131089 4.073 4875ms
7 2809705 637938 3447643 4.485 5922ms
8 3243694 439893 3683587 4.792 7782ms
9 3569534 293856 3863390 5.025 10671ms
10 3804583 189751 3994334 5.196 11578ms

表5.1 book1不同阶数测试

  表5.1中的码表大小、数据大小和总计大小的单位都是位。码表大小是指压缩输出时码表占用的大小。数据大小是指压缩输出时压缩数据的大小。而总计大小是码表大小和数据大小之和。另外,bpc是根据最后输出文件的大小计算的。根据表5.1中的数据制作对应的分析图表,如图5.1所示。

图5.1 测试分析图表

  通过观察表5.1和图5.1可以发现,输出压缩数据的大小随着阶数的提高而减少。如图5.12)所示。由于在实现的时候,对于单叶子节点不输出编码。所以随着阶数的不断提高,压缩数据会越来越少。当阶数超过待压缩数据的最长重复子串(可重叠)的长度时,输出的压缩数据大小为0。即:只输出码表数据,没有压缩数据。此时,所有的上下文中都只有一个符号。所有的符号都可以通过上下文直接判断出来。当然,此时的码表将会十分庞大。

  从图5.1 1)可以看出,输出码表的大小随着阶数的提高而增加。虽然对码表进行了压缩,但是输出的码表数据大小仍然十分庞大。在第5阶的时候,码表的大小超过了压缩数据的大小。这就意味着,在总体输出数据中有一半以上的数据是为了在解码时重建模型。另外,值得注意的一点:比较图5.1的1)和2)可以发现,码表的增加速度比压缩数据的减少速度要快。这一点也可以从图5.1 3)中看出来。这就意味着,高阶哈夫曼算法的压缩率有一个上限。并不是说阶数越高压缩率也越高。当阶数到达上限后,继续提高阶数只会使压缩率下降。这就是说有一个最优阶数。使用最优阶数进行压缩时,压缩率达到最高。现在对卡尔加里语料库[4]中的18个文件进行0阶到5阶的压缩测试。计算压缩后的bpc,其结果如表5.2所示。

文件名 0阶 1阶 2阶 3阶 4阶 5阶 最优
bib 5.236 3.529 3.002 2.924 2.891 3.097 4阶
book1 4.563 3.640 3.024 2.852 3.152 3.609 3阶
book2 4.824 3.816 3.058 2.745 2.837 3.115 3阶
geo 5.676 5.105 5.512 7.569 6.555 6.516 1阶
news 5.228 4.200 3.578 3.508 3.588 3.785 3阶
obj1 6.010 5.440 5.244 5.213 5.259 5.454 3阶
obj2 6.295 4.274 3.742 3.631 3.722 3.920 3阶
paper1 5.026 3.901 3.394 3.433 3.662 3.977 2阶
paper2 4.641 3.688 3.186 3.241 3.546 3.870 2阶
paper3 4.700 3.801 3.538 3.747 4.004 4.309 2阶
paper4 4.769 4.049 4.114 4.210 4.340 4.588 1阶
paper5 5.014 4.275 4.318 4.302 4.492 4.749 1阶
paper6 5.057 3.942 3.526 3.564 3.762 4.067 2阶
pic 1.663 1.540 1.682 1.786 1.764 1.729 1阶
progc 5.245 3.970 3.520 3.559 3.718 3.997 2阶
progl 4.806 3.407 2.758 2.543 2.519 2.627 4阶
progp 4.906 3.455 2.775 2.557 2.571 2.741 3阶
trans 5.575 3.614 2.721 2.295 2.172 2.233 4阶

表5.2 不同阶数测试的bpc结果

  首先说明一点,我编写的高阶哈夫曼算法的程序无法进行0阶的压缩。表5.2中0阶的测试数据来自我写的另一篇论文[3]。观察表5.2中的数据可以发现,不同的文件其最优的阶数也不同。5阶测试之内,最优阶数分布在1阶到4阶。从这点可以看出,高阶哈夫曼算法的压缩率是不稳定的。

  综上所述,从算法耗时的角度分析,高阶哈夫曼算法的瓶颈在于建模结构。高阶哈夫曼算法压缩数据时,需要对数据扫描一遍,建立模型、统计频度。接着要对模型遍历一遍,分配编码、保存码表。最后还要对数据再扫描一遍,输出编码。反复的对模型进行查找。意味着对于建模结构的要求很高。优秀的建模结构可以有效的缩短算法耗时。本论文中使用双数组Trie进行高阶建模。虽然如此,随着阶数的提高算法耗时仍然大幅提高。这点可以从表5.1中看出来。当然不排除还有其它的更优秀的结构。不管怎样,对于高阶哈夫曼算法来说,算法耗时主要集中在模型的建立和查找上。

  从压缩率的角度分析,高阶哈夫曼算法的瓶颈在于码表输出大小。从前面的测试数据可看出码表大小严重拖累了压缩率。随着阶数的增加码表的大小也大幅增加,以至于超过压缩数据的大小。正是由于码表的影响,使得高阶哈夫曼算法的压缩率很不稳定。对于部分文件,高阶压缩甚至出现了负压缩率。这可以算是高阶哈夫曼算法的最大缺点。极大的影响了高阶哈夫曼算法的应用。

  当然,本论文主要还是讨论高阶哈夫曼算法的理论实现。在具体的实际应用中,一般只使用1阶哈夫曼算法。因为从各方面分析,1阶算法的综合性能最高。无论是内存占用、算法耗时,还是压缩率。1阶算法都取得了一个不错的平衡。与0阶算法相比,对于大部分文件来说,1阶算法的压缩率得到了相当高的提升。1阶算法实现的时候,不再需要使用双数组Trie建模。直接使用一个大数组就可以完成建模。在本论文的实现程序中也提供了一个固定1阶的哈夫曼算法压缩程序。

6 结束语

  本文介绍了高阶哈夫曼算法的实现原理。详细讨论了高阶建模、码表保存等技术的理论基础和实现方式。并给出了一个切实可行的应用程序。希望本文能够对压缩算法的研究人员有所帮助。

参考文献

[1] Donald E. Knuth, The Art of Computer  Programming, Addison-Wesley, 1972, Vol 3.
[2] Jun-Ichi Aoe, An Efficient Digital Search  Algorithm by Using a Double-Array Structure, IEEE Transactions on Software  Engineering, 1989, 15(9), 1066-1077.
[3] 叶叶, 范式哈夫曼算法的分析与实现, 编程论坛,  2010, http://programbbs.com/bbs/view12-29332-1.htm .
[4] The Canterbury Corpus, http://corpus.canterbury.ac.nz/descriptions/  .

附录:项目说明

1 程序项目

  本程序项目是论文《高阶哈夫曼算法的分析与实现》(以下简称“《高》”)的配套程序。本程序项目同时作为免费开源程序进行发布。本程序项目中的代码无需任何授权或许可即可用于个人和商业目的。使用者一切后果自负。

  本程序项目在Delphi 7.0下开发,编译通过并且调试正常。本程序项目提供了一个文件到文件的,高阶范示哈夫曼算法的压缩程序。本程序项目中还提供了相关测试代码,以分析高阶范式哈夫曼算法的运行性能。本人发表过另一篇论文《范式哈夫曼算法的分析与实现》(以下简称“《范》”)。本程序项目中的部分文件来自于论文《范》中的配套文件。

  本程序项目中的主要文件及相关说明如表1.1所示。

文件 说明
Project1.dpr 项目主文件
Project1.exe 项目可执行文件
Unit1.pas 主窗口单元文件
Unit1.dfm 主窗口窗体文件
MemoryBuffer.pas 内存缓冲区管理单元文件
CanonicalHuffman.pas 范式哈夫曼算法实现单元文件
HOCanHuffman.pas 高阶哈夫曼算法实现单元文件
HOCH_Debug.pas 带测试信息实现的单元文件
OOCanHuffman.pas 1阶哈夫曼算法实现单元文件
示范数据.txt 论文《高》中的例子数据

表1.1 项目主要文件说明

  在程序项目中MemoryBuffer.pas和CanonicalHuffman.pas两个文件来自于论文《范》中的配套文件。这两个文件的详细说明请参考论文《范》中的项目说明。另外,HOCanHuffman.pas是核心文件。在这个文件中实现了论文《高》中描述的所有算法。同时,这个文件可以与MemoryBuffer.pas文件一起独立使用。将这两个文件添加到其它项目中,调用其中的相关函数就可以实现数据压缩。类似的,OOCanHuffman.pas文件也可以与MemoryBuffer.pas文件一起独立使用。

2 HOCanHuffman.pas文件

  我在这个单元文件里编写了高阶哈夫曼算法的实现代码。这个单元文件实际上是在CanonicalHuffman.pas文件的基础上修改而来。在这个单元文件中一共定义了5个类。其中,THOCHDblAryTrie实现了双数组Trie结构,THOCHAlloc实现了编码分配的过程,THOCHEncode实现了编码过程,THOCHDecode实现了解码过程,THOCHCoding提供了对THOCHEncode和THOCHDecode的简单封装。

  THOCHDblAryTrie类实现了双数组Trie结构。THOCHDblAryTrie类中的FBase 和       FCheck用来保存两个数组。这两个数组中的空闲单元会用来保存一个双向循环链表。THOCHDblAryTrie类中的Relocate方法专门用于解决插入时的冲突问题。这个类的实现,对应于论文《高》中的第3节。

  THOCHAlloc类实现了编码分配的过程。THOCHAlloc类实际上就是对CanonicalHuffman.pas文件中的TCHEncode类的简单修改。将TCHEncode类中的编码分配部分提取出来,删除其它部分。虽然在高阶建模中出现位长溢出的可能性非常的低。但是在THOCHAlloc类中仍然保存了位长限制的代码。与TCHEncode类不同,THOCHAlloc类不负责工作缓冲区的分配与回收。这个工作由调用程序完成。

  THOCHEncode类实现了高阶范式哈夫曼算法的编码过程。压缩的时候可以设定阶数,最低1阶。THOCHEncode类内部封装了THOCHDblAryTrie类和THOCHAlloc类。利用THOCHDblAryTrie类实现高阶建模。利用THOCHAlloc类实现编码分配。THOCHEncode类中的SaveBitLen方法来自于CanonicalHuffman.pas文件中TCHEncode类的SaveBitLenG方法。即,使用G方案保存二次码表。THOCHEncode类中的SaveModel方法实现了对Trie结构的遍历、分配编码、导出码表中间数据等过程。对应于论文《高》中的第2、3节和第4.1节。THOCHEncode类中的SaveTable方法实现了对码表中间数据的压缩过程。对应于论文《高》中的第4.2节。SaveTable方法对Sym元素压缩时会计算两种方案的压缩效果。并选择最优秀的一种方案。THOCHEncode类的其它方法说明见单元文件中的相关注释。

  THOCHDecode类实现了高阶范式哈夫曼算法的解码过程。注意:解码时设定的阶数必需和编码时设定的阶数一致。否则解码会出现无法预知的后果。THOCHDecode类中的LoadBitLen方法来自于CanonicalHuffman.pas文件中TCHDecode类的LoadBitLenG方法。即,使用G方案读取二次码表。THOCHDecode类中的LoadModel方法实现了导入码表中间数据、对Trie结构的重建、构建解码表等过程。对应于论文《高》中的第2、3节和第4.1节。THOCHDecode类中的LoadTable方法实现了对码表中间数据的解压缩过程。对应于论文《高》中的第4.2节。THOCHDecode类的其它方法说明见单元文件中的相关注释。

  THOCHCoding类实现了高阶范式哈夫曼算法的编解码过程。THOCHCoding类是对THOCHEncode和THOCHDecode的简单封装。THOCHCoding类提供了一个缓冲区到缓冲区的压缩与解压缩过程。THOCHCoding类中的Encode方法是以字节为单位从缓冲区中读取数据进行压缩,然后保存到另一缓冲区中。同时,Encode方法会将阶数一同保存到输出数据中。THOCHCoding类中的Decode方法是从缓冲区中读取压缩数据进行解压缩,然后保存到另一缓冲区中。Decode方法会根据输入数据中的阶数信息来设定解压缩时使用的阶数。在Unit1.pas单元文件中的测试程序就是调用THOCHCoding类中的相关方法完成文件压缩与解压缩的。

3 HOCH_Debug.pas文件

  本单元文件是在HOCanHuffman.pas单元文件的基础上添加了测试数据输出代码。本单元文件中的基本功能与HOCanHuffman.pas单元文件完全相同。除此之外,在调用本单元中的一些方法的时候,这些方法会向Unit1.pas单元中的Form1.Memo1输出测试信息。正是由于如此,本单元文件必需与Unit1.pas单元文件一同使用。

  在本单元文件中,THOCHDblAryTrie类在使用时会输出双数组Trie的使用情况。同时THOCHDblAryTrie类中多出了一个方法DelItem。在InsItem和DelItem中有部分被注释代码用于实现有序链表。在默认情况下使用无序链表。详细内容可以参考《高》中的第3节。另外,THOCHEncode类和THOCHDecode类在使用时会输出码表的压缩和解压缩情况。

  在本程序项目中带有一个例子文件:示范数据.txt文件。这个文件中的数据与论文《高》中的例子相对应。现在对该文件进行测试。在程序中选择“高阶范式哈夫曼算法(测试)”算法,将阶数设定在3阶。程序输出结果如下:

  ==================================================================

  使用3阶范式哈夫曼算法压缩(测试)...

  从:E:\示范数据.txt

  到:E:\_Temp.pack

  使用方案一

  方案一:31

  方案二:33

  输出二次码表大小:101位≈12字节

  Num个数:11

  Sym个数:14

  Bit个数:3

  输出码表大小:160位≈20字节

  输出压缩数据大小:9位≈1字节

  Trie数组占用空间:2048B ≈2KB ≈ 0MB

  数组单元个数:256

  使用单元个数:39

  空闲单元个数:217

  空置率:84%

  发生冲突次数:9次

  操作完成,耗时:16

  压缩前:16 字节

  压缩后:28 字节

  压缩率:-75% 14.000bpc

  ==================================================================

  ==================================================================

  使用高阶范式哈夫曼算法解压缩...

  从:E:\_Temp.pack

  到:E:\_Temp.data

  输入二次码表大小:101位≈12字节

  Num个数:11

  Sym个数:14

  Bit个数:3

  输入码表大小:160位≈20字节

  Trie数组占用空间:2048B ≈2KB ≈ 0MB

  数组单元个数:256

  使用单元个数:26

  空闲单元个数:230

  空置率:89%

  发生冲突次数:5次

  操作完成,耗时:15

  ==================================================================

  比较文件:

  E:\示范数据.txt

  E:\_Temp.data

  长度16字节,比较一致。

4 OOCanHuffman.pas文件

  由于在实际的应用中,一般都使用1阶的哈夫曼算法。所以我编写了OOCanHuffman.pas单元。OOCanHuffman.pas单元文件中实现了一个固定1阶的高阶哈夫曼算法。并且压缩时只能处理字节数据。OOCanHuffman.pas单元中程序的结构大体上同HOCanHuffman.pas单元文件一致。不过,由于OOCanHuffman.pas单元中固定使用1阶,用户不能设定阶数。所以对于程序结构进行了一些修改。

  首先,高阶建模时不再使用双数组Trie。而是用一个256×256大小的数组保存频度。分配编码后这个数组用来保存指向编码表的索引。解码时用一个256大小的数组保存不同上下文对应解码表的索引。其次,在压缩码表的Sym元素时,当使用1阶的情况下,使用方案二保存会比较合算。即:保存Sym的差值。所以在进行码表压缩时,不再判断哪种方案更优秀。而是直接使用方案二。于是,TOOCHEncode类中的SaveTable方法被合并到了SaveModel方法中。这样在输出码表中间数据的同时,可以进行频度统计。

  经过这些修改,在同样1阶的情况下。OOCanHuffman.pas中的程序会比HOCanHuffman.pas中的程序更快。

叶叶

2010年7月30日

  评论这张
 
阅读(1167)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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