XML关键字搜索中一个高效的寻找XLCA的算法

摘要

XML关键字搜索是一个用户友好的信息发现方法,非常适用于XML文档不存在schema的情况,但用户在XML关键字搜索中很难准确地表达搜索语义。现有的一些XML关键字搜索的研究是基于SLCA(最小最低公共祖先)方法,这种方法返回一组被称为SLCA的结点,一个SLCA结点满足:1)标签中或者后代结点的标签中包含所有关键字;2)没有任何一个后代结点是SLCA.SLCA方法的主要缺点是可能会丢失一部分有意义的结果,于是有的研究提出使用一种被称为XLCA的结点来取代SLCA.XLCA实际是一种概念扩展了的SLCA,可以通过一种简单但低效的递归方法取得:取得文档中的SLCA并将以SLCA为根的子树从文档中删除,再寻找文档剩余部分的SLCA.形式化定义了XLCA的概念,并提出一个高效的算法来取得以XLCA为根的文档片段作为结果;另外,还提出了一个有效的评价模型对所得到的结果进行评价和排序.