摘要
提出一种基于坏字符序检测的快速模式匹配算法(BCSBM)。该算法利用相邻字符序列在模式串中不出现的概率较单字符高的特性,基于好字符和坏字符序表实现字符匹配过程的"跳跃"。BCSBM算法显著减少了匹配窗口内字符的匹配次数,同时增大了匹配窗口的平均移动距离。算法的实际测试效率较高,在文本或模式串相对较长的情况下该算法的效率提高明显。
The paper introduces BCSBM algorithm based on bad characters sequence checking.BCSBM algorithm takes advantages of the less probability of the presence of an adjacent character sequence than that of a single character within a pattern string,and realizes the jumping of the character matching process according to good characters and bad character sequences.BCSBM algorithm significantly reduces the times of character matching inside the matching window while increases the average movement distance of the matching window.As tested in reality,the algorithm＇s efficiency is higher than other pattern matching algorithms,especially when there are longer texts or pattern strings.
出处
《计算机应用与软件》
CSCD
北大核心
2012年第5期114-116,129,共4页
Computer Applications and Software
基金
安徽高校省级自然科学研究重点项目(KJ2009A61)
安徽高校省级自然科学研究一般项目(KJ2010B041)
关键词
模式匹配
字符序
BM算法
BMHS算法
Pattern matching Character sequence BM algorithm BMHS algorithm
