一种新的基于流过滤的Twig模式匹配算法  

Novel Twig Pattern Matching Algorithm Based on Stream Filtering

作　　者：张青平[1] 蒋夏军[1] 皮德常[1] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机与数字工程》2014年第5期751-756,790,共7页Computer & Digital Engineering

基　　金：航空科学基金(编号:20111052010)资助

摘　　要：针对传统XML文档小枝模式查询算法中,与模式树中标签名相同的节点均入内存,易造成很大的空间浪费问题,提出了一种新的算法—StreamFWM(StreamFilter Without Merging)。StreamFWM采用区间编码方式,依据节点间的结构关系过滤标签流中无用的中间节点,且不用归并,只用简单的栈和列表实现。实验结果证明,算法StreamFWM相比TwigStack在查询处理的性能上有所提高。Traditional twig pattern matching algorithms for XML document have their defects, the algorithms put all the nodes whose label name is the same with that of pattern tree into memory, resulting in high space complexity. To im- prove the performance of twig pattern matching, a novel algorithm without merging called StreamFWM（StreamFilter With- out Merging） is proposed in the paper. StreamFWM algorithm uses the method of the region code and filters useless interme- diate nodes by the structural relationship between nodes, and uses only a few simple stacks and lists. Experimental results show that the StreamFWM algorithm improves performance of query processing compared with TwigStack.

关 键 词：XML 小枝模式 区间编码 标签流 归并 

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