中文多模式匹配算法性能的分析与研究  

Analysis and Research of Chinese Multi-pattern Matching Algorithm Performance

作　　者：朱永强[1,2] 江雪[1,2] 

机构地区：[1]成都网安科技发展有限公司,四川成都610092 [2]电子科技大学示范性软件学院,四川成都610054

出　　处：《计算机技术与发展》2014年第2期67-70,75,共5页Computer Technology and Development

基　　金：四川省科技型中小企业创新基金(10C26215122841)

摘　　要：模式匹配算法一般不具有所有环境下的通用性,不同的算法在不同语义环境下的表现,往往差异较大。为实现中文环境下对模式串的快速多模式匹配,选择出在中文环境下的最优匹配算法,分析了几种经典的多模式匹配算法。通过对各个算法设计思路、时间性能与空间性能的研究,推导出基于"坏字符"的算法设计思路最适用于中文环境下大字符集、短字符串的特点,并通过实验对理论推测的中文环境最优算法-Wang算法的性能与其他几种经典算法的性能进行了比较,验证了理论推导的正确性。Generally ,pattern matching algorithms do not have the versatility of all circumstances. For realizing the fast multi=pattern matching ,selecting the optimal matching algorithm under the Chinese environment, analyze several common multi - pattern matching algorithm. By researching the various algorithm design ideas, the time and space performance, deduced that the design idea based on the ＂ bad character＂ is the best way which can be used to fast matching under Chinese environment,and the experiment shows that the Wang algorithm is the optimal algorithm under Chinese environment compared with other classical algorithm, and verifies the correctness of theory deduction.

关 键 词：多模式匹配 中文环境 AC算法 WM算法 Wang算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]