（计算机应用技术专业论文）xml文件压缩存储和自索引研究.pdf

天津师范大学硕士学位论文 摘要 ) 0 v i l 目前已经成为i n t e r n e t 上的“国际语言”，所以，如何使数据库管理系 统对x m l 文件进行良好的支持就成为了当前的研究热点。 本文讨论的内容，就是在纯) l m l 数据库管理系统下，对x m l 文件进行压 缩存储以及对压缩后的文件实现自索引。 由于j c d v i l 文件需要对数据的结构进行描述，具体的方式就是加入标签，这 使得l 文件所占的存储空间变大。而对应的解决办法，就是对文件进行压缩。 传统的压缩方法不能保持 c i v i l 文件的结构，所以当进行查询的时候，需要将文 件先进行解压缩，或者先要对查询关键字进行同样的压缩处理，才能够进行查询。 本文针对 c m l 数据冗余大的问题，同样对文件进行了压缩处理。但是，本 文采取保持x m l 文件结构，只对其中文本结点中的文字内容部分进行压缩。这 样在节点级别进行查询操作时可以不进行解压，当查询定位到某个节点以后，才 需要把相应的内容进行解压缩操作，这样就提高了效率。 对于本文提出的存储方法，给出了对应的查询方式，其特点就是在锁定要查 询内容所在的节点位置的前提下，再对节点内容进行解压缩，同时，在解压缩的 过程中，创建出文本的后缀数组作为节点内容文本的全文索引，然后使用索引进 行进一步的查询，其查询效率就大大提高了。因为系统并不需要单独存放文本内 容的索引文件，而是在解压缩的过程中生成索引，这也就使被压缩的文件具有了 自索引的特点。 关键词：x m l 压缩自索引b w t 后缀数组 天津师范大学硕士学位论文 a b s t r a c t x m lh a v eb e c o m et h e “g l o b l el a n g u a g e ”i nt h ei n t e r n e t s o ，h o wt od e a lw i t ht h e x m li nd b m sh a v eb e c o m ef o c u s w h a td i s c u s s e di n t h i sp a p e ri sh o wt oc o m p r e s sa n ds t o r ex m lf i l ea n dc r e a t e s e l f - i n d e xo fi ti nn a l ：i v ex m ld b m s s i n c ex m lf i l en e e dt od e s c r i b et h es t r u c to ft h ed a t a ，i th a sl o to fm a r k t h i sm a k e x m lt a k eu pm o r es t o r a g es p a c e p e o p l et r yt or e s o l u t et h ep r o b l e mt h r o u g h c o m p r e s st h ex m l m a n yi d e ac a nn o tk e e pt h es t r u c t u r eo fx m l w h e nc o m p r e s s e d x m lf i l eb eq u 嘶e d ，w em u s tu n c o m p r e s si tf i r s t o rw eh a v et oc o m p r e s st h e k e y w o r di nt h es a m ew a y ia d a p tt h ec o m p r e s s i o na st h em e t h o dt oe l i m i n a t ed a t ar e d u n d a n c yo fx m l b u t ，i o n l yc o m p r e s st h et e x tn o d eo ft h ex m l f i l et ok e e pt h es t r u c t u r eo fi t t om y s t o r a g e s t r a t e g y , t h es p e c i a l i t yi st h ed a t an e e dt ob eu n c o m p r e s s e do n l ya f t e ra p p l i c a t i o nf i n d i t sn o d ep o s i t i o n s oi tm o r ee f f i c i e n c y t ot h i ss t o r a g es t r a t e g y ，t h ep a p e rg i v eas e a r c hm e t h o d d u r i n gt h ep r o c e s so ft h e u n c o m p r e s s ，t h es y s t e mc a nc r e a t eaf u l lt e x ti n d e xo ft h en o d ec o n t e n t i tu s es u f f i x a r r a ya st h ed a t as t r u c t s ot h eq u e r yw i l lf a s t e rb e c a u s et h ei n d e x s o ，t h i si st h et e x t n o d el e v e ls e l f - i n d e x k e yw o r d s ：x m l c o m p r e s s s e l f - i n d e xb w ts u f f i xa r r a y 4 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得鑫鲞竖基盘鲎或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 鹆匡奎日 学位论文版权使用授权书 期： 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文 的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇 编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：日期：竺121i 天津师范人学硕十学位论文 第一章绪论 1 1 背景 ) ( m l 语言被大家称为i n t e r n e t 上的通用语言，因为它诞生的目的就是为了统 - - i n t e r n e t 上不同格式的数据，实现异构数据系统之间的信息共享。x m l 语言出 现不久，很多数据库厂商就提供了在关系数据库中以x m l 形式发布数据的功能， 但是却无法直接存储以x m l 形式存在的半结构数据。后来，随着技术的进步，很 多关系数据库也逐渐支持了直接存储和管理x m l 文件的功能。 与之对应的，x m l 数据库自然也就成为了一个研究热点。目前对于x m l 数据库 的研究，主要有两种思路：第一个就是上面提到的，依托于关系数据库来实现x m l 数据库的功能，叫做x e d ( x m l e n a b l e dd b m s ) ；另一种思路就是研究纯x m l 数据 库，叫做n d x ( n a t i v ex m ld b m s ) 。一般x m l 数据库研究的具体内容主要包括这 么几个方面：x m l 文件的存储技术、x m l 数据的索引技术、x m l 文件解析和内容管 理技术，以及数据查询和发布技术等。 目前，x m l 文档因为其固有的描述性特点而趋向于变得冗长，这是因为x m l 是一种元数据语言( m e t a d a t al a n g u a g e ) ，它包含了许多优点比如支持解析、验 证、转换等等，但是这些也就决定了x m l 文档会比另一些同内容的文档大很多。 由于x m l 被广泛地作为一种数据交换的中介格式来使用，被交换的文档如果过大 就会降低应用程序的性能和可扩展性，而这就会在进行数据交换时出现效率底下 和正确性验证复杂等问题。 有很多方法可以使x m l 文档变小。如简化内容( 通过缩写，简写等方法) ，切 分x m l 文档等技术。但是，这几种方法并没有有效的解决x m l 本身的冗余问题， 而且会带来进一步的问题一如缩写的歧义、切分文档的重组等。 目前，减小x m l 文档的一种有效的方法就是对文件进行压缩，人们已经实现 了一些有效的x m l 压缩工具和压缩方案，如x m i i i ，m i l l a u 和w b x m l 等，但是压 缩后的x m l 文档需要解压后才能对其进行验证、查询等操作，这在某些应用中存 在时问或者空间代价过高的问题( 如手持设备或者接收压缩x m l 文档的服务器 等) ，所以如何在有效压缩x m l 文件的同时又能够实现在压缩后的文档上进行快 速的查询和其他操作，就成为基于x m l 的数据库系统中需要解决的一个问题。 天津师范大学硕士学位论文 本文的内容就是讨论纯x m l 数据库中，x m l 文件的压缩存储方式和索引方式， 以及对应的查询相应方式。 1 。2 本文的组织结构 本文的主要内容是提出了一种保持x m l 文件结构的节点级压缩存储策略，以 及给出了对于这种存储策略所对应的索引方式和查询方法。 在第一章的绪论之后，接下来的第二章中，本文首先要向大家介绍一下理解 文章内容所需要的基础知。在基础知识之后，第三章详细的介绍了本文提出的对 x m l 文件的压缩存储策略的具体方法和操作流程，以及在这个过程用到的数据结 构和算法。然后，文章的第四章就会讲解详细的查询响应过程，当然也同样会细 致说明用到的数据结构和算法，以及这种存储策略所能实现的x m l 压缩文件的自 索引。最后，第五章使用一个简单的x m l 文件作为例子，向大家实际模拟整个压 缩存储x m l 文件的过程及索引结构建立和查询响应的过程。第五章是对实验的情 况做报告，最后是总结和展望。 2 天津师范人学硕士学位论文 第二章基础知识介绍 2 1 x m l 概述 x m l 是1 9 9 8 年2 月由w 3 c 组织发布的一种“推荐标准”，它的英文全称叫做 “e x t e n s i b l em a r k u pl a n g u a g e ”，翻译成中文叫可扩展的标记语言，是从原来 的s g m l ( s t a n d a r dg e n e r a l iz e dm a r k u pl a n u a g e 标准通用标记语言) 所简化而 得到的一种标记语言。x m l 和h t m l 一样，都是s g m l 的子集，而x m l 是专为i n t e r n e t 应用而设计的一个经过优化了的s g 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 文档类型定义) 来定义 ) ( i l 文档中的元素结构；第二，数据大都是非常不规则的，所以，x m l 数据和传统 的数据库系统中的数据，不管是关系数据库或者是面向对象数据库，都是存在较 大的差别的，不能简单采用处理结构化数据的方法来处理半结构化的x m l 数据。2 1 x m l 本质上是一种定义语言，使用者可以自由定义标签，并且通过其本身具 有的元素之间的嵌套来体现层次关系。这又包含两个要素：s c h e m a ( 模式) ，x s l ( e x t e n s i b l es t y l e s h e e tl a n g u a g e 可扩展样式语言) 和x l l ( x m ll i n kl a n g u a g e 可扩展链接语言) 。s c h e m a 定义了x m l 文件的逻辑结构，定义文件的元素、元素 的属性和元素与对应元素属性之间的关系，可以用x m l 解析器来分析校验x m l 文件 的合法性，s c h e m a 允许把内容类型定义为某种数据类型，比如整型、浮点型等。 x l s 是规定x m l 文档样式的语言，可以使w e b 浏览器改变显示方式，这样也就不需 要与服务器进行交互了。x l l 可以进一步扩展现在w e b 上已有的简单链接。综上， 一个x m l 文档是友元素、子元素、属性、p c d a t a 以及元素与后三者的连接而构成 的。 目前) ( m l 家族包括三个成员：x m l ( 可扩展标识语言) 、x li n k ( 可扩展链接 语言) 、x s l ( 可扩展样式语言) ，它们分别完成信息资源描述、信息资源链接 与信息资源的可视化和格式化三方面的功能。 天津师范人学硕十学位论文 任何x m l 文档对任何类型的应用和正确的解析都必须具有良好的结构，即所 谓“w e l l - f o r m e d 。一个结构良好的文档应该具备的条件是：每一个打开的标 签都必须有与之匹配的结束标签；不得含有次序颠倒的标签；并且在语句构成上 应符合技术规范的要求。此外，x m l 文档可以是有效的，但并非一定要求有效。 所谓有效是指符合其文档类型定义( d t d ) 或者模式( s c h e m a ) 的文档。 d t d 描述了文档中对象( x m l 中的元素) 的内容和结构，是描述x m l 数据模式 的模式定义语言。d t d 基本上就是一种语法，它给出的内容是：什么样的标签是 允许的，它们的出现顺序如何，它们怎样被嵌套。文档中的元素名字的尾部可以 追加重现操作符，以定义元素是仅仅出现一次，还是可以出现零次或多次、一次 或多次，或者作为可选项根本不需要必须出现。d t d 为x m l 数据带来了可移植的特 性，举个例子，它可以规定“饮品 的属性，其中只有“奶 、“橙汁 、“咖 啡 和“汽水”是合理的值，这就使解析器可以判定文档内容是否合理，防止出 现数据错误。d t d 还针对标签出现的顺序做了规定，使得其他接收到该x m l 文档的 应用软件，知道在接收到这个x m l 文件时该如何处理和搜索。 x m ls c h e m a 是用一套预先规定的x m l 元素和属性创建的，这些元素和属性定 义了文档的结构和内容模式。 和d t d 相比，x m ls c h e m a 最大的优势就在于对数据类型的支持。除了更为丰 富的内置数据类型( d o u b l e ，d e c i m a ld a t e t i m e 等) 外，s c h e m a 还允许用户通过 扩展或者组合己有的简单类型或者复杂类型来定义自己的数据类型。这种丰富的 类型有助于减小使用) ( m l 标签文档和实际数据之间的差异，例如，可以直接使用 日期类型，而不需要应用程序做进一步检查。 另外，s c h e m a 提供了l l d t d 更强的内容模型，可以验证混合内容( 文本和子 元素混合) 的有效性，指定元素出现的确切次数，还可以用来为元素组命名等。 x p a t h 即) ( m lp a t hl a n g u a g e ，是一个独立的技术规范，定义了x m l 文档中的 特定条目该如何定位，为x s l t 和x p o i n t e r 大量使用。在x p a t h 技术规范中，一个 x m l 文档被认为是一个节点树，树中每个节点都可以通过详细描述该节点在树中 的位置进行存取操作。在这里，节点指的是任何一段x m l 数据，包括元素属性或 文本数据。 4 天津师范人学硕七学位论文 用来对x m l 进行处理的工具很多，他们让x m l 的优越性能得以一一实现。s a x 是x m l 简单a p i ( s i m p l ea p if o rx m l ) 的缩写，它提供了一个用来解析) ( m l 数据 的基于事件的框架，使用数据流的方式扫描整个文档，并将数据拆成几个有用部 分的一种处理过程。d o m 是文档对象模型( d o c u m e n to b j e c tm o d e l ) a p i ，它把 x m l 文档描述成一棵树，很容易用程序语言实现遍历和其他操作树的过程。d o m 需要将整个x m l 文档读入内存，并将所有数据存储在节点里，使整个文档可以快 速使用。j a x p 是s u n 公司的x m l 解析j a v aa p i ( j a v aa p if o rx m lp a r s i n g ) 的简 称，它为s a x 和d o m 的a p i 提供了核心并添加了一些方便的函数，使得x m la p i 易于 在j a v a 环境中开发和使用。j d o m 是以j a v a 表述的x m l 文档，这样的表述为用户提 供了更简单有效的读、写和操作方法，它具有简单直接的a p i ，轻松快捷，可以 被j a v a 程序员优化。j d o m 既可以和s a x ，d o m 完美结合使用，也可以替代s a x 和d o m 的使用。x m l 的处理可以很好的和j a v a 集成在一起，其基本原因是：j a v a 是可移 植的代码，x m l 是可移植的数据。 下面给出一个简单的x m l 文档及其d t d 文件的实例。 1 ) x m l 文档：e x a m p l e ：x m l d 、陈 中国 福建 福9 - h llo d 、陈 g m a i l c o m d x 林 天津师范人学硕七学位论文 中国 福建 福少b l12 d 、林 g m a i l c o m 2 ) d t d 文档：e x a m p l e d t d 2 2x m l 文档的内容 x i v l l 用于对于文档进行数字化和结构化的表示，把文档转变成计算机可读的 代码，让计算机对这些数据可以进行像存储、查询等操作。为了使计算机能够有 效的处理，x i v l l 就必须告诉计算机自己表示的文档的结构和内容。 ( 1 ) 元素与属性：逻辑结构 大多数文档( 如书籍和杂志) 都可以分成一些组件( 比如章节和文章内 容) ，这些组件又可以分成更小的组件( 比如标题、段落、图片等) ，而文档 中的具体内容用文本表示。在x m l 中，组件称为元素，表示具体内容的文本成 为文档的字符数据。x m l 元素用来描述文档的逻辑结构。其中，包含所有元素 6 天津师范人学硕十学位论文 的元素( 比如论文) 称为根元素，它是唯一没有前导元素的元素。根元素直接 包含的元素称为子元素，它们可以嵌套的继续包含自己的子元素。除了子元素， 元素还可以包含相关信息，这些信息称为属性，属性用以描述元素的一些特征。 ( 2 ) 实体：物理结构 x m l 提供了一种机制，可以使文本被线性的组织，即以多片( m u l t i p l e p i e c e s ) 的形式组织。“文本片这个概念称为实体，每个实体都有名字。x m l 元素是描述文档的逻辑结构，而实体是描述组成x m l 文档的字节块的位置的，就 是描述文档的物理结构。 在文档中，可以通过插入实体来使用实体，x m l 处理器会用实体替换相应的 实体引用，这一过程为文本替换。这样，同一文本可以在很多不同的环境中自动 的重复使用，在某一处的更新就可以影响到使用这一文本的所有地方，这种特性 称为外部实体。非) ( m l 对象( 包括图形、电影、声音、原始文本p d f ，h t m l 等) 也 可以用同样的方式引用，称为不可分析的实体，也称为数据实体。 ( 3 ) 标记 元素构成x m l 的树形文档，实体管理文档的尺寸和复杂性。而描述文档的逻 辑结构、连接物理实体的记号称为标记。x m l 文档就是由标记和字符数据构成的。 两者都使用u n i c o d e ，都称为) ( m l 文本，即字符数据加标记就是x m l 文本。 为了区别字符数据，标记使用一种特殊字符，这种字符称为分隔符。最常见 的分隔符是小于号( “ ) 、或与号( “) 和分号( “；) 。 在h t m l 和基于s g m l 的语言中都使用了类似的语法。 ( 4 ) 文档类型 文档类型是根据其中的元素定义的。如果两个文档包含了完全不同的元素， 或虽然元素相同，但是它们以完全不同的方式组合在一起，那么它们很可能不属 于同一种文档类型。 如果是一个y d v l l 文档，它必须有某种由元素、属性和组件构成的结构。在为 文档创建样式表的时候，要根据这个结构知道其中的元素，根据元素类型名称知 道它们的含义，然后根据元素确定在何处显示。这种结构就是文档类型。 在) ( m l 中，可以使用文档类型定义( d t d ) 形式化文档类型，也可以用说明来 描述这种文档的结构，但使用d t d 可以让) ( m l 文档的书写者更专注于自己的工作。 天津师范大学硕+ 学位论文 2 2 全文文本压缩技术 数据压缩最初是作为信息研究中的一个重要课题，在信息论中被称为信源 编码。但近年来，数据压缩已不仅局限于编码方法的研究和讨论，这门技术已经 成为独立的体系。它主要研究数据的表示、传输和转换方法，目的是减少数据所 占的存储空间。 数据压缩可以被分成可逆压缩和不可逆压缩。其中可逆压缩也叫做无失真、 无差错编码( e r r o rf r e ec o d i n g ) 或无噪声( n o i s e l e s s ) 编码。在不同的专业 的其他文献中还采用了另外一些术语，如冗余度压缩( r e d u n d a n c yr e d u c t i o n ) 。 在不可逆压缩中压缩就是有失真( l o s s y ) 编码，信息论中称为熵压缩( e n t r o p y c o m p r e s s i o n ) 。 目前，根据不同的应用领域，数据压缩技术的研究主要包括如下几个分支： ( 1 ) 图形、图像压缩技术； ( 2 ) 数据库压缩技术； ( 3 ) 声音、视频信号压缩和传输信号的压缩： ( 4 ) 文本压缩技术； 其中，文本压缩可以说是最基本的一种文件压缩，其目的是要减少文件所 占的存储空间，这种压缩要求在压缩过程中不丢失信息，即要求压缩了的文件在 解压缩之后，内容与压缩前的文件完全相同。本文中的压缩即是属于这类压缩。 近年来，随着文本信息的飞速增长，文本压缩技术仍然是数据压缩领域一个重要 分支。 全文文本，是指由若干个只包含文本信息的文档聚集在一起而形成的文件 合集，近年来，随着数字图书馆、办公自动化系统及文本数据库等信息检索系统 的大量使用，可供人们查阅的文本信息量正在飞速增长着。 传统的信息检索系统并没有使用压缩技术，因为经过压缩后的文本并不能 迅速的存取。这也是纯x m l 数据库中对于x m l 文件处理面临的一个问题。目前对于 这项技术的研究就是为了使得整个文本数据减少占用的空间，并且在查询直接在 压缩过的文本上进行，或者减少磁盘读写次数，从而提高解压缩速度。目前对于 文本文件的压缩和压缩后的查询处理基本上就是两种处理方式，第一种就是先解 压缩文件，然后进行查询，当然速度上就会很慢，虽然减少了文件占用的磁盘空 天津师范大学硕士学位论文 间，但是对于数据库管理系统的响应时间的要求，显然是不能满足的；另一种办 法就是采用查询串重写的方式处理，对于查询的关键字进行和文本文件算法相同 的压缩处理，然后使用压缩过的字符串去和压缩文件进行匹配，把匹配的结果解 压缩返回应用，作为查询结果。第二种方法虽然可行，但是对于x m l 文件的半结 构化的特点，显然就缺乏处理办法了，所以目前对于x m l 数据库中压缩文件的处 理，仍然是个难题。 任何一种文本压缩方法都包括两个方面的内容：压缩模型以及编码方法。目 前的压缩方法绝大多数是自适应模型的，即允许在遍历一遍文本后就完成压缩， 并且不需要在解压缩过程中独立地使用任何参数( 如有关文本的分布的统计数 据) 。这种方法虽然有很好的压缩和解压缩性能，但由于使用自适应模型的编码 方法只能在文本的开始处，而不能在文本的任何位置进行解压缩，这样就降低了 解压缩速度。所以在使用自然语言的全文本数据库的检索系统中，基于自适应模 型的编码技术并不是最有效的压缩技术。 那么能否把大型的全文本数据库划分成多个小块，并在每个小块上使用自适 应压缩技术进行压缩呢? 使用自适应模型的压缩方法，需要在得到文本的信息分 布之前处理完一些数据以使得压缩更高效。一些学者研究后，认为得到理想的压 缩比率，在实际应用中得出这些数据至少应在1 0 兆字节以上，对于直接存取这 是一个相当大并且可行性不高的数字。所以这种分块的想法也是不可行的。 如果不考虑自适应模型，对于基于数据压缩的信息检索，可以考虑使用静态 模型技术来压缩文本数据库。使用这种模型，对于文本数据库首先要假定一个有 关它的平均分布。然而这种模型是不灵活的，并且可能带来比较差的压缩比率， 因为很难找到一种对于大多数数据分布都能带来好的压缩比率的静态模型。 另一种模型是静态模型技术，但使用这种模型来压缩文本数据，可能带来 比较差的压缩比率。还有一种模型是半静态模型，对于全文本数据，半静态模型 技术为每个标识符产生固定的编码来压缩数据，虽然这样需要多遍历一遍文本， 但是可以取得较高的压缩比，也使得在压缩过的文本文件上进行查找或者提高查 询效率成为可能，所以目前适用于全文本数据检索。文本也正是考虑了这个因素， 所以也采用了这种模型对x m l 文件进行压缩处理。 9 天津师范大学硕七学位论文 2 3 算术编码 压缩技术有三个重要指标，一是压缩前后所需的信息存储量之比要大；二是 实现压缩的算法要简单，压缩、解压速度快，尽可能做到实时压缩和解压；三是 恢复效果要好。按照香农( s h a n n o n ) 的理论，信源s 的熵定义为h ( s ) = p i * l 0 9 2 ( 1 p i ) ，其中p i 是符号s i 在s 中出现的概率；l 0 9 2 , ( 1 p i ) 表示包含在 s i 中的信息量，也就是编码s i 所需要的位数。 熵作为理论上的平均信息量，即编码一个信源符号平均所需的二进制位数， 在实际的压缩编码中的码率很难达到熵值，不过熵可以作为衡量一种压缩算法的 压缩比好坏的标准，码率越接近熵值，压缩比越高。 由于在很多场合，开始时不知道要编码数据的统计特性，也不一定允许事先 知道它们的统计特性，因此算术编码在不考虑信源统计特性的情况下，只监视一 小段时间内码出现的概率，不管统计是平稳的或非平稳的，编码的码率总能趋近 于信源的熵值。算术编码是无损压缩的一种，在算术编码中，消息用0 和l 之间 的实数编码，该编码用到两个基本的参数；符号的概率和它的编码间隔，信源符 号的概率决定了压缩编码的效率，也决定了编码过程中信源符号的间隔，而这些 间隔包含在o 和1 之间，编码过程中的间隔决定了符号压缩后的输出。 2 4 基于x m l 的索引技术 一般对x m l 文档进行查询都是将其解析为d o m 树来进行处理。x i v l l 查询最简 单的方法是，根据路径条件深度优先遍历所有的节点，寻找符合谓词条件的原子 对象，这种方法称为自顶向下的查询方法。一般这种方法都是对d o m 树进行遍历， 但是对多个较大的x m l 文档组成的大量x m l 数据库，这种方法将会占用超大内存 并且查询响应时间非常长，令查询用户无法接受。d o m 遍历方法的查询时间是随 着测试数据量的增大而类指数增长，而使用索引后的查询方法基本上是呈线性增 长。因此，x m l 数据库的索引技术对x m l 数据查询处理起着至关重要的作用，如 果没有索引的支持将会带来巨大的i 0 代价和语义方面的限制。 对结构化的文档使用索引来检索已经进行了好多年，并且涉及很多领域，如 信息检索、数据库、x m l 。s h a n mu g a s u n d a r a mj 等提出对于不同的路径表示法 进行不同的s q l 转换，z h a n gc h u n 等提出建立i n v e r t e d1 i s t 来支持内容检索 l o 天沣师范大学硕七学位论文 乜1 。并且已经产生了好多种可行的索引技术，如树匹配( t r e em a t c h i n g ) 口钔，路 径索引( p a t hi n d e x ) 嵋m 3 ，串索引( s t r i n gi n d e x ) ，本体索引( o n t o l o g yi n d e x ) 口1 等。其中s t a n f o r d 大学的l o r e ( l i g h t w e i g h to b j e c t r e p o s i t o r y ) 嘲就是一个著 名的x m l 数据系统，他们在对半结构化数据进行多年研究的基础上，实现了用关 系数据库存储、查询和表示x m l 数据的一整套解决方法，该系统中的d a t a g u i d e s 是专门为半结构化数据设计的索引技术，其中包括v a l u ei n d e x ，l a b l e i n d e x ，e d g e l n d e x 和p a t hi n d e x 等4 种不同的索引结构。这些索引技术大部分 都使用了基于正则路径表达式的查询语言，适用范围较小，而且实现复杂，索引 文件量非常大。 下面介绍下几类近年来出现的索引： 1 ) l o r e 系统针对自身的o e m 结构和d a t a g u i d e 结构建立了4 种不同的索引， 用来加快对x m l 的查询速度：v i n d e x ( v a l u ei n d e x ) 支持查找有给定边并满足 某个谓词的所有原子对象；l i n d e x ( l a b e li n d e x ) 支持查找所有给定边的父对 象；e i n d e x ( e d g ei n d e x ) 支持查找所有由给定标签连接的父子对象对；p i n d e x ( p a t hi n d e x ) 支持查找通过给定的路径能找到的所有对象。这类索引在使用时 更多的依靠x m l s c h e m a ，限制条件比较复杂。 2 ) 元素索引( e l e m e n ti n d e x ) 、属性索引( a t t i b u t ei n d e x ) 、结构索引( s t r u c t i n d e x ) ：这三种索引分别用来支持3 种必须的功能。通过元素索引可以找到所有 具有相同元素名字的元素实例；通过属性索引可以找到具有相同属性名字的属性 实例；结构索引用来查找某一给定元素的父元素和子元素。在这种设计中存在如 下不足之处，基于这种设计提出的快速确定x m l 数据层次结构中的祖先、子孙关 系的编号机制，可以很容易从父亲、孩子关系表中演化出祖先、子孙关系，但是 很难从一般的祖先、子孙关系表中区分出父亲、孩子关系，因此不容易建立结构 索引。所以这种方法不能支持路径中父子关系的元素之间的连接操作，也就无法 支持元素和属性之间的连接操作。 3 ) 父子对索引( p n a m ei n d e x ) ，属性值索引( a t t r i b u t ev a l u ei n d e x ) 、 引用索引( r e f e r e n c ei n d e x ) 、全文索引( e l e m e n t t e x ti n d e x ) 。查询时候通过 这些索引而不是直接遍历d o m 树本身，可以大大提高查询效率，但是这也就曾加 天津师范火学硕十学位论文 了索引本身的体积，查询的时候也要建立d o m 树和相应的索引结构，也客观增加 了查询准备的时问代价。 另外还有一些常见的索引结构，下面也向大家做一个简单介绍。 结构索引，构建一个结构索引的主要思想就是用最少的节点和边表示树模型 中所有的路径信息。先在树模型中把同一层的等价节点联合起来，为每个索引节 点定义n 定义范围函数e x t ( n ) ，如果e x t ( a ) 中的某节点到e x t ( b ) 的某节点有一 条边，在结构索引中把节点a 和节点b 之间加一条边。通过上面的步骤可知结构 索引是通过划分数据节点建构的。索引中的每个节点a 都有一个唯一标识符 i d ( a ) 。结构索引索引的仅仅是x m l 文档的结构部分，忽略了文本节点。 倒排表在x m l 文档系统库中，倒排表是在标记名和关键词上构造的，它可有 效支持x m l 文档中关键词的搜索。 定义1 对每个元素节点n 和标记t ，在倒排表中有相应的词条以五元组形式 出现： ，我们把s t a r t 标识为n s t a r t 。其 它的域类似。d o c i d 表示文档唯一标识符，i n d e x i d 表示唯一索引i d 号，l e v e l 表示树节点的深度。 定义2 对每个文本节点的l a b e lk ，在相应的倒排表中的词条以下面的四元 组形式出现： 。 推论1 对于每个元素节点n ，有n s t a r t n e n d 。 推论2 如果元素节点n l 是元素节点n 2 的祖先，那么就有下面的关系： n 1 s t a r t n 2 s t a r t n 2 e n d n 1 e n d 推论3 如果元素节点n 1 是文本节点n 2 的祖先，那么就有下面的关系： n 1 s t a r t n 2 s t a r t n 1 e n d 推论4 如果元素节点n 1 和n 2 是兄弟节点，并且o r d ( n 1 ) o r d ( n 2 ) ，有 n 1 e n d n 2 s t a r t 这对n 1 节点和n 2 节点是文本节点的情况同样适用。可以用连 接倒排表的方法查询路径表达式阳1 。为了更有效地进行连接，需要用到附加索引。 a h a l v e r s o n n 州等人提出了在查询过程中用b 树跳过不参与连接的元素节点，其 中涉及倒排表连接的算法称为i v l 。 综上是基于x m l 文档的索引技术的基本介绍，本文的工作也是参考了上面的 结构和索引策略而设计的，尽量的避免了它们的缺点，集合它们的优点。从下一 天津师范大学硕十学位论文 章开始，就具体开始介绍文本的x m l 文件压缩存储的策略和查询响应及索引建立 策略。 小结，本章介绍了x m l 文档的概念和特点，以及目前的文本压缩技术和基于 x m l 文档的索引技术，这些都是本文工作的相关知识，有助于理解本文的工作。 天津师范人学硕十学位论文 第三章基于b w t b 勺x m l 文件压缩和存储策略 3 1 存储策略和查询响应整体流程图示及解释 本文的工作是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 文件内容的自索引结构，这样 就有利于应用程序进行数据查询，尤其在进行全文搜索时，减少了查询的响应时 间，下面总体说明一下具体的工作流程。 一图胜千言，这个是整个存储策略的总体过程图。 图3 1 存储流程图 1 4 天津师范大学硕士学位论文 上图中的圆圈二号步骤就是本文的压缩算法，当然自索引的特点也是在压缩 和解压缩的过程中体现出来的。 先不具体解释压缩算法，先解释一下总体的工作流程。首先是解析，使用的 是第三方的解析库( x e r c e s 库) 来解析的x m l 文件，第二章中对x m l 文件已经 做了很详细的介绍，这里就不多说了。总之经过解析以后的x m l 文件的标签和标 签之间的内容会被区分开，并且存放在不同的文件里，至于存放的文件的结构， 在后面的内容里会详细介绍，这样做的目的是使得x m l 文件保持它的基本结构不 被破坏。 然后压缩和索引的部分是每一对儿标签内部的全部文本内容，这里面有一个 细节需要说明下，就是如果一对儿标签之间的文本内容的信息量不大，那么本文 的处理方法是不对其进行压缩处理，而是当作一个标签节点同样对待，这样做的 目的是减少处理文件的代价。最后，将压缩后的结果存储到对应的文件的对应位 置。至此总体压缩和存储过程的操作就结束了。 下面是压缩过程的图示，即图3 1 中部分的操作过程。 r l b 哈 e w 夫 编 t 曼 码 变编 压 缩 换码 图3 - 2 压缩流程图 这个就是压缩算法的具体过程，其中第一步操作采用的b w t 变换方式后面会 具体介绍，第二部的哈夫曼编码是可选操作，读者也可以尝试采取不同的编码方 式来尝试取得更高的压缩比和压缩速度，本文只实现了字符串的哈夫曼编码，最 后的r l e 压缩算法虽然比较简单，但是经过前面的处理，已经可以取得比较好的 压缩效果了，本文在后面也给出了r l e 算法的解释。 天津师范大学硕士学位论文 下面来看看查询响应的流程图。 查询关键字的输入 1r 到存储标签的文件中去查找是否有 匹配的标签，若有，记录标签节点 的编号 1 r 从存储内容的文件中按编号提取对 应标签节点的内容，进行解压缩，在 解压缩的过程中生成这部分所有内 容的全文索引信息 ， 将解压缩结果和索引信息一并返回 给应用程序 图3 - 3 查询响应过程 图3 3 所示的就是本文的响应查询的总体工作流程。其中我要说明的就是在 解压的过程中才提取出索引结构所以系统就不需要额外再保存文本内容的全文 索引结构了，节省了存储空间，压缩存储之前也不需要将索引结构提前提取出来 了，这是自索引结构的一个优势，即文件本身带有索引结构。 下面具体说明下上图中中的过程，见图示3 - 4 所示。 下面具体解释一下途中的索引生成，即压缩后的文件是如何具有自索引结构 的。因为在b w t 逆变换的过程中，程序是可以顺便提取出文本的后缀集合的，所 以作为索引结构的后缀数组，并不是普通的在压缩前就从原文本直接生成好存在 磁盘上作为索引的，而是在解压缩的过程中同时生成了全文文本所有的后缀和后 缀数组作为索引的，这也正是本文工作中的最大特点，即使压缩后的x m l 文件具 有自索引。其具体的算法在下面的文章中将详细介绍。 1 6 天津师范大学硕士学位论文 i 逆r l e 解压过程，还原l i 到b w t 变换后的结果i r ib w t 逆过程，同时生成l i 文本的所有后缀l ii 1r i 利用后缀生成后缀数组i 图3 - 4 解压缩及索引生成的具体过程 3 2x m l 压缩后文件存储结构设计 本文对解析后的x m l 文件的存放的结构是这样设计的，在逻辑上，x m l 文件 仍然以一棵树的结构来存在，这棵树类似于它的d o m 树的模型，这样做的目的也 是保持x m l 文件的结构不变，方便了后面的查询。 具体的实现结构，本文注意到前文提到的基于x m l 的索引中的一种叫父子对 索引的结构，又以经典的存储树的数据结构双亲表为基础，给出了存储文件的结 构。对于x m l 文件，需要有两个文件对它进行存储，其中一个存储的主要是x m l 文件的结构信息，各个节点的信息和各个节点之间的层次关系；另一个文件则是 对大信息量文本内容节点中的文本进行压缩后的结果进行存放。 现具体描述如下，对于某一个x m l 文件来说，第一个文件的结构描述应该是 这样的： 每个元素的结构 s t r u c tp t n o d e 天津师范火学硕十学位论文 e l e m e n t t y p ed a t a ； 数据( 就是x m l 介绍部分提到的d o m e l e m e n t i n tp a r e n t ： ) p t n o d e ： 整棵树的结构 或者其他类型的对象) 父节点的下标 s t r u c t p t n o d en o d e s m a x s i z e ：结点数组 i n tr ，n ： 根的下标和结点数 ) 下面给出第一个文件结构的图示： or- 1 1a o 2 b ( t ) o 3co 4 d ( t ) 1 5 e ( t ) 1 6f3 7 g ( t ) 6 8 h ( t ) 6 9 k ( t ) 6 图3 - 5 外部文件组织结构a 上图表示的是第一个外部文件的组织结构，其实就是刚才提到的“双亲表” 的结构，因为x m l 文件在被x e r c e s 解析到树结构里以后，结点就只有两种( 不考 虑跟结点或者说把根结点也考虑成一个e l e m e n t 结点) ，所以我们的第一个文件 就包含所有的结点，但是，在解析然后写到文件上的过程中要做判断，如果当前 天津师范大学硕十学位论文 结点是一个标签结点的话，那么就把标签的内容按照d o m d o c u m e n t 类的数据组织 方式写到文件上，然后写入对应结点的父结点的序号；如果判断当前结点是个文 本类型( d o m t e x t ) 的话，那么就把数据域做上标注，即图中的“t ”标志，说明 这个结点是个文本结点，把这个结点父结点的序号写入这个文件，而把文本内容 写入对应的另一个文件( 写入之前就要经过压缩算法压缩了) 。 下面看看文本内容存放的文件的结构，这个结构其实是“双亲表 的相反结 构，也就是父结点的序号写在前面，后面跟着真正的经过压缩的文本字符串，而 且，顺序是按照父结点的序号排好的，这也是个小小的自索引。因为只有文本节 点才会被写入到这个文件