（计算机软件与理论专业论文）基于元素链接的xml信息检索系统的研究.pdf

j r n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n da s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y 1丫5111111i18lll12hl115lljl7lllll6lllll4llllll r e s e a r c ho fx m li n f o r m a t i o nr e t r i e v a l s y s t e m b a s e do ne l e m e n tl i n k s a t h e s i si n c o m p u t e rs c i e n c ea n dt e c h n o l o g y b y y uj i - b o a d v i s e db y p r o f m a oy u g u a n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g m a r c h ，2 0 1 0 一! ；一| i 警 ，、 、 童 、 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京航 空航天大学或其他教育机构的学位或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：，整逵叁 e l 期： 垄f 竺：盖：! 占 4 鼍 矿 ，_ 南京航空航天大学硕士学位论文 摘要 x m l 信息检索是在传统信息检索基础上发展起来的，是数据库领域和信息检索领域相结合 的一门技术。研究表明，x m l 文档中的元素链接关系无论对元素的内容，还是结构都会产生重 要影响，从而影响x m l 信息检索的结果。本文主要针对x m l 文档中的元素链接关系，从x m l 索引技术、x m l 信息检索模型和冗余信息削减等方面展开研究。 首先，提出了一种面向元素链接的x m l 索引技术，该索引包含两部分：文档外部链接索 引和基于p s e u d od e w e y 编码的内部元素索引。其中p s e u d od e w e y 编码是一种基于s c h e m a 的局 部编码方式，每个元素的编码由该元素类型在s c h e m a 中的位置和元素顺序等信息决定；内部元 素索引本身则按照关键字类型、编码的逻辑大小等标准来组织结构。实验表明该索引具有支持 元素链接、检索效率高、更新代价低等特点。其次，提出了一种基于图型建模的x m l 信息检 索模型，该模型充分考虑了x m l 文档中元素链接关系对元素结构的影响；然后根据公共子序 列的长度、位置和比重等因素来计算模型中上下文的相关性值，并得出该模型的上下文相关性 矩阵：最后通过拓展传统向量空间算法来计算元素与用户检索语句的相关性，从而提高了检索 结果的查准率和查全率。最后，建立了一种基于用户检索语句的m a r k o v 链用户浏览模型，并 结合用户浏览历史记录和元素的上f 文信息推导出该模型的转移概率矩阵；然后提出了一种基 于结果集最优相关性的冗余信息削减技术及其贪心法优化方案，实验表明该贪心法优化方案时 间消耗低，执行效率高，具有很好的实用价值。 关键词；x m l 信息检索，元素链接，x m l 索引，p s e u d od e w e y 编码，图型建模，m a r k o v 链， 用户浏览模型 基于元素链接的x m l 信息检索系统的研究 a b s t r a c t x m li n f o r m a t i o nr e t r i e v a li sat e c h n o l o g yd e v e l o p e df r o mt h et r a d i t i o n a li n f o r m a t i o nr e t r i e v a l ， i n t e g r a t e dt h ed a t a b a s ef i e l dw i t ht h ei n f o r m a t i o nr e t r i e v a lf i e l d r e s e a r c hi n d i c a t e st h a tt h ee l e m e n t l i n k si nx m ld o c u m e n ti n f l u e n c en o to n l yt h ec o n t e n to fe l e m e n t ，b u ta l s ot h es t r u c t u r e ，s ot h a t i n f l u e n c et h er e s u l to fx m li n f o r m a t i o nr e t r i e v a l b a s e do ne l e m e n tl i n k st h i sp a p e rr e s e a r c h e so n x m li n d e x ，x m li n f o r m a t i o nr e t r i e v a lm o d e la n dr e d u n d a n c yi n f o r m a t i o np r u n i n gt e c h n o l o g y f i r s t l y , w ep r o p o s ean e wk i n do fx m l i n d e xt e c h n o l o g yb a s e do ne l e m e n tl i n k s ，w h i c hi n c l u d e t w o p a r t s ，t h ee x t e r n a ll i n k si n d e xa n dt h ei n n e re l e m e n t si n d e xw h i c h b a s e do np s e u d od e w e yc o d i n g t h ep s e u d od e w e yc o d i n gi sb a s e do ns c h e m a ，w h i c ht h ec o d i n go fa ne l e m e n ti sd e p e n d i n go nt h e l o c a t i o no ft h ee l e m e n tt y p ei nt h es c h e m aa n de l e m e n to r d e r , a n ds o0 n m e a n w h i l e ，t h ei n n e r e l e m e n t si n d e xo r g a n i z e si t ss t r u c t t l r eb a s e do nc r i t e r i a ，s u c ha sk e y w o r dt y p e s ，t h el o g i cs i z eo f c o d i n g t h ee x p e r i m e n tr e s u l ts h o w st h a tt h i si n d e xt e c h n o l o g yh a st h ec h a r a c t e r so fs u p p o r t i n g e l e m e n tl i n k s ，g o o de f f i c i e n c yi nr e t r i e v a la n dl o w e ru p d a t i n gt i m ec o s t s s e c o n d l y , w ei n t r o d u c ea n e wx m li n f o r m a t i o nr e t r i e v a lm o d e lb a s e do ng r a p h i cm o d e l ，t h en e wm o d e lt a k et h ei n f l u e n c eo f e l e m e n tl i n k si n t oa c c o u n t ，t h e nw ec a l c u l a t et h er e l a t i v i t yo fc o n t e x t sa c c o r d i n gt ot h es i z e ，l o c a t i o n ， p r o p o r t i o no ft h ec o m m o nd e s c e n d a n ts e q u e n c e s ，a n dd e d u c et h ec o n t e x tr e l a t i v i t ym a t r i xo ft h e m o d e l a tl a s t ，w ee x t e n dt h et r a d i t i o n a lv e c t o rs p a c ea l g o r i t h mt oc a l c u l a t et h er e l a t i v i t yb e t w e e n e l e m e n t sa n dl l s e rr e t r i e v a ls e n t e n c e s ，i m p r o v et h ep r e c i s i o na n dr e c a l lo ft h er e t r i e v a lr e s u l t c o n s e q u e n t l y f i n a l l y , w ee s t a b l i s ham a r k o vc h a i nu s e rn a v i g a t i o nm o d e lb a s e do nt i g e rr e t r i e v a l s e n t e n c e s ，a n dd e d u c et h et r a n s i t i o np r o b a b i l i t ym a t r i xa c c o r d i n gt ot h eu s e rb r o w s eh i s t o r yr e c o r d s a n dt h ec o n t e x to fe l e m e n t s t h e nw ei n t r o d u c ear e d u n d a n c yi n f o r m a t i o np r u n i n gt e c h n o l o g y , w h i c h b a s e do ni d e a lr e l a t i v i t yo fr e s u l t ss e t ，a n di t sg r e e d yo p t i m i z a t i o na p p r o a c h t h ee x p e r i m e n tr e s u l t d e m o n s t r a t e st h a tt h eg r e e d yo p t i m z a t i o na p p r o a c hh a s t h ep r o p e r t i e so fl o w e rt i m ec o s t s ，g o o d e x e c u t i o ne f f i c i e n c y , a n di th a sm o r ep r a c t i c a lw o r t h k e y w o r d s ：x m li n f o r m a t i o nr e t r i e v a l ，e l e m e n tl i n k s ，x m li n d e x ，p s e u d od e w e yc o d i n g ，g r a p h i c m o d e l ，m a r k o vc h a i n ，u s e rn a v i g a t i o nm o d e l n 南京航空航天大学硕士学位论文 目录 第一章绪论l 1 1j ；l 言1 1 2x m l 信息检索及其国内外研究现状1 1 3 选题及其本文的主要：l ：作3 1 4 本文的组织4 第二章x m l 信息检索相关知识5 2 1x m l 介绍5 2 2x m l 数据查询语言6 2 3x m l 信息检索7 2 3 1x m l 信息检索与x m l 语言查询的区别7 2 3 2x m l 信息检索与传统信息检索的区别8 2 4x m l 信息检索的检索类型9 2 4 1 基于简单关键字的检索9 2 4 2 基于严格结构和内容约束的检索9 2 4 3 基于模糊结构和内容约束的检索l o 2 5x m l 信息检索举例1l 2 6d 、l ；与l ：! 第三章基于元素链接的数据索引研究1 3 3 1x m l 索引技术。1 3 3 1 1 现有x m l 索引技术分类1 3 3 1 2 现有x m l 索引技术的特点1 4 3 2 建立x m l 索引需要考虑的因素1 5 3 2 1 索引的大小1 5 3 2 2 元素结构关系的获取1 5 3 2 3 元素链接关系的表达1 6 3 2 4 保持元素的顺序1 6 3 2 5 索引对元素更新的支持1 6 3 3 一种基于元素链接的索引技术1 6 哼气 基于元素链接的x m l 信息检索系统的研究 3 3 1x m l 数据模型1 6 3 3 2 文档外部链接索引1 8 3 3 3p s e u d od e w e y 编码技术1 9 3 3 4p s e u d od e w e y 编码的性质2 2 3 3 5 构造基于p s e u d od e w e y 的x m l 索引2 4 3 4 索引对相关更新操作的支持2 7 3 4 1 添加节点的索引修改算法2 8 3 4 2 删除节点的索引修改算法2 9 3 4 3 修改节点值的索引修改算法3 0 3 5 实验研究3 1 3 5 1 索引的大小3 l 3 5 2 索引的检索效率一3 3 3 5 3 索引更新的代价3 4 3 6 ，j 、结3 5 第四章基于图型建模的x m l 信息检索3 7 4 1 引言一3 7 4 2 基于? ( l i n k 的图型建模及其分析3 7 4 2 1 建立文档外部链接索引3 8 4 2 2 改进的文档优先级计算方法p r 3 8 4 3 基于i d i d r e f 1 d r e f s 的图型建模及其分析一3 9 4 3 1 建立基于p s e u d od e w e y 的索引4 0 4 3 2 上下文相关性矩阵4 l 4 3 3 基于上下文相关性的元素矩阵4 3 4 4 实验及结果分析4 5 4 5 ，j 、结4 6 第五章基于m a r k o v 链冗余信息削减技术4 7 5 1x m l 信息检索中用户浏览模型的特点4 7 5 1 1 传统信息检索中的用户浏览预测模型4 7 5 i 2x m l 信息检索中用户浏览模型的特点4 8 5 2 基于检索语句的m a r k o v 链用户浏览模型4 8 5 2 1 基于检索语句的用户浏览模型的建立4 8 5 2 2 用户浏览模型的m a r k o v 性分析5 0 妒 - n 哈 i 【 南京航空航天大学硕七学位论文 5 3 冗余数据削减技术5 2 5 3 1 元素的信息冗余度5 2 5 3 2 基于结果集最优相关性i d r 的冗余数据削减5 3 5 3 3 一种贪心法优化方案5 4 5 4 实验5 5 5 5 小结5 7 第六章总结与展望5 8 6 1 总结5 8 6 2 展望5 9 参考文献6 0 致谢6 4 在学期间的研究成果及发表的学术论文6 5 v 基于元素链接的x m l 信息检索系统的研究 图表清单 图2 1x m l 文档树形结构图6 图2 2b o o k s x m l 部分内容。l l 图3 1 含元素链接的x m l 文档d i 的有向图1 7 图3 2 文档外部链接图1 8 图3 3x m l 文档外部链接索引1 9 图3 4x l v l l 文档对应的s c h e m a 2 0 图3 5x m l 文档的p s e u d od e w e y 编码2 2 图3 6 基于p s e u d od e w e y 编码的x m l 索引。2 6 图3 7 “s t r i n g 索引中对元素链接关系的处理2 7 图3 8 索引运行时间比较3 3 图3 9 各索引支持d b l p 数据集更新的时间代价3 4 图4 1 包含x l i n k 的x m l 文档集3 8 图4 2d l 、d 2 和d 3 的文档外部链接索引图3 8 图4 3x m l 文档实例一4 0 图4 4 文档集基于p s e u d od e w e y 编码的索引。4 1 图4 5 文档集的d g 图和e d g 图示例4 1 图4 6 查全率、查准率曲线图4 5 图5 1x m l 文档实例、p 划分及用户浏览模型4 9 图5 2 穷举法和贪心法求解时间比较5 6 图5 3 初始结果集、穷举法及贪心法性能比较5 6 ， p 表3 1x m l 数据集的统计信息3 2 表3 2 各x m l 索引的大小3 2 。 卜 表4 1 上下文集合s u mc o n t e x t s 4 2 表4 2q 1 、q 2 的检索结果4 5 表5 1 用户浏览模型中节点的上下文信息5 l 表5 2 用户浏览历史记录5 2 南京航空航天人学硕十学位论文 x m l i r 斟e x s l c a v s m u n m w 3 c s g m l c o s c a s v c a s u r j d o m d t d 注释表 e x t e n s i b l em a r k u pl a n g u a g e i n f o r m a t i o nr e t r i e v a l i n i t i a t i v ef o rt h ee v a l u a t i o no fx m lr 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 v e c t o rs p a c em o d e l u s e rn a v i g a t i o nm o d e l w b r l dw i d ew b bc o n s o r t i u m 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 c o n t e n to n l y s t r i c tc o n t e n ta n ds 咖c t u r e v a g u ec o n t e n ta n ds t r u c t u r e u n i f o r mr e s o u r c ei d e n t i f i e r d o c u m e n t0 b j e c tm o d e l d o c u m e n tt y p ed e f i n i t i o n 重 南京航空航天人学硕十学位论文 1 1 引言 第一章绪论 随着互联网的迅猛发展和普及。人们可以通过计算机与且联网连接，从世界各地实时地接 收和发送大量、最新的信息，但在信息交换的过程中存在着一个突出的问题，就是多种多样的 数据格式。给信息的有效使用带来了障僻。所以在信息时代。如何以最便捷、最可靠、最有效 的方式获取所需信息是一个很人的困扰。人们期待着能够找到一种可以描述任何逻辑关系的数 据格式米统一电子数据的存储，从而不雨冈为数据格式的不统一而苦恼和困惑。目前，能够担 当此任的就是x m l ( e x t e n s i b l em a r k u pi _ m l g u a g e 可扩展符号化语言) ，它已经成为i n t e m e t 以及电子商务中进行数据表示和数据交换事实上的标准。对于传统的结构化数据和无结构的文 本数据，我们都已经拥有比较成熟的管理技术和。l ：具，结构化的数据可以采用关系型数据库或 对象型数据库进行管理，而无结构的文本则可以采用信息检索( 承) 的方式进行访问。而对于 如x m l 的半结构化数据，如何进行有效的管理，包括存储、索引、查询等，是当前亟待解决 的问题。x m l 信息检索作为一门帮助用户从人鹫结构复杂的x m l 数据中快速找剑需求信息的 技术，受到了越来越多的关注i l j 。 1 2x m l 信息检索及其国内外研究现状 x m l 信息检索是数据库领域与信息检索领域的结合，其概念是根据x m l 文档的内容和结 构信息，以及用户的检索需求，通过相关技术从x m l 文档中找出能满足用户在内容以及结构 方面约束的元素集合；并通过相关的计分算法，将元素以优先级的顺序返回给用户。 国外对x m l 数据的信息检索研究开始于8 年前，随即成为d b 和瓜界研究热点之一。第 一个世界性的x m l 信息检索相关学术论坛是i n e x ，i n e x 是i n i t i a t i v ef o rt h ee v a l u a t i o no f x m lr e t r i e v a l 的简称，它是在d e l o sn e t w o r ko f e x c e l l e n c eo nd i g i t a ll i b r a r i e s 和i e e e 的支持 下，由德国d u i s b e r gu n i v e r s i t y 的n o r b 鲥f u h r 教授和英国q u e e nm a r y ，u n i v e r s i t yo fl o n d o n 的m o u n i al a l m a s 教授负责发起的专门致力于x m l 信息检索与评价的国际性学术论坛，i n e x 的主要任务是为参加者提供相应的x m l 数据集、实验平台、实验评价方法和标准等，参加者 需根据i n e x 的要求在不同阶段完成不同的实验和任务，并在最后阶段提交检索的实验结果。 i n e x 将根据一定的x m l 信息检索评价方法，对各参加者提交的检索结果进行评价，并将评价 结果发布给所有参加者，以供进一步研究之用。每年一次的i n e x 会议吸引了众多研究机构与 学者参与x m l 信息检索问题的讨论。 l 基丁元素链接的x m l 信息检索系统的研究 国外现有的x m l 信息检索工作主要体现在四个方面： ( 1 ) x m l 的信息检索语言。或者延伸瓜的关键词检索，或者延伸x m l 查询语言( 如 x p a t h 、x q u e r y ) 。n e x i l 2 l 采用类x p a t h 语法，在查询表达式中加入“c o n t a i n s ”操作符，是传 统的基于x p a t h 的查询可以包含关键字的检索，n e x i 是i n e x 官方定义的一种x m l 检索语言； x 取q l l 3 】支持索引、排序、相关度查询，但语法复杂不适合普通用户；泌n k f 4 】延伸类似w e b 关键词检索至x m l ；x k s e a r c h 5 】支持关键词检索，返回s l c a ( s m a l l e s tl o w e s tc o m m o n a n c e s t o r ) 节点；t e x q u e r y l 6 1 提出了可组合的全文检索元语，检索语句嵌入x q u e r y 中。 ( 2 ) x m l 信息检索的模型。主要是将传统w e b 信息检索中的模型扩展到x m l 信息检索 领域，比如自然语言模型( n a t u r a ll a n g u a g em o d e l ) 、向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 、 上下文相关性模型( c o n t e x t u a l i z a t i o nm o d e l ) 、基于关键字权重的概率模型、基于本体的模型、 基于概念的模型。 ( 3 ) 计分排序算法。主要也是将传统w e b 信息检索领域的计分排序算法扩展到x m l 信息 检索领域，通常的做法是在计分排序算法中加入结构的因素。目前有基于词频和本体相似度计 分 7 1 、向量空间计分建模【8 】、概率计分建模p i ，标准化合并排序 9 1 、基于检索放松调整t f * i d f 的 小枝计分( t w i gs c o r i n g ) 、路径计分( p a t hs c o r i n g ) 和二元计分( b i n a r ys c o r i n g ) 方法等。 ( 4 ) x m l 信息检索系统性能评价的指标。传统的检索评价方法是以查全率( r e c a l l ) 和查 准率( p r e c i s i o n ) 为基础的。对于全文检索，在此基础上提出了相应的评价方法如f - m e a s u r e ， r - p r e c i s i o n ，a v e r a g ep r e c i s i o n 以及m e a na v e r a g ep r e c i s i o n 等等。对于x m l 检索来说，由于其 评价的是元素而非文档的相关性，因而需要有新的评价方法。i n e x 从两个角度考察元素的相 关性，即穷尽性( e x h a u s t i v i t y ) 和专指性( s p e c i f i c i t y ) 。穷尽性是指元素覆盖检索主题范围的 程度，分为完全穷尽、部分穷尽、相关但元素太小以及完全无关四个层次；专指性是指元素与 主题相关的程度( 即元素描述该主题的内容比例) ，其范围从0 到l ，0 为不相关，l 为全部相 关。i n e x 在这两个指标的基础上提出了2 0 0 5 年的官方检索模型n x c g 和印。此外，也有学者 提出了改进的评价模型如e p r u m 和h i r e x 等。然而，总体看来，x m l 的检索评价方法还存在 很多争议，不管是官方模型、还是提出的改进模型，都有需要进一步完善的地方，如官方模型 中关于太小元素的处理问题、元素穷尽性的级别划分问题、专指性的计算方法问题等都需要进 一步完善。 近两年国内学者对基于x m l 的信息检索技术研究主要在如下两个方面进行了积极的探索： 对传统x m l 数据索引结构的优化研究，集中体现在基于结构连接的索引和基于路径的索引， 通过这些优化减小了索引的大小，加快了对路径表达式的检索。但是x m l 信息检索的目标不 是基于精确的路径查询，而是元素与用户检索要求的内容和结构匹配，所以可以考虑从这个方 向来设计索引基于关键词的x m l 检索模型研究，然而x m l 有内容也有结构，检索满足用 2 ， 一 参 南京航空航天大学硕士学位论文 户特定需求的x m l 元素，不仅需要检索关键词，还应检索x m l 元素的上下文( 即路径结构) 信息，现有：i ：作在结构与内容检索结合方面研究得不够。此外，现有工作在x m l 排序机制方 面( 即如何在x m l 元素层上计算语义相关度，如何计算检索结果在关键词和路径语义匹配上 的得分) 做得相当有限。 总体而言，现有国内外组织机构对x m l 信息检索的研究主要体现以下特点： ( 1 ) 多数x m l 信息检索系统都是采用传统的基于元素结构的x m l 索引，并集中体现在 基于结构连接和路径的索引。这些索引的工作较多放在以数据为中心如何存储和检索x m l 数 据的数据库技术，对以文档为中心带排序支持的x m l 索引研究较少：而且这些索引技术对x m l 文档中元素之间的链接关系考虑得较少，索引更新的代价也较高。 ( 2 ) 多数：i = 作采用层次树型对x m l 建模，而x m l 文档中还存在文档到文档、元素到元 素的链接( 由x l i n k 或d i d i 也f ，m r e f s 指出) ，同传统w e b 信息检索一样，这些链接对于元 素相似度的计算会产生影响；同时x m l 文档中的元素链接使元素之间往往形成“图型”的关 系。因此，基于图型结构的x m l 文档建模值得探讨。 ( 3 ) x m l 信息检索结果对用户的友好度不够，现有信息检索技术的返同结果中包含大量 的冗余信息，其中包括重叠的元素，语义信息较少不易理解的元素；而且基于计分的排序方式 可能会导致用户多次观察相同的数据，这样既浪费了空间，也浪费了用户的浏览时间和效率。 因此可以考虑结合用户浏览模式( u s e rn a v i g a t i o nm o d e l ，u s m ) 对x m l 信息检索的结果进行 处理，从而减少检索结果集中的冗余信息，提高用户信息检索的速率。 1 3 选题及其本文的主要工作 结合国内外x m l 信息检索研究的现状以及特点，本文以面向元素链接的x m l 信息检索索 引，基于图型模型的建模，以及结果集中冗余信息削减的研究为题，也就是本文的主要工作， 具体包括以下几个方面： ( 1 ) 针对当前x m l 信息检索中索引的特点：面向精确查询，快速的路径定位，没有充分 考虑元素链接关系，对关键字查询的支持不够等等，提出了一种新的索引技术。该索引技术不 仅包含了文档外部链接索引，主要用于记录文档间的链接关系；还包含一个基于p s e u d od e w e y 编码的索引，索引中节点的位置信息通过一种仿杜威码的区间编码( p s e u d od e w e y 编码) 来表 达，通过该编码可以方便地表达元素的链接关系，定位节点所处的文档，确定节点间的结构关 系，节点的所有祖先节点编码，节点和祖先的标记名称，以及节点所包含的关键字信息：然后 对常见的x m l 数据更新方式：插入元素、删除元素、修改元素的值信息，设计了相关算法来支 持x m l 索引对应的更新，并分析了算法的时间复杂度。 ( 2 ) 分析了基于树型模型的检索技术存在的两个方面不足：每个x m l 文档不应当被看 3 基于元素链接的x m l 信息检索系统的研究 成一个单独的个体，w e b 上的所多x m l 文档之间都存在着密切的联系，同h t m l 的h y p e r l i n k s 一样，w 3 c 也为x m l 数据提供了一种类似的外部链接( x l i n k t l 0 1 ) ，通过x l i n k 每个x m l 文档都 可以与其它x m l 文档建立外部链接，显然这些链接关系对x m l 信息检索是很有价值的。同 h t m l 一样，x m l 也有自己的内部链接( m m r e f ，i d r e f s 1 1 1 ) 形式，m 佃i 迮f ，d r e f s 的功 能是通过x m l 文档的内部连接，建立x m l 文档内部元素之间的联系，这些内部联系对x m l 信 息检索也是很有价值的。但是基于树型模型的信息检索技术只是将x l i n k 和i d i d r e f i d r e f s 当成一种普通的属性元素，没有考虑链接的影响。本章通过考虑x l i n k 和m r e 【d r e f s 带 来的文档与文档之间、元素与元素之间的联系，提出了一种基于图型模型的x m l 建模，并在此 基础上拓展经典的向量空间算法 1 2 , 1 3 ，详细描述了一种新的基于元素上下文相关性矩阵的x m l 信息检索技术。 ( 3 ) 分析了现有x m l 信息检索系统返回结果集的一些问题：如包含太多冗余信息，用户 多次浏览重复的元素。在比较传统w e b 信息检索中用户浏览模型同x m l 信息检索中用户浏览模 型区别的基础上，提出了一种基于用户检索语句的m a r k o v 链用户浏览模型，并结合用户浏览历 史记录和元素上下文信息计算出该模型的状态转移矩阵，然后根据该模型设计了一种基于结果 集晟优相关度的冗余信息削减技术，并提出了该技术的贪心法优化方案。 1 4 本文的组织 本文共分为6 章，各章的内容安排简要描述如下： 第一章介绍了x m l 信息检索的基本知识及其国内外的研究现状，选题的依据以及本文的 主要工作和组织结构。 第二章介绍了x m l 的基本知识、x m l 查询语言、x m l 信息检索及其3 种检索模型，并 举例进一步说明了x m l 信息检索的相关知识。 第三章介绍了一种新的基于元素链接的x m l 信息检索索引，包含文档外部链接索引和内 部元素索引，文档中元素的位置信息和链接关系采用p s e u d u d e w e y 编码来表示，并定义了一 组支持x m l 文档更新的索引更新算法。 第四章介绍了一种基于图型建模的x m l 信息检索模型，该模型分析了x m l 中文档与文档 链接，元素与元素链接对信息检索结果的影响，并采用一种上下文相似性矩阵来计算元素与检 索语句的相关性并通过实验证明了该模型具有较好的查准率和查全率。 第五章介绍了一种新的检索结果处理技术，通过m a r k o v 链用户浏览模型对结果集冗余信 息进行削减，使返回的结果更有利于用户浏览，并快速地获取所需要的信息。 第六章进行了相关总结和展望。 4 r ， 摹 南京航空航天人学硕+ 学位论文 第二章x m l 信息检索相关知识 本章主要介绍了x m l 相关的基础知识，其中包括x m l 查询语言，x m l 信息检索的详细 叙述，并且细致分析了x m l 信息检索的检索模型，最后通过示例来进一步理解x m l 信息检索。 2 1 l 介绍 x m l 是由w 3 c 于1 9 9 8 年2 月发布的一种标准。它同样是s g m l 的一个简化子集，它将 s g m l 的丰富功能与h t m l 的易用性结合到w e b 的应用中，以一种开放的、自我描述方式定 义了数据结构。在描述数据内容的同时能突出对结构的描述，从而体现出数据之间的关系。这 样所组织的数据对于应用程序和用户都是友好的、可操作的。 x m l 与h t m l 的比较【1 4 】： ( 1 ) x m l 不是h t m l 的替代。实际上x m l 可以视作对h t m l 的补充。x m l 和h t m l 的目标不同：h t m l 的设计目标是显示数据并集中于数据外观，而x m l 的设计目标是描述数 据并集中于数据的内容。 ( 2 ) 与h t m l 相似，x m l 不进行任何操作。虽然x m l 标记可用于描述订单之类的项的 结构，但它不包含可用于发送或处理该订单以及确保按该订单交货的任何代码。其他人必须编 写代码来实际对x m l 格式的数据执行这些操作。 ( 3 ) 与h t m l 不同，x m l 标记由架构或文档的作者定义，并且是无限制的，h t m l 标记 则是预定义的：h t m l 作者只能使用当前h t m l 标准所支持的标记。 x m l 实例： e v e r y d a yi t a l i a n o i a d ad el a u r e n t i i s 2 0 0 5 3 0 0 0 h a r r yp o t t e r jk r o w l i n g 5 基于元素链接的x m l 信息检索系统的研究 2 0 0 5 2 9 9 9 x m l 树形模型： 每篇x m l 文档对应一个树形模型，上例中的x