针对QSP算法的研究与分析

Research and Analysis of QSP Algorithm

BM算法是经典的单模式匹配算法,QS算法是基于BM算法的改进算法,由于QS算法仅仅分析下一字符T[j+m]计算右移量,整体的匹配效率并不高,因此在QS算法的基础上提出一种改进算法(QSP).QSP算法在预处理阶段从左向右找出模式串中出现1次以上的单字符,计算出这些字符的跳转期望值差,得到最大差值和相对应的字符位置max Pos,并修改skipp2数组的值;在匹配阶段,首先比较P[max Pos]与T[j+max Pos]是否相等,然后再利用两个数组skipp1和skipp2进行右移,保证每次右移的距离达到最大.通过实验证明,该算法总的比较次数和运行时间都低于QS算法,匹配效率得到明显的提高.

BM algorithm is a classical single pattern matching algorithm. QS algorithm is an improved algorithm of BM algorithm. Because computing the moving distance to right position only by analyzing the character T[j＋m], the overall matching efficiency of QS is not high. Therefore, an improved algorithm（QSP） accordingly to the QS algorithm is proposed. The core idea of QSP algorithm is finding all characters that appear more than once in the pattern string from left to right, calculating the jumping expectation difference value of these characters, getting the highest expectation difference value and max Pos value that is the position of it in the preprocessing phase, and changing the value of skipp2 array. During the matching phase, in order to move the pointer farthest at each time, it firstly considers the relationship between P[max Pos] and T[j＋max Pos], then moves to right by using the skipp1 and skipp2 arrays. The experimental result shows that the comparison number and matching time of QSP are less than QS. Its efficiency has been improved obviously.