XML内容筛选中的快速串匹配算法

摘要

本文提出了一种对XML文本进行快速串匹配的算法-XMatch.在对于XML文本的含路径信息的模式串匹配中,由于XML文本的结构化特点,使得传统的串匹配算法不能直接有效的使用;而现有的大部分XML内容筛选方法都是基于SAX分析的事件驱动过程,效率普遍较低.XMatch在对XML文本的结构-schema进行分析的同时,结合模式串的路径信息,建立一个扫描自动机的有限状态自动机;此外,算法还支持带循环引用路径信息的模式串匹配.XMatch容易扩展,可以支持普通的结构化文本的串匹配.实验结果显示,本算法的效率比使用SAM事件驱动的方法有明显的提高.