（计算机应用技术专业论文）支持压缩域查询的xml数据压缩方法研究.pdf

支持压缩域查询的x m l 数据压缩方法研究 摘要 近年来，随着i n t e m e t 的迅猛发展，x m l 已经成为数据交换和表示的 主要标准。由于x m l 具有良好的可扩展性和跨平台性，越来越多的信息以 x m l 文件的形式进行交换和存储。x m l 数据的一个特点是存在较大的数据 冗余，会造成存储空间的浪费、查询效率的降低。因此，对x m l 数据行有 效压缩和查询成为x m l 数据库研究领域的一个重要的研究问题。 本文主要研究x m l 数据的压缩和查询技术，对x m l 数据的存储模式 拆分调整、x m l 数据的规范化存储、x m l 数据的相似性分析、频繁子树的 挖掘、基于树文法的压缩、基于签名自动机的压缩数据查询技术等方面进行 了深入的研究，提出了有效的算法。 本文的研究工作主要围绕以下几个方面进行： 首先对x m l 的研究历史与现状进行综述，分析了当前x m l 数据压缩 与查询的研究现状和目前已有x m l 数据压缩方法的不足，并指出了研究主 题及目标。 其次，提出了x m l 模式规范化方法，利用函数依赖和规范化规则发现 和消除x m l 文档中存在的冗余结构，实现在语义一级消除x m l 数据冗 余；研究并阐述了基于树文法的x m l 数据压缩方法。研究了x m l 文档集 之间和文档内部的结构冗余问题，并在此基础上，通过对文档集进行聚类、 发现频繁子树，最终实现压缩，并对所提出的算法进行了实验，验证了算法 的功能和有效性；提出了基于压缩域的x m l 压缩数据查询处理方法。为了 实现非完全解压缩状态下的查询处理问题，提出将签名技术和自动机技术相 结合的基于签名自动机的查询处理算法，实现x m l 压缩数据在非完全解压 缩状态下的查询处理；提出了x m l 数据存取控制规则的压缩与查询方法。 为了处理x m l 压缩数据的安全控制，以及由此带来的存取控制规则规模膨 胀的问题，提出了基于d a c 模型的存取规则剪枝处理方法，有效地压缩存 取控制规则所占用的空间，并给出了规则压缩的查询处理方法。 关键词：x m l ；规范化；数据冗余；数据压缩：查询处理；存取控制规则 略尔演1 程大学辩士学位论定 i i i i ii l l l 岛嗣嘣i i 豳_ 墨 a b s t r a c t i nr e c e n ty e a r s ，a sx m lh a sb e c o m ea l le m e r g i n gs t a n d a r df o ri n f o r m a t i o n e x c h a n g eo nt h ew o r l dw i d ew e b ，i ti sc l e a rt h a ta ne n o l l t l o u sa m o u n to fd a t ai n t h ei n t e r a c tw i l tb ee n c o d e di nx m li nt h en 凇f u t u r eb e c a u s eo f i t se x t e n s i b i l 蓊 a n de h a r a c t e r i s t i co fc r e s s - p l a t f o r m 。h o w e v e r , x m ld o c u m e n t si nt h e i rt e x t n a l f o r ma r er a t h e rv e r b o s ea n dt e n dt op r e d a t ed i s ks p a c ea n dh i n d e rt h ea b i l i t yo f q u e r y , d u et ot h et e x t u a la n dr e p e t i t i v en a t m eo ft h ex m lt a g sa n do fs e v e r a l x m l t y p e s ，h o wt oe f f i c i e n t l yc o m p r e s sx m ld a t aa n de w a l u a t ex p a t hq u e r i e s o v e rc o m p r e s s e dx m ld a t ai saf u n d a m e n t a lp r o b l e m i nt h i sp a p e r , m e t h o d s0 fx m ld a t ac o m p r e s s i o nw i t hq u e r ys u p p o r tw e r e s t u d i e di n t e n s i v e l y , i n c l u d i n gx m ld a t am o d e l s ，s c h e m af o r m a l i s m sa n d d e c o m p o s i t i o n , t h es i m i l a r i t ya n a l y s i so fx m ld o c u m e n t s , f i n d i n gf r e q u e n t s u b t r e e s ，t r e eg r a m m a rb a s e dc o m p r e s s i o na n dp u s h i n gq u e r i e st oc o m p r e s s i o n d a t ab a s e do i ls i g n a t u r ea u t o m a t a , e t c 。 强em a i nr e s e a r c hw o r k sa n ds p e c i f i cc o n t r i b u t i o n sf o u n di nt h i st h e s i sc o v e r t h ef o l l o w i n ga s p e c t s ： t h er e s e a r c hh i s t o r ya n ds t a t u s a r to fx m lw e r es u m m a r i z e d 。m o r e o v e r , t h e x m ld a t am a n a g e m e n tt e c h n o l o g i e s 丽徽a n a l y z e d ；t h ed i s a d v a n t a g e so fe x i s t m e t h o d so fx m ld a t ac o m p r e s s i o nw e r ea n a l y z e di nd e t a i l f u r t h e r m o r e ，t h e d e v e l o p i n ga s p e c t sa n dg o a l so f t h es t u d yo nx m l d a t ac o m p r e s s i o nw e r eg i v e n a c o n c e p to fx k - n fn o r m a lf o r mf o rx m ld o c u m e n t sb a s e do nd t dp a t h e x p r e s s i o ni sp r o p o s e d 。t h ea d v a n t a g eo f t h ed e f i n i t i o ni st h a ti tc a nr e p r e s e n tt h e n o r m a lf o r mw i t hk e yc o n s t r a i n sw i mt h r e ef o r m so ff u n c t i o n a ld e p e n d e n c y t h e d e c o m p o s i t i o na l g o r i t h mf o rx m ls c h e m ai sp r o p o s e df o rr e d u c i n gt h ed a t a r e d u n d a n c i e sb a s e do nt h ef o r m a l i z a t i o nr i d e s ，w h i c hi sn o tm e n t i o n e d 坶妇 y d v l lc o m p r e s s o r t h em e t h o do fc o m p r e s s i n gx m ld a t ab a s e do nt r e eg r a m m a ri sp u tf o r w a r d r e d u n d a n td a t aa r 辫a r i n gn o to n l yi nas i n g l ex m ld o c u m e n tb u ta l s ow i t h i n 支持压缩域查询的x m l 数据压缩方法研究 d i f f e r e n td o c u m e n t s ，a nx m lc o m p r e s s i o nm e t h o db a s e dt r e e g r a m m a ri s p r o p o s e d i no r d e rt oc o m p r e s sx m ld a t aw i t hq u e r ys u p p o r t ，ac l u s t e r i n gs t e p b a s e do nk m e a n si sp e r f o r m e da st h ef i r s ts t e pf o rr a wx m ld o c u m e n t st o g e n e r a t ec l u s t e r s n e x t ，w i t h i nac l u s t e r ，af r e q u e n ts u b s t r u c t u r em i n i n ga l g o r i t h m i sp r e s e n t e dt og e n e r a t et h ec o m p r e s s i o nd i c t i o n a r ys i m i l a rt of p - g r o w t hm e t h o d f i n a l l y , s u b t r e e sa r es u b s t i t u t e db yb i n d i n gv a r i a b l ea n df r e q u e n ts u b s t r u c t u r e b a s e do nt h et h i n k i n go f t r e e g r a m m a r 1 1 1 em e t h o do fq u e r y i n gc o m p r e s s e dd a t ai ss t u d i e d as i g n i f i c a n tp o g i o no f t h i st h e s i si sd e v o i dt oq u e r yo v e rc o m p r e s s e dx m ld a t aw i t ht h ea n a l y s i so f i n d e x i n gs c h e m a sa n dq u e r ym e t h o da p p e a r e di n o t h e rx m lc o m p r e s s o r t h e q u e r i e sa r ep e r f o r m e de f f e c t i v e l yb a s e do ns i g n a t u r ei n d e x a n ds i g n a t u r ea u t o m a t a u n d e rn o n f u l ld e c o m p r e s s i o n am e t h o do fa c c e s sc o n t r o lr o l e sc o m p r e s s i o nw i t hq u e r ys u p p o r ti sg i v e n i n o r d e rt oc o p ew i t ht h ed u p l i c m i o no fa c c e s sc o n t r o lr u l e ，ar u l ep r u n i n gm e t h o di s p r o p o s e df o rx m l d a t aa c c e s sc o n t r o lb a s e do nd a cm o d e l ，w h i c hc a nc o m p r e s s t h ea c c e s sc o n t r o lr u l e se f f e c t i v e l y f u r t h e r m o r e ，t h eq u e r ya l g o r i t h mi sp r e s e n t e d f o rc o m p r e s s e da c c e s sc o n t r o lm a p k e yw o r d s ：x m l ，n o r m a l i z a t i o n ，d a t ar e d u n d a n c y , d a t ac o m p r e s s i o n ， q u e r ye v a l u a t i o n ，a c c e s sc o n t r o lr u l e s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指静 下，囱彳乍者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中融 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成采。对本文的研究做出重要贡献的个 人和集体，均基在文中以明确方式标明。本人完全意谈到 本声明的法律结果由本人承担。 作者( 签字) 趁苎在 网期：幽移年占月一e t 第1 章绪论 第 章绪论 随潜现代社会逐步迈向信息化，在互联网迅速发展的搬动下，产生了大 量懿备秘形式懿倍怠；这些售爨鼠结梅纯程度熬囊度可以划分隽三类：繁一 种是究全结构纯的数据，魏关系黧数据和西离对象的数据；第二种是无缩构 的数据，如文本、声音数据等；还有一种介于二者之间的数据类型，称之为 半结构他数据，这种数据的特点魑拥有不规则、可变的数据结梅。近年来出 褒豹掰扩震标记谬蠹x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 1 1 是半缝稳纯数 据的一种特殊表现形式，它已经成为i n t e m e t 以及电子商务中进行数据交换 和表承事实上的标凇。对于传统的结构化数据和无结构的文本数据，已经拥 鸯毙较成熟熬管理工兵窝接本：臻魏伲数据霹激采雳关系黧数据库或对象壁 数据麾避行管理；无结构的文本数据则可以采用信息检索( i r ) 静方式滋行 访问。如何对半结构化数据( x m l ) 进行有效的管理，包括存储、索引、 查询等，是一个有铸鳃决的问题。 l 。1 磺窕的强麓及意义 璇卷i n t e m e t 的迅速发展，使其成为全球倍患传递和共率的重要资源， 出于i n t e m e t 上的数据多以举结擒或无结橡的形式出域，躐熊传统豹数据模 掰= 不适合表示这些数据。x m l 的出现引起了人们极大的关：i 奎，x m l 是由嵌 黉姻标记元素构成豹自描述标记谮亩。强前，x m l 文档懑经成为t n t e m e t 上戆镶怠交换鞠处理豹熬黉菰壤。x m l 产生静矮糖瑷凌力是为了髂决 h t m l 终为w e b 数据交羧拣擦聪赘来熬混乱届瑟，麓h t m l 穗魄，x m l 其寄缀大的灵活性，不毽爵蔽表承茏结稳懿文本蕊惠，也霹以表示高度缝橡 他的数据，它极大地推动了驻联网技术在电子商务、电子数据交换和电予图 书馆镣多方面的应用。在这方瑟泌经开展了一些研究，如x m l 数据的存储 技术【2 3 ，4 1 、发布技术阶，w 、x m l 数据查询与优化技术8 , 9 j 0 1 、索引技术等啡 。 淹羞x m l 数据豹不凝增糖，麴籍有效地存髓x m l 数攘藏秀一个追锈 鬻簧瓣决麓淘题。嚣兹，缀然避缀捷凄了一臻x m l 数豢熬存德方法，瞧是 。l 一 暗零溪工狴大学媾士学整论文 x m l 的存储闽艨仍然怒数据库领域研究的热点之一。 目前，存在的x m l 文件的存储模式燕要可l 1 分为以下两类：关系模式 和n a t i v e 搂式。关系模式以传统的美系型数据库作为存储居台，牾x m l 文 档转化为关系中的表来存储。而n a t i v e 存储模式通常阱文件系统或专门设计 的x m l 存绦系统作为嚣台，薅x m l 文耥无转亿邈存锉銎| 文 孛系统或专翻 的x m l 存储系统中。 x m l 数据盼一个鞠显特征是冀数据冗余较大，无论采用郡种模式来存 储x m l 数据，都必须露对x m l 数据冗余较大这一特点。冗余既造成了存 储空间的浪费，又增加了查询处理的i 0 ，从而降低了效率，故有必要对 x m l 数攒进程鼹缝存储。 1 。2x m l 麓套 1 2 1x m l 的历史 1 9 6 9 年，i b m 翡磷究入受e m o s h e r 、r l o d e 帮e fg o l d f a r b 发甥7 一 种文件描述语言g m l ( g e n e r a l i z e dm a r k u pl a n g u a g e ) ，用来解决不同系统中 文件格式不丽的问题。g m l 是一种自描述的语京，它w 以餍于标滔任何数 据集会的缤掏，围豺它又是糖元谬言，能够描述其它语言及其语法和词汇 表。1 9 8 6 年，g m l 成为国际标准s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u p l a n g u a g e ，掭毽逶曩辣逶语衰) 。s g m l 爨骞与辫畜无关、结橡纯、霹扩展 等特点。由于其功能强大，可以用来创建、处理和发布大量的文本信息。 1 9 8 9 年，e 琶r n 欧溯粒子耪瑾骈究中心静醑究天爱开发了基于s g m l 的趣文本版本，称为h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) ，目的是为了能 用超链按方式在其研究机构内部共辜文本信患。h t m l 以其简单易学、灵 活邋曩豹特点褒i n t e m e t 上褥剿了广泛豹应用。h t m l 然零了s g m l 的许多 重疆特点，比如结构化、实现独立和可描述性等，h t m l 文档不仅能以文 本形式显零， 塾霹瀑寇图形接霉圭照忝，豢至可豁逯遵声啻、携犊等多媒转 形式来呈现。但是，它也存在很多缺陷，比如它只能简单地显示资源内容。 却茏法表达资深内容静含义。勇井，h t m l 廷僚餍一筑固定秘元素类塑， 第1 苹绪论 不能扩展，因此不鼹謦 对特定的文档类型进行设计。 鹣着i n t e m e t 鹃浃速发震，h t m l 存在豹逡登缺点越来越突出，缀多入 开始不满足于h t m l 固定的文档类型，于是人们力图对h t m l 进行扩展。 经过不断的探索，认识到扩展的关键是能够把数据本身和数据的显示分离 嚣。程这一过程中，c s s ( c a s c a d i n gs t y l es h e e t ) 群式警被怒寒为h t m l 添 加抽象机制。为了能够定义文档类型，进行有效性检焱，w 3 c 开发了 x m l 。它是s g m l 的一个子集。x m l 保留丁s g m l 的很多优点，它闯时 具有强大的功能、良好的可扩展，陡以及简单懿结梅。1 9 9 8 冬，x m l 威麓了 w 3 c 的正式标准。灏对，还发稚了x l i 瞌( e x t e n s i b l el i n k i n gl a n g u a g e ，可 扩展逑接语言) 和x s l ( e x t e n s i b l es t y l el a n g u a g e ，可扩展的样式语言) 。 l 。2 。2 x m l 数据 x m l 是一种元标记语言，可以用来定义熊它的标记谮言，并且选种标 记语言的元素标记怒由用户自定义的。 x m l 数据静优点在予： ( 1 ) 能应用与i n t e m e t 上的数据交换，豳予i n t e r n e t 上存在各种格式的 数据，既有结构化数据，也有无结构化数据，还有如音频和视频那样的流数 据，x m l 数据的出现使得本文耐以实现各种格式数据之间的无缝交换； ( 2 ) 能实褒受霄意义、更准确豹援索，黼l 数器熬鑫我捂述戆力後褥 搜索能够依靠标记和内容之间的必系实现更加准确的定位； ( 3 ) 它能实现髯构异质系统间的通信，传统的结构化数据库难以适应 多系绕器魄数据懿黻会，嚣x m l 数豢出予冀蠡我绉述，穰好建适应邀耱 数据集成的需要。 x m l 文档一般由四个部分构成：x m l 声明，处理命令，x m l 元素和 注释。其中x m l 玲明和x m l 元素是必须的，丽处理命令霉珏注释则是雕选 肉容。x m l 声强粥予声鞠该文糨是一个x m l 文档；鲶瑷指令荽| j 毽禽在 x m l 文档种的一些命令性语句，目的是告诉x m l 处理魑信息或执行一 定的动作；x m l 元索是x m l 文件内容的基本单元，一个元素包含一个起 始拣谗、一拿缝窳探记浚及拣落之趣夔建骞，元素里还霹以褥簸套元素，安 现嵌褰循环，最辨滕的元素称为根元素，一个x m l 文稻强能有一个粳元 喻尔滨工程大学博十学位论文 1 1 1 1 1 1 1 1 1 - _ _ _ 皇田目i _ 薯_ _ - _ _ _ 暑嗣墨_ 黼糊皇蚺 紊；注释是x m l 文件种一些用作解释的字符数据，x m l 处理器不对它进 幸亍任谤处璎。 一个绾梅良好的x m l 文俸逶鬻攒没有语法错谈鼢x m l 文件。如果一 个x m l 文档满足以下要求，则称其为个良构的x m l 文档：( 1 ) 文档的 搿始必须悬x m l 声明；( 2 ) 含有数据的元素必须有起始和结束标记； ( 3 ) 只毒一令禳元素；( 4 ) 元素哭缝媛套不髭嚣爨。下嚣是一今蹇鞫戆 x m l 文档例子。 c o x b i t l j a c k f l o w c o x 舭 m e m h “a n o - 叭“ n 心b 山“砌 q m e 衲e 口 # 鞴出# 冉鲫。柚z e 燃) | 牡塾辅m # l 自h l p q 黼o 辩蚶n p n 俨。p 吖) 哪t 弛喇e 龇赫埘a n m m o l ” ( n 帆 8 班q 址i 撼撑程舡檄势 # 耐b 睁 唧f 叩 q o d u p ( a ) g r o u p x m l ( b ) g r o u p x m l 的文档树 豳1 1x m l 文档和文档树 f i g 1 1x m ld o c u m e n ta n dd o c u m e n tt r e e 在x m l 交箨褥孛，辫莱一个嚣繁不霉包含英窃子元素，褥密势野元素 ( 或叶节点) ，如果能够从根元素出发达到这个元索，称这个元豢为分支元 素( 或分支带点) 。例如，g r o u p x l m 文件中的m e m b e r 是分支，而n 锄e 元 素是砖。狳子元素数磐，元素还可以瘸寝牲寒臻逡瓣鸯叠售息。疆性瑗来擒 述元素的特征，记录元索特有的僖惑用黻与其它同名元素滋行医甓。 g r o u p x m l 文件中的p r o j e c t 元素就拥肖一个属性 p n o ，用来记录该项目的 编号。通常惩素前恧添加 符号，用来区剐文件树中的元素和属性。 恤 、 太 济 一公一 笊万一 彳雠群 田 鲫。 嗡尔蒺工程大学搏士学位论文 i i i i j _ _ x m l 文档可以划分成若干冉勺文本片，把这些文本片称为实体 ( e n t i t y ) ，通过搓文件中插入实体弓| 用( e n t i t yr e f e r e n c e ) 来使用实体。实 体分为两种；一种是内部实俸，是在文件内部定义；另种怒外部实体，它 是在文梢外部定义，存放在另外一个文件或存储在数据库中。通过使用外部 实俸，可醣将一个大黧静x m l 文襁分解为多个文件，倭予缝壤。 x 磁l 文褴逶常分为磷类；一爨敷数摄麓中心熬文传，逡耱文终在结搦 上怒较裁剐熬，在内容土是溺棱戆，宅可以曩 乍存镳w e b 数攥豹一令容 器。男一釉蹩以文档为中心的文档，邀手中文4 孛续掏是不规则的，鬻用来在嘲 页上发商描述性信息、产品性能介绍、e - m a i l 傣息等。在本文中，主要关注 的照以数据为中心的) ( 1 l 文档。 3 数据愿缩 大多数惰怠的表达都存在着一定鹃冗余度，邋过采错一寇的模墅靳编礴 方法，可以降低这种冗余度。对于数据压缩技术，眈较系统的研究开始于上 毽纪4 0 年代裙罐出黪信崽论。早期傣惠谂研究的内容之一憝在穗稚淆怠串 各符号密瑗靛频率，没法褥造一耱编璃按术使缀债惑获翥戆察蠲爨霹憨乡。 近二+ 零柬，由予模式谈鬟、图豫憝毽、诗算极运臻、数据黪技零等技术豹 出现，鼹进了数据压缨理论翻应用的快速发展。 贝尔实骏塞的c l a u d es h a n n o n 和m i t 的r m ，f a n o 在1 9 4 9 年几乎同 时提出了最晕的对符譬进行有效编码从而实现数据聪缩盼s h a n n o n - f a n o 编 码方法。 d a h u f f m a n 于1 9 5 2 年第一次发袭了谴盼论文“鬣小冗余发代鹞静擒 造方法”f am e t h o df o rt h ec o n s t r u c t i o no f m i n i m u mr e d u n d a n c yc o d e s ) 。 2 0 落篼8 0 年 弋，数学家嚣j 举满足予h u f f m a n 编码中豹装些皴佘聪 点，建 l 从获载焦度入手，遂簇h u f f m a n 编弱的主导愚想，设计出另一鼬 更为糖确，鼹能接近信息论中“熵”极限的编码方法算术编鹳。凭借髯 拳编码的精妙设计和卓越表现，人们终于可以向麓数据服缩的极限靠近。w 以证明，算术编码得到的压缩效果可以最大地减小储息的冗氽度，用最少薰 的符号精确表达原始信息内容。当然，算术编礴同时也给程窿员帮计算枫带 第l 章绪论 来了新的挑战：要实现和运行算术编码，需要更为艰苦的编程劳动和更加快 速的计算机系统。也就是说，在同样的计算机系统上，算术编码虽然可以得 到最好的压缩效果，但却要消耗也许几十倍的计算时间。这就是为什么算术 编码不能在本文日常使用的压缩工具中实现的主要原因。 为了找到既在压缩效果上超越h u f f m a n ，又不增加程序对系统资源和时 间的压缩方法，1 9 7 7 年，j a c o bz i v 和a b r a h a ml e m p e l 发表了论文“a u n i v e r s a la l g o r i t h mf o rs e q u e n t i a ld a t ac o m p r e s s i o n ”。1 9 7 8 年，他们发表了 该论文的续篇“c o m p r e s s i o no fi n d i v i d u a ls e q u e n c e sv i av a r i a b l e r a t e c o d i n g ”。在这两篇论文中提出l z 7 7 和l z 7 8 算法。简单地说，这两种压 缩方法的思路完全不同于从s h a n n o n 到h u f f r a a n 到算术压缩的传统思 路，而是采用字典式编码。字典式编码不但在压缩效果上大大超过了 h u f f m a n ，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。 1 9 8 4 年，t e r r yw j l c h 发表了名为“at e c h n i q u ef o rh i g h p e r f o r m a n c e d a t ac o m p r e s s i o n ”一文，描述了他在s p e r r yr e s e a r c hc e n t e r 的研究成果。 他实现了l z 7 8 算法的一个变种l z w 。l z w 继承了l z 7 7 和l z 7 8 压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受，实现也 比较简单。 当数据压缩被用于减少存储空间时，可以减少程序的执行代价和执行时 间。这是因为存储两的减少将导致磁盘存取次数的减少，虽然数据的压缩和 解压缩过程会增加额外的代价，但由于这些代价通常少于数据的存取时间， 因此总的代价减少了。尽管存储系统的容量和性价比在近些年来的到了很大 的提高，但不断出现的i n t e m e t 应用、复杂业务系统的数据等仍然使得数据 压缩技术在计算机技术飞速发展的今天起着很重要的作用。 目前，根据不同的应用领域，数据压缩技术的研究主要包括以下几个方 向： ( 1 ) 图形、图像压缩技术； ( 2 ) 数据库压缩技术； ( 3 ) 声频、视频信号的压缩技术和传输信号的压缩技术； ( 4 ) 文本压缩技术。 其中，数据库压缩可以说是一种特殊目的的压缩技术，其目的不仅要减 7 嗡囊；滨工稷丈攀搏士学位论文 少数据所占的存储空闼，要求在压缩过程中不丢失信息，而且要求能够在一 定稷度上对压缩数据进行存在操作。 文本压缩是基本晌一种文件压缩，其掰的蹩要减少文彳串所占的存储空 间，要求压缩了的文件在解压缩后，内容与未压缩之前完全相同，是一种笼 损聪缩技术。近年来，随着i n t e r a c t 瀚快速发展，数据静形式弱内容酃发生 了深蕤懿交纯，镶麴蹬臻了娃承载半结构佳数糖为健表豹半缝稳纯文终、 x m l 数据等。阉懿，翻羽数据痒技术黠这些数据类型避季亍警理凌是逛年袋 豹磅究热点。对于这拨数糕的压缨，鼠经不单纯应用文本压缨技术，甄是数 据黪压缭技术、文本聪缀技术等多种技术的综合应用。 在本文中，主要磷究支持信息检索的x m l 数攒库的压缭技术，所以羹 点介绍相关的文本压缩和x m l 数据压缩技术。本章的下面几节阐述了 x m l 数据席压缩技术教冀研究现袄。 1 4x m l 数据压缩研究现状 数摄蓬缀起潦予碡0 冬我哟c l a u d es h a n n o n 蓄创魏嫠惠论。大多数绩慰 遴 篷一定豹攘型霸编鹃方法，哥以终低其麝包含瓣数据冗余。蒋缓的数据瑟 缩方法1 1 6 】仅仅= ；妻重压缩效率，没谢考虑到数据的髓机移取和操作问题，不 适念于数据艨系统。数据库压缩是种特殊目的的聪缩技术，它不同于普通 压缩之簸在于充分考虑了所鲶理数攥的特殊性，分析数据的结构和特点，在 普通压缩算法基础上进步提高压缩效率，并撼供数据在压缩域上的查询处 理方法。 嚣懿，数据撵歪雅技零静赣究主要集串在敦t3 个方霖：( ) 数摄簿 疆缩方法豹疆究，惫糖馁羯蠢骞静数攥蘧缭算法遮续数攥蓐釉秘嶷耨躯逶袋 子数据黪存取模妓的数搬压缨方法。效应用于数据麾压缩的传统数据压缩肖 法包括字典愿缩技术、游程压缩技沭、算术压缩【l7 】和l z 压绻技术，提出的 适爝于数据熙存取模式的数据压缩方法包括索弓l 遥缩方法、绦序压缩技术、 基乎语义的眶缩技术、面向块的增攘服缩方法、映像完全的数据压缩算法。 ( 2 ) 压缩数据上莳搽作弊法的研究，主要是在蓬缩数蠢上燹矮解运缩，躐 第1 章绪论 解压代价极小的数据操作算法。 ( 3 ) 压缩数据库上的查询优化处理技术的 研究 1 8 , 1 9 。 在数据库压缩技术的研究中，压缩方法的研究是最活跃的，特别是针对 数据的不同模型及其操作的具体特点来研究数据库压缩算法，例如半结构化 数据、x m l 数据、关系数据、g r a p h 结构数据类型等。文献【5 】提出结构上 下文模型s c m ( s t r u c t u r a lc o n t e x t sm o d e l ) ，利用这种半自适应的压缩模型 对半结构化( x m l ) 数据进行压缩；文献【2 0 】为了在压缩的关系数据库中实 现无须解压缩的连接操作，将关系拆分成二元关系，并用m a s k 方法实现 了数据库的压缩存储；k u n i h i k os a d a k a n e 等在文献 2 2 】中对文本数据库的 压缩和查询算法作了概括和总结；用压缩技术减少搜索引擎和w e b 仓储系 统的节点链接结构的规模是另一个比较有趣的应用 2 3 1 。 x m l 自身的特点决定了其数据冗余较大，由此造成了存储空间的浪 费、查询效率的降低。x m l 压缩技术就是针对x m l 数据的特殊数据模 型，在x m l 结构特征和语义信息的帮助下对其进行压缩的过程。根据应用 的目的不同，x m l 压缩技术又可以分为有损压缩和无损压缩；根据对查询 的支持程度，又可以分为支持查询的压缩技术和不支持查询的压缩技术。在 本文中主要研究支持压缩域查询的x m l 无损压缩方法。 1 4 1 不支持查询的x m l 压缩方法 不支持查询的压缩方法作为早期的x m l 压缩方法，目的单一，就是要 解决x m l 的冗余问题，以满足网络带宽和存储空间的要求。它们的共同特 征是压缩率都好与一般的压缩算法，如b z i p 等；其次是不支持随机存储， 也就是如果要对其进行查询处理，就必须进行完全解压缩。近年来，提出了 多种不支持查询的压缩方法，如x m i l l 、x m l p p m 等，这些压缩方法为了 取得较好的压缩效果，都不支持随即存取和查询处理。 其中，x m i l l l 2 4 1 是最早的不支持查询的x m l 数据压缩系统。x m i l l 中压缩方法的核心思想是将结构和内容分离，然后利用a p p r o x i m a t i o n m a t c h i n g 算法对相似语义的数据项进行分组，形成数据容器( c o m a i n e r ) 。 对于结构，用字典编码( d i c t i o n a r ye n c o d i n g ) 方法对属性( a t t r i b u t e ) 和元 素( e l e m e n t ) 进行替换。对每个容器，利用通常的l z 7 7 算法分别进行压 9 哈尔滨工程大学博士学位论文 缩，最后将已经压缩的片断合并成一个完整的压缩文件，能够取得两倍于 g z i p 的压缩效率。 x m l p p m t 2 5 1 提出了一种基于p r e d i c t i o nb yp a r t i a lm a t c h ( p p m ) 的压缩 方案。与x m i l l 不同，x m l p p m 利用s a x 解析器将x m l 整理成一个数 据流，作为x m l p p m 的输入。根据语法，对元素或属性名、结构、属性值 和数据项等分别利用相应的p p m 算法进行编码压缩。由于p p m 算法是一种 速度较慢的压缩方法，所以x m l p p m 算法要比x m i l l 方法慢。但是在压 缩率上，x m l p p m 要好与x m i l l 。 m l e v e n e 和p t w j o d 【2 q 利用结构压缩算法( s t r u c t u r ec o m p r e s s i o n a l g o r i t h m ：s c a ) 对x m l 进行压缩。在此种方法中，x m l 文档必须具有 相应的d t d ( d o c u m e n tt y p ed e f i n i t i o n ) 。首先，s c a 算法采用分析树 ( p a r s et r e e ) 对数据进行预处理，然后再对分析树剪切，形成剪切树 ( p r u n e dt r e e ) ，最后对剪切树编码。s c a 的核心思想是两阶段最小描述长 度编码( m i n i m u md e s c r i p t i o nl e n g t he n c o d i n g ) 的改进，力求用最短的编码 对x m l 结构进行编码压缩。s c a 方法的缺点是在对大容量x m l 文件压缩 时，必须提供较大的内存空间来存储中间数据结构，如p a r s et r e e 和p r u n e d t r e e 等。 其它不支持压缩域查询的x m l 数据压缩方法还包括：王志宏、李建中 等 2 7 1 提出的基于编辑距离的x m l 文档聚类压缩方法：陈敏敏、唐常杰等【2 8 1 在其提出的s g c m 算法中，通过三个阶段实现对x m l 数据的压缩。从本质 上来说，上述两种方法都是x m i l l 方法的延伸。此外，文献【2 9 】利用 h e d g e 自动机技术实现对x m l 文档的压缩。 1 4 2 支持查询的x m l 压缩方法 随着x m l 应用范围的扩大，x m l 文档的容量也在不断加大，如果通 过完全解压缩来对压缩数据进行查询将耗费很长的时间，因此，在非完全解 压缩状态下进行随机存取和查询处理是必然的要求。下面几个典型的研究项 目从结构、语义等不同思路对支持查询的x m l 压缩方法进行了研究，如 x g r i n d 、x p r e s s 、x q u e c 等。 其中，x g r i n d | 3 0 】是t o l a n i 和h a r i t s a 提出的一种支持压缩域查询的x m l 第1 章绪论 自_ i _ _ _ _ 篷缩方法。力了实现蒺于 宪垒嬲压缩条件下的有效焱途，x g r i n d 采甭了 上下文无关( c o n t e x t f r e e ) 的模式，也就是压缩质的编码与其位置无关，这 样，就可强不用解压缩就可戳实现搜索功能。在x g r i n d 中，首先对x m l 文档进行统计，囱h u f f m a m 编码提供统计信息，然后x g r i n d 对这熬统计镶 息进行归类、判断，再进行实际的编码。 x g f i n d 豹一夺特鑫就是支持壹羧查询，就是说不臻宠全黪矮缩就虿班实 现蠢询。在x o r i n d 压缩体中保留了x m l 文件的结构。x g r i n d 在僳留了绒 褐静完熬往豹丽对，又其有x m i l l 的数灞与结构分离的特煮。当然， 寸出 的代价是压缩效率要比x m i l f l 低。 x p r e s s 3 1 】的压缩器支持直接在压缩数据上避行查询，它采用了一种叫 傲r e v e r s ea r i t h m e t i ce n c o d i n g 匏编鹎方法，对x m l 数握趋每一个黢径送行 编鹕。它的试验表明，x p r e s s 能够在取得平均7 3 压缩比的条件下支持 鸯谗莲缩数据。x g r i n d 帮x p r e s s 郡实现了蘩予h u f f m a n 编码静压缩方 法。 此外，b u n e m a n 等【3 2 l 提出了一个能够辩x m l 压缩文件誊接进行路径蠢 询豹框架( s k e l e t o nc o m p r e s s i o nf r a m e w o r k ：s c f ) 。通过共摩子树 ( c o m m o ns u b t r e e s ) 方法将x m l 转换为一个紧凑的有向非循环圈 ( d i r e c 耗da c y c l i cg r a p h ：d a g ) 。是了熊够对蕊绩数据避褥套诲，弓| 入了 实例( i n s t a n c e ) 和双向模拟( b i s i m u l a t i o n ) 概念，来