（计算机软件与理论专业论文）综合文档语义与用户查询语义的xml关键字查询研究.pdf

， 。10 乞 ： i - 1 3 研究目标与内容3 1 4 研究的技术路线4 1 5 本章小结5 第2 章关键字查询过程中的语义问题7 2 1 文档语义的获取7 2 1 1x m l 文档的表示7 2 1 2 文档隐含语义的挖取9 2 1 3 表达基本语义的实体子树的存储1o 2 1 4 值节点的全文索引1 2 2 2 用户查询语义的获取1 3 2 2 1 明确关键字语义的查询语法1 3 2 2 2 用户关键字的分类1 4 2 3 本章小结1 4 第3 章基于相似度计算的关键字模式无关查询1 5 3 1 基于w o r d n e t 的概念相似度计算15 3 1 1w o r d n e t 概念网络图1 5 3 1 2 三类相似度计算方法1 7 3 1 3 一种新的概念相似度计算方法2 0 3 2 模式无关查询的具体实现2 2 3 3 本章小结2 4 第4 章综合语义的关键字查询算法2 5 4 1 算法的核心思想2 5 4 2 算法的具体实现2 7 4 2 1 相关实体子树集的计算2 7 4 2 2 语义相关实体子树集的计算2 8 4 2 3 查询结果的返回2 8 4 3 算法的实例2 9 j ，2 t 4 4 本章小结 第5 章实验结果与分析 5 1 实验设计的依据 5 1 1 数据集描述 5 1 2 实验方法描述3 3 5 2 实验的具体方案及分析3 4 5 2 1 单词语义相似度实验3 4 5 2 2 查询有效性测试实验3 6 5 2 3 查询效率测试实验。3 8 5 3 实验结论4 0 第6 章总结与展望4 1 6 1 本文总结4 1 6 2 进一步的研究工作4 1 参考文献4 3 致谢4 7 攻读学位期间所发表的学术论文4 9 ， 芷， ， 一l l f 丑 近年来x m l 数据查询的一个研究热点。为了解决x m l 关键字查询中语义信息丢失导致查询 结果质量不高的问题，本文提出了一种综合文档语义与用户查询语义的x m l 关键字模式无关 查询方法，通过增加查询结果的语义相关性，提高查询的准确率。 论文的主要研究工作如下： ( 1 ) 分析了x m l 文档树的结构和对应的模式信息，对文档中各节点间存在的隐含关系进 行挖掘，将文档中的节点划分为实体、属性和值节点。基于节点的划分，使用表达文档基本 语义的实体子树存储x m l 文档节点间隐含的语义信息，获得查询文档的语义信息。 ( 2 ) 规范了用户的关键字查询表达式，对查询关键字进行分析，明确了查询关键字相互间 隐含的语义信息；针对用户不同的查询期望，把查询关键字归为预测关键字和结果关键字两 类，预测关键字主要用于查询，结果关键字主要用于返回查询结果。 ( 3 ) 提出了一种改进的基于w o r d n e t 计算概念间相似度的算法，算法主要考虑了关键字查 询过程中概念间的非对称性。并且结合相似度计算方法对两类查询关键字进行扩展查询，实 现x m l 关键字的模式无关查询。 ( 4 ) 在获取文档语义和用户查询语义的基础上，对查询返回结果集进行了研究，提出了一 种新的返回结果集语义相关实体子树集。对现有最小最低公共祖先算法进行改进，实现 了语义相关实体子树集的求解算法。 ( 5 ) 通过实验对比，证明了本文提出的综合文档与用户语义的关键字模式无关方法相比于 传统的关键字查询算法，能够更准确的捕获用户查询意图，同时查询的有效性和效率等方面 都能取得满意的结果。 关键词：概念相似度关键字查询最小最低公共祖先语义相关实体子树集 o 引 ，、 r t 、 m a s t e rc a n d i d a t eo fc o m p u t e rs o f t w a r ea n dt h e o r y ：l i j u n s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rx i o n gh a i l i n g a bs t r a c t w t ht h er a p i dd e v e l o p m e n to fi n t e r n e t t h en u m b e ro fx m ld o c u m e n t si n c r e a s e se x p o n e n t i a l l y , x m l k e y w o r d sr e t r i e v a lb e c o m e sar e s e a r c hh o t s p o ti nr e c e n ty e a r s ax m lk e y w o r d ss c h e m a f r e e r e t r i e v a lm e t h o dw h i c hi n t e g r a t e sd o c u m e n t sa n dt h es e m a n t i c so ft h eu s e r s w a sp r o p o s e dt od e a l w i t ht h el o s so fs e m a n t i ci n f o r m a t i o ni nx m lk e y w o r dr e t r i e v a l i tc a ni m p r o v eq u e r ya c c u r a c yb y i n c r e a s i n gt h es e m a n t i cr e l e v a n c eo fq u e r yr e s u l t s t h ec u r r e n tt h e s i sc o v e r st h ef o l l o w i n gf i v ep a r t s ： f i r s t l y , a f t e ra n a l y z i n gt h es t r u c t u r eo fx m ld o c u m e n tt r e ew i t ht h ec o r r e s p o n d i n gs c h e m a i n f o r m a t i o na n dm i n i n gt h ei m p l i e dr e l a t i o n s h i pb e t w e e ne a c hn o d ei nt h ed o c u m e n ld i v i d e dt h e s e n o d e si n t oe n t i t y , a t t r i b u t ea n dv a l u en o d e s t h ec l a s s i f i c a t i o nb a s e do nn o d e sc a ns t o r et h e i n f o r m a t i o ni m p l i e di nt h en o d e st og e tt h es e m a n t i ci n f o r m a t i o no ft h eq u e r yd o c u m e n t sb yu s i n g t h ee n t i t ys u bt r e e st h a tc a nh e l pe x p r e s st h eb a s i cs e m a n t i c so fad o c u m e n t s e c o n d l y ，s p e c i f i e dt h eu s e r s k e y w o r d sq u e r ye x p r e s s i o na n dc l a r i f i e dt h ei m p l i e ds e m a n t i c r e l a t i o n s h i pa m o n gk e y w o r d sb ya n a l y z i n gt h eq u e r yk e y w o r d s ；d i v i d e dt h eq u e r yk e y w o r d si n t o p r e d i c tk e y w o r d sa n dr e s u l tk e y w o r d s t h ep r e d i c tk e y w o r d sa r eu s e df o rr e t r i e v a lw h i l er e s u l t k e y w o r d sa r em a i n l yu s e df o rg e n e r a t i n gq u e r yr e s u l t s t h i r d l y , p r o p o s e d a l li m p r o v e da l g o r i t h mb a s e do nt h es i m i l a r i t ya m o n gt h ec a l c u l a t i o n c o n c e p t so fw o r d n e t c o n s i d e r i n gt h ea s y m m e t r yo fd i f f e r e n tc o n c e p t sa n dc o m b i n i n g t h es i m i l a r i t y c a l c u l a t i o nm e t h o d ，t h ea l g o r i t h ma c h i e v e st h ex m ls c h e m a - f r e eq u e r y f o u r t h l y , s t u d i e dt h eq u e r yr e s u l t sb a s e do nt h es e m a n t i c so ft h ed o c u m e n t sa n dt h eq u e r y s e m a n t i c so ft h eu s e r s ，p r o p o s e dan e ws e to fq u e r yr e s u l t sw h i c hr e f e r st ot h es e m a n t i c a l l yr e l a t e d e n t i t ys u bt r e es e t i th e l p si m p r o v et h ea l g o r i t h m sf o rs m a l l e s tl o w e s tc o m m o na n c e s t o ra n dg e t t h ea l g o r i t h mf o rs e m a n t i c a l l yr e l a t e de n t i t ys u bt r e es e t a tl a s t ，p r o v e dt h a tt h ep r o p o s e dx m lk e y w o r d ss c h e m a - f r e er e t r i e v a lm e t h o d ，c o m p a r e dw i t h t h et r a d i t i o n a lk e y w o r d sq u e r ya l g o r i t h m ，c a nc a p t u r et h eu s e r sq u e r yi n t e n tm o r ea c c u r a t e l ya n d i t i 总： 两南人学硕十学伊论文 m e a n w h i l ei ti sm o r es a t i s f y i n gi nq u e r ye f f e c t i v e n e s sa n de f f i c i e n c y k e yw o r d s ：c o n c e p t u a ls i m i l a r i t y ；k e y w o r d sr e t r i e v a l ；s m a l l e s tl o w e s tc o m m o na n c e s t o r ( s l c a ) ；s e m a n t i c a l l yr e l a t e de n t i t ys u bt r e es e t ( s r e s t s ) i v i 一 竹i 抽 y 信息发布、信息集成、内容管理等领域。伴随着x m l 文档数量的急剧增加，越来越多的研究 人员开始关注如何高效地对x m l 文档进行检索。 目前，x m l 文档检索方法主要分为两类，结构化查询和关键字查询方式，这两类方法都 各自存在着一些问题： ( 1 ) 结构化查询及其扩展方式 对于x m l 数据的检索，传统方式使用x m l 结构化的查询语言进行。x m l 数据的查询语 言有很多种，x p a t h 1 1 和x q u e r y 2 是查询语言的代表。x p a t h 主要用于x m l 数据的周游，它 是x q u e r y 的基础。x q u e r y 语言于2 0 0 1 年2 月由w 3 c 组织公布，它由q u i l t l 3 1 衍生而来，吸 收了x p a t h 和x q l 中的路径表示语法，同时融入了s q l 中关键字系列子句的思想。x q u e r y 的查询处理的一般过程为：首先，导入x m ls c h e m a 文档，将查询所需的模式映射为x q u e r y 的系统类型：其次，加载x m l 数据文档，将x m l 文档映射为x q u e r y 数据模型的实例；紧 接着对x m l 查询表达式进行处理，包括表达式的解析：优化、求值等过程；最后将查询结果 构造成x m l 文档形式串行化输出。 结构化查询方式在检索x m l 文档的效率和性能上有比较满意的结果，但是却不适用于普 通用户检索网络中大量存在的x m l 文档，原因主要有两方面：一是用户必须学习同查询语言 相关的语法机制，这无疑增加了用户使用它们的难度，限制了用户的是使用；二是在用户已 经掌握了相关的语法机制的情况下，如果不了解预查询x m l 文档的数据组织情况，用户依然 不能正确的书写出查询语句。 针对结构化查询方式上的不足，文献【4 6 】对传统查询方式进行了扩展，部分改善了用户 使用的友好性，但对普通用户来说，使用扩展结构化查询语言仍然具有相当的难度。 ( 2 ) x m l 关键字查询方式 以关键字查询为核心支撑技术的搜索引擎是信息检索领域一种易于普通用户使用的工 具，它在数据查询中具有突出的便利性，因而在x m l 数据的查询处理中吸收基于关键字的信 息检索的优点，成为x m l 数据检索的另一个重要方向。 与传统搜索引擎返回整个h t m l 文档作为查询结果不同，x m l 查询以x m l 元素为粒度， 返回结果仅为用户感兴趣且符合关键字的x m l 文档的一些片段，从而使检索结果更加精确， 同时还可以有效减少数据的传输量。但同样因为这些原因使得x m l 片段包含的信息量较少， 1 2 国内外研究现状 在国外，x m l 数据的信息检索研究开始于2 0 0 1 年1 7 j ，随即成为数据库与信息检索领域的 研究热点。目前，x m l 关键字查询算法一般先将x m l 文档表示为树形结构，然后利用d e w e y 码等编码方式记录x m l 文档节点间的层次关系，最后以关键字接近的思想构造查询结果集， 已有的研究包括x r a n k t 引、m e a n i n g f u ll o w e s tc o m m o na n c e s t o r ( m l c a ) 9 1 、g r o u p e dd i s t a n c e m i n i m u mc o n n e c t i n gt r e e ( g d m c t ) 1 10 1 、x s e a r c h i l l l 、s m a l l e s tl o w e s tc o m m o na n c e s t o r ( s l c a ) 12 1 、x s e e k 4 】等。 x r a n k 是康奈尔人学的l i ng u o 等人提出的x m l 搜索引擎，它最早考虑x m l 文档的 分层结构，提出以x m l 元素为粒度的搜索理论，实现了一种基于栈的l o w e s t c o m m o n a n c e s t o r ( l c a ) 算法，并且通过e l e m r a n k 衡量x m l 元素的客观重要性。密歇根大学的y u n y a ol i 等人 在l c a 的基础上提出m l c a 的概念，m l c a 部分改进了l c a 没有考虑节点语义的问题， m l c a 中语义主要表现为x m l 文档中的节点只与某个节点集合中与其最近的节点语义相关。 s a r ac o h e n 等人实现了另一个搜索引擎框架x s e a r c h ，提出了用于判断节点间是否语义相关的 i n t e r c o n n e c t i o n 概念：对于x m l 文档中两个节点，如果两节点到它们最低公共祖先的路径上 没有两个相同标签的节点，认为它们语义相关，否则认为这两节点语义不相关。加利福尼亚 大学的y ux u 等人提出了s l c a 的概念，并给出了计算s l c a 的三种算法：i n d e x e dl o o k u p e a g e r ( i l e ) 、s c a ne a g e r ( s e ) 和s t a c k 算法，使得基于结构的x m l 关键字查询的研究达到了一 个新的水平。v a g e l i sh r i s t i d i s 等人重点研究了关键字结果集中的连接方式，提出了基于栈的 s t a c k - b a s e d a l g o r i t h m ( s a ) 算法【1 0 1 ，有效的返回包含关键字节点间的连接。2 0 0 7 年，亚利桑那 州立大学的z i y a n gl i u 和y ic h e n 研究了关键字的查询结果集，提出并实现了搜索引擎x s e e k ， 通过分析关键字，提出了关键字分类的思想，将查询关键字分成指定查询条件以及表明返回 结果的两类关键字，以此体现更多的查询语义，从而达到减小结果集规模的目的。 国内对x m l 查询的研究，一方面集中在x m l 数据的索引结构【1 5 - 1 7 】上，包括基于结构连 接的索引和基于路径的索引，现有工作大多放在以数据为中心的x m l 数据库存储和检索技术 上。另一方面主要是研究基于关键词的x m l 检索模型【1 剐。 2 t i - d e w e y 码前缀集合的交集，可以得到对应不同层的s l c a 节点。清华大学的李国良、冯建华 等在2 0 0 7 年提出了v a l u a b l el c a ( v l c a ) 算法f 2 0 1 ，改善了l c a 返回结果缺乏语义的问题，他 们又在2 0 0 9 年提出了一种通过分割树返回m e a n i n g f u ls e l f - i n t e g r a lt r e e s ( m s i t r e e s ) 僦1 2 1 | ， 该方法通过人为判定的语义，将x m l 的模式分解成有意义的部分，之后将x m l 划分成一些 s e l f - i n t e g r a l 子树，最后根据算法生成m s i t r e e s 。此外，北京交通大学、复旦大学等的一些学 者【2 2 之5 1 也都对x m l 检索进行了研究。 国内外不少学者都对x m l 文档的关键字查询进行了研究，使得查询在一定程度上能够返 回比较符合用户查询的结果，但x m l 文档查询仍然存在着以下问题： ( 1 ) 已有方法大都以l c a 为基础，对于x m l 文档节点间语义信息获取不足，从而导致查 询结果的准确性往往不高。 ( 2 ) 现有方法不能准确捕获用户的查询意图，往往返回大量不符合要求的结果。 ( 3 ) 在解决查询过程中语义丢失的问题，已有的一些方法需要用户知道x m l 的模式信息 ( 数据组织结构) ，缺乏通用性，从而制约了用户的使用。 1 3 研究目标与内容 x m l 文档具有与平台无关、易于处理、可格式化、语义性强、可扩展性强等特点，使其 成为i n t e m e t 上数据描述和交换的新标准，因此，简单、高效地检索x m l 文档变得越来越重 要。相对于x q u e r y 等传统的x m l 查询方法，关键字查询对用户没有先验知识的要求，也不 需要用户事先掌握复杂的查询语法，它吸收了信息检索简单易用的特点，用户仅仅需要输入 与感兴趣的内容相关的关键字即可完成查询。 通过对国内外研究现状的分析，我们知道目前x m l 关键字查询还存在一定的问题，返回 结果集与用户的查询意图间还存在一定差距。为此本文对x m l 关键字查询进行研究，以期实 现以下目标： ( 1 ) 实现一个用户输入与具体模式文档无关的x m l 文档的检索系统。 ( 2 ) 返回符合用户查询语义的结果，提高系统的查准率。 为了能够达到以上两个目标，本文主要从以下方面进行研究： ( 1 ) 关键字查询语义的获取 x m l 关键字查询结果包含大量不符合用户查询意图的结果，很大程度上是因为对查询中 语义地把握不准确造成的。关键字查询中涉及的语义信息，主要包含文档语义和用户查询语 3 两南人学硕十学何论文 义两部分。对文档语义的获取，不少文献都对其进行了研究，但对用户查询语义的挖掘较少。 x s e e k 对用户关键字进行了研究，提出了关键字分类的思想，但是x s e e k 并没有使两种类型 的关键字充分发挥其各自不同的作用，使得多数情况下仍无法准确捕捉用户的查询意图。因 此本文在现有研究基础上，对文档和用户语义进行挖掘，从根本上提高查询结果的准确率。 ( 2 ) 基于相似度计算的模式无关查询 现有研究很少考虑词汇的扩展，使得用户在准确描述自己查询意图时必须对文档本身结 构有明确的了解，这个要求往往会直接限制用户的使用。通过对用户关键字与x m l 模式信息 中的概念进行相似度计算，可以有效解决用户查询意图表达与文档模式信息的强耦合，实现 x m l 的模式无关查询。因此，本文分析了语义词典w o r d n e t 的概念网络结构图，结合概念相 似度的非对称性，提出一种新的概念相似度算法，以期得到更好的查询效果。 ( 3 ) 语义相关返回结果集 查询返回结果集与查询的准确率息息相关，现有结果集s l c a 及m l c a 缺乏语义相关性， 使得经常返回错误的查询。在此基础上，本文提出了一种新的返回结果集语义相关实体 子树集，试图通过增加结果集中的语义相关性来提高查询结果的准确性。 1 4 研究的技术路线 为了实现综合文档与用户语义的x m l 关键字模式无关查询，本文按照图1 1 所示的方法 进行研究。 4 离 线 处 理 l _ 1 广。 扩展 毒 f ，i i t 雷 囝 当o o 虱 、 义关系。文档语义的获取在用户进行查询之前离线处理，这样可以减少用户查询的响应时间。 第二步规范用户查询语法，捕获用户查询语义。现有研究的查询结果存在不满足条件的 结果，一定程度上是因为对用户查询意图的不明确，而通过制定简单的语法，能够更好分析 用户关键字，抓取用户语义。 第三步在前两步获取语义的基础上，使用w o r d n e t 语义词典，对查询关键字进行扩展， 实现关键字的模式无关查询，得到初始查询结果。 第四步使用第三步中得到的初始查询结果，构建语义相关实体子树集。在求取s l c a 的 算法l i s a 的基础上，给出了求取语义相关实体子树集的相关算法。 整个综合文档与用户语义的关键字模式无关查询方法的基础和难点是x m l 文档模式的解 析；用户查询关键字的分析；基于w o r d n e t 概念相似度的计算，整个方法核心是语义相关实 体子树集的构造。接下来将逐一介绍有关研究内容，全文正文共分为六章，各章的主要内容 如下： 第1 章，主要介绍了x m l 关键字查询的研究背景和国内外研究现状，根据研究提出了一 种综合文档与用户语义的关键字模式无关查询方法的思路。 第2 章，x m l 关键字查询的查询效果与查询过程中语义的获取有重大关联，这一章具体 阐述了查询中文档语义以及用户查询语义的获取策略。 第3 章，针对当前用户查询语义表达与文档模式强耦合的问题，改进了w o r d n e t 概念相 似度计算方法，提出了基于相似度实现模式无关查询的方法。 第4 章，在分析目前返同结果集不足的基础上，提出一种新的返回结果集语义相关 实体子树集，并且给出了相关算法。 第5 章，通过实验对方法进行了分析与评价。 第6 章，总结了论文的研究成果并提出了未来的工作方向。 1 5 本章小结 本章首先阐述了x m l 关键字查询的研究现状和问题，说明了研究综合文档与用户查询语 义的x m l 关键字模式无关查询的背景和意义。然后结合现有x m l 关键字查询存在的问题提 出了本文的研究目标和内容，并且给出了综合文档与用户语义的x m l 关键字查询方法的技术 路线。最后介绍了本文的组织结构。 5 - f ， 一 l ： 、 文档不仅仅描述了数据内容，同时还定义了数据的结构，因此x m l 关键字检索可以做到信息 的精确定位，检索的返同结果为满足条件的x m l 片段。由于现有研究对查询的文档语义以及 用户语义获取不足，导致返回大量不满足条件的x m l 片段，降低了查询的准确率。因此本文 提出了文档语义与用户语义的获取策略，以期从根源上提高查询的准确性。 2 1 文档语义的获取 x m l 是一种元标记语言( m e t a - m a k e u pl a n g u a g e ) ，可以提供描述结构化资料的格式，是用 来描述数据的语言，其具有自描述、可扩展以及数据的结构和表示分离等特征。因此在进行 关键字查询过程中有必要对x m l 文档中的数据进行分析，挖掘出其中隐含的语义信息。 本文采取的文档语义获取流程如图2 1 所示： 图2 1 文档语义获取流程 当用户输入待处理的x m l 文档后，系统查询数据库，判断文件是否已经存储于数据库中。 如果文件不存在，则开始对x m l 文档进行预处理：首先，找出文档对应的模式文档，对x m l 模式文档进行解析，获取文档节点间的组织结构关系；然后，采用s a x 方式遍历x m l 文档 中每个节点，使用关系数据库存储节点的基本语义；最后，为了加快关键字的查询，使用l u c e n e 对文档中的值节点建立全文索引。接下来对处理中各个流程逐一进行阐述。 2 1 1x m l 文档的表示 研究中一般将x m l 数据映射为树状结构，称为x m l 树1 2 4 】：x m l 数据模型采用树状结 构作为数据的组织形式，每份x m l 文档都是一棵有向树，有向树开始于唯一的一个根节点， 向更低级别的树状分支结构扩展；x m l 文档由若干元素组成，每个元素都有一个文档逻辑组 件，而一个元素也可以包含若干的子元素。x m l 文档这种层次结构对应到x m l 树结构中， 节点表示文档中的元素、属性和值，边代表了元素间的嵌套关系。x m l 文档树一般形式化表 示为g = ( v g ，e g ，r ，a ) ，其中：v g 表示树中节点集合；e g 表示树中边的集合；r 为标签有向树的 7 d e w e y 编码是一种前缀编码，每个编码包含了一个节点所在路径上所有节点的d e w e y 码 信息，通过这些信息可以建立与路径有关的关联关系，从而使得在保存结构关系信息的同时 也保存了整个文档的位置编码。x m l 文档以及其对应的带d e w e y 编码的x m l 文档树如图2 2 所示： 8 d e p t h ( c e ) 时，有s i m ( e j ，c g ；，s i m ( c 2 c o 。 f七牛百depth(c：)-depth(c1)，depth(c1)depth(呦 撕忉。”乞卜 塑丝曼笺：，二嘶，二：嘶：，纠 公岚3 18 )d ie p t h s = , 一1 。1 一。 一 其中o ，将e r d i 集合中的d e w e y 编码分别转化为实体 节点i d 号并排序得到：e r d l = 2 ，3 ，e r d 2 = ( 2 ，4