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

Performance analysis of improved quick search algorithms for pattern matching

在详细分析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.