【作者】 梁作鹏；

【导师】 董逸生；

【作者基本信息】 东南大学 ， 计算机应用技术， 2005， 博士

【摘要】 Web作为一个全球化信息空间,蕴含着海量的信息和知识。随着Web上资源的日趋丰富,各种基于Web的信息检索服务应运而生并得到了迅速发展。实践证明,Web搜索引擎是一个非常有用的信息检索工具。但对任一用户查询,搜索引擎都将返回成千上万个所谓的“匹配”文档,其中可能只有一小部分与用户的查询目标有关,而绝大部分毫无关系。如何组织和消化如此大量的信息,一直是困扰着最终用户的难题。如何帮助用户准确提出信息需求,并快速获得“满意”的查询结果,从而提高检索的效率,一直是研究的热点。尽管目前有大量的研究工作关注于Web数据检索,但现有的技术还远不能令人满意。目前XML已经成为表示Web上多样性数据的事实标准,可以预见Web上的数据将主要以XML形式存在。XML规范的提出,使得信息的组织更加规范,使更准确的信息查询成为可能。随着XML获得越来越广泛的应用以及Web技术的不断发展,如何检索Web上海量的XML数据受到学术界越来越多的重视。在对目前国内外研究现状进行深入剖析的基础上,本文提出了一种面向Web的XML信息检索系统解决方案,对其中的检索模型、文档聚类、索引以及检索等关键技术进行了深入研究。本文的主要工作可以概括为以下几个方面:1.提出了检索模型X2VSM。针对Web上XML信息检索的特点,本文对目前信息检索系统中应用最广泛的信息检索模型-向量空间模型(VSM)进行了扩展,提出了适合XML的信息检索模型X2VSM。与VSM中的关键词term对应,加入相应的路径限定信息,提出了XTerm的概念;针对XML的元素嵌套的特点,提出逻辑文档的概念;提出逻辑XML文档和XML查询的统一向量表示方法;定义了XTerm的权重计算方法,并给出了文档和查询向量的相似度计算方法。X2VSM支持对XML文档进行内容和结构查询,支持任意嵌套层次的元素作为返回结果,还支持基于内容和结构相关性的查询结果排序,同时继承和保持了VSM简单易用等优点。2.研究了XML文档的聚类。分析和比较了直接和间接的聚类策略,在此基础上提出一种基于路径信息的XML文档间接结构聚类算法PBSC。它没有直接计算文档的结构距离,而是采用间接聚类的策略。与其它基于编辑距离的算法相比,具有算法简单、效率较高以及聚类过程直观等优点。聚类结果可用于用户导航以及提高检索的效果。3.研究了XML的结构索引问题。提出一种基于广义后缀树的XML结构索引PIGST。通过PIGST,把对XML文档的路径查询转换为后缀树中的字符串匹配,显著提高了查询处理效率;对传统的后缀树构建算法做了改进,使之能够用来创建由路径集合转换得到的字符串集合的广义后缀树;提出了间接包含路径查询,即查询式包含子孙-后代关系(含有“//”)的高效处理算法。PIGST的构造时间复杂度和空间复杂度是线性的,只与查询字符串的长度有关。4.研究了查询处理算法。基于我们提出的XML信息检索模型X2VSM,提出了一种支持XML元素相关性计算的查询处理算法;对传统的倒排索引进行了扩展,提出了一种带Dewey编码的倒排索引;结合结构索引PIGST,提出了一种高效的内容索引和结构索引的联合索引结构,以支持对XML文档的检索及权重的动态计算;研究了路径的相似性问题,给出相应的计算方法,并将其集成于查询处理算法XRank,使XRank不仅支持内容相关排序,同时还支持结构(路径)相关性排序。更多还原

【Abstract】 As the global information matrix, WWW contains all kinds of data, including structured, semi-structured and no structured data. Much research has focused on the study of Web information retrieval. However, its current status is still far from satisfaction of Web users.XML has become the de facto standard to represent data in WWW and it provides a uniform data model for Web data. It is reasonable to imagine that most of the data on Web will be in XML, as the result, research on XML play a crucial role in Web information retrieval.The dissertation focuses on the key techniques for XML information retrieval issues. The main contributions of this paper include the following.1. XML allows representing both content and structure of documents. An information retrieval model for XML called X2VSM is proposed which is an extension of the well-known retrieval model, vector space model (VSM). A term in VSM is added with a path specification under which it appears and is called an XTerm. We extend the definition of tem frequency (tf) and inverse document frequency (idf) to the need of XML search. Only terms under specified paths are involved in the calculation of tfs and idfs. Both tfs and idfs are calculated with respect to the queries dynamically. We define the weight of XTerm and represent both XML data and queries as weight vectors. We also define the similarity between XML data and queries. With XTerm queries, we can inquire both structural and content information of XML. Returning results can be whole documents or elements with relevance ranking score.2. We investigate the problem of XML document clustering and present a novel approach called path-based clustering (PBSC). Instead of comparing XML documents structure and clustering them directly, we cluster the paths contained in these documents. For each path, we form a cluster containing documents that have that path. After that, we combine clusters that contain similar sets of documents. The resulting clusters will contain documents that share a similar set of paths. Compared to edit distance based approaches, PBSC is much more efficient.3. This paper proposes an index structure based on generalized suffix tree (PIGST) and presents a query evaluation algorithm. The distinct paths in an XML collection are mapped into strings. The construction algorithm of the PIGST for the path strings is presented based on the modification and improvement of a well-known suffix tree construction algorithm that only requires linear time and space complexity. The query process merely needs m character comparisons for direct containment queries, where m is the length of a query string. An efficient processing method for the indirect containment queries that avoids the inefficient tree traversal operation is also presented.4. We propose a combined index structure of path index and content index. We use inverted files extended with Dewey encoding to store the content index. Based on our index structure, an algorithm called XRank is proposed to process queries. The similarity between paths is investigated and the similarity measurement is integrated into XRank. Thus, XRank not only support content-based similarity search, but also support structure (path) based similarity search.更多还原