分块法的模式匹配算法的研究  

Pattern matching algorithm based on block method

作　　者：巫喜红[1] 

机构地区：[1]嘉应学院计算机学院,广东梅州514015

出　　处：《重庆邮电大学学报（自然科学版）》2014年第4期551-555,共5页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

基　　金：广东省科技创新项目(2012KJCX0097)~~

摘　　要：为提高模式匹配算法性能,介绍经典的模式匹配算法Byoer-Moore和Sunday,分析它们改进后的效率,根据分块法的特点,提出一种新的分块模式匹配(block pattern matching,BPM)算法。BPM算法在预处理阶段先确定模式串的首字符在文本串的位置,再确定此字符后长度等于模式串长度的字符是否等于模式串的尾字符,若符合条件,采用单链表存储结构进行存储,在匹配阶段,利用单链表信息进行双向匹配。实验结果表明,BPM算法大大减少了匹配次数和字符比较个数,从而提高匹配效率。In order to improve the performance of pattern matching algorithms, the paper analyses the classic BM and Sun- day algorithm and their improved efficiency, then it poses a new pattern matching algorithm： block-pattern-matching（BPM） algorithm according to the characteristics of the block method. In the Preproeessing stage, firstly, the BPM algorithm confirms the position of the pattern string＇ s first character in the text string, secondly, after skipping some characters which the length equal to the pattern string minus 1, it confirms whether the character equals to the text string＇ s tail character. If it matches the condition, the BPM algorithm saves the position of the first and the tail characters through the single link list storage structure. In the matching stage, the BPM algorithm uses the mode of bidirectional parallel matching. The experimental results show that the BPM algorithm reduces greatly the match number times and the character comparison, thus it improves the matching efficiency.

关 键 词：分块法 模式匹配 分块模式匹配(BPM)算法 BM算法 Sunday算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]