XML倒排序的研究精品.doc

《XML倒排序的研究精品.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、摘要：本文分析了评价搜索引擎中索引机制优劣的几个指标，针对XML文档的特点，设计了一个索引模块，给出了一种倒排索引方法。关键词：XML文档；索引；倒排表中图分类号：TP391.3文献标识码：A文章编号：1009-3044(2007)05-11279-021引言•••I!!!•当今，互联网已成为人类有史以来资源最多、品种最全、规模最大的信息库。作为网上最主要的信息检索工具，搜索引擎发挥着非常重要的作用。搜索引擎的索引部分是整个搜索引擎最关键的部分,也是本文的研究重点。在对HTML文档数据建立索引时，需要保存的信息是文档中的词项信息，就是某一个词项在哪篇文档中出现，出现了几次以及出现的位置。对XM

2、L文档数据建立索引时,要保存更多的信息。首先当然是标签间的数据信息，另外还有标签中的词项信息和文档中标签的嵌套层次信息等。衡量索引的好坏是看它本身占据多少额外的磁盘空间和查询时的检索速度。本文将根据搜索引擎中索引的需要，设计一个索引模块，并给出一种新的倒排索引方法。2索引的评价指标搜索引擎的索引器需要有两个功能：一是如何建立和维护搜索索引；二是在此基础上如何快速建立有效的检索机制。目前，索引通常采用倒排表的方式,在这种方法中，每篇文献都用一系列关键词来表示，从检索的目的来说，这些关键词描述了文献的内容。对于每个关键词，都有一个指针表，该表的每个指针都指向一篇包含该关键词的相关文献。当用户提出检

3、索要求时，搜索引擎会根据用户所提供的关键词在索引文献中找到匹配或相似的关键词，并根据此关键词的指针表把此关键词所存在的文档返回给用户o由于这种方法实现相对简单，查询速度快，很容易支持同义词查询，所以很多搜索引擎的索引都支持这种方法［1］。索引的合理与否直接决定搜索引擎的响应速度快慢，进而影响其受欢迎程度。对于如何评价索引机制的优劣，主要从以下几个方面来考虑。%1数据表示数据表示包括数据在数据库中的逻辑表示以及索引结构的逻辑表示。索引的逻辑结构通常可以用表、树或有向图来表示。%1导航性1=1导航性是指在查询过程中，沿着结构索引的路径，对查询计划的各步进行依次匹配的过程。索引导航一般有四种策略：自

4、底向上、自顶向下、混合和由里向外。%1节点标识节点标识是指对文档中单个节点进行唯一标识。不同的索引方案可以采用不同的节点标识方案。有的索引方案可以采用特殊的节点标识方案来编码父子关系或者祖先/子孙关系等。%1索引更新由于数据库中的数据可能会修改，索引也要随之变化。一种良好的索引结构要求索引能够增量更新，也就是说当数据库部分数据改变时，索引结构中只是相应的索引部分随之改变，而不需要对整个索引进行重构。%1索引存储索引同数据库中数据一样也要进行存储，这必然会占据一定的存储空间，而且索引大小决定索引是否能常驻内存。不同的索引结构其大小差别很大。设计时应尽可能使索引较小[2]o3索引模块的设计基于XM

5、L文档检索的搜索引擎属于基于内容的搜索引擎，而基于HTML文档检索的搜索引擎是基于文本的。前者不但要考虑关键词的匹配，而且还要兼顾语义上是否一致，后者则简单的多，只要考虑字符的匹配与否就可以了。所以,为XML文档建立索引前，需要将每个节点的结构弄清楚，即该节点的标签名、编码、父亲编码、属性值等，所以本文设计的索引模块中有一个节点结构构造器，用来将已解析好的文档树中各节点结构列清楚，以方便索引器建立索引。所以索引模块的具体结构如图1所示。图1索引模块结构图节点结构构造器是为索引器做准备工作的。XML文档分结构信息和内容信息，这些都要编入索引，把XML文档看成一棵树，树中的节点作为一个基本的存储单

6、元，每个节点有一个唯一的标识符，这个标识符是由解析模块中的节点编码器（此文暂不论述）分配的，本文将其简记为Id,其标识符为一个编码,形式为(start,end)o把每个节点看成一个记录存储在索引数据库中，叶子节点和中间节点结构稍有不同，中间节点的节点结构包括如下部分:%1Id：元素节点标识符;%1Tag：元素标记;®Attrs：元素属性及属性值;©Parent：父元素节点Id,即父元素节点标识符；©Previous：下一个兄弟元素节点Id,即右兄弟元素节点标识符。叶子节点的节点结构包括如下部分：①Id一元素节点标识符；©Parent：父元素节点标识符;%1Text：文本内容。XML文档经过节点

7、编码器后生成DOM(文档对象模型)树，再经过节点结构构造器后产生的节点结构仍是一颗树，树的最下一层是叶子节点，即文本部分,其余都是中间节点，即结构部分。4XML文档的索引为了加快用户检索要求的响应速度，需要给采集到的数据建立索引。在检索技术的发展历程上，有过前方一致检索、关键词检索、布尔检索等，然而这些技术没有能很好的满足用户查询的需要，比如前方一致检索方法很呆板，关键词检索方法以及基于关键词的布