基于双字符序检测的BM模式匹配改进算法

BM算法是一类效率较高的单模式匹配算法,通常改进的BM算法往往从提高字符首次不匹配概率和匹配窗口的最大移动距离入手,但为实现此目的所带来的高访存开销使算法实际效率受到影响。DCSBM算法以适当减小关键步长为代价,在利用双字符序检测提高首次匹配失败概率的同时,对匹配窗口移动关键步长字符距离所需的查表次数和访存次数进行优化。经测试,DCSBM算法显著提高了匹配窗口的平均移动距离。在文本或模式串相对较长情况下,该算法实际测试效率优于BM、BMHS、BMN等算法。

An Improved BM Pattern Matching Algorithm Based on Double Character Sequence Checking

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.