何志学，廖湖声

(1.北华航天工业学院 计算机与遥感信息技术学院， 河北 廊坊 065000；2.北京工业大学 计算机学院， 北京 100124)

0 引 言

各种传感器应用的发展，移动互联网特别是智能移动终端的普及，使得在环境监测、交通流量监测、金融交易、网络舆情分析和社交网络等场景中产生了海量的数据。而这些数据中80%以上都是半结构化或无结构的数据。如何从如此大量的数据中分析提取出有用的信息辅助决策的制定是大数据研究的一个重要方向[1]。XML是互联网中半结构化数据表示和传输事实上的标准，本文以半结构化XML流数据为研究对象，提出了基于森林自动机的XPath查询处理方法。

XML流查询处理主要分为基于自动机、基于栈和基于数组的方法[2,3]。流数据一般将元素、属性、文本值等都抽象为事件，而自动机由事件驱动运行进行状态转换，是处理流数据比较自然的选择，被很多系统采用，如GCX[4]系统利用静态和动态分析相结合的方式实现了XQuery流处理引擎，该方法采用了文档投影技术和动态垃圾回收机制，使得处理过程中内存占比最小化，与其它引擎相比在内存需求上有明显的优势。文献[5]采用森林自动机[6]处理XQuery的核心查询取得了较好的效果，但文中主要讨论了如何将查询转换为自动机，对于自动机的具体处理方法并未给出，本文在此基础上做了进一步的工作，侧重于自动机的执行和缓存的处理。其它方法多采用各种自动机的变形，如嵌套的字自动机[7]、对自动机投影[8]等。……