用于检测过滤的多模式匹配  

Multiple Patterns Matching for Filtering and Detection

作　　者：魏景芝[1] 辛阳[1] 杨义先[1] 钮心忻[1] 

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室信息安全中心,北京100876

出　　处：《北京邮电大学学报》2007年第6期69-72,共4页Journal of Beijing University of Posts and Telecommunications

基　　金：国家"973计划"项目(2007CB310704)

摘　　要：针对目前匹配速率过慢的问题,在有限自动机的多模式匹配算法的基础上,结合Boyer-Moore(BM)算法和改进的quick search(QS)算法的优点,提出了一个快速的多模式字符串匹配算法.一般情况下,该算法能充分利用匹配过程中本次匹配不成功的信息和已经匹配成功的信息,尽可能多地跳过待查文本串中的字符,所以不需要匹配目标文本串的每个字符就能一次性实现对文本的快速搜索.实验证明,在模式串较长和较短的情况下,算法都有很好的匹配性能,有效改善关键字检测过滤系统的性能.For the weakness of low string matching speed, a fast algorithm to perform multiple pattern matching in a string, based on finite state automaton combined with Boyer-Moore（BM） algorithm and an improved quick search（QS） algorithm, was presented. In general, the algorithm described does not need to test each character in the string, By making full use of the results of matching successes and failures, the algorithm can often bypass inspection of as many characters as possible and get all matching locations after one quick search. Experimental results demonstrate that the proposed algorithm has achieved excellent performance in the cases of both short patterns and long patterns and effectively improved the performance of keyword detection and filtering.

关 键 词：多模式匹配 有限自动机 关键字检测过滤 字符串 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]