一个快速的字符串模式匹配改进算法  

A Fast Improved Algorithm for Pattern Matching in String

作　　者：张娜[1] 张剑[1] 

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230009

出　　处：《微电子学与计算机》2007年第4期102-105,110,共5页Microelectronics & Computer

摘　　要：在分析了BM算法以及一些重要的改进算法的基础上,提出了一种新的改进算法——BMG算法。该算法结合了BMH算法和BMHS算法的优点,同时考虑了字符串后一位字母的唯一性,提高了最大位移m+1的出现概率,有效地加快了匹配速度。BMG算法已经通过实验测试,并证明是有效的,测试结果表明该算法比BM、BMH、BMHS算法有更好的性能。On the basis of BM algorithm and some important improvement algorithms, a new improved algorithm- BMG is presented, This algorithm combines the merits of BMH and BMHS.At the same time, the uniqueness of next character is taken into account. This algorithm greatly enhances the probability of occurrence of the largest right Goodsuffix m＋1, thus improves the matching speed effectively. BMG algorithm passed test and proves to be valid. The test results shows that the algorithm has better performance than BM, BMH, BMHS algorithm.

关 键 词：模式匹配 字符串检索 BM算法 BMH算法 BMHS算法 

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