文档介绍：模式匹配BM算法改进    摘要:研究BM串匹配算法,分析国内外各种改进算法,结合其优缺点,增加对模式串串末字符或坏字符的邻接字符在模式串中的首次出现位置、存在性、惟一性的判断。根据判断的结果对移动距离重新设置,增加模式串移动距离,减少字符重复比较的次数,以提高匹配效率。关键词:串匹配;末字符;坏字符;邻接字符;惟一性;存在性中图分类号::A文章编号:1001-3695(2009)09-3249-04doi:.1001--mei,FANMing-yu(puterScience&Engineering,UniversityofElectronicScience&TechnologyofChina,Chengdu610054,China)Abstract:,thefirstposition,,increasedthenewshiftdistance,reducedthetimesofthematch,:stringmatch;endcharacter;badcharacter;neighborcharacter;uniqueness;existence0引言串匹配是文本挖掘、文献检索、搜索引擎、IP路由查找、模式识别、图像处理以及入侵检测技术等普遍采用的技术策略之一。串匹配算法是系统性能改进中极为重要的部分,系统性能的好坏取决于匹配算法及其实现的效率。学者们已提出大量串匹配算法,如Knuth等人[1]构造出KMP算法,Boyer等人?[2]于1977年设计出BM算法。在这些常用的字符串匹配算法中,KMP和BM算法是其中较为著名的两种算法。这两种算法在最坏情况下均具有线性的查找时间,KMP算法匹配从左向右进行,移动距离不可能大于一次匹配操作所进行的字符比较次数;而BM算法匹配从右向左进行,当模式串?P的末字符P[m]与对应的正文串T中的字符T[i+m]进行比较时,若T[i+m]在模式串P中并不存在,则模式串可以一次向右移动m个字符,?使模式串只经一次比较就可以移动模式串的长度,这使BM比KMP算法更快。在实用上,BM要比KMP算法快3~5倍?。本文分析BM算法及其各种相关改进算法,结合其优点对BM算法作出新的改进。针对坏字符在模式串中出现的惟一性,坏字符的前驱以及坏字符在正文串中对应字符的后继字符在模式串中的存在性,模式串末字符是否为模式串串首字符,以及坏字符与其后继字符在模式串中是否存在同样的子串进