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

摘要：

在详细分析QS匹配算法的基础上，提出了一种改进的算法I_QS算法。I_QS算法把模式串中每相邻两个字符构成一个字符串，由这些字符串组成字符串表并确定其位置，同时通过当前匹配窗口的后三个字符来确定下一次的右移量。为了分析I_QS算法的性能，从不同模式串数目角度，对I_QS算法进行匹配所需要的时间、所尝试的次数、所比较的字符个数三方面进行实验。实验结果表明，由于I_QS算法能够最大限度地向右移动，从而大大地减少移动次数和缩短匹配时间，有效地提高模式匹配速度。

关键词：快速搜索(QS)算法、改进的快速搜索(I_QS)算法、性能、模式匹配

分类号：TP301.6(计算技术、计算机技术)

资助基金：广东省教育部产学研合作项目基金资助项目No.2011A090200068；梅州市科技计划基金资助项目No.2011A04。

在线出版日期：2014-01-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：44-48