计算机工程与科学2012，Vol.34Issue(3)：113-117,5.DOI:10.3969/j.issn.1007-130X.2012.03.021
基于双字符序检测的BM模式匹配改进算法
An Improved BM Pattern Matching Algorithm Based on Double Character Sequence Checking
摘要
Abstract
The BM algorithm is a more efficient single pattern matching algorithm. The common method of improving the BM algorithm is to start with increasing the probability of the first failure character matching and the maximal moving distance of the matching window. At the same time, the higher cost of accessing memory counteracts the actual efficiency of the new algorithm. Optimizing the number of the look-up table and the times of accessing memory when it moves the key distance of the matching window, and DCSBM makes good use of the double character's first failure matching probability at the cost of reducing the key steps properly. It is tested that DCSBM obviously increases the average moving distance of the matching window. In larger length of the text or pattern, the real efficiency of DCSBM is higher than BM, BMHS, or BMN algorithm.关键词
模式匹配/双字符序/BM算法/BMHS算法Key words
pattern matching/double character sequence/BM algorithm/BMHS algorithm分类
信息技术与安全科学引用本文复制引用
王浩,张霖,张庆..基于双字符序检测的BM模式匹配改进算法[J].计算机工程与科学,2012,34(3):113-117,5.基金项目
安徽高校省级自然科学研究重点项目(KJ2009A61) （KJ2009A61）
安徽高校省级自然科学研究一般项目(KJ2010B041) （KJ2010B041）
