基于QS的字符串匹配改进算法

串匹配问题是计算机科学领域研究中的一个焦点问题，它在诸多非数值处理方面都有着非常广泛的应用。串匹配就是在一个大的正文T中搜索指定模式P的所有出现位置。按照功能，串匹配算法主要分为三类：精确串匹配算法、近似串匹配算法和正则表达式算法。其中，最有影响的是KMP算法、BM算法、RK随机算法和SUANDAY算法以及由此而产生的一些改进算法。在实际应用中，这些算法都各有千秋，各有侧重。

1  BM和QC算法分析

字符串匹配问题描述：

1.1 BM算法

BM是由Boyer和Moore于1977年提出的，它是一种简单、快速、通用的工程算法。它的特点是在窗口内部从右向左逆向匹配，采用坏字符启发和好后缀启发两种方法，通过预处理模式分别计算BadcharShift[char]和GoodSufShift[char]转移表。当发现不匹配时，选择两者中的最大值作为模式向右移动的距离。

BM算法的预处理分为坏字符转移表和好后缀转移表。

坏字符移动表记录的是字符char在模式串P中的最右出现位置。具体表述为：

BM算法的空间复杂度和预处理时间均为O（m+σ）。在最坏情况下，它的时间复杂度为O（nm）；在最好情况下，时间复杂度为O（n/m）。

从理论上讲，BM算法的时间复杂度要大大高于KMP算法的时间复杂度O（m+n），但在实际应用中，BM算法的搜索步长接近于模式长度m，所以执行效率非常高。

1.2 QS算法

QS算法是一种简单、快速、实用的算法。在模式匹配过程中，该算法将发生失配的字符与计算右移量两者独立开来的现象，其仅利用T[i+m]字符计算BadcharShift[T[i+m]]来决定模式转移。通常情况下，模式转移量为m+1，这大大提高了算法的搜索步长和匹配效率。

QS算法的预处理与BM算法的对坏字符启发的预处理相同。

QS算法的匹配过程如下：

QS算法的空间复杂度和预处理时间均为O（m+σ）。在最坏情况下，它的时间复杂度为O（mn）；在最好情况下，时间复杂度为O（n/m+1）。

QS算法利用了失配情况下T[i+m]字符引起的Badchar-

Shift[T[i+m]]使其编码简单且调试迅速。通常情况下，QS算法比BM算法要快，但是当T[i+m-1]不在模式中，而T[i+m]在模式中时，QS算法的效率就会大打折扣。

2  新算法

2.1 算法基本思想及步骤

本文在上述分析的基础上，充分挖掘了其潜在可利用的隐含信息，进一步优化和完善了QS算法。在预处理方面，新算法与QS算法基本相同，不同的是当模式在当前模式匹配窗口内自右向左匹配正文的过程中发生失配时，比较正文中T[i+m]和T[i+m-1]这两个字符的移动距离，取其最大值进行移动，然后在新位置重新开始模式匹配。图1为一个新算法匹配过程示例。
 

新算法的匹配过程如下：

新算法在QS算法的基础上，充分利用了失配时T[i+m-1]和T[i+m]两个字符引起的移动距离的最大值，使得移动距离增大，减少了模式匹配的比较次数。通常情况下，新算法的时间复杂度为O（n/m+1）。

2.2 性能测试

针对本文提出的新算法，从参考文献[1]中抽取chapter 32 STring Matching中第一段内容作为测试正文，并在同样的软硬件环境下对BF、BM、QS和新算法进行比较，以检测新算法在性能和效率方面的表现。表1为各种算法性能比较结果。

测试正文：

Finding all occurrences of a pattern in a text is a problem that arises frequently in text editing programs.Typically，the text is a document being edited，and the pattern searched for is a particular word supplied by the user.Efficiedt algorithms for this problem can greatly aid the respONsiveness of the test editing program.String matching algorithms are also used，for example，to search for particular patterns in DNA sequences.

搜索模式：the pattern searched

由表1可知：新算法是一种比较次数少、耗时小、效率高的快速字符串匹配算法。