一种高效的连续不确定XML小枝模式匹配算法

摘要

针对目前不确定XML小枝模式匹配算法均基于归并,易造成很大的空间和时间浪费问题,提出基于P-文档模型的连续不确定XML的非归并的小枝模式匹配算法.算法在节点入队列和出队列时分别进行过滤剪枝操作,减少待处理节点的个数,匹配过程使用相互关联的链表存储中间结果,不需要归并.理论分析与实验结果表明,该算法是一种高效的连续不确定XML查询算法.%At present on account of the uncertain XML twig pattern matching algorithm were based on merging, which including many defects such as waste time and space. This paper proposed a new twig pattern matching algorithm based on existing P-document model which was also for continuous uncertain XML, when the nodes got into the queue and got out of the queue, executed filtering pruning operation, in order to reduce the number of pending nodes, matching process using interrelated list to store the intermediate result, this procedure did not need to merge. The theory research and the results of experiment show that this query algorithm is high efficient.