改进的QS模式匹配算法的性能分析

摘要

在详细分析QS匹配算法的基础上，提出了一种改进的算法I_QS算法。I_QS算法把模式串中每相邻两个字符构成一个字符串，由这些字符串组成字符串表并确定其位置，同时通过当前匹配窗口的后三个字符来确定下一次的右移量。为了分析I_QS算法的性能，从不同模式串数目角度，对I_QS算法进行匹配所需要的时间、所尝试的次数、所比较的字符个数三方面进行实验。实验结果表明，由于I_QS算法能够最大限度地向右移动，从而大大地减少移动次数和缩短匹配时间，有效地提高模式匹配速度。%The paper suggests an Improved Quick Search(I_QS)algorithm for string matching based on the detailed analysis of Quick Search(QS)algorithm. The I_QS algorithm uses every adjacent two characters of pattern string to make up of a string and constitutes a string table, then confirms the position of strings. It uses back three characters of the current match-ing window to determine the distance of next shif. To analyse the performance of the I_QS algorithm, some experiments are done from three aspects which are matched time, trial times and characters’numbers through the number of different pattern strings. The experimental results show that because the I_QS algorithm can maximum limit to move to right, so it can reduce the times of moving and the time of matching. The I_QS algorithm enhances the algorithm’s efficiency.