《基于ppm方法的中文文本压缩》由会员分享，可在线阅读，更多相关《基于ppm方法的中文文本压缩（3页珍藏版）》请在金锄头文库上搜索。
1、第十七届全国数据库学术会议论文集( 技术报告篇)基于P P M方法的中文文本压缩( 复旦大学计算机系草周水庚2 周傲英“ 1 ，1196 2 4 2 6 3 . ne t ; 2 卿卜 以 . ， a y z l长 阅 J 卜 d 曰 、 . 曰u . 二)剐 比 打 傲 t ln如s p 耳 犯 r 快 曰1征 t 拢日 p p l 画t lon oft hel 阳 rt 回p r 日 ic t 巧 Ie 皿tc 场 11 9 0 】 n p r es - j 即 t f h l 创 q u e ( P l 水 1 ) 1 0 “ 的 不 牙 已 弱 C l“ 。 裂 l ex tw e l
2、 峨 林能义 v 阴1 11 1 唾 川 爪 1巴 1 】 曰 ltsm P p Mtoll 笼 山 it ef f ec t i、 1 for C 肠 t 以t ， n 坦 山 l y m 倔 a 斗 死 ( tsoft he or g 毛 日 1 幽t 切 ofdata s t r l，c t 峨 ， th e n 团 让 堪 曰 n e ll t ofll 旧 l x 玛 l a l ld t 址环 司i c a t i以 l oft 阮 ，引 ， 】 pe。 刻 e . A c 戊 企 d i 昭tot 址士 巴d 侣of叮 e x p 三 r l - ts ， t 址 幻 r 泪 1
3、 方 曰 1 呼 伙 心 胡th e ”蓝 ， 猖 e a 期 l p r e s ， 口 门 石 。 JO I 五 1 嘿 士 ext tod g . 98 悦 ts 【叉 r c 卜 丑 旧 c t erand t he卜 万 1 仪 习 1 ， p r l王 资 im ra ti 。 仍65 9 b ll . B 招 id l笼 。 t 阮司 9 h t 恤， n 氏 吐 弓 旧p 代 t r e It - t 习 11 1 咖 悦.蟹1 怕如 p r 巴 洛text 团 已inl 1 ll e r l. 1堪 IJ 昭 1拐K ”俐 ， 山 C I 云 t 以t O 1 刀 1万 已
4、里 迈 。 1】F P M 刀 找 词 叮 曰Cti，malc 枯 ng) 勘旧e1 概述文本压缩是文本存储和传输中 普遍使用的技术。目 前的压缩技术大多是针对英文文本的。本文 将适 合于 英文压结的P P M方法进行改进， 使之应用于中文文本压缩时也能取得良好的效果。2 基于P P M方法的中文文本压缩21 救据结构采用类似trie 树的结构T R I E(如下所示) 来存储可能出现的上下文组合， 工 N F O结构用来存储上下文所接的后续字母。t 刃 刘己st 川 C t 晰et ” 曰己s l n 职 比 in fo1wl R l t 石 e _笼叮 a 、 【 E F ;in t吟 t
5、 _c 阮;in ti而 _日 r l，a 、 1 【 1 犯 ;i m日 p p _n tnn;W 张】 】爬 p 田 n 有 时;i n lnex t _p 二 ;，.t 囚 9 ” 司d r uP_c l 从 比 ;c l 阳 ril巧 址 氏_valid _f l超;t n tuse _num ; 1 卜 R) ;卜 l rvalid_ 几 ag; TRIE;T R IE结构中有两个数组， 其中t ri e _a r r a y 数组存放下一级T 卫 IE节点的序号， 1而 _aITa y 数组存放 指向后续字符的指针( 详见下面的INR 结构) 。另外还有一些附加信息: 玛 阳 m
6、t 二存放上一级T R IE节点 的 序 号. uP_C h 庄 记录 前一 个字 符， * _二 记录 该节点在压缩过程中 被访问的次数， 诫d _月 昭标识 该T R I E节 点是否为有效节点( 0 -无效， 1 一有效) 。内 存管理时要用到这些信息。1 04、弃阵第十七届全国数据库学术会议论文集( 技术 报告篇)I N F O结 构中， n e x t _ c h a r 存放 后续 字 母+ a p p - n 存 放该 字 母 在当 前 上 下文 后出 现 过的 次 数. n e x t - P 存放下一个后续字母的I N F O ) 节点的序号。I N F ( 节点通过n e
7、x t _P -的连接， 形成一个对应于该 上下文的后续字母的链表( n e x t - P C s 二一 1 表示链表的末尾) 。另外， 分量in fo re c - v a li d - ( la g 标识该 I N FI ) 节点是否为有效节点( 0 - 一 无效， 1 一有效) 。 这些同样是用于内 存管理的 信息。下面是一个简单的例子 如图1 ) ， 可以更清楚地看到数据结构的情况。丁 R 工 E结构加e a a a y - A -9 7 a 9 8 b M b aa y9 7 a 铭、，9 9 c， 二 二Mt =结构9 7 a 9 8 6 当前出 现 字 母次 数 / 气9 7
8、a 9 8 b 9 9 c23:4:59 7 a 9 8 b 9 9 c/.祖、21111、9 7 a 9 8 6 9 7 a 9 8 b 9 9 cp 。I9 9 c ，39 9 c2盯 al9 7 a69 7 a2 _ _ 一 一 门“ - 一一749 8 b、，3图 1 一个例子从图中可以看到: 0 号T R I E 节点的下一级节点是1 号T R I E 节点; I 号T R I E 节点的下一级节点是2 号T R I E 节点; 2 号T R I E节点的下一级节点是3 号 I N D 节点。这表明前文中曾出现过三阶上下文a b c , 且上下文a t ( 后出现过的字母存放在以3
9、号I N F O节点为首的链表中。 从链表的内容可以看出 a b i 后曾 出现过字母a 一次( 记录在3 号I N F O节点中) ， 字母 b 四次( 记录在9 号I N F O 节点中) 。 9 号 I N F O节点 的。t _ p c s = 一 1 ， 表 示 该 节 点 是 钻 表 的 最 后 一 个 节 点 。使用T R I E 结构可以快速的找出当前上下文在前文是否出现过、 出现次数、 后面是否 接过当前字符、 接 过多少次等对预侧概率来说非常重要的 信息 2 . 2 内存管理节点个数是有限的， 当已 经使用了 所有节点， 却还有信息需要记录时， 就必须剧去一些原有记录。一
10、个节点的被访问次数越多， 说明它记录的信息越重要认这样的节点信息如果被删掉， 可能很快就需要再次 访问， 显然不合适。因 此， 应该删除那些“ 无关紧要 的节点。T R I E 节点中有一个分量， _二 记录该 T R I E 节点在压缩过程中被访问的次数。当 所有节点都被用完的时候， 州去那些使用次数最少的节点。 23 转义字符概率的 估算在实现P P M算法时， 我们用的转义字符概率的计算公式为r / ( n + r ) ， 其中n 是当前上下文中已 见到1 0 5第十七届全国数据库学术会议论文集( 技术报告篇)的 符号总数, r 是已区分出的字符数。运用这种方法， 转义字符的概率将随着新
11、字符出现频率的增加而减少。3 实验结果实验时， 以字节作为编码单位， 使用三阶模型。 对新闻、 杂志和小说三种不同类型的文本进行了压缩， 得到的 最佳压缩比 为6 . 5 9 b p c ( 在压 编新闻时 达到) ， 平均压缩比 为9 . 9 8 6 p c o我们对三阶、 二阶和一阶模型进行了同样的实验， 结果一阶摸型的平均压缩效果最好， 二阶其次， 三阶 最差。一阶模型的平均压缩比为8 . 3 3 b p c , 最佳压缩比为5 . 5 9 6 p c o4 结论由于对文本进行压缩后再存储和传输可以节省大量的空间和时间。本文根据中文的特点， 将适合于 英文文本压缩的P F M算法进行了
12、数据结构、 内存管理和转义字符的概率预洲等方面的改进， 使之也适合 于中文文本的压编。对三类中文文档的测试表明: 改进后的P P M算法 使用三阶模型) 对中文文本文件的 平均压缩比 可达9 . 9 8 6 p c , 最佳压缩比为6 . 5 9 b p c 。如果有更多的内存可用， 还能获得更高的压缩比。今考文献 I P M I V in -, J u s ti n Z o b e l , C a n p n s s i o n T h n iq f C h i n ， 丁 e x t , Sot-Practice- a n d E rz p v i . re，V o l . 1 ( 1 ) : 1 - 4 . 2 1 L a n H . W i n rn等 著， 张仲 顺、 曹文 斌、 曹 水革泽 燕卫华校 海量数据管理 一文档和图像的压编与 索引1 9 9 6 . 1 7 - 5 3J a n u a r y 1 9 8 8 ,， 科学出版社，t 0 6丁 王
