字符串匹配问题 ---- 算法导论读书笔记

字符串匹配是一个很常见的问题，可以扩展为模式的识别，解决字符串问题的思想被广泛地应用。介绍四种解决该问题的办法，包括：最朴素的遍历法，Rabin-Karp算法，自动机机匹配，Knuth-Morris-Pratt算法即耳熟能详的KMP。

在一开始，先对时间复杂度做出一个总扩（从大到小）：【1】朴素法：O（ (n-m+1)m ）；【2】Rabin-Karp：预处理：O（m），匹配：最坏O（ (n-m+1)m ），但是平均和实际中比这个好得多；【3】自动机：预处理O（m|Σ|），匹配O（n）；【4】KMP：预处理O（m），匹配O（n）。其中， m代表模式P的长度，n代表被匹配的数组S的长度，Σ代表P和S的字符表。

接下来分开说一下他们是怎么工作的，和他们的思想。

朴素法

朴素法很简单也容易想到，没多少可说的。就是从T的每一个字符开始，看它之后（包括它）的m个字符与P是否一样。P从S中第几个字符开始，可以看作，P在S中位移了几步。

朴素法的效率低的问题在于，它几乎忽视了所有的信息，每一次匹配都是“全新地”。如果P=abc，S=abdabc，从位置0开始，当我们匹配到位置2，即c != d，朴素的做法是下一步从位置1开始匹配，然而，在之前的匹配过程中，我们可以知道位置1的值b必然不匹配位置0的a。这是我们光通过P就能知道的，因为既然前一步已经开始去匹配位置2了，证明说明0和1已经成功匹配，而通过P自己，我们知道P的位置1不匹配0，则前一步的S位置1必然也不匹配P的位置1，这样就可以跳过这一步。

问题在于，告诉程序跳过多少步，这就是我们接下来的算法要做的。显然，跳过得越多匹配越快，同时我们为了尽可能得到跳步的信息，可能需要进行预处理，预处理会产生另外的时间。

Rabin-Karp

算法 将字符串转化为数，进制就是字符表的字符数目。那么，P是一个m位数，这个转化很容易用O（m）算出来，遍历一遍就好嘛。再将S变为n-m+1个数：第一个数同P一样，O（m）完成预处理；当有了第k个数，算第k+1个数的时候，只需要去掉高位，补上低位，O（1）完成这个递推过程；总的预处理还是O（m）。匹配的时候就是比较n-m+1次，所以复杂度是O（n-m+1）。那么，为什么说它匹配最坏是O（ (n-m+1)m ）呢？

原因在于这个转化得来的数可能很大，算术运算不是常数，怎么处理大数呢？这个时候可以用模除来做一个简单的hash，匹配的数hash一定匹配，hash匹配原数不一定匹配，需要再回去做检查。如果读者知道布隆过滤器，布隆过滤器跟这个也是非常像的，只不过多hash了几个数，并没有回去做检查这个步骤。最差的时候，所有的hash都一样，每个hash都匹配了，全部需要回去检查一遍，那么这个时候匹配过程和朴素法一样。工程上来说，通常选取一个较大的素数来做模除。

算法的最差运行时间是O（ (n-m+1)m ），当素数比模式P长度大很多时，期望运行时间是O（n+ m）。

自动机

对于了解自动机的朋友，对一个给定的模式，自己构造一个自动机去匹配，这种问题应该不会陌生。那么这里的问题是，模式是参数输入的，如何自动地构造自动机。这样，问题变成，需要几个状态，哪些是终止状态，状态的转移函数如何？前两个问题比较好办，模式有m个字符，就有m+1个状态，初始状态0，匹配一个字符跳到下一状态，m状态就接受。那么问题就是需要解决各个状态对于输入不是下一个字符，无法跳转到下一个状态的时候，跳到哪一个状态。

做几个定义，f(q,a)是状态q时收到a字符，返回这之后应该在的状态，即我们要求的状态转移函数；g(x)在x的后缀中尽可能地匹配P的前缀，返回最大匹配字符数，即找出x的后面和P的前面重叠了多少，如x=adbs，P=bsf，g(x)就返回2；Pq是P的前q个字符，也即在状态q下已经匹配了前Pq个字符。那么有f（q,a）= g（Pqa），对此我们可以有一个感性地认识：因为当前处于状态q，也就是已经匹配了q个字符，那么S中当前位置的前面就是Pq，S当前字符是a，【1】如果a也匹配上了，即Pga就是P的前缀，返回q+1是对的；【2】如果a没有匹配上，那状态应该到哪一个状态呢，假设是q2吧，显然q2<q+1吧，在S中以当前字符a结尾，往前q2个字符（包含a），匹配上了P的前q2个字符，由于q2<q+1，所以S中的这个字符串一定是Pqa匹配上P前缀的最大后缀，即g（Pqa）。

那么，只要遍历q,a，算出所有g（Pqa）就好了。算g（Pqa）用最朴素的办法，先设定一个最大的k，min(m,q+1)，看看匹配吗，不匹配再递减1直至0。由于看是否匹配最多O（m）。那么这个复杂度应该为O(|Σ|m^3) 。可以有O（m|Σ|）的方法，书上没说，由于有KMP算法，对此也不再深究，体会这个方法的思想就好。估计是与KMP类似，不过将S[q]换为Σ中的字符吧。

还是给一下这个方法的伪代码吧，略微修改：

COMPUTE-TRANSISTION-FUNCTION(P,Σ)

m <- length[P]
for q <- 0 to m
   for each a 属于 Σ
      k <-  min( m+1, q+2)
      while( k!=0){
         if( Pk 是Pqa 的后缀） break;
         k--;
      }
      f(q,a) <- k;
return f;

至于匹配过程，状态机有了，自然遍历一边S，查询状态机就好了，O（n）。

KMP实际上也是利用自动机的思想，但是我们并不是预先算好变迁函数。书上说是“现场”计算变迁函数，我觉得，倒不如理解为，自动机是接收一个新字符后跳到另一个状态，再接收下一个字符；KMP是遇到新字符，如果匹配当然是下一个状态，不匹配的话并不像自动机一步到位地接收新字符后到另一个状态，而是先到另一个状态，再递归地看是否接收这个字符，最终接收后在看下一个字符。关键在于，不匹配时，改变状态时是带着新字符还是不带。那么辅助的数组（数组也好，函数也好，总归还是查表），就从多维降到一维，多维是因为自动机遇到不同新字符跳到不同的状态，一维是KMP遇到新字符不匹配时直接跳到另一个状态，跳的时候不考虑新字符。直观上看，构建这样的数组也不再需要遍历Σ，预处理过程复杂度应该会降低。事实，确实省去了O（|Σ|）的复杂度，降到O（m）复杂度。同时，匹配时的复杂度还保持在了O（n）。分析复杂度用到平摊分析法。

匹配过程是很容易想到的，如前所述，遇到新字符，借助辅助数组π不断地改变状态。还是记录下伪代码：

KMP-MATCH(S,P)

n <- length[S]
m <- length[P]
π <- KMP-COMPUTE-PREFIX(P)
q <- 0               // state , number of char matched
for i <-  1 to n
  while q>0 && P[q+1] != S[i]  // P and S range from 1 to n, not 0 to n-1
    do q <- π[q]
  if P[q+1] == S[i] then q <- q+1
  if q == m then print... q <- π[q]

那么，问题的关键还是在于计算辅助数组 π，即状态如何转移，KMP-COMPUTE-PREFIX(P)。由前所述，与自动机的区别在于跳的时候是否带着新字符，回顾一下自动机的状态迁移f（q,a）= g（Pqa），那么KMP就为 π（q）= g（Pq）。而这里KMP计算的时候，从P的低位（左边）开始计算 π，显然只会用到前面低位的信息，不会用到后面高位的信息。那么利用动态规划中利用记录减少迭代的思想，再把计算 π的过程看做与匹配过程类似，比如计算q+1那么就是用Pq去匹配Pq+1嘛，而Pq的数组 π已经建立好了。那么KMP-COMPUTE-PREFIX(P)为：

KMP-COMPUTE-PREFIX(P)

m <- length[P]
π[1] <- 0
k <- 0               // just like q above, number of char matched
for q <-  2 to m     // like i above, and actually it is state, so its name is q
  while k>0 && P[k+1] != P[q]  // P range from 1 to n, not 0 to n-1
    do k <- π[k]
  if P[k+1] == P[q] then k <- k+1
  π[q] <- k
return π

转载请注明出处。

秒客网

字符串匹配问题 ---- 算法导论读书笔记

相关文章