论文部分内容阅读
自从XML,诞生以来,越来越多的数据以XML文档格式存储和发布,XML已经成为Internet和Intranet上数据集成和交换的标准,被广泛应用于电子商务、内容管理、多媒体、数字图书馆以及中间件等众多的领域。如何高效的的索引、存储以及检索互联网上的XML数据成为一个具有显著现实应用意义的研究课题。
XML数据与传统文本数据的最大区别是:XML数据含有丰富的层次结构信息。这使得XML能够更加精确地描述数据以及数据之间的关系。如何将XML数据所包含的层次结构信息存入索引中并使之能支持高效的关键词检索算法成为XML关键词检索研究中的核心问题之一。
Dewey编码是一种能有效保存XML层次结构信息的方法,也是目前关键词检索中最流行的方法之一。研究人员提出了很多基于Dewey编码的检索算法,如栈算法、Scan Eager算法等。但是,Dewey编码有两个明显的不足:首先,XML元素的Dewey编码长度与XML元素在XML树中的深度成正比;其次,在很多算法中,比较两个Dewey编码大小的操作是一个原子操作,而比较两个Dewey编码大小的时间复杂度是O(N),其中N为杜威编码的长度,在处理大规模的XML数据集时,这将严重影响检索算法的性能。
为了克服Dewey编码的不足,本文提出了LAF编码策略,对于任意一个XML元素,其编码的长度恒为3;在LAF编码基础上,结合XML,文档的自身特征,设计了一种能支持高效XML关键词检索算法的二层索引结构;最后,文章实现了一个基于堆的高效XML,关键词检索算法HBA,HBA算法能有效支持各种XML检索语义模型。
通过在多个数据集上的对比实验,与传统的索引方法相比,基于LAF编码的二层索引方法具有较大的空间效率优势;与传统的关键词检索算法相比,HBA算法不仅具有较大