高效字符匹配算法的研究  

Research on high-performance pattern matching algorithm

作　　者：王志伟[1] 平玲娣[1] 陆敏锋[1] 

机构地区：[1]浙江大学计算机科学与技术学院,杭州310027

出　　处：《计算机工程与应用》2010年第1期28-31,共4页Computer Engineering and Applications

基　　金：国家"十一五"科技支撑计划重大项目资助No.2008BAH21B03;浙江省科技计划(No.2007C11088);浙江省重大专项(No.2007C11068)~~

摘　　要：在分析BM算法以及它的衍生版本BMH、Sunday等算法的基础上,提出一种新的改进算法。改进算法有三个重要特点:(1)采用双字符启发策略,提高模式串最大移动位数及其概率,最大移动位数为n+2;(2)采用窗口动态分段方法,尽量减少字符匹配次数;(3)建立模式串中相同字符的位置链,充分利用启发字符,降低模式匹配的冗余度。实验结果表明,改进算法具有较高的匹配效率。On the basis of the BM algorithm and its derivative versions：BMH,Sunday and other algorithms,a new improved algorithm is presented.The improved algorithm has three important features： （1）using two-character inspired strategy to improve the pattern moving length and its probability.The largest length is n＋2;（2）using the method of dynamic segmentation to minimize the matching; （3）building the chain with the location for the same character in the pattern to take full advantage of inspiring characters and reduce the redundancy of matching.Experimental results show that the improved algorithm has higher matching efficiency.

关 键 词：BM算法 双字符启发 窗口动态分段 位置链 

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