一种基于版本树的三阶段XML枝匹配算法

摘要

本发明涉及一个基于版本树的三阶段XML枝匹配算法Twig3Version，该算法的执行过程可分为三阶段：第一阶段：结构匹配。利用已提出的在原文档上执行的XML枝匹配算法(TwigStack)在一个压缩的索引结构(版本树)上执行查询枝结构的匹配，得到所有满足查询枝结构约束的版本树的子树；第二阶段：版本过滤。通过版本号来过滤掉第一阶段返回的匹配子树中不满足的版本号；第三阶段：归并连接。通过归并第二阶段返回的版本号对应的XML文档元素得到最终的匹配枝。该算法综合利用了精简的版本树结构、TwigStack算法和TJFast算法的优点，在精简的版本树上执行结构匹配和在精简的中间结果上执行高效简单的版本过滤模块大大提高了查询算法的性能。XML作为日渐广泛采用的数据形式，从中提取有用的信息是一个不可回避的问题，本发明提出的方法可以帮助用户从大量的XML数据源中快速提取出用户感兴趣的信息。

主权项

一种基于版本树的XML枝匹配算法Twig3Version，步骤如下：步骤一：将用户输入的查询通过查询解析模块解析成一个查询枝；步骤二：如果当前需要搜索的XML文档没有建立版本树索引，根据版本树构建模块构造该文档对应的版本树，并将版本树索引存入磁盘文件，以便后序搜索的使用；步骤三：Twig3Version的结构匹配模块在版本树索引上进行查询枝的结构匹配，返回满足查询枝结构约束的版本树子树；步骤四：对于步骤三返回的每一个版本树子树，Twig3Version的版本过滤模块对其进行自底向上的版本过滤操作，返回版本枝方案；步骤五：Twig3Version的归并连接模块对步骤四返回的版本枝方案进行归并连接操作，返回最终的匹配枝。