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

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

A Fast String Matching Algorithm in Content-based XML Filtering

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 canpt 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.