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

A Fast String Matching Algorithm in Content-based XML Filtering

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

We propose an algorithm to do fast string match of XML files XMatch. In the pattern string matching of XML files which contain path information, traditional string match algorithms cant be effectively directly used due to the structured characteristics of XML files; Most of the available methods of XML content filtering are based on SAX event driven which is not very efficient. When analyzing schema the structure of XML files, XMatch utilizes the path information of pattern string to construct a DFA ; In addition, the algorithm support pattern matching with loop reference path information. XMatch is scalable and can support string matching of common structure text. Experiment results show that, the efficiency is distinctly improved compared with using the method of SAX event driven.