论文部分内容阅读
XML(Extensible Markup Language)即可扩展的标记语言,是一套定义语义标记的规范,其目的在于定义计算机和人都能方便识别的数据类型。随着网络应用的快速发展,XML已经被广泛应用到Internet智能信息检索、数字图书馆、数据集成、Web Service等领域,这使得XML类型的数据已成为主流的数据形式,从XML数据中提取有用的信息也就成为了当前的研究热点。目前,XML查询根据查询请求描述特点的不同,可概括为两大类查询模式:XML结构化查询和XML关键字查询。XML结构化查询要求用户必须掌握XML文档结构及查询语言,这对用户来说有着较大的难度,不易使用。而XML关键字查询则相对比较灵活,它只需要用户提供简单的关键字信息,而无需懂得任何查询语言或文档结构就可方便使用,因此该模式被广泛采用,有着重要的研究价值。XML关键字查询的基本问题是求解满足关键字组合语义的最紧致片段,求解最紧致片段算法的性能及对最紧致片段的定义决定了XML关键字查询的性能和准确率。目前,对最紧致片段的最好定义是SLCA,对SLCA求解算法的研究也较为成熟。因此,本文围绕SLCA展开,分析SLCA求解算法性能上的缺点并提出新的改进算法,之后通过实验进行验证。实验过程中发现,尽管算法性能有较大提高,但结果集中存在较多并非期望的节点,因此,本文又对SLCA的概念进行扩展,提出同源SLCA(Heterogeneous SLCA,HSLCA)的概念,HSLCA在SLCA的基础上引入标签信息,能够显著提高XML关键字查询的准确率。在改进SLCA求解算法性能方面,本文在分析已有经典算法基础上展开,做出了以下创新:一、提出基于并查集的SLCA求解算法USSSA。针对求解SLCA性能最优的LISAⅡ算法空间复杂度较大,占用存储空间较多的缺点,USSSA算法使用层次编码进行求解,算法的空间复杂度明显降低,在理论求解时间与LISAⅡ基本相同的情况下,使用了更少的存储空间。二、提出基于叠加树思想的SLCA求解算法TREE_Set。针对LISAⅡ算法在查询关键字较少时性能较差的缺点,TREE_Set以树的方式求解SLCA,当查询关键字较少时,TREE_Set比LISAⅡ具有更好的性能。同时,这种算法具有很强的直观意义,便于理解,易于实现。在提高XML关键字查询准确率方面,本文在分析SLCA概念本身不足的基础上展开,所做工作和改进有:一、对SLCA的概念进行改进,提出新的最紧致片段定义同源SLCA(HSLCA),HSLCA在SLCA的基础上引入标签信息来判断查询关键字节点之间的相关度,提高XML关键字查询准确率。二、对求解SLCA的LISAⅡ算法进行扩展,得到求解HSLCA的算法HLISA。HLISA较LISAⅡ在时间复杂度上并没有数量级的增加,理论上拥有同样优越的性能。本文对XML关键字查询中最紧致片段SLCA进行深入研究,通过实验验证对SLCA的改进提高了XML关键字查询的性能和准确率,对用户有着重要的现实意义。