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

为提高模式匹配算法性能,介绍经典的模式匹配算法Byoer-Moore和Sunday,分析它们改进后的效率,根据分块法的特点,提出一种新的分块模式匹配(block pattern matching,BPM)算法?BPM算法在预处理阶段先确定模式串的首字符在文本串的位置,再确定此字符后长度等于模式串长度的字符是否等于模式串的尾字符,若符合条件,采用单链表存储结构进行存储,在匹配阶段,利用单链表信息进行双向匹配?实验结果表明,BPM算法大大减少了匹配次数和字符比较个数,从而提高匹配效率?

Pattern matching algorithm based on block method

In order to improve the performance of pattern matching algorithms,the paper analyses the classic BM and Sunday 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 Preprocessing 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 texts tring''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.