改进的基于小枝模式的匹配算法——cTwigStack  

cTwigStack: Improved twig pattern matching algorithm

作　　者：姚全珠[1] 郭祯[1] 房美君[1] 

机构地区：[1]西安理工大学计算机科学与工程学院,西安710048

出　　处：《计算机应用》2011年第10期2782-2785,共4页journal of Computer Applications

摘　　要：给定一个小枝模式查询,如何快速地在XML数据集中找到所有感兴趣的信息,已成为当前研究的热点。针对TwigStack算法在处理含有父子节点的情况下会产生大量的中间结果等问题,通过栈来对非叶子节点缓存和对叶子节点延迟输出的思想,提出了一种改进的小枝模式匹配算法——cTwigStack。采用Treebank数据集进行测验,结果表明该算法不仅仅在处理祖孙/后继节点时能使输出结果的准确性达到最优,而且在处理父子节点时,相对目前提出的算法,也是非常高效的。How to quickly locate the interested information in the XML database under a certain twig pattern is a popular research topic.To solve the problem that the TwigStack algorithm for handling the case with parent-child nodes would come out with massive intermediate results,an improved twig pattern query algorithm of cTwigStack was proposed,which was based on caching the non-leaf nodes and delaying the leaf nodes output.The experimental results on Treebank dataset indicate that the proposed algorithm can achieve the most accurate results of the queries that contain the ancestor-descendant relationships below branching nodes.Besides,compared with the present algorithm,it is also highly effective when processing parent-child relationships below branching nodes.

关 键 词：小枝模式匹配 XML数据库 XML模式匹配 XML文档 XPATH 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]