（计算机软件与理论专业论文）基于slca的xml关键字查询研究与改进.pdf

山东大学硕士学位论文 摘要 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 ) 即可扩展的标记语言，是一套定义语义标 记的规范，其目的在于定义计算机和人都能方便识别的数据类型。随着网络应用 的快速发展，x m l 己经被广泛应用到i n t e m e t 智能信息检索、数字图书馆、数据 集成、w e bs e r v i c e 等领域，这使得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 l c a 求解算法的研究也较为 成熟。因此，本文围绕s l c a 展开，分析s l c a 求解算法性能上的缺点并提出新 的改进算法，之后通过实验进行验证。实验过程中发现，尽管算法性能有较大提 高，但结果集中存在较多并非期望的节点，因此，本文又对s l c a 的概念进行扩 展，提出同源s l c a ( h e t e r o g e n e o u ss l c a ，h s l c a ) 的概念，h s l c a 在s l c a 的基础上引入标签信息，能够显著提高x m l 关键字查询的准确率。 在改进s l c a 求解算法性能方面，本文在分析已有经典算法基础上展开，做 出了以下创新： 一、提出基于并查集的s l c a 求解算法u s s s a 。针对求解s l c a 性能最优 的l i s ai i 算法空间复杂度较大，占用存储空间较多的缺点，u s s s a 算法使用层 次编码进行求解，算法的空间复杂度明显降低，在理论求解时间与l i s a1 1 基本 相同的情况下，使用了更少的存储空间。 山东大学硕士学位论文 二、提出基于叠加树思想的s l c a 求解算法t r e es e t 。针对l i s a 算法 在查询关键字较少时性能较差的缺点，t r e e s e t 以树的方式求解s l c a ，当查 询关键字较少时，t r e es e t 比l i s a 具有更好的性能。同时，这种算法具有 很强的直观意义，便于理解，易于实现。 在提高x m l 关键字查询准确率方面，本文在分析s l c a 概念本身不足的基 础上展开，所做工作和改进有： 一、对s l c a 的概念进行改进，提出新的最紧致片段定义同源s l c a ( h s l c a ) ，h s l c a 在s l c a 的基础上引入标签信息来判断查询关键字节点之间 的相关度，提高x m l 关键字查询准确率。 二、对求解s l c a 的l i s ai i 算法进行扩展，得到求解h s l c a 的算法皿i s a 。 m i s a 较l i s ai i 在时间复杂度上并没有数量级的增加，理论上拥有同样优越的 性能。 本文对x m l 关键字查询中最紧致片段s l c a 进行深入研究，通过实验验证 对s l c a 的改进提高了x m l 关键字查询的性能和准确率，对用户有着重要的现 实意义。 关键词：x m l 关键字查询；最紧致片段；s l c a ；l i s a ；同源s l c a i i 山东大学硕士学位论文 a b s t r a c t x m l ，s t a n d sf o re x t e n s i b l em a r k u pl a n g u a g e ，i sas t a n d a r do fs e m a n t i cm a r k u p i td e f i n e st h ed a t a 够p ea i m e da te a s i l yr e c o g n i z e db yb o t hc o m p u t e r sa n du s e r s w i t h t h ef a s td e v e l o p m e n to fn e t w o r ka p p l i c a t i o n s ，x m lh a sb e e nw i d e l ya p p l i e dt ot h e i n t e m e ti n t e l l i g e n ti n f o r m a t i o nr e t r i e v a ls y s t e m , d i g i t a ll i b r a r i e s ，d a t ai n t e g r a t i o n ， w e bs e r v i c ea n ds oo n ，w h i c hm a k e sx m lb e c o m eap r i m a r yd a t af o r m s oh o wt o f i n dt h eu s e f u li n f o r i l l a t i o nf r o mx m 臣d a t ah a sb e e nah o tr e s e a r c ha r e a a c c o r d i n gt od i f f e r e n tf e a t u r e so fx m lq u e r yr e q u e s t ，w ec a l ld i v i d et h ex m l q u e r ys t r a t e g yi n t ot w oc a t e g o r i e s ：x m ls t r u c t u r a lq u e r ya n dx m lk e y w o r dq u e r y x m ls t r u c t u r a lq u e r yr e q u e s t su s e r st om a s t e rt h ex m ls t r u c t u r ea n de x q u i s i t e q u e r yl a n g u a g e i ti sab i gc h a l l e n g et ou s e r s h o w e v e r , x m lk e y w o r dq u e r yi s m u c hm o r ef l e x i b l e u s e r sc a ne a s i l yu s ei tb yo n l yp r o v i d i n gk e y w o r di n f o r m a t i o n i n s t e a do fa n yq u e r yl a n g u a g eo rd o c u m e n ts t r u c t u r e s s ot h i ss t r a t e g yi sw i d e l yu s e d a n dv a l u a b l et os t u d y f o rx m lk e y w o r dq u e r y ，t h eb a s i ci s s u ei st of i n dt h es m a l l e s tx m l f r a g m e n t s w h i c hc o n t a i na l lo ft h ek e y w o r d s 1 1 1 ed e f i n i t i o no ft h es m a l l e s tx m l f r a g m e n t sa n d t h ee f f i c i e n c yo fc o m p u t i n gt h e mw i l ld i r e c t l ya f f e c tt h ee f f i c i e n c ya n da c c u r a c yo f x n 儿k e y w o r dq u e r y a tp r e s e n t ，s l c ai st h eb e s td e f i n i t i o nf o rt h es m a l l e s tx m lf r a g m e n t s a n d t h e r ea r ea l s om a n yg o o ds o l u t i o n sf o rc o m p u t i n gs l c a i nt h i sp a p e r , w ef i r s t a n a l y z et h ed i s a d v a n t a g eo fp r e v i o u sa l g o r i t h m sf o rs l c aa n dt h e np r o p o s et w o m o r ee f f i c i e n ta l g o r i t h m sf o ri m p r o v e m e n t b u ta c c o r d i n gt ot h ee x p e r i m e n t ，w e f o u n dt h a tt h e r es o m en o d e si nt h ea n s w e r s s ow ei m p r o v et h en o t i o no fs l c aa n d p r o p o s eh e t e r o g e n e o u ss l c a ( h s l c a ) w h i c hb r i n g sl a b e l si n f o r m a t i o ni n h s l c a c o u l di m p r o v et h ea c c u r a c yo fx 陋，k e y w o r dq u e r yo b v i o u s l y i nt h ee f f i c i e n c ye n h a n c e m e n to fa l g o r i t h mf o rs l c a ，t h i sp a p e ra n a l y z e st h e c l a s s i c a la l g o r i t h m sa n dm a k e st h ei n n o v a t i o n sb e l o w ： 1 w ep r o p o s et h eu s s s aa l g o r i t h mw h i c hb a s e so nt h eu n i o ns e t i tu s e st h e l e v e lc o d i n gt od ot h ec o m p u t a t i o na g a i n s tt ot h ed i s a d v a n t a g eo fm o r es p a c e c o m p l e x i t ya n dm o r es p a c es t o r a g eo fl i s ai i t h es p a c ec o m p l e x i t ya n dt h es p a c e s t o r a g eo f u s s s aa r em o r ea d v a n c e dt h a nl i s a1 1i nt h es a l t l et i m es c e n a r i o i i i 山东大学硕士学位论文 2 w ep r o p o s et i l e1 1 江e s e ta l g o r i t h mw h i c hb a s e so nt h ei d e ao fo v e r l a p p i n g t r e e i tc o m p u t e st h es l c ai nt h et r e em o d ea g a i n s tt ot h ep o o re f f i c i e n c yo fl i s a w h e nt h e r ea r el e s sk e y w o r d s m e a n w h i l e ，t h i sa l g o r i t h mi sm o r ei n t u i t i o n a la n de a s y t ou n d e r s t a n da n dr e a l i z e 。 i nt h ea c c u r a c ye n h a n c e m e n to fa l g o r i t h mf o rt h ex m lk e y w o r dq u e r y ，w e a n a l y z et h ed i s a d v a n t a g e so fs l c a a n dm a k et h ei r m o v a t i o n sb e l o w 1 w ei m p r o v es l c aa n dp r o p o s eh s l c aa san e wn o t i o nf o rt h es m a l l e s t f r a g m e n t f o rh s l c a 1 a b e li si n t r o d u c e dt od e t e r m i n et h ec o r r e l a t i o n b e t w e e n k e y w o r d s a n dt oi m p r o v et h ea c c u r a c yo f x 几k e y w o r dq u e r y 2 t h ei l i s aa l g o r i t h mi si n n o v a t e dw h i c hi sas o l u t i o no fh s l c aw i t ht h e e n h a n c e m e n to fl i s a a l g o r i t h m h l i s at h e o r e t i c a l l yh a v et h es a m es u p e r i o r p e r f o r m a n c ew i t hl i s a i is i n c et h e yh a v et h es a m et i m ec o m p l e x i t y t h i sp a p e rm a k e sa ni n d e p t hs t u d yo ns l c a t h r o u g hi t ，w ei m p r o v et h e e f f i c i e n c ya n da c c u r a t eo fx m lk e y w o r dq u e r yw h i c hi sv e r ys i g n i f i c a n tf o ru s e r s a n da p p l i c a t i o n s k e y w o r d s ：x h lk e y w o r ds e a r o h ；t h es - - i al ia s tf r a l 箜n e n t ；s l o a ；l is a ；h s l c a 原创性声明和关于学位论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：鱼墨墨 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：i 塾叠叠导师签名： 山东大学硕士学位论文 第一章绪论 x m l r x t e n s i b l em a r k u pl a n g u a g e ) 即可扩展的标记语言，是一套定义语义标 记的规范，其目标是能够定义计算机和人都方便识别的数据类型【1 1 。随着网络应 用的快速发展，符合x m l 规范的数据( 称为x m l 数据) 已大量存在于当前的 信息社会。如何从x m l 数据中准确而快速的提取用户感兴趣的信息就成为x m l 数据管理研究的重要主题。 1 1 研究背景与意义 x m l 由于其所具有的自描述性、灵活的数据结构以及丰富的数据表示能力 等特点，现在己经被广泛应用到i n t e m e t 智能信息检索、电子商务中的数据表示 和数据交换、数据集成、w e bs e r v i c e 、数字图书馆等领域。这使得x m l 类型的 数据成为当前主流的数据形式，对x m l 数据的有效管理也随之成为当前数据库 领域研究的热点 2 1 。 作为日渐广泛采用的数据形式，从x m l 数据中提取有用的信息是一个不可 回避的研究内容【3 4 】。为了从自描述的、半结构化的x m l 数据中抽取用户感兴趣 的信息，研究人员开发了许多查询描述形式，文献【5 】根据查询请求描述特点的 不同，可概括为两大类查询模式：x m l 结构化查询和x m l 关键字查询。 x m l 结构化查询首先定义精确的查询描述语言，用户借助它来描述自己感 兴趣的模式，将用户的模式交由实际的x m l 数据处理系统处理，然后返回与模 式相匹配的结果。这就要求用户掌握x m l 文档结构及查询语言。然而，i n t e m e t 的大多数使用者，是那些既不懂得查询语言，又不了解x m l 文档结构的普通用 户( n a i v eu s e r ) ，这时，基于关键字的x m l 数据查询是比较方便的，它只需用户 提供简单的关键字信息，而无需用户懂得任何查询语言或文档结构【6 i 。 x m l 关键字查询中，主要有两种方式：一是直接将纯关键字方式不加修改 地应用到x m l 数据的查询中；二是辅助信息限定关键字所在节点的范围，例如 标签或标签路径信息 7 1 。由于后者引入的标签信息使得用户还要了解x m l 数据 的实际组织，增加了用户使用的复杂性，而且本质上讲，这种扩展关键字的方式 山东大学硕士学位论文 只是增加了过滤关键字节点的作用，实际处理与纯关键字方式并无很大不同，因 此，大多将研究的重点放在纯关键字查询中。下文所说的x m l 关键字查询都指 的是纯关键字查询【8 12 1 。 x m l 关键字查询的基本问题是获得所有满足关键字组合语义的最紧致片段 【3 1 ，对最紧致片段的定义及求解最紧致片段的算法性能将直接影响x m l 关键字 查询的性能和准确率，而这恰恰是用户最关心的方面。 分析国内外在x m l 最紧致片段上的研究得知，目前，定义最紧致片段的概 念中最好的是s l c a ( s m a l i e s tl o w e s tc o m m o na n c e s t o r ) t 5 1 ，因此，本文将重点对 s l c a 的概念及求解s l c a 的算法进行研究并改进，以提高x m l 关键字查询的 性能和准确率，这对用户有着重要的现实意义。 1 2 国内外研究现状 x m l 关键字查询根据查询请求描述特点的不同，可概括为两大类查询模式： x m l 结构化查询和x m l 关键字查询。 x m l 结构查询下的算法偏向于传统的结构化的查询方法，即采用了正则表 达式的描述形式 1 3 , 1 4 。它首先定义了精确的查询描述语言，用户借助查询描述语 言来描述自己所感兴趣的数据，x m l 结构查询引擎返回按照用户需求的形式化 描述而检索到的x m l 片段。目前，属于此类的查询语言有很多，包括：l o r e l 1 5 】， x m l q l l l 6 1 ，x m l g l p t ，q u i l t t l 引，x p a t h 1 9 1 ，x q u e r y l 2 0 等。 目前，该类查询语言发展到现在已出现了集中的趋势，其代表便就由w 3 c 推出的x p a t h 和x q u e r y 2 1 - 2 3 】。然而，该类查询语言的缺陷是明显的：首先，查 询语言的使用者必须学习相关的语法机制，这一点本身就增加了普通用户使用它 们的难度。而且用户即便是已经掌握了相关的查询描述机制，如果不了解实际要 查询的x m l 数据的组织情况同样不能完成查询语句的书写。 针对绝大多数用户并不了解x m l 文档结构和查询语言的现状，x m l 关键 字查询提出可以根据用户提供的查询关键字得到用户期望的信息，不需要用户了 解x m l 文档结构及查询语言，适合绝大多数用户使用。 2 山东大学硕士学位论文 1 2 。1 最紧致片段研究现状 在x m l 关键字查询中，最基本的问题就是获得所有满足关键字组合语义的 最紧致片段。相关研究中，文献 2 4 1 最早出提出了最紧致片段的定义l c a ( l o w e s t c o m m o na n c e s t 0 0 ，l c a 指在x m l 文档树中，包含所有查询关键字节点的最近 公共祖先节点，该节点的任意子节点都不再包含所有的关键字节点伫5 筇1 。在l c a 的基础上，又相继提出了s m a l l e s tl c a ( s l c a ) 2 7 、v a l u a b l el c a ( v l c a ) 1 2 引、 m e a n i n g f u ll c a ( m l c a ) 1 2 9 1 等概念来提高x m l 关键字查询的性能和准确率。 s l c a 是在l c a 的基础上改进而来的，基本思想是，如果x m l 文档树节点 v 已包含所有的关键字，那么v 的祖先节点的相关度肯定是较低的。即，s l c a 给出了一个最小树，该树包含了所有的关键字，且该树的任一子树都不完全包含 所有关键字。 v l c a 包含满足如下条件的节点：如果一个x m l 节点包含至少一个关键字 匹配，并且它的子节点都没有包含关键字的匹配，则称该节点为一个v l c a 节 点。 m l c a 是在l c a 求解完成以后，通过排除相关度较低的l c a 而得到的。 s l c a 、v l c a 、m l c a 等的引入，相对于简单的l c a 求解，提高了x m l 关键字查询的性能和准确率。其中，对s l c a 的研究相对较多，s l c a 的发展也 较为成熟，被认为是最好的最紧致片段的定义，本文将围绕s l c a 展开。 在获取了所有包含给定关键字的最紧致片段后，另一个重要的问题就是 x m l 片段相似程度的计算【5 1 。由于x m l 片段具有结构信息，使得针对它的相似 性计算可以考虑传统的相似性计算方法，即可以通过用户对于结果的反馈来进一 步计算符合用户意图的最终结果。而对于结构信息的计算，很多算法引入了传统 信息检索( i n f o r m a t i o nr e t r i e v a l ，埘的思路，其代表有x r a n k 3 们、x s e e k 3 1 1 等。 ( 1 ) x r a n k 是最早将x m l 文档的分层和超级链接结构、关键字二维接近 的概念考虑进来的x m l 检索系统，其设计目标是为用户提供类似g o o g l e 的基 于超链接的删，搜索引擎，并且支持h t m l 和x m l 混合文档查询。 ( 2 ) x s e e k 区分代表实体的节点和代表属性的节点，并返回与关键字匹配 的实体节点。 山东大学硕士学位论文 由于本文研究并不涉及到x m l 关键字查询中最紧致片段的相似性度量，对 此不再做更多的说明。 1 2 2 $ l c a 求解算法研究现状 在给出x m l 关键字查询中最紧致片段的定义之后，对最紧致片段的求解便 成为了一个重要的问题，因为求解算法的性能很大程度上决定了x m l 关键字查 询的性能。 目前，对s l c a 的求解算法研究较多，都是基于d e w e y 编码的【3 2 , 3 3 1 。 文献【2 9 】提出了求解s l c a 的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 l c a 。该算法基于栈 来进行计算，所以被称作s t a c k 算法。 s t a c k 算法利用d e w e y 编码的有序压入和弹出，求解最长公共节点，不仅需 要扫描所有节点，而且还需要大量的编码比较的操作和栈的压入与弹出操作，不 能避免扫描对结果不起任何作用的无效节点，耗费了大量的c p u 周期。 为此，文献【3 0 】提出了m e 0 n d e x e dl o o k u pe a g e ra l g o r i t h m ) 算法，尝试利用 索引来减少扫描d e w e y 码的工作量 3 4 - 3 8 】。i l e 算法使用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 ) 被提了出来，通过缓存指针用 来加速左匹配和右匹配算法。 但是，i l e 算法必须修改b + 树结构以支持必要的d e w e y 码操作，并将全部 x m l 数据保存入改造过的b + 树，实现较为复杂。 针对这些问题，文献 3 2 1 提出了求解s l c a 的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 ) 算法，即最小子树根节点问题的分层算法，该算法在获取了包含关键 字的节点的编码集合后，通过计算对应于不同关键字、不同层次的编码前缀集合 4 山东大学硕士学位论文 的交集，可以得到对应不同层的s l c a 节点。l i s a 算法跟据是否将d e w e y 码转 换为整数参与计算的不同设计了两种实际的l i s a 实例，分别称为l i s ai 和 l i s a 。 文献【2 7 ，3 2 对以j 2 算法进行分析，并通过实验证明l i s a 算法拥有较好的 性能，因此，本文对s l c a 求解算法的改进主要基于对l i s ai i 算法的研究分析。 1 3 论文主要工作及创新点 x m l 关键字查询不需要用户掌握复杂的查询语言和x i v i l 文档结构，方便 普通用户使用，是x m l 查询中值得进一步深入探讨的方向。 x m l 关键字查询的基本问题是获得所有满足关键字组合语义的最紧致片 段，根据目前的研究，对最紧致片段的定义最好的是s l c a ，本文便是围绕s l c a 展开的。 本文首先深入研究现有s l c a 求解算法的性能，分析s l c a 求解算法存在的 不足，在此基础上提出两个改进算法：基于并查集的s l c a 求解算法( u s s s a ) 和基于叠加树思想的s l c a 求解算法( t r e es e t ) 。实验证明，u s s s a 算法能够 显著的节省存储空间，降低内存使用；t r e es e t 算法在查询关键字个数较少时 有更快的查询速度。这两个算法在性能方面的优势通过实验分别得以证明。 但是，在实验过程中发现，尽管新的s l c a 求解算法性能上有显著提高，但 在求出的s l c a 结果集中，有许多并非用户期望的节点存在，经分析，这是由于 s l c a 定义本身的不足引起的。因此，本文又对s l c a 的概念进行改进，提出同 源s l c a ( h s l c a ) 的概念。h s l c a 通过引入x m l 文档标签信息来判断查询关键 字节点间的相关度，弥补了s l c a 在此方面的不足，显著提高了x m l 关键字查 询准确率3 9 1 。 为求解h s l c a ，本文尝试将求解s l c a 的l i s ai i 算法进行扩展，提出 h l i s a 算法。h l i s a 算法在l i s a 分层求解s l c a 的每一层计算中加入对标签 信息的比对，算法复杂度并未有数量级的增加，理论上有较好的性能。 最后，本文通过实验验证基于h s l c a 的x m l 关键字查询比基于s l c a 的 舭关键字查询在准确率上有显著的提高。 本文的主要贡献和创新概括如下： 山东大学硕士学位论文 ( 1 ) 提出基于并查集的s l c a 求解算法u s s s a 。u s s s a 算法针对求解s l c a 性能最好l i s ai i 算法空间复杂度较大，占用存储空间较多的缺点，使用层次编 码而非d e w e y 码进行求解，算法有较低的空间复杂度，在理论时间性能与l i s a 几乎相同的情况下，使用更少的存储空间。 ( 2 ) 提出基于叠加树思想的s l c a 求解算法t r e es e t 。当查询关键字较少 时，t r e es e t 较l i s ai i 具有较好的性能。同时，这种算法是直接以树的形式 进行的，具有较好的直观意义，便于理解，易于实现。 ( 3 ) 对s l c a 的概念进行改进，提出h s l c a 的概念。h s l c a 在s l c a 的 基础上引入标签信息来判断查询关键字节点之间的相关度，提高了x m l 关键字 查询的准确率，是较s l c a 更好的定义最紧致片段的概念。 ( 4 ) 将求解s l c a 的l i s ai i 算法进行扩展，得到求解h s l c a 的算法 h l i s a ，h l i s a 算法较l i s ai i 算法在时间复杂度上并没有数量级的增加，理论 上有较好的性能。 1 4 论文组织结构 本文围绕x m l 关键字查询中最紧致片段s l c a 展开，从提高s l c a 求解算 法的性能和改进s l c a 以提高x m l 关键字查询准确率两方面进行研究，具体组 织结构如下t 第一章是本文的绪论部分，说明了本文的研究背景与研究意义，并对目前国 内外研究现状做了概要总结，概括了本文的内容和主要创新之后，列出了全文的 组织结构。 第二章详细介绍了x m l 关键字查询中最紧致片段及s l c a 的相关概念：指 出了最紧致片段l c a 在查询准确率方面的不足，给出了s l c a 的准确定义，分 析了s l c a 相对于l c a 在x m l 关键字查询准确率方面的提高。 第三章分析s l c a 的几种求解算法：对求解s l c a 的几种经典算法进行深入 分析研究，指出各算法在性能上的优点与不足，阐明l i s ai i 算法具有较好的理 论和试验性能，是一种比较理想的s l c a 求解算法。 第四章提出了求解s l c a 的算法u s s s a ：说明了u s s s a 算法较l i s a1 i 算 法在空间复杂度及占用存储空间方面的提高，并通过实验进行验证。 6 山东大学硕士学位论文 第五章提出了求解s l c a 的算法t r e es e t ：说明了t r e es e t 较l i s a l i 算 法更适合查询关键字较少的情况，证明了算法的正确性，分析了算法的复杂度， 并通过实验进行验证。 第六章对s l c a 的概念进行改进，提出了新的最紧致片段h s l c a 的概念： 指出了s l c a 在x m l 关键字查询准确率方面存在的不足，对s l c a 的概念加以 改进得到h s l c a 的概念。同时，对l i s a 算法进行扩展，得到支持h s l c a 求解的甩i s a 算法，最后通过实验验证h s l c a 对x m l 关键字查询准确率的提 高。 第七章对本文的研究工作进行了总结和归纳，并提出了将来进一步需要完善 和研究的工作。 7 山东大学硕士学位论文 第二章最紧致片段及s l c a 相关概念 对于儿关键字查询来说，基本操作就是找到包含给定关键字的最紧致片 段。目前对包含所有关键字节点的最紧致片段的描述中，s l c a 最为成熟，基于 s l c a 的x m l 关键字查询在查询性能和准确度上有较好的表现。本章将详细介 绍x m l 关键字查询中最紧致片段及s l c a 的相关概念，为后面的研究打下基础。 首先，给出x m l 数据及x m l 文档树的定义。 2 1x m l 数据及其树结构 x m l 但x t e n s i b l em a r k u pl a n 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 e b 服务、电子商务等诸多网络相关应用领域已被广泛使用， 成为目前网络数据交换和表示事实上的标准。 符合x m l 规范的数据称作x m l 数据，x m l 规范规定了x m l 数据必须满 足的条件。x m l 数据有两个基本特点：一是自描述，x m l 数据本身就已经包含 了元数据关于数据本身的信息，表现为不同语义的标记( 例如元素、属性等 等) 。在所有标记中，元素标记最为重要。一个元素标记由两个起、止标签构成， 起止标签所含的文本就是对应的语义单元：二是半结构化，即不同于传统关系数 据库( 传统的数据库都有一定的数据模型，可以根据模型来具体描述特定的数 据) ，舳数据的结构限制并不严格，表现为语义单元相互嵌套的层次关系。 x 池数据内容的限制通常由x m l 模式来描述。常用的模式包括d t d 4 0 和 x _ m ls c h e m a 4 1 , 4 2 1 。文档类型定义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 更强的 描述性，能够更好的验证x m l 文件逻辑结构的正确性。 山东大学硕士学位论文 x m l 数据的基本形式为x m l 文档。 明、元素、注释、字符引用和处理指令， 例。 一个x m l 文档通常由5 部分组成：声 图2 1 即为一个实际的x m l 文档的示 b i b l i o g r a p h yo nd a t ad e s i g n k a r e nb o t n i c h f a c er e c o g n i t i o n c o l ac o h e n 2 0 0 3 g e r m a n y ， 图2 1x m l 文档举例 在实际处理x m l 数据时，更为常见的是x m l 标签有向图模型，由x p a t h 规范描述。通常简化为x m l 标签有向树模型，g = ( 啊，叫) ，其中的矿表示g 中 所有节点的集合，e 表示g 中所有边的集合，表示g 的根节点，a 是所有节点 所带标签的集合。图2 2 即为图2 1 中x m l 文档对应的x m l 文档树。 9 山东大学硕士学位论文 2 2 最紧致片段相关概念 么 p r o 譬e d i n g s 么 a r t i c l ey e a r a d d r e s s 图2 2x m l 文档树 在x m l 关键字查询中，用户只需输入查询关键字便能得到期望的结果，这 就涉及一个重要的问题：如何根据查询关键字定义查询结果。为此，提出最紧致 片段的概念，最紧致片段指在x m l 文档树中，满足所有查询关键字组合语义的 最小树片段，这样，x m l 关键字查询问题便转化为查找所有最紧致片段的问题。 最早的最紧致片段定义是l c a ( l o w e s tc o m m o na n c e s t o r ) 矧。l c a 是图论中 经常使用的一个概念，指在有向图中，两个节点的最近公共祖先节点f 2 4 ，2 ”。在将 l c a 的概念引入x m l 关键字查询中时，l c a 指所有包含查询关键字的节点的 最近公共祖先。为给出l c a 的准确定义，首先明确x m l 树中的一些概念。 在x m l 树中，我们用y 表示一个节点。对于任意节点v ，用，( v ) 表示该节点 的标签信息。对于任意节点“、v ，” _ v ) 表示”是v 的祖先( 后代) ，u i t 表示材_ v 或者r - l t 。” d 表示在x m l 树前序遍历中，材的序列在，之前 ( 之后) ，但材并不是1 ，的祖先( 后代) 。例如，在图2 3 的x m l 文档树中， 1 0 1 山东大学硕士学位论文 咖；b i b 。d 1 3 i l a m e i v l d b 7 爻孓沁“9 y e a r p a p e rp a p e r c h a i r i 2 0 0 6 6 t i t l e i x m 吐 2 乞忿、2 7 n a m e y e a rp a p e r c h a i r l s i g m o d 8 a u t h o r b i bt i t l ea u t h o ra u t h o r 土9 i 皇t i o m ，蔓 c o n f 1 0 小1 2 n a m e y e a r i l s i g m o d2 0 0 5 p a p e r 盏、盯 i i r + t o m i 2 0 0 6 t i t l e i x m l l 妒。 a u t h o ra u t h o r jj j o h n l u c y 图2 3x m l 文档树 下面，给出l c a 的准确定义： 给定查询关键字集合k = 岛，屯，k 及待查询关键字文档d ，厶表示d 中直 接包含关键字岛的节点集合。 定义2 1 - l c a ，在x m l 文档d 中，给定1 7 1 个节点一，t 1 2 ，如果对于 v j f 俄，节点v 是胁的祖先，且不存在节点掰，y 材，”也是所有 绝的祖先，则我们称v 是这历个节点的一个l c a ，记做 v = l c a ( n l ，刀2 ，n m ) 。 定义2 2 ：l c a s e t ，给定查询关键字集合足= 向，如，屯 及待查询x m l 文 档d ，在d上关于k的l c a s e t定义为 l c a s e t = l c a ( z 1 ，厶，k ) = 1 ，l ，= c z ( h ，吃，) ，q 厶( 1 i ，行) 山东大学硕士学位论文 例如，在图2 3 中，用户希望查询题目中包含“瓜并且作者中有“j o h l l ” 的文章，则输入的关键字集合为 “i r ，“j o h n ) ，根据l c a 的定义，节点p a p e r ( 1 5 ) 是这两个关键字的一个l c a ；所以p a p e r ( 1 5 ) 是查询的一个输出。 l c a 是x m l 关键字查询中最紧致片段的基础定义，在l c a 的基础上，相 继又提出了s m a l l e s tl c a c s l c a ) 口7 1 、v a l u a b l el c a ( v l c a ) e 2 8 i 、m e a n i n g f u ll c a ( m l c a ) 2 9 1 等概念来提高x m l 关键字查询的性能和准确率。其中，对s l c a 的研究相对较多，s l c a 的发展也较为成熟，被认为是目前最好的最紧致片段的 定义。 2 3s l c a 概念详述 l c a 给出了x m l 关键字查询中最紧致片段的定义，但是l c a 的概念过于 简单，查询准确率较低。 例如，在图2 3 中，假定给出的关键字集合为 i r ，“t o m ，节点c o n f ( 2 ) ， p a p e r ( 1 2 ) 和p a p e r ( 1 5 ) 都为该关键字集合的l c a ( 其中，c o n f ( 2 ) 是t i t l e ( 1 3 ) a n d a u t h o r ( 1 7 ) 的l c a ) ，然而，我们可以很清楚的知道，c o n f ( 2 ) 本不应该是该查询 关键字集合的输出，因为t i t l e ( 1 3 ) 和a u