（计算机软件与理论专业论文）xml关键字查询中最紧致片段问题的研究.pdf

山东大学硕士学位论文 摘要 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 ) 在w e b 服务、电子商务、数字图书馆 等诸多网络相关应用领域已经成为描述数据的事实上的标准。为了方便用户从 海量的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 关键字查询方式中最关键的问题是如何求解包含所有关键字的最紧 致片段，即s l c a ( s m a l l e s t l o w e s tc o m m o n a n c e s t o r s ) i 口- 题。目前已有许多求解 算法，包括s t a c k 、i l e 、s e 、u s a 和l i s a 等。i l e 和s e 在与s t a c k 的实验 对比中表现得效率更高，适合需要频繁i o 操作的海量x m l 查询，他们仅需要 顺序读取x m l 数据一遍；相比i l e 和s e ，l i s a 和l i s a1 i 在轻量级x m l 查 询中，无论是在理论分析上还是试验对比中都表现出了更好的性能。 然而，l i s a 不仅需要频繁扫描节点，而且需要引入集合交操作，耗费了大 量c p u 周期。l i s a l i 虽然在避免不必要扫描方面改进了l i s a 算法，但却使用 了自己独有的编码，不仅引入了编码映射，而且也使得该算法的通用性大大削 弱。这两种算法即便作为一种仅在内存中执行的算法，以上缺点也影响了查询 速度。 为此，本文提出一种轻量级的、使用x m l 关键字查询通用的d e w e y 编码 的新算法，n d t ( n - d i 、，i d e dt r a v e la l g o r i t h m ) ，即求解最紧致片段问题的n 分遍 山东大学硕士学位论文 历算法。该算法不仅消除了集合交操作，而且仅仅扫描所有节点至多一遍。 n d t 无论在理论分析上还是试验对比中，都表现出了较好的性能，是一种 可行的最紧致片段求解算法。作为一种新的x t v i , 关键字查询算法，n d t 具有 查询简便快捷、普通用户使用门槛较低、用户友好等的特点，但是也会存在查 准率相对于x m i , 结构查询算法较低的x m l 关键字查询的先天缺陷。 关键词：x m l 关键宇查询；d e w e y ；s l o e , ；n d t i i 山东大学硕士学位论文 a b s t r a c t x 池( e x t e n s i b l em a r k u pl a n g u a g e ) h a sb e c a m et h ef a c ts t a n d a r df o rd e s c r i b i n g d a t ai nt h ef i e l do fw e bs e r v i c e ，e l e c t r o n i cc o m m e r c ee t c i no r d e rt oh e l pu s e r st o r e t r i e v ei n f o r m a t i o nm e yn e e df r o mo v e d a r g ea m o u n to fx m ld o c u m e n t s ，m a n y a l g o r i t h m sh a v eb e e nr a i s e d r e s e a r c ho nx m lq u e r ym a k e ss e n s e f r o mt h a tp o i n to f v i e v 忆 a c c o r d i n gt or e t r i e v a lb a s i so ft h o s em e t h o d s ，t h i sp a p e rd i v i d e sx m l r e t r i e v a l a l g o r i t h m s i n t ot w oc a t e g o r i e s ，x m ls t r u c t m a lr e t r i e v a la n dx m lk e y w o r d r e t r i e v a l t h ef o r m e ro n et a k e sa d v a n t a g eo fr e g u l a re x p r e s s i o n sa st r a d i t i o n a l q u e r i e sa n dc o u l de x p o s eu s e r s sn e e de a s i l y t h el a t t e ro n e i sm o r el i k ei n f o r m a t i o n r e t r i e v a la n dt h eo n l yi n p u t sn e e d e df r o mt h en s e r sa r ek e y w o r d s x m ls t r u c t u r a lr e t r i e v a lr e t u r n sa c c u _ r a t er e s u l t sju s ta c c o r d i n gt oe x p r e s s i o n s i n p u t h o w e v e r , i ta l s oq u a l i f i e st h eu s e r sn o to n l yo nt h eq u e r yl a n g u a g eb u ta l s oo n t h es t r u c t u r eo fx m ld o c u m e n t s t h o s eq u a l i f i c a t i o n sa r ei m p o s s i b l ef o rm o s to ft h e u s e r s ，s of r o mt h ea s p e c to ff r e e i n gl a s e r s ，i ti st h ex m lk e y w o r dr e t r i e v a lt h a tw i l l h a v eab r i g h tf u t u r e x m l k e y w o r dr e t r i e v a lh a sab a s i cp r o b l e m w h i c hi sh o wt oc o m p u t es m a l l e s t l o w e s tc o m m o na n c e s t o r s ( s l c a ) m a n yr e s e a r c h e r sh a v eb e e nc o n t r i b u t i n go n t h a tp r o b l e ma n dr a i s e ds e v e r a la l g o r i t h m s ，l i k es t a c k ，i l e ，s e ，l i s aa n dl i s ai i i l ea n ds ep e r f o r mb e t t e rt h a ns t a c ka n a l y t i c a l l ya n de x p e r i m e n t a l l y t h e yd e a l w i t hx m ld a t ab yr e a d i n gs e q u e n t l y i nl i g h tw e i g h ts c a l e ，l i s aa n dl i s ai ih a v e t h e i ro w np r e d o m i n a n c e h o w e v e r , l i s an o to n l ys c a n sa l ln o d e sm o r et h a no n c e ，b u ta l s oi n t r o d u c e sm a n y j o i no p e r a t i o n sb e t w e e ns e t s t h e ya r el i s a sd i s a d v a n t a g e s l i s a i m p r o v e sb y u s i n gf i r s to r d e rd e w e yc o d ew h i c hi sd i f f e r e n tt od e w e yc o d e t h a ti sw i d e | yu s e d f i r s to r d e rd e w e y , 勰ap r i v a t ec o d ef o rl i s a ，n e e d sam a p p i n gs c h e m ak e p ti n m e m o m i l l 山东大学硕士学位论文 t h i sp a p e rp r e s e n t san e ws l c as o l v i n ga l g o r i t h m , n d i v i d e dt r a v e la l g o r i t h m f n o t ) n d ti sad e w e y b a s e dm e t h o dw i t h o u tj o i no p e r a t i o n sa n de x t r ad a t a s 订u c t u r e s n d th a sa n o t h e ra d v a n t a g et h a ti to n l ys c a n sa l lt h ed e w e yc o d e sa tm o s t o n c ei ni t sw o r s ts i t u a t i o n n d t p e r f o r m se f f e c t i v e l ya n a l y t i c a l l ya n de x p e r i m e n t a l l y i ti sav i a b l es l c a s o l v i n ga l g o r i t h m a san e wx m lk e y w o r dr e t r i e v a lm e t h o d , n d tc o u l db eu s e d e a s i l ya si td e a l sw i 血x m ld a t aw i n ln oe x t r aq u a l i f i c a t i o n st ou s e r s h o w e v e r , l i k e o t h e rx m lk e y w o r dr e t r i e v a l m e t h o d s ，i tp e r f o r m sw o r s et h a nm o s tx m l s t r u a u r a lr e t r i e v a lm e t h o d si np r e c i s i o nr a t i oa si th a sab i r t hd e f e c tt h a tn e a r l ya l l x m l k e y w o r dr e t r i e v a lm e t h o d sn e v e rc o n s i d e rs t r u c t u r a li n f o r m a t i o n k e y w o r d ：x i i lk e y w o r dr e t rie v ai ：d e w e y ；s l c a ；n d t i v 原创性声明和关于论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：蕴瘤 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：j 虹导师签枷期：出 山东大学硕士学位论文 第一章绪论 1 1 课题研究背景 ( e x t e n s i b l em a r k u pl a n g u a g e ) ，即可扩展的标记语言，是一种半结构 化的标记语言。它需要自行定义标签，具有自描述性。其设计的初衷就是为网 络环境下各种应用提供便捷的数据交换方式。x m l 是受限的s g m l ( s t a n d a r d g e n e r a l i z e dm a r k u pl a n g u a g e ) 的实现。【l 】 随着网络应用的快速发展，x m l 数据已经大量存在于当前的信息社会，尤 其是随着电子商务、w e b 服务、数字图书馆等应用理念的进一步发展，使得x m l 格式的数据成为当前主流的数据形式【2 】。因此，如何对大量的x m l 数据进行 有效的管理，就成为目前数据库研究领域的热点【3 】。 对x m l 数据的管理，主要涉及数据存储和查询两个方面的内容。无论是 纯x m l 数据库系统( n a t i v ex m ld b m s ) 【4 】还是x m l 使能数据库系统 ( x m l e n a b l e dd b m s ) 【4 】都在上层提供了查询机制。针对当前涌现的大量x m l 数据查询算法，按照查询模式描述的不同，本文参照已有的分类方法，将目前 x m l 查询分为两大类，即x m l 结构查询( x m ls t r u c t u r a lr e t r i e v a l ) 和x m l 关 键字查询( x m lk e y w o r dr e t r i e v a 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 最紧 致片段的问题，在实际研究中，研究者往往将这个问题转化为s l c a ( s m a l l e s t l o w e s tc o m m o n a n c e s t o r s ) f 口- 题 5 】。 目前求解s l c a 问题的算法很多，本文在详细描述和分析了这些算法后， 山东大学硕士学位论文 提出了自己的解决最紧致片段问题的新思路，即n 分遍历算法( n - d i v i d e dt r a v e l a l g o r i t h m , n o t ) 【6 1 ，并进行了详细的理论论述与试验分析对比，证实了该算法 的可行性和高效性。 1 2x m l 查询研究现状 1 2 1x l 结构查询研究现状 x m l 结构查询模式下的算法偏向于传统的结构化的查询方法，即采用了正 则表达式【7 ，8 】的描述形式。它首先定义了精确的查询描述语言，用户借助查询 描述语言来描述自己所感兴趣的数据，x m l 结构查询引擎返回按照用户需求 的形式化描述而检索到的x m l 片段。 x m l 结构查询模式不仅涉及到了内容的相似性，而且要求查询结果在结 构上也要和查询条件相匹配。这种查询模式下的算法，定义了严格的正则语法 机制来确保描述的严密性。从早期的l o r e l 【9 1 、x q l 【1 0 、x m l q l 【1 1 、 x m l g l 1 2 等，到被w o r l dw j d ew e bc o n s o r t i u m ( w 3 c ) 规范化的) p a t h 【1 3 】 和x q u e r y 【1 4 】都具备上述特征。 以x p a t h 为例， 该语言同时也具有在x m l 文档中通过元素和属性进行 导航的特性，通过捕捉x m l 数据单元间的结构关系和内容，为x m l 数据周游 提供了保证，成为x q u e r y 等x m l 操纵语言的基础。 至于x q u e r y ，该语言起源于q u i l t 【1 5 ，以x p a t h 为基础，定义了线性路 径表达式、分支路径表达式和路径树表达式三个层次上的查询。路径树包含了 前面两个层次，也定义了x m l 结构查询中最重要的小枝( t v d g ) 的概念，即具有 多个叶节点的树结构形式的路径树查询形式。 t w i g 问题是x m l 结构查询中实际需要解决的问题之一。目前t w i g 形式的 求解过程可以归纳为如下步骤： 1 将待查询的模式分解为父亲孩子、祖先- 子孙二元结构关系： 2 从x m l 数据库中寻找所有满足结构关系的连接算法和上述结构关系的 节点集合； 3 将中间结果合并为满足全部结构关系的最终结果。 2 山东大学硕士学位论文 mnmmm !mm 。皇曼皇曼鼍曼鼍曼鼍曼曼曼曼曼曼量曼曼曼曼曼蔓! 皇曼曼曼皇曼皇曼量 从t 、i g 求解思想中可以看出，最终的求解速度主要取决于结构连接算法的 效率。如何对结构连接进行求解，并使之最大限度的优化，便成为目前已有的 众多t 、i g 求解算法的目标。 m p m g ( m d t i p r e d i c a t em e r g ej o i n ) 【1 6 1 ，即多谓词归并连接算法，参照 关系数据库系统如何有效实现包含连接算法而实现的。它对每一个外表中的元 素，从内表中搜索需要扫描的第一个元组，即从扫描始点开始扫描，检索满足 包含条件的元组。每次扫描可以从上一次扫描的扫描始点开始扫描，从而跳过 了无需扫描的节点，加速了连接算法。重叠扫描意味着缓存的使用可以提高扫 描的效率。 多谓词归并连接算法通过内外表在算法的迭代中的转换和适当调整，可以 使得输出结果按照祖先有序或者按照后代有序。t r e e m e r g e a n c 和 t r e e m e r g e d e c 【1 7 】分别实现了上述调整。 鉴于利用内外表扫描算法忽略外表本身的父子或者祖孙关系，从而造成重 复扫描的弊端，通过使用栈来实现的新的归并连接算法在文献【1 7 】中被提了出 来。具体方法为将外表的当前元素压入栈底，若此时外表待扫描的第一个元素 为当前栈顶元素的子孙，则继续压栈，直到下一个元素不与栈顶元素存在祖先 和子孙关系为止。使用当前栈顶元素对内表进行扫描，如进行m p m g j n 的连 接，对于符合条件的内表元素，同样也适合于栈底所有元素。于是，不仅输出 栈顶元素与内表当前元素组成的元素对，而且也同时输出栈中其他元素与当前 内表元素组成的元素对。s t a c k t r e e d e s c 和s t a c k t r e e a n c 算法分别实现了查 询结果的后代有序输出和祖先有序输出。 s t a c k t r e e 算法的栈实际起到了缓存的作用，并加速了连接。但是，仍然存 在许多节点，参与了连接却并没有符合连接条件的输出。鉴于以上情况，文献 【1 8 】提出了a n c e s cb + 算法。该算法使用b + 树索引来跳过不参与连接的后续 节点的情况，直接定位到下一个需要做连接的节点，从而加速了连接的速度。 该算法局限性也在于，索引的建立时间和查询时间必须要小于计算可以被跳过 的节点从而节省的时间。 关系数据库查询中广泛的使用了索引，而a n cd e s eb + 算法的加速也正是 归功于x m l 数据索引的引入。而且，x m l 数据索引也有自己的许多特点，如， 山东大学硕士学位论文 编码本身就可以看作是一种索引形式，该索引包含了可以替代原始x m l 数据 的所有信息，关于索引的建立和操作等更进一步的专门探讨，不属于本文论述 范围，可以参阅文献 1 9 】来做进一步的研究。 以上结构连接算法总体归结起来就是利用编码的性质来判断两个节点是否 满足父子关系或者祖先与后代关系，从而实现x m l 查询处理。具体方法是每 个节点对应的编码集合分别作为内表和外表进行计算。对于一个复杂的t w i g ， 产生了大量的父亲孩子、祖先子孙二元结构关系，计算中间结果数量多，处 理繁杂，影响了整体计算的效率。 除了上述使用中间结果来进行t w i g 求解的方法以外，许多研究者通过对 t w i g 的特点的观察，还提出了许多t w i g 整体计算的新方法。整体t w i g 查询中， t w i g 的整体计算减少了中间结果的生成和再计算，提高了效率，是目前应用最 普遍的x m l 查询算法之- - 2 0 】。 h p j ( h o l i s t i cp a t hj o i n ) 【2 1 ，即完整路径连接，首先依照t w i g 查询模式设 置相应的堆栈结构，每个堆栈对应t w i g 查询模式中相应的节点，堆栈的排列次 序与前序遍历t w i g 查询模式时的节点次序相同；然后，顺序地扫描x m l 数据 片段，将扫描过程中遇到的对应于t w i g 查询模式标签的节点顺序地压入对应的 堆栈，当遇到对应于t w i g 查询模式叶节点标签的节点时，回溯经过的相应堆栈， 这样，符合t w i g 查询模式结构关系的节点序列即为满足查询请求的结果。 利用整体t w i g 查询的思路，p a t h s t a c k 算法解决了不含分支的t w i g 模式查 询任务，而t w i g s t a c k 实现了完整的t w i g 模式查询的任务。许多细节的工作都 围绕如何完善h p j 来展开，例如，文献 2 0 1 针对t w i g 查询模式的包含通配符“” 的情况展开了探讨。 类似于a n c _ d e s c _ b + 对s t a c k - t r e e 算法改进原理，t s g e n e r i c + 【2 4 算法对 p a t h s t a c k 和t w i g s t a e k 算法，利用索引技术提高了它们的性能。具体做法是通 过引入索引来加速判断下一个需要进行连接运算的节点，即跳过不参与连接的 节点。避免不必要的连接加速了t w i g 整体计算，但是也要确保索引的建立时间 和查询时间必须要小于计算可以被跳过的节点而节省的时间。 至于其他t w i g 整体查询模式，文献【2 2 】提出了通过特征向量矩阵来描述和 匹配的方法，而文献【2 3 】使用有限状态自动机来完成符合t w i g 查询模式的集合 4 山东大学硕士学位论文 皇曼曼曼曼曼曼皇毫i - - - - - - - - - - 鼍皇曼曼曼皇曼皇曼曼曼曼曼! 曼皇曼! ! 鼍量皇曼皇量曼曼 的筛选。 以上所列举的众多连接计算算法或者t w i g 整体计算思想有效的支持了包含 以x p a t h 为代表的众多x m l 结构查询的需要。这些算法目前普遍使用的是区 间编码。区间编码方案会在后面章节展开叙述。 1 2 2x 札关键字查询研究现状 上文中所提到的所有x m l 结构查询模式，不仅考虑了待查询的内容，而 且也需要考虑相应的结构信息，再加上查询语言的语法等机制，无疑都对查询 用户提出了更高的要求。站在多数用户的立场上，让他们去了解查询语言和目 标x m l 数据的树结构是不切实际的。为了解决这一矛盾，在x m l 关键字查询 领域，许多学者做了大量研究。 文献 2 4 】提出了解决最紧致片段问题的d e w e yi n v e r t e dl i s t ( d i l ) 方法，即 基于d e w e y 码的倒排列表方法。由于其利用栈进行操作，只考虑具有最长公共 前缀的d e w e y 码，排除了s l c a 节点祖先节点和父亲节点的干扰，通过标记来 识别当前的最长公共前缀( l o w e s tc o m m o na n c e s t o r s ，l c a ) ，最终判断求解最紧 致片段。该算法基于栈来进行计算，所以被称作s t a c k 算法。 i l e ，( i n d e x e dl o o k u pe a g e r a l g o r i t h m ) 【5 】使用b + 树来实现其提出的左匹 配和右匹配算法，通过一个节点与一个集合的匹配运算，利用递归扩展到多个 集合的间的匹配运算，从而实现了快速的最紧致片段的查找。该算法依据的基 本思想是，一个节点与其在树中左匹配节点的l c a 和该节点与其在树中右匹配 节点的l c a 的最小者为s l c a ，即最紧致片段节点。针对b + 索引的查找代价 要高于顺序扫描的代价的情况，i l e 的变形算法s e ( s c a ne a g e r ) 被提了出来， 通过缓存指针用来加速左匹配和右匹配算法。 l i s a ，( l a y e r e di n t e r s e c t i o ns c a n , a l g o r i t h m ) 【2 5 】，即最小子树根节点问题的 分层算法，通过在获取了包含关键字的节点的编码集合后，通过计算对应于不 同关键字、不同层次的编码前缀集合的交集，可以得到对应不同层的s l c a 节 点。该算法是根据d e w e y 码的特点，从计算出的编码尾部位置，即所有关键字 集合最长编码中的最短者的倒数第二层，开始扫描，分层计算实现的。针对集 合交操作需要比较d e w e y 码前缀的弊端，l i s ai i 做了d e w e y 编码的扩展，减 【l i 东大学硕士学位论文 少了节点编码的扫描工作，从而提高了整体的性能。 鉴于绝大多数x m l 关键字查询仅针对“a n d 单个操作符的操作，文献 【4 2 】引入了在具有“o r 操作符的情况下，查询的具体方法。 最紧致片段问题的引入，相对于简单的l c a 求解，提高了x m l 关键字查 询的查准率，而为了在用户参与下更好的返回查询结果，在获取了所有包含给 定关键字的x m l 片段后，另一个重要的问题就是x m l 片段相似程度的计算【2 】。 由于x m l 片段具有结构信息，使得针对它的相似性计算可以考虑传统的相似 性计算方法，即可以通过用户对于结果的反馈来进一步计算符合用户意图的最 终结果。而对于结构信息的计算，很多算法引入了传统信息检索( i n f o r m a t i o n r e t r i e v a l ，瓜) 的思路。 在传统树编辑距离 2 6 】思想的启发下，文献【2 7 】把树节点的插入、删除和重 命名三种基本操作作为变换的基本度量，并以此作为判断条件来计算目标x m l 片段与待查询的x m l 片段之间的相似程度。该算法通过考虑片段之间的结构 信息，实现了x m l 片段的相似性度量。 利用传统的向量空间模型( r e o rs p a c em o d e l ，v s m ) 下的t f * i d f 计算方 法【2 8 】，文献 2 9 】实现了计算以叶节点为单元的计算模型，而文献【3 0 】等实现了 以t w i g 为单元的计算模型。 x m l 片段相似度计算在用户参与下增强了结果的查准率，是x m l 关键字 查询算法的扩展。文献【4 3 】通过引入语义信息，实现了提高查准率、增强用户 满意度的查询模型。 1 3 研究内容和主要工作 在众多的x m l 数据查询算法中，x m l 关键字查询最大限度的方便了用户， 因此，其应用前景是非常广泛的。本文针对x m l 关键字查询进行了研究，针对 其核心的s l c a 问题，即最紧致片段的求解问题，作了一番细致的论述和分析。 在借鉴已有相关算法的优点，摒弃他们诸多不足的基础上，提出了一种新的x m l 最紧致片段问题的求解方案，即n 分遍历算法( n - d i v i d e dt r a v e la l g o r i t h m ) ， 简称n d t 。 本文的主要工作体现在如下四个方面： 6 山东大学硕士学位论文 曼! 曼曼曼! 曼曼量曼皇曼皇量量曼曼 mmmmm 曼t 鼍曼鼍曼曼曼曼皇皇曼曼鼍曼曼曼曼量皇曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼 1 总结了x m l 数据查询的现状，并重点研究了x m l 关键字查询相关算 法，针对他们的优缺点进行了论述和分析。 2 提出了n 分求解x m l 最紧致片段节点的新思路，即n d t 算法，并将 其设计实现。 3 探讨了新思路的可行性，并在理论上证明了该算法的正确性，之后与 其他s l c a 求解算法做了理论上的分析和对比。 4 实现了l i s a ，将其与n d t ，在手工生成的数据集合和标准平台 址生成的数据集合上进行对比试验，并做了进一步的论述和分析。 1 4 本文的组织结构 本文是按照下面的结构组织的： 第一章分别概述了x m l 结构查询和x m l 关键字查询的现状，对部分算法做 了概述。 第二章首先对x m l 关键字查询中需要用到背景知识做了简短的介绍。而 后给出了x m l 关键字查询的基本思想。最后，对s t a c k 、皿、s e 、h s a 、u s a 算法的思想、实现和优缺点做了细致的论述和分析。 第三章在借鉴已有x m l 最紧致片段求解算法的基础上，提出了新的求解算 法，并对新算法的思想、实现做了详细描述。在完成新算法的正确性证明后， 进行了试验分析和对比。 第四章对全文进行了总结，分析了本文研究成果的理论意义和应用前景， 并指出了今后需要进一步研究的工作。 山东大学硕七学位论文 第二章x m l 关键字查询 x 池关键字查询解决了舭结构查询对普通用户使用门槛过高的问题， 便于研究人员生成对用户友好的信息检索系统，并因此而受到了极大的关注。 与普通文档上的关键字查询不同，v i i ，数据上关键字查询的目标通常不是整个 x 池文档，而是满足给定关键字的最紧致儿片段，即s l c a 片段。对这些 作为返回结果的x m l 片段进行相似度的计算，按照相似性进行排序，提高了 检索系统的查准率，可以更好的满足用户。 2 1 背景知识 2 1 1x m l 文档树结构 x m l ( e x t e n s i b l em a r k u pl a l l g u a g e ) 即可扩展标记语言，它与h t 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 pl a n g u a g e ，标准通用标记语言) 的子集。 x m l 是i n t e m e t 环境中跨平台的，依赖于内容的技术，是当前处理结构化文档 信息的有力工具，在w 曲服务、电子商务等诸多网络相关应用领域已被广泛使 用，成为目前网络数据交换和表示事实上的标准。 x m l 常被用作一种简单的数据存储语言，使用一系列易用的标记描述数 据，而这些标记可以用方便的方式建立。虽然x m l 文档占用的空间比二进制 数据占用的空间更多，但是x m l 表示极其简单，易于掌握和使用。 x m l 规范规定了x m l 数据必须满足的条件，其基本的形式是x m l 文档。 从逻辑上讲，一个x m l 文档通常由5 部分组成：声明、元素、注释、字符引 用和处理指令。这五部分统称为x m l 数据单元。x m l 数据内容的限制通常由 x m l 模式来描述。常用的模式包括d t d 【31 和x m ls c h e m a 3 2 ，3 3 。文档类型 定义d t d ( d o c u m e n tt y p ed e f i n i t i o n ) 是一种保证x _ m l 文档格式正确的有效方 法，可以通过比较x m l 文档和d t d 文件来看文档是否符合规范，元素和标签 使用是否正确。而x m ls c h e m a 具有比d t d 更强的描述性，能够更好的验证 龇文件逻辑结构的正确性。 山东大学硕士学位论文 ( n o 0 0 1 t h i n k i n gl nl a v a t i t l e b r u c ee c k e i a u t h e r 0 0 2 t h i n k i n g b r u c ee c k e l a u t h e r d i t e r a t u r e ( 1 - 省略具体b o o k 节点 - 一 图2 1l o l l 文档举例 一个符合x m l 模式的舳文档可以被抽象为一颗逻辑上的树形结构，于 是图2 1 中所表示的舳文档，可以使用图2 2 中所呈现的x 池文档树来表 不o n o l 0 0 1 l i b r a r y 八。k 、 i t h i n k i n g 西j - 么洌 ( 。2n k a u t h o r l b r 矗c e e ，c k e l 图2 2x 札文档的树结构 把x m l 文档以树结构的逻辑视图来处理，是d o m ( d o c u m e n to b j e c tm o d e l ) 【3 4 】的处理方法。d o m 是一种与浏览器，平台，语言无关的接口，使得你可 【l j 东大学硕士学位论文 以访问页面其他的标准组件，它以层次结构组织节点或信息片断的集合。这个 层次结构允许开发人员在树中导航寻找特定信息。分析x m l 文档结构通常需 要加载整个文档和构造层次结构，然后才能做其他操作。由于它是基于信息层 次的，因而d o m 被认为是基于树或基于对象的。 对于特别大的舳文档，使用d o m 方式解析和加载整个文档可能很慢 且很耗资源，因为d o m 方式需要在内存中构建整个的x m l 文档的存储数据 结构，因此迫切需要其他的解析方法，比如s i m p l ea p if o rx m l ( s a x ) 。s a x 适用于处理数据流，即随着数据的流动而依次处理数据。因此，s a x 在大数 据量处理中有其明显的优势，但是却不能像d o m 一样直接进行快速的定位或 者回溯等操作。 2 1 2 编码方案 当进行x m l 查询时，如果提前对x m l 文档中的节点或者边等结构进行编 码，以便能够根据编码来确定节点之间的结构关系，从而不再对整个的x m l 文档进行遍历，这将有效的提高查询的效率。因此，为了有效的支持x m l 查 询，特别是结构查询，编码方案被提出并广泛的使用。 当按照编码对象的不同而进行分类时，编码分为节点编码和结构编码。前 者针对不同的节点进行编码，而后者根据不同的分支或者片段进行编码。对节 点进行编码时，按照处理节点次序的不同，可以分为全局编码、局部编码和混 合编码。全局编码，例如前序编码，有效的标识了节点间的次序关系，但缺少 层次信息；局部编码，仅仅能区分每层的编码，不能处理祖先后代关系和父子 关系：混合编码融合前两种编码的优点，不仅能正确的区分前后关系，而且也 同时包含了节点的层次信息。目前多数使用的节点编码都是混合编码，例如位 向量编码、带层次信息的区间编码和d e w e y 编码等。 本节针对在结构查询和关键字查询中常使用的编码方案进行了描述和分 析。 2 1 2 1 区间编码 区间编码( i n t e r v a lc o d e ) 方法【3 5 】通过数字标识的区间来表示节点覆盖范 1 0 山东大学硕士学位论文 围，是目前所提出的编码方法中，在结构查询方面应用得最普遍的一种方案。 它赋给每个元素节点一个编码o 衄疗，e n d ) 。s t a r t 和e n d 分别表示节点在树中的 起始和结束位置。对任意两个不同的元素节点“和 ，它们的编码所覆盖的区 间不会部分相交，即材和 ，之间或者完全包含，或者不相交。图2 3 给出了前 文中x m l 文档的区间编码的示意图。 譬p ( 3 , 4 8 ) 伽，、咖k ( 4 - 11 ) ( 4 0 ，4 7 ) n 。嚣a u 血叮墨a u t h 叮 t 卫翌鼍 翌 图2 3x m l 文档的区域编码不例 为了支持实际数据中在包含多个文档的情况下，进行父子结构关系的判断， 将区间编码扩展为( d o c l d ，s t a r t ，e n d ，l e v e l ) ，d o c l d 是文档的标识，l e v e l 给出 了元素节点在树中的层次。对任意的两个元素节点材和，如果满足 i t d o c l d - = v d o c l d ，i t s t a r t v s t a r t v e n d 。由于树t 中的一个祖先节点u 在 先序遍历( 后序遍历) 中必然出现在它的后裔节点，之前( 之后) ，因此，节点和 ，是祖先与后裔关系，当且仅当以下关系成立：p r e ( u ) p r e ( v ) 且p o s t ( v ) p o s t ( u ) 。 因此，树t 中的任意两个节点之间的祖先和后裔之间的检测能够在两次比较中 完成。对于d i e t z 编码方案，p r e 或者p o s t 均能够作为节点的唯一标识。为了能 够在不连续的编码时候能够判断父亲和孩子节点的关系，可以引入l e v e l 来做树 1 2 山东大学硕士学位论文 层次判断。 2 1 2 2 前缀编码 前缀编码直接将一个节点的双亲节点的编码作为该节点编码的前缀。例如， 设x m l 树t 的一个节点4 的前缀编码为c ( ”) ，则节点4 的孩子节点，的编码 c ( v ) = c ( 1 ，) 拧。其中，刀是节点 ，在节点4 中所有孩子节点中的序号。 对于前缀编码，要判断一个节点1 ，是否是另外一个节点4 的后裔，只需要 判断字符串c ( “) 是否是字符串c ( v ) 的前缀。 前缀编码的一个重要性质是他们字典有序性：以节点，为根的子树中的任 意一个节点”，它的前缀编码c ( 砂大于( 小于) 它的左兄弟子树( 右兄弟子树) 中所 有节点的前缀编码。因此，前缀编码相对于区间编码来说，不仅能够有效地支 持包含关系等结构上的查询运算等操作，而且能够有效地支持文档的位置关系 的运算。也正是由于这个原因，前缀编码被更广泛的用于x m l 文档的关键字 查询之中。 前缀编码不仅考虑了父亲节点的编码，而且每层的子女再单独编码，因此 是一种全局编码和局部编码结合的方案，即混合编码。全局编码有效的支持了 祖先后代等包含先后关系的运算，而局部编码可以有效的进行左右兄弟关系的 判断，于是作为全局编码和局部编码结合的方案的混合编码，有效的继承了前 两种编码方案的优点，这也是前缀编码在x m l 文档的关键字查询中能被广泛 使用的另一个原因。 d e w e y 码 3 7 】有效的实现了前缀编码的思想，在本文涉及的s t a c k ，i l e ， s e ，l i s a 和l i s a1 - 等算法和新算法n d t 中，使用的编码都是d e w e y 编码或 者d e w e y 码的扩展方案。 2 1 2 3d e w e y 编码 定义2 1d e w e y 编码： 给定对应x m l 数据的标签有向树c 产- ( v , e , r ) ，g 中任意节点的d e w e y 编 码由下列规则确定： ( 1 ) 根节点，的d e w e y 编码为o ； 山东大学硕士学位论文 ( 2 ) 在对g 进行宽度优先遍历的过程中，如果节点1 ，是节点甜的第f 个孩子 节点，那么，节点 ，的d e w y 码为d ( “) ( 卜1 ) ，其中的d ( 材) 表示节点扯的d e w 锣 编码。 d e w e y 码甜中所有被“。 分割的整数的个数表示该d e w y 码”的长度，以五表 示。取x m l 树中根节点，所在的层为l ，那么称d e w e y 码 中与第i 层节点对应的 整数为该d e w e y 码的第i 层整数，表示为u i 。由1 到f 层整数组成的d e w y 码称为 该节点d e w y 码甜的第f 层前缀，表示为p l l ( i ) 。 h b r a r y n 一 。1 0。i n l 入夕弋 入 小t i t l e 砒甜吣咄供 n 。1 0 0 00 0 1 0 j0 0 r 卫n 。i n m n n f ) 。n 2 j0 。n 。i 啦2 0 0 1 i l l l n k i n g b m e e0 0 2 t h i n k i n g b m 图2 4 舭文档的d e w e y 编码 图2 4