精确字符串匹配算法性能分析

鉴于大家对其他类别十分关注，我们编辑小组在此为大家搜集整理了“精确字符串匹配算法性能分析”一文，供大家参考学习!

客服咨询，网学网竭诚为您服务，本站永久域名：myeducs.cn

一、基于前缀搜索的匹配算法

（一）KMP算法

这是在字符串匹配界内的一个非常著名的算法，称为KMP算法。这种算法出现较早，是由D.E.Knuth, V.R.Pratt, J.H.Morris三人一同发现的。

这种算法的最主要的优点是，指示文本的指针在整个匹配的过程中不会发生回溯，即，当进行到某个字符不匹配的情况下，不必同蛮力算法那样把指针再回溯，而是在原来位置等待模式串窗口向右滑动，与下一个有可能匹配的字符对齐。那么KMP算法的关键就在于怎样找到，当发现不匹配时，将匹配串口向右滑动到最远而不丢失匹配的距离。此算法所寻求的规律就是，找出在已经得到的“部分匹配”的字符串之中，它的最长的前缀在模式串中出现的最左面的距离。

分析KMP算法的性能，此算法需要对模式串进行预处理，此过程需要O（m）时间复杂度。匹配过程中由于不需要回溯指针，复杂度为O（n）。那么总的来说需要O（n+m）的时间复杂度。但通常情况下m是远小于n的。但是由于这种算法所体现的优势是基于在文本中存在很多与模式串“部分匹配”的情况下，只有这样才会使指针一次跳跃多个距离。所以并不是在所有的情况下它的性能都很高。

（二）shift-and算法

在介绍shift-and算法之前，首先要向大家介绍一些关于位并行思想的有关知识。位并行技术利用了计算机机器字位并行运算的并行性，即可以把多个值装入同一个机器字之中，然后只需一次运算就可以更新所有的值。利用这种技术可以使原来的运算次数最多减少为原来的1/w。w为机器字的长度。当前的系统中，w为32或者64，所以性能的提升是很显著的。

首先对于位的重复出现，本文中将会使用指数的形式来表示：比如，111110就会表示成1⁵0。我们用b_m………b₁ 来表示长度为m的位掩码。对于位的运算有 “&”，“|”,“~”,“<<”,“>>”等，他们的意义与在C语言中的含义是相同的，分别表示，“与”，“或”，“取反”，“左移位”（最右边填充0），“右移位”（最左面填充0）。

下面来介绍一下shift-and算法的思想。它需要构造一个集合，集合中的每个字符既是模式串的前缀，也是已读入文本的后缀。然后每读入一个字符就用位并行的方法来更新这个集合。这个集合我们使用一个位掩码D=d_m………d₁来表示，m为模式串的长度。如果位掩码D的第j位被置为1，（称为第j位是活动的）则表示 p₁………p_j 是 t₁………t_i 的前缀。那么我们便知道了，如果d_m为1，则就成功找到一个匹配。

同样，这种算法也需要我们做预处理，得首先构造一个用来判断文本是否存在与模式串对应位置相匹配的字符的表B。此表用来记录下整个字母表中每个字符的位掩码b_m………b₁。如果p_j等于某个字符char，那么B[char]的第j位置为1，其他位置为0。

将D初始化为0^m，每读入一个新的字符t_i+1时，需要更新D。我们知道如果D的第j+1位是活动的，就必须第j位是活动的，并且还得有t_i+1= p_i+1的条件。那么，就使用下面的公式对D更新： D = ((D<<1)|0^m^-11) & B[t_i+1] 。此公式包括了模式与文本匹配的过程。当D & 10^m^-1!= 0^m时，即，d_m是活动的，就成功匹配了。

观察这个公式，我们可以看出，左移位操作<<将D的第i+1位的值置为第i位的值。由于空串也是文本的后缀，所以需要与0^m^-11进行相或的操作。而与B[t_i+1]进行相与的操作，就是进行了t_i+1与p_i+1相比较的操作。

由上可知，此算法的关键之处是对字母表的所有字符的处理从而得到B[char]。

以下是我得到B[char]的预处理程序代码：

public int[] B( )

{

int[] box = new int[128];

for (int i = 0; i < 128; i++)

{

box[i] = 0;

}

for (int i = 0; i < p.Length; i++)

{

box[(int)p[i]] += (int)Math.Pow(2, i);

}

return box;

}

分析shift-and算法的性能。该算法预处理时需要在整个字母表上构造表B，那么预处理的时间复杂度为O（M），M为字母表的长度。因为在匹配过程中的运算都是在一个机器字中进行，是在常数时间里完成的。所以整个匹配的时间复杂度为O（n+M）。根据该算法的原理可知，它对模式串的长度是有要求的，需要将模式的长度控制在一个机器字之内。