硕士学位论文基于XML关键词检索的索引技术以及相关算法研究

1、硕士研究生学位论文题目：面向xml关键词检索的索引技术及其相关算法研究与实现姓 名： 学 号： 院 系： 信息科学技术学院 专 业： 算机应用技术 研究方向： 智能商务与web智能 导师姓名： 二0一0 年 六 月版权声明任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。摘要自从xml诞生以来，越来越多的数据以xml文档格式存储和发布，xml已经成为internet和intranet上数据集成和交换的标准，被广泛应用于电子商务、内容管理、多媒体、数字图书馆以及中间件

2、等众多的领域。如何高效的的索引、存储以及检索互联网上的xml数据成为一个具有显著现实应用意义的研究课题。xml数据与传统文本数据的最大区别是：xml数据含有丰富的层次结构信息。这使得xml能够更加精确地描述数据以及数据之间的关系。如何将xml数据所包含的层次结构信息存入索引中并使之能支持高效的关键词检索算法成为xml关键词检索研究中的核心问题之一。dewey编码是一种能有效保存xml层次结构信息的方法，也是目前关键词检索中最流行的方法之一。研究人员提出了很多基于dewey编码的检索算法，如栈算法、scan eager算法等。但是，dewey编码有两个明显的不足：首先，xml元素的dewey编码

3、长度与xml元素在xml树中的深度成正比；其次，在很多算法中，比较两个dewey编码大小的操作是一个原子操作，而比较两个dewey编码大小的时间复杂度是o(n)，其中n为杜威编码的长度，在处理大规模的xml数据集时，这将严重影响检索算法的性能。为了克服dewey编码的不足，本文提出了laf编码策略，对于任意一个xml元素，其编码的长度恒为3；在laf编码基础上，结合xml文档的自身特征，设计了一种能支持高效xml关键词检索算法的二层索引结构；最后，文章实现了一个基于堆的高效xml关键词检索算法hba，hba算法能有效支持各种xml检索语义模型。通过在多个数据集上的对比实验，与传统的索引方法相比

4、，基于laf编码的二层索引方法具有较大的空间效率优势；与传统的关键词检索算法相比，hba算法不仅具有较大的时间效率优势，而且hba算法能有效支持各种xml关键词检索语义模型。关键词：xml关键词检索; laf编码; hba; 二层索引; slcaresearch on indexing technique and related algorithm for xml keyword searchyongqing xiang (computer application)directed by kunqing xie and zhihong dengabstractsince xml was pro

5、posed, more and more data has been stored and published in xml format. xml has become the standard of integration and exchange of data on the internet and intranet. xml documents are widely used in e-commerce, content management, multimedia, digital libraries, the middleware and many other fields. h

6、ow to efficiently index, store and search xml data has become a very valuable problem.the biggest difference between xml data and plain text is that xml data has structure information besides content. this helps xml to describe data more accurately. how to code the hierarchy information into indices

7、 for supportting highly efficient keyword search algorithm is one of the core issues in the field of xml keyword search. dewey number is an effective method to code hierarchical information. many algorithms based on dewey number are proposed. however, dewey number has two obvious shortcomings. first

8、ly, the length of the dewey number for an xml element increases with the depth of this element in a xml tree, which may cause indexing redundancy when processing large scale documents set; secondly, many algorithms based on dewey numbers need to sort elements according to the lexicographic order of

9、dewey numbers, the complexity for comparing two dewey numbers is o (n) (here n is average length of dewey numbers), which will be unacceptable in processing large scale xml documents set.to overcome the disadvantages of dewey number, we propose laf numbering strategy in this paper. for any xml eleme

10、nt, the length of its laf number is constantly 3; based on laf number, we devise a kind of new index structure, called two-layer laf inverted index, which can greatly decrease the space complexity compared to dewey number based inverted index. further more, we proposed a new keyword query algorithm

11、based on two-layer laf inverted index called hba, which can quickly find all slcas for multi xml documents set.we experimentally evaluate the two-layer laf inverted index and hba algorithm on real xml document sets and synthetic document sets generated using the xmark benchmark. our experimental res

12、ults show that our method offers both space and performance benefits when compared with existing approaches.keywords: xml keyword search; laf numbering; hba; two-layer; slca目录摘要iabstractii第一章研究背景11.1xml简介11.2xml检索21.3xml关键词检索41.4本文工作以及创新点61.4.1问题的提出61.4.2本文主要工作81.4.3本文主要创新点91.5本文组织结构91.6本章小结10第二章xml

13、关键词检索相关概念及技术112.1xml数据模型122.2检索语义模型132.3本章小结15第三章laf编码163.1xml元素编码概述163.2dewey编码163.2.1dewey简介163.2.2dewey编码的不足183.3laf编码183.3.1laf编码简介193.3.2laf编码的性质203.4本章小结21第四章基于laf编码的二层索引结构224.1dewey倒排索引224.2二层索引模型234.2.1xml文档的二重属性234.2.2二层索引244.3空间效率比较254.4本章小结26第五章hba检索算法275.1引言275.2基于dewey编码的检索算法275.2.1求解el

14、ca的栈算法275.2.2求解slca的scan eager算法285.3hba算法295.3.1数据结构295.3.2hba算法描述305.3.3算法实例335.4本章小结36第六章实验结果与相关分析376.1实验环境376.1.1软硬件环境376.1.2实验数据集简介386.2原型系统简介396.2.1系统结构396.2.2xml文档解析396.2.3索引系统406.2.4检索系统416.3空间效率比较426.4时间效率比较436.5本章小结46第七章总结与展望47参考文献48发表论文列表52参加项目53致谢54第一章 研究背景1.1 xml简介随着互联网技术的发展，一方面使得互联网上的数

15、据量呈爆炸式增长，另一方面也使得数据表达的手段越来越丰富。由于信息量的增长和表达手段的丰富，html的缺点日益暴露出来。首先，html文档不包括结构信息，难以适应互联网发展对数据描述精确性的需求；其次，html文档缺乏自描述性，不能提供表达元数据信息的有效手段。html的上述缺点限制了其在更多领域的推广和应用。html是一种有效的数据表达工具，但并不适合数据传输、数据集成和数据存储的应用场合。1998年，w3c（the world wide web consortium）颁布了xml1.0（extensible markup language）标准。xml允许用户自定义标签，并通过标签和标签之

16、间的结构关系携带更多更精确的信息，其中标签用于解释文本的内容，标签间的结构则用于解释文本间的结构关系。xml在很大程度上弥补了html在数据描述应用上的不足，自诞生之日就被寄予厚望。经过十多年的发展，目前，xml已经广泛应用于电子商务、数字图书馆、内容管理、中间件以及语义网等领域，越来越多的数据以xml的格式进行存储和发布，并形成趋势，如ieee inex、library of congress documents、sigmod和dblp等。与传统html格式文本相比，xml数据具有如下的一些优势。首先，xml具有非常广泛的开放性，它允许各个组织、个人建立适合自己需要的标签集合，并且这些标签可

17、以迅速地投入使用。这一特征使得xml可以在电子商务、政府文档、司法、出版、cad/cam、保险机构、厂商和中介组织信息交换等领域中大展身手，针对不同的系统、厂商提供各具特色的独立解决方案。 第二，xml的分离性使xml的数据存储格式不受显示格式的制约。一般来说，一篇数据文档包括三个要素：数据、结构以及显示方式。对于html来说，显示方式内嵌在数据中，这样在创建文本时，要时时考虑输出格式，如果因为需求不同而需要对同样的内容进行不同风格的显示时，要从头创建一个全新的文档，重复工作量很大。此外html缺乏对数据结构的描述，对于应用程序理解文档内容、抽取语义信息都有诸多不便。 第三，xml把文档的三要

18、素 (数据、结构、显示方式) 独立开来，分别处理。首先把显示格式从数据内容中独立出来，保存在样式表中，这样如果需要改变文档的显示方式，只要修改样式表就行了。xml文档的结构则由dtd或者xml schema确定。第四，xml的自我描述性质能够很好地表现许多复杂的数据关系，使得基于xml的应用程序可以在xml文件中准确高效地搜索相关的数据内容，忽略其他不相关部分。1.2 xml检索xml的出现无疑是互联网发展史上一个非常重要的里程碑，随着xml应用的成熟，大量的xml文档被用来传递和存储和交换数据，用户如何有效的检索并且利用这些数据成为了互联网应用的又一重大挑战。此外，在最近研究很热的语义网中，

19、xml也是处于一个基础核心的地位。因此，xml检索对实现面向语义网的语义检索也有非常重大的意义。虽然目前的html搜索引擎也可以用于xml文档的检索，但是这些搜索引擎都没有充分体现xml文档的结构优势，因此，对面向xml文档的信息检索研究就成了一件非常有意义的事情。xml搜索引擎与传统搜索引擎的区别以及带来的挑战主要表现如下：(1) 在进行xml文档检索时候，不仅要考虑文档的内容，更重要的是要考虑文档的内部层次结构，这样才能体现xml比html在结构上的优势，考虑文档的结构使得关键词之间的关系变得更加复杂，给xml检索带来了新的研究空间。(2) 在xml检索中，为了提高用户查询的精度，根据不同

20、用户的需要，可以返回不同粒度的文档。比如可以和传统html检索一样返回一整篇文档；有时候为了更加精确定位信息，需要的也许仅仅是xml文档中某一个元素的信息。对于文档粒度问题的考虑，给xml检索在索引结构建立、词频统计、词汇权重计算等方便带来了新的挑战。(3) 如何有效的将xml文档中所包含的层次结构信息保存到索引中，并且使得索引能够有效支持高效的检索算法。xml文档除了含有文本信息之外，最重要的是它能够体现文本之间的结构关系，这种关系能够起到更加精确描述数据的作用。如何有效保存这种结构信息到索引中关系到xml检索的精确性和xml检索系统的效率。(4) 如何定义xml检索的结果模型以及如何设计高

21、效的xml检索算法。由于xml检索不仅可以返回整篇文档，也可以返回xml文档内部的元素，因此，什么样的内部元素才是最佳的结果这个问题在xml检索中就显得非常重要。在确定了检索结果模型后，最重要的是要设计出支持这种模型的高效检索算法，即如何才能够高效地从大规模的xml文档集中找出符合这种结果模型的所有结果。xml信息检索已成为国际数据管理和信息检索等相关领域的研究热点。2002年，ieee和delos成立了专门的xml信息检索研究和性能评估机构inex (initiative for the evaluation of xml retrieval)1。2007在北京召开的sigmod大会上，国际

22、数据管理界著名学者，美国计算机学会会士（acm fellow），德国马普信息研究所（max-planck institute for informatics）数据库与信息系统部主任 gerhard weikum 教授做了题为“db & ir: both sides now”的大会特邀报告2，xml信息检索方面的内容是该特邀报告的重点之一。随后，vldb 2007和sigmod 2009分别就xml信息检索设立专门的研讨会34。xml信息检索可分为两大类：关键词检索和“关键词结构”检索。由w3c颁布的xml检索标准xpath和xquery是“关键词+结构”检索的代表，“关键词结构”检索在为用户准

23、确表达其查询需求方面提供了有效的描述手段，从而能获得高质量的查询结果。但是“关键词结构”检索要求用户掌握相关的查询语言，并且对xml文档的结构信息有所了解，从而限制了这种检索方式在实际中的应用范围。为了提供对xml数据库的查询支持，面向xml数据库的查询语言xql5也被应用在许多xml数据库中。无论是xpath和xquery，还是xql，都要求用户知道文档的内部结构并且需要熟悉这些查询语言的基本语法，这对于普通用户来说是不能接受的也是没有必要的。关键词检索一种经过实践证明且取得巨大成功的检索方式，是在传统搜索引擎中被广泛采用的检索手段。在传统搜索引擎的影响下，普通互联网用户现在已经习惯于关键词

24、检索方式，因为关键词检索简单易用，能迅速被普通用户所掌握。因此，xml关键词检索比“关键词结构”检索更具有现实应用意义。xml关键词检索也因此成为了xml信息检索领域的研究重点。xml关键词检索即用户以关键词作为表达查询的手段对xml文档（集）进行检索的模式。由于xml文档是包含层次结构信息的，而关键词检索只能模糊的表达用户的查询语义，如何通过关键词检索，充分利用xml文档内部的结构信息，来为用户提供精确的检索服务就是一件非常有现实意义且具有极大挑战性的事情。本文将从xml关键词索引和检索算法两个方便来探讨xml关键词检索相关技术。1.3 xml关键词检索xml关键词检索已经得到国际数据管理和

25、信息检索等领域研究人员的广泛关注，国内外知名大学和研究机构从索引结构、查询语义、结果排序和查询算法等方面研究了xml关键词检索面临的问题，其中有代表性的研究成果如下。美国康纳尔大学研发的xrank系统采用树结构作为xml文档的数据模型，基于lca提出elca作为查询语义模型。在索引结构方面，xrank7采用杜威编码方法(dewey number)对xml中的元素进行编码，并对编码的元素采用倒排技术进行索引，采用elemrank作为结果排序的方法。基于杜威编码的倒排索引有效解决了内容和结构信息统一索引问题，因此，已经成为目前xml关键词检索系统的主流索引技术。xrank首次在xml关键词检索中引

26、入了top-k查询处理技术来实现对用户查询请求的快速响应。以色列耶路撒冷希伯莱大学的xsearch是以语义查询作为主要研究内容的xml关键词检索系统。xsearch以树结构作为xml文档的数据模型，提出以lca为基础的ir作为查询语义模型，并实现了求解ir的算法。美国加利福尼亚大学圣迭哥分校在xrank的基础上通过进一步研究杜威编码和xml树结构的性质研发了基于树模型的xml关键词检索系统xksearch。xksearch基于lca提出新查询语义模型slca，并提出了有效的求解slca的查询算法8。亚利桑那州立大学研发了xseek系统91011、extract系统1213和xred系统14。x

27、seek把xml与数据库中的实体关系模型建立对应关系，利用实体关系的方法分析xml结构，基于对xml结构的分析和关键词匹配模式，xseek有可能生成更符合用户查询需求的结果，xseek的查询语义模型仍然是基于lca的，只不过增加了实体关系的限制。extract以xseek输出的检索结果为处理对象，抽取出其中的重要信息生成摘要树呈现给用户。 xred系统主要解决结果分化（result differentiation）的问题，为用户提供一种对xml检索结果自动组织的服务，方便用户浏览、察看和分析结果。xred可以任何xml关键词检索引擎输出的结果为处理对象，获取其中的dfs（differentia

28、tion feature set），以dfs为基础、以表格为形式输出具有最大区分展示度的结果。新加坡国立大学研发的xreal 系统15把搜索意图识别、搜索结果获取和面向相关排序等融合转化成xml检索中的一个问题，并基于xml数据的统计信息借鉴信息检索中的方法予以解决，统一解决用户搜索意图识别、关键词歧义以及结果排序等问题。实验表明xreal比xksearch和xseek更为有效。研发xreal 系统的相关科研人员基于杜威编码提出了dde（dynamic dewey，动态杜威编码)16 。当xml数据发生更新，dde的可以完全避免重新编码。近几年，国内相关研究人员在xml关键词检索方面也取得了一

29、定的成果。17把面向节点的lca泛化到面向标签路径的plca，提出了一种有效的索引结构pn-inverted和基于plca的查询算法用于支持xml关键词检索。18利用euler序列来对xml树进行编码，并在此编码的基础上建立倒排索引并设计了求解slca的算法。19根据slca节点按“层”分布的规律，基于逐层求解的思想提出了有效发现slca节点的新方法lisa。20引入vlca的概念并在其基础上定义cvlca作为查询语义模型，利用cvlca的特性提出高效的查询算法。21对信息检索中的几种典型内容相似性度量方法应用于xml关键词检索进行结果排序的效果进行了深入的分析。22通过先扩展查询词,再在扩展

30、查询词的基础上进行结构查询扩展，最终形成“内容+结构”查询来实现查询扩展。在国家高技术研究发展计划（863）项目“高性能xml关键词检索系统及其关键技术的研究”（2009aa01z136）和北京大学富士通青年研究基金“xml文档检索研究”的支持下，我们组在xml关键词检索方面开展了系统的研究工作。在系统研制方面，我们组开发了面向xml文档的关键词检索原型系统23。在查询算法设计方面，我们以树的杜威编码为基础,分析并证明了slca的两个重要性质，并在其基础上提出了基于二分迭代查找的nearest pair算法24，将求解中间结果的计算量降低了一个数量级，从而使得该算法的性能在绝大多数情况下优于现

31、有主流算法。在查询语义模型研究方面，发现slca等查询语义模型可能忽略了部分结果，而这些结果正是用户需要的，在此基础上，我们提出了新的查询语义模型xtree25并设计和实现了相应的查询算法。在结果排序方面，我们提出了基于机器学习的排序方法listbm26。 在inex 2008 xml信息检索测试文档集上的实验表明listbm要优于传统的okapi bm25。在top-k查询处理方面，通过综合考虑分值排序序列（score-sorted-sequence） 和杜威id排序序列（dewey id-sorted-sequence）我们提出了面向slca查询语义的有效top-k查询算法27。在索引设计

32、方面，通过结合传统倒排索引和基于杜威编码的xml节点索引的优点，我们提出面向xml文档的二级索引模型28，并实现了基于二级索引的求解slca的栈算法。1.4 本文工作以及创新点1.4.1 问题的提出由于xml文档不仅不含文本内容，更重要的是它包含丰富的结构信息，因此，如何将这种结构信息完整无损的保存到xml索引中以及在这种索引的基础上设计高效的检索算法成为xml关键词检索需要解决的核心问题之一。(1) 如何将xml文档中的层次结构信息保存到xml索引中？在xml关键词检索中，一种有效的保存xml文档结构信息的办法是对xml文档中的元素进行编码，这个编码能够唯一确定该元素在xml树中的位置。de

33、wey编码是目前一种非常流行的xml元素编码方式，它能有效地将xml文档中的机构信息保存到倒排索引中。6第一次将dewey编码用于对xml元素进行编码。781920293031都采用dewey编码作为xml元素的编码方式来进行xml关键词检索的相关研究。32提出利用区间编码(interval encoding)对xml元素进行编码，该编码的主要思想是将xml元素在对应xml树的前序遍历序号pre和后续遍历序号post组成数对(pre, post)作为元素的编码，这种编码也能唯一确定元素在xml树中的位置，但这种编码不易扩展也不易理解，很难设计出基于区间编码的高效xml关键词检索算法。33提出利

34、用素数对xml元素进行编码，素数编码的思想来自于判定两个整数是否具有整除关系的规则：整数间非整除关系的判定规则(indivisibility)：如果整数a的素数因子中不存在整数b的素数因子，那么，b对a是不能整除的。 素数编码的缺点是，素数的获取不是一件很容易的事情，而且随着xml树中元素的增加，需要的素数也是越来越多，素数也在越变越大，这将大大降低索引的空间效率和检索算法时间效率。34采用ordpath方法来对xml元素进行编码，该编码是对dewey编码的一种改进形式，它与dewey编码相比，主要优势是能够节省索引空间，但是34并没有提出有效支持ordpath编码的检索算法。dewey编码作

35、为一种主流的xml元素编码方法，它的确能有效保存xml文档的结构信息并且支持较为高效的检索算法。但是，仔细研究发现，dewey编码的空间效率其实是不高的，因为元素对应的dewey编码的长度与该元素在xml树中的深度是成正比的，dewey编码是通过重复保存元素父节点的dewey编码作为当前元素dewey编码的前缀来保存xml的层次结构信息的，因此，在处理大规模xml文档集时，dewey编码的空间效率可能会很低。(2) 如何设计高效的xml关键词检索算法？dewey编码被用作对xml元素进行编码的工具后，很多基于dewey编码的检索算法也都被提出来。7提出利用基于dewey编码的栈算法来求解xml

36、检索结果，栈算法以elca模型作为查询语义模型，栈算法能有效的求解elca结果。8在栈算法的基础上，提出了一种新的检索语义模型slca，并且提出了求解slca的scan eager算法和look-up eager算法。slca模型基本能满足用户的查询需求，是目前较为流行的一种检索结果模型，本文将主要采用slca作为检索结果模型。栈算法和scan eager算法以及look-up eager算法是目前引用次数最多的几个检索算法，本文将比较hba和这几种算法的检索效率。19提出利用lisa算法来求解slca结果，lisa采用的一种自底向上的查询策略。目前的xml关键词检索算法，很大一部分都是基于d

37、ewey编码的。而在这些算法中，有一个原子操作是要比较两个dewey编码的大小，比较两个dewey编码大小的时间复杂度是o(n)(n为杜威编码的长度)。如果在一次查询中，有m次这样的比较，那么仅仅dewey编码之间的比较操作的时间复杂度就是o(mn)，那么，这些算法在处理大规模的xml文档集时，时间性能肯定不高。1.4.2 本文主要工作为解决1.4.1中基于dewey编码索引空间效率不高以及相应检索算法时间效率低下的问题，本文从节点编码，索引结构以及检索算法三个方面展开了相关的调查与研究工作。首先，本文提出一种新的xml元素编码方式laf编码，laf编码的长度与元素在xml树中的深度无关。la

38、f编码的详细介绍将在第三章中给出。其次，由于xml文档既包含文本信息又包含层次结构信息，因此，xml文档天生就具备有两种属性，一种属性即普通文本文档都具有的属性，比如文档长度，文档的地址等；另一种属性是xml文档作为半结构化文档的属性，比如元素的编码，内部元素的长度等。本文提出了一种新的索引结构，即基于laf编码的二层索引结构，将xml文档的这两种属性分别存储在不同层次的索引中，通过指针将这两层索引关联起来。相比单层的倒排索引，这种索引结构不仅能提高空间效率，并且能支持更加高效的检索算法。二层索引的相关介绍将在第四章中给出。第三，在基于laf编码的二层索引基础上，本文提出了一个基于堆的新型检索

39、算法hba，hba是一个自下而上的xml关键词检索算法，能有效支持多种检索语义模型。hba的相关介绍将在第五章给出。第四，利用本文所提出的新型元素编码方式，新的索引结构以及计算算法，实现了xml检索的原型系统。并通过在多种数据集上的对比实验，通过对比实验发现，本文所提出的方法不论在空间效率方面，还是在时间效率方面，较传统的方法都有较大的改进。实验部分的相关数据以及分析将在第六章给出。1.4.3 本文主要创新点本文的创新点主要体现在以下三个方面：(1) 本文提出了一种新的xml元素编码方式laf编码，laf编码能有效保存xml文档的结构信息并能支持高效xml检索算法。(2) 本文提出了一种新的索

40、引结构，即基于laf编码的二层索引结构，二层索引不仅能降低索引空间冗余度，而且能支持更高效的xml检索算法。(3) 本文第一次利用堆来设计xml关键词检索算法，并采用自底向上的检索策略，hba算法不仅具有较高的检索效率，而且能有效支持多种不同的检索语义模型。1.5 本文组织结构本文一共分为七个部分。第一部分为本文的研究与应用背景，介绍了xml的特点、为什么需要进行xml关键词检索相关研究、国内外的相关研究的现状以及本文的工作以及创新点；第二部分为xml关键词检索相关概念以及技术简介，介绍了当前xml关键词检索领域所采用的检索模型，主流的检索语义模型slca以及elca。第三部分主要介绍了dew

41、ey编码的相关概念并指出dewey编码的不足，并重点讲述本文提出的laf编码的定义以及应用；第四部分重点介绍基于laf编码的二层索引模型，并与传统基于dewey编码的一层索引模型进行了比较；第五部分介绍了hba算法的基本思路、所采用的数据结构以及hba算法的实现，并用一个例子讲述hba算法的执行过程。第六部分为本文的实验比较部分，首先简单介绍了本文实现原型系统的软件以及硬件环境；其次介绍了本文原型系统实验所采用的5个数据集；最后详细列出了对比实验过程中所得出的时间和空间效率数据，并对数据进行了详尽的分析。第七部分是本文的总结部分，总结了本文所做的基本工作、工作中还存在的一些不足以及未来开展工作

42、的基本方向。本文主要研究xml关键词检索的相关方法，为方便讲解，本文后续部分出现的xml检索均指xml关键词检索。1.6 本章小结本章主要介绍了xml关键词检索的研究以及应用背景。第一节分析了xml的应用背景以及xml文档与传统html文档在应用上的区别。第二节首先介绍了xml检索的基本特点，xml检索与传统文本检索的区别以及xml检索所带来的挑战，然后介绍了xml关键词检索的应用现状以及其现实应用意义，xml关键词检索需要解决的核心问题。第三节介绍了国内外研究者在xml关键词检索领域与本论文相关的一些研究工作。第四节介绍了本文所要解决关键词检索中的基本问题，以及本文所做的主要工作以及本文的几

43、个创新点。第二章 xml关键词检索相关概念及技术一篇完整xml文档一般由处理指令，根元素，元素以及属性以及文本值等组成。在进行xml关键词检索时，主要关注文档内的元素和属性、文本值以及它们之间的结构关系。由于属性也可以看成是一种特殊的xml元素，本文只考虑xml文档内部元素和文本值。在图2- 1的xml文档中，第2行的为根元素，第三行的中的paper为一个xml元素，而id则为元素paper对应的属性，第20行的文字为文本值。为了方便处理，不特别考虑元素属性，而把元素属性看成元素的子元素来统一考虑。图2- 1 xml文档示例2.1 xml数据模型xml文档的内部元素以及文本值之间存在一种严密的

44、层次结构关系。文档数据模型dom将xml文档内的这种结构关系定义为一棵树，也叫dom树。dom树中节点的构成规则为：xml文档中的根元素对应于dom树中的根节点；xml文档内部元素和属性对应于dom树中的内部节点；文本值则对应于dom树中的叶节点。xml文档元素之间的包含关系转化为对应节点在标签树中的父子关系，元素之间的平行关系转化为对应节点在标签树中的兄弟关系。图2- 2是中图2- 1xml文档对应的dom树，图中方框表示xml文档中的元素，椭圆表示xml文档中的文本值。为了方便描述，对树中节点进行了dewey编码，例如根节点的dewey编码为0，而institution节点的编码为0.0.

45、1，任何两个节点之间的dewey编码是不同的。在该图中，根节点proceedings对应图2- 1中的根元素，内部节点paper(0.0)对应图2- 1第3行的paper元素，而内部节点paper(0.1)则对应图2- 1第18行的paper元素，叶节点yu xu(0.0.1.1.0.0)对应第8行元素下的文本值。在图2- 1中这两个paper元素为平行关系，在图2- 2的dom树中它们为兄弟节点。而在图2- 1中，元素包含元素，因此，在图2- 2的dom树中它们的关系为父子关系。图2- 2 dom树示例2.2 检索语义模型检索语义模型是xml关键词检索的基础，它决定了如何设计索引结构以及如何

46、设计相应的检索算法，其定义如下。定义 1 检索语义模型：指如何根据一定的规则定义xml检索的返回结果，xml根据不同的应用场景，可以定义不同的检索语义模型。目前，slca是最流行的查询语义模型之一，而elca模型是较早的查询语义模型，本节将简单介绍slca模型，elca模型以及由我们研究室提出的xtree模型。由于这3个模型都是基于lca模型的，下面首先介绍lca的定义，然后依次给出slca，elca以及xtree的定义。定义 2 lca（lowest common ancestor）：对于n个不同的关键字k1,k2kn，分别被dom树中的n个节点n1,n2nn所包含, 则有n=lca(n1,

47、 n2nn)，其中n是节点n1,n2nn的最小公共祖先节点，这里最小的含义是，若存在n1, n2nn的另一公共祖先节点n，则n是n的祖先节点。定义 3 slca(smallest lowest common ancestor)：定义查询q=k1,k2kn，其中k1,k2kn 是n个不同的关键词，对应于dom树中n个不同的节点集合s1，s2sn，其中si中的节点直接接包含关键词ki(0i = n)，则有：lca(s1, s2sn) | nlca(s1, s2sn)nisi(0i=n)n=lca(n1,n2.nn)，那么，slca可定义如下：slca(s1, s2sn) | nslca(s1, s

48、2sn)nlca(s1, s2sn)(nslca(s1, s2sn) (ancestor(n, n)n=n)。ancestor(n, n)函数是用来判断两个节点n和n是否具有祖先-子孙关系，如果有，则该函数返回真，反之则返回假。定义4 elca：定义查询q=k1,k2kn，其中k1,k2kn 是n个不同的关键词，定义。其中ne是元素即节点的集合，contains(v, k)表示节点v包含关键词k。根据定义，r0是包含所有关键词的节点的集合。在定义了r0后，模型进一步定义查询结果result(q)=，其中n是所有节点的集合，ce是包含关系。定义 5 xtree：定义查询q=k1,k2kn，其中k

49、1,k2kn 是n个不同的关键词，定义，即r0是包含所有关键词的节点集合，contains(v,k)表示节点v对关键词k的包含关系。那么xtree结果定义如下：result(q)=，其中subs(v)表示节点v的所有子孙节点。假定图2- 3是一个xml对应的dom树，在图中，圆形表示xml内元素，方框表示文本值，方框内的字母代表该文本内的一个关键词，比如a和b分别代表两个不同的关键词。假定现在有查询q=a, b，从图中可以知道，节点12和13直接包含关键词a和b，由此可知这两个节点的lca为节点9。同样，由图中可知，包含关键词a的节点结合为sa = 4, 12, 7, 10, sb = 6,

50、13, 11，那么slca(sa, sb) = 9, 8，即查询q对应的slca查询结果为节点8和节点9。而有elca的定义容易知道，图中的节点2,8,9都是elca的查询结果。对于xtree模型，其结果则为节点2,3,8,9。事实上，对于以上3种不同的查询语义模型，他们对应的查询结果集之间具有一种内在的包含关系，即：slca elca xtree图2- 3 检索模型示例2.3 本章小结本章首先介绍了xml检索的数据模型，为了精确描述xml文档的内部层次结构关系，在dom模型中，xml文档被建模成一棵dom树。因此，dom树是xml关键词检索的基础数据模型。第二节介绍了常见的几种查询语义模型，

51、其中包括slca，elca以及xtree，这三种语义模型对同一个关键词检索请求，所得到的检索结果集是不一样的，他们所得检索结果之间具有一种包含关系，即：slca elca xtree本文将以slca作为检索语义模型，从xml元素编码，索引结构以及检索算法3个方面展开对xml关键词检索的一些相关研究工作以及成果的描述。第三章 laf编码3.1 xml元素编码概述如何有效保存xml文档内部的层次结构信息是xml关键词检索需要解决的关键问题之一。目前，解决这个问题的办法有很多，比如保存元素到根元素之间的路径，对xml中元素进行编码等。在关键词检索中，对xml文档内部元素进行编码是一种非常有效的保存文

52、档内部层次结构的方法。所谓对xml元素编码就是根据xml元素在xml树中的位置，利用某种遍历方法(比如前序遍历，宽度优先遍历)，根据每个元素在遍历中的次序，给每个元素分配唯一的编码。元素在遍历中的次序关系反映的是xml文档内的结构关系，因此，通过对xml元素的编码，能够有效保存xml文档内的层次结构关系。那么，什么样的编码才是合理的呢？一种编码要用来给xml元素进行编码，那么这种编码必须是稳定，下面是编码稳定性的定义。定义 6 编码稳定性：如果对于一篇xml文档中的每个元素，根据某种编码方式，都能得到唯一编码。反过来，通过xml元素的这组编码，能唯一确定一个结构稳定的xml文档(xml树)，那

53、么，我们就说，这种编码时稳定的。我们知道，由树的前序编码序列和后序编码序列能确定唯一结构稳定的树，因此，以元素在前序遍历中的序号pre和在后序遍历中的序号post组成的序号对来对xml元素进行编码是稳定的。下面将介绍目前最为流行的一种xml元素编码方式dewey编码，然后介绍由本文提出的一种新的xml编码方法laf编码。3.2 dewey编码3.2.1 dewey简介根据对xml树的不同遍历方式，可以将xml元素编码分成全局编码和局部编码两大类。全局编码一般指用全局遍历方式生成成元素编码序列，比如前序编码，后序编码等都是全局编码。局部编码一般指用父节点的编码信息和当前节点在父节点中的相对位置信

54、息来确定其编码的一种编码方式。dewey编码是一种典型的局部编码方式。 6第一次使用dewey编码来对xml内元素进行编码。dewey编码的定义如下。定义 7杜威编码：t为一棵xml文档对应的dom树，且r为树t的根，对于树中任意节点n，其儿子节点分别为n1, n2nn，那么对t中节点进行杜威编码的方法为：(1) r的杜威编码为0。(2) 对于节点n的子节点从左至右依次为n1, n2nn，若其父节点的杜威编码为m，则这n个子节点的杜威编码分别为m.0，m.1，m.2m.n。(m.i，“.”是一个编码分隔符)。(3) 按照规则(1)(2)对t中节点递归编码，直至把所有节点编码完毕。图2- 2是对

55、图2- 1中的xml文档中元素进行编码后对应的dom树，在图2- 2，是dom树中的根节点，因此其dewey编码为0，节点是的子节点，根据dewey编码定义中的规则(2)，左边节点的编号为0.0，右边节点的编号则为0.1。根据类似的规则，节点为(0.0)节点的第二个子节点，因此其编码0.0.1，节点为(0.1)节点的第二个子节点，因此其编码为0.1.1。以下是杜威编码的几个主要性质。性质1 ：dewey编码是稳定的，从图2- 2可知这个是显然的。性质2 ：给出任意两个节点的dewey编码，能在o(n)的时间内，判断两个节点之间的关系，并求得他们公共祖先节点的dewey编码。例如，在图2- 2中

56、，节点的编码为0.0.1，而节点的编码为0.0，由于0.0是0.0.1的前缀，由dewey编码的定义可知，是的父节点，本身也就是他们的公共祖先节点。节点0.0.1.1.0.0和节点0.0.1.1.1.0，他们具有公共前缀0.0.1.1，因此他们的公共祖先节点为节点0.0.1.1，即节点。3.2.2 dewey编码的不足dewey编码是一种能有效保存xml文档内部结构的编码方法。它采取了局部编码策略，通过重复保存父节点的编码信息从而达到保存树的层次结构信息的目的。通过这种重复保存父节点编码的方式来保存xml文档的层次结构信息给dewey编码带来了两个潜在的不足。首先，dewey编码可能导致索引空间的冗余。由于dewey编码通过重复保存父节点的编码来实现对xml文档层次结构的保存，这种重复保存直接导致的一个事实是：节点dewey编码的长度与节点在对应dom树中的深度成正比。例如，在图2- 2中，节点的深度为3，其dewey编码0.0.1的长度也为3，而“yu xu”所在节点的深度为6，其dew