摘要: 针对BM模式匹配算法的效率问题,提出其改进算法。分析BM模式匹配算法的原理,若文本串中连续的几个字符不在模式字符串中出现,则不需要被比对,以此改变模式字符串的匹配顺序,提高算法的匹配效率。实验结果表明,改进的BM模式匹配算法可以有效地减少字符串的匹配次数和比对次数,能获得良好的字符串匹配效率。
关键词:
模式匹配,
滑动距离函数,
比对算法,
模式串
Abstract: Considering the efficiency problem of the BM pattern matching algorithm, this paper proposes an improved BM pattern matching algorithm. Analyzing the character of it, if some continuous characters are not appearing in the model string, then the characters needn’t to be compared, so this method changes the model string comparing order, and the matching efficiency of BM algorithm is enhanced. Experimental results show that the improved BM pattern matching algorithm can effectively decrease the times of string matching and comparing, and get the good string matching efficiency.
Key words:
pattern matching,
sliding distance function,
comparison algorithm,
pattern string
中图分类号:
刘沛骞, 冯晶晶. 一种改进的BM模式匹配算法[J]. 计算机工程, 2011, 37(17): 248-249.
LIU Pei-Jian, FENG Jing-Jing. Improved BM Pattern Matching Algorithm[J]. Computer Engineering, 2011, 37(17): 248-249.