【摘要】 针对流数据在线实时到达,顺序性一次访问及处理时效性高、缓存量小的需求,提出一种基于森林自动机处理XPath查询的方法。定义XPath查询到森林自动机实例的转换规则;采用栈结构和抽象语法树相结合的方式,不断接收流数据结点,驱动自动机的运行,完成结点匹配和状态转换动作;在抽象语法树中维护各状态函数之间的关系及中间结果,归约过程中获得查询结果随即输出。实验结果验证了该方法处理流数据的有效性,在标准测试数据集下,与同类方法和引擎相比,在处理效率上有近30%的提高,内存占接近于常量,较好解决了时空复杂度平衡问题,为其它方法提供了有益的参考。更多还原

【Abstract】 Focusing on the characteristics of processing semi-structure XML streaming data such as the stream arriving continuously,requiring to be read sequentially and only once into memory,the querying must be processed on the fly,a method of processing XPath query based on forest transducer was proposed.The conversion rules of forest transducer were defined for XPath query.The transducer was driven by input streaming data nodes.Stack and abstract syntax tree were applied to implement match and state transformation in running procedure.The relationships between state functions and intermediate results were kept by abstract syntax tree,and the query results were outputted in the reduce process.Experimental results show that the proposed approach is effective and efficient on this problem,and outperforms about 30 percent over the state-of-the-art algorithms especially for deep nested processed data.At the same time,memory usage is nearly constant.This method resolves the balance between time and space complexity,and it is a useful reference for other methods.更多还原