基于坏字符序检测的快速模式匹配算法

摘要

提出一种基于坏字符序检测的快速模式匹配算法( 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. Ab tested in reality, the algorithm* s efficiency is higher than other pattern matching algorithms, especially when there are longer texts or pattern strings.