StringMatching

字符串，是定义在规定的有限字符集合上的一个字符自由组合的序列结果。

字符串匹配问题(String matching)是指在一个大字符串T中搜索另一个字符串S出现的所有位置，其中T,S都是定义在字符集上的字符串

前言

文本编辑问题经常需要到一串大文本序列中查找某一个文本的出现，在大字符串中去寻找匹配某个模式的字符串的问题叫做**“字符串匹配问题"**。高效率的字符匹配算法在很多应用场景秀啊有非常大的作用。

在亲子鉴定中是运用解螺旋的单链DNA的序列（有A,G,C,T四种嘌呤或嘧啶）去匹配另一条解螺旋的DNA序列来验证是否亲子关系。比如网络搜索引擎在爬取网页的时候也会用到字符串匹配算法去查找相关网页。

Notation & Terminology

• $\Sigma = \{a,b,c,...,z,0,1,...,9\}$：表示一个字符的集合，字符可以是字母或数字.
• $\Sigma^{*}$：表示一个由任意个其中字符的任意种组合的所有字符串的一个集合
• $\epsilon$：表示一个空字符串
• $w\sqsubset x$(prefix)：如果字串w是x的前置
• $w\sqsupset x$(Suffix)：如果字串w是x的后置
• $P_{k}$：=P.substring(0,k)表示P的一个长度k的字符串前缀

下面介绍四种字符串匹配算法，分别是 基础匹配算法，Rabin-Karp 算法，KMP算法 和 DFA算法

通用匹配算法

Naive String-Matching Algorithm

通用匹配算法一般是最愚蠢最直接的方式，通过循环作移位比较来判断字符串是否匹配

比如一个字符串P, 去匹配字符串T。执行T.length - P.length次检查，每次从T.substring(index, index + P.length)开始逐字符和P比较。

1
2
3
4
5

n = T.length
m = P.length
for s = 0 to n - m :
	if P[1..m] == T[s+1..s+m]
		print("Pattern occurs with sifts",s)

复杂度分析

时间复杂度：O((n-m)*m)

Rabin-Karp 算法

Rabin和Karp 共同提出的一种算法，在相关问题中也有较好的表现。

主要用到了基础数论的模运算相等来做匹配

原理

$\Sigma = \{0,1,2,...,9\}$表示一个有限字符集。每一个字符都是一十进制位。于是我们可以将基于 $\Sigma$ 的一个字符串 S 看作一个 S.length 位的十进制数。比如字符串"31415"就相当于31415.

于是我们可以这样设想，P[1…m] = “01248222324…1212”. p = value(P) 表示字串P的数值. 每一个字串都有一个唯一的十进制数值。同样，在T[1…n]字符串上也可以做相同的操作，对于index = 0,1,…,n-m 的T.substring(index+1,index+m) = P[1…m] 当且仅当t_s==p , 其中 t_s 为substring对应的十进制数值. 于是可以确定在index个移位后可以匹配字符串.

时间复杂度

p：O(m) 预处理

t0 ：O(m) 首项

t1,t2,…,t(n-m): O(1) 通项

虚假匹配: O(cm)

total：O(n+m)

通项公式

如何从t_s 得到 t_s+1 , 明显是一个滑动窗口问题：

很明显，借用取模运算，我们可以得到

$$t_{s+1}=10\left(t_{s}-10^{m-1} T[s+1]\right)+T[s+m+1]$$

于是，t₀, t₁, … ,t_n-m能在 $\Theta(n-m+1)$ 的时间内计算出。

这时，问题来了，有可能P，T是一个很大的字串，这样的结果就是 p 和 t_s 可能太不方便处理。于是我们想到了用初等数论的素数同余理论来解决：

$$t_{s+1}=\left(d\left(t_{s}-T[s+1] h\right)+T[s+m+1]\right) \bmod q$$

通过计算 p 和 t_s 对某一个素数同余来判断 显然，这样是有风险的。因为同余的两个数是不一定相等的。而只有相等的 p 和 t_s 才能唯一确定p和t.substring(0,p.length)匹配。

于是，我们希望能有一个足够大的 q 来让这种虚假匹配的发生概率特别低，低到让这种额外的检查的消耗低到能够接受的程度。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13

def rabin-matcher(T:str,P:str,d:int,q:int):
	n,m = len(T),len(P)
  h = pow(d,m-1) % q
  p,t = 0,0
  for i in range(1,m):
    p = (dp + p[i]) % q
    t0 = (dt0 + T[i]) % q
  for s in range(0,n-m):
    if p==ts
    	if p == T.substr(s,s+m):
        print("pattern ouccrs with shifts: ",s);
    if s < n-m:
      t[s+1] = (d(t[s] -T[s+1]h) + T[s+m+1])mod q;

KMP 算法

Knuth-Morris-Pratt字符串查找算法

Donald Knuth 是计算机科学的圣经《TAOCP》系列图式的作者，斯坦福大学教授，曾获图灵奖，和Patt共同构思出来，同年Morris也独立设计出了该算法。

KMP匹配算法应该是最常用的一种高效率匹配算法。主要思想就是借用已经匹配的信息，不用每一次都从匹配串的第一个字符开始判断是是否匹配。KMP是一种线性时间O(n)复杂度的一个匹配算法，避免了计算状态转移函数 $\delta$ 。为了达成这种匹配上的便利，需要对匹配序列 P 做一个预处理，得到一个匹配偏移函数(表).

前缀函数 $\pi$

前缀函数 $\pi$ 为我们封装了不匹配时的偏移数的方法，可以让我们避免了一些没必要的移位，一次性移位到足够好的位置。

$\pi(q)$ ：表示如果在 P 中的第 q 个字符开始不匹配(前 q-1 个连续的字符能匹配)，然后将 P 移 $\pi(q)$ 位后，可以继续匹配。如何移位，移位多少，可以通过之前预处理得到的匹配便宜函数(表)来确定下一个匹配字符的偏移

构造 $\pi[q]=\max \left\{k: k<q \text { and } P_{k} \sqsupset P_{q}\right\}$

• 观察 P = “ABCDABD” 在上图中的表现，为什么’D’不匹配了，将P调整到从第三处移位字符开始重新匹配呢，因为P的’D’字符前缀出现了自匹配
• 所谓自匹配就是P的一个子串出现了等长的前缀和后缀匹配的情况
• 这样，如果在某一个字符初出现了不匹配，如果我们事先知道该字符’D’的P前缀字串的前缀和后缀出现匹配的情况，可以直接从移位该等长度从P中相应位置开始新的匹配

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def compute-prefix-function(P:str):
  m = len(P)
  pi = [0] * m
  pi[1] = 0
  k = 0
  for q in range(1,m):
    while k > 0 and P[k+1] != P[q]:
      # 开始寻找
      k = pi[k]
    if P[k+1]==P[q]
    	k = k + 1
    pi[q] = k
    
	return pi           

细品原理：

如果 P = a b c a b d d d a b c a b c 那么 $\pi = [0,0,0,1,2,0,0,0,1,2,3,4,5,?]$

我们在如下的字符串上存在这一些，其中now为前缀的下一个考量位，当 P[now] != P[x] 时，说明字串A+P[now] 与 B+P[x] 开始不匹配，但是A与B是匹配的，本质上是找A的最大K前缀与B的最大K后缀匹配的的K的最大值为新的now值，恰好，A与B相等，问题也就变成了找招next[now-1] 赋值给now，此时若P[x] = P[now]就可以继续在输入字串T上匹配下一位了，不然继续让now = next[now-1]来继续找匹配。

构造完前缀函数 $\pi$ 后，匹配就非常简单了

1
2
3
4
5
6
7
8
9
10
11
12

def KMP-match(T,P)
	n,m = len(T),len(P)
  pi = compute-prefix-func(P)
  q = 0
  for i in range(n):
    while q>0 and P[q+1]!=T[i]:
      q = pi[q]
    if P[q+1]==T[i]:
      q = q+1
    if q==m:
      print("pattern occurs with shitf",i-m)
      q = pi[q]

DFA 算法

Regular-Expression String-matching (Regex)

学习过编译原理或者计算理论就应该知道，编译一段程序代码的第一步就是词法分析(lexical analysis), 词法分析的目的就是分析出token给语法分析器来推导产生式，代码都是一系列的字母数字换行回车等字符组成的字符串，很明显，词法分析器的一个工作就是用编程语言的保留字和既定语法的规则来匹配出现在代码文本文件字符串的关键字和函数名，类名，变量名等

有限自动机

一个有限自动机 $M = (Q,q_{0},A,\Sigma,\delta)$ 是一个五元组，其中：

• $M$ 是一个有限状态集
• $q_{0} \in Q$ 是开始状态
• $A \subseteq Q$ 是一个接受状态集
• $\Sigma$ 是有限的输入字符表􏰒
• $\delta$ 是M的从(Q, $\Sigma$):->Q 的一个转移函数

一个有限有限自动机从初始状态开始，每次从输入字符串中读取一个字符来 a, 然后"移位"（从状态 q 到 $\delta (q,a)$。任何时候到当前状态 q 都是 A 到一个元素，自动机已经读接受了目前已经读进来的字符。

字符串匹配自动机

对于一个给定的匹配字符串P，在开始搜索之前必须在预处理阶段构建一个字符串匹配自动机。

现在给定一个匹配 $P = ababaca$ ，匹配过程如下：

状态转移函数(表)的构建

状态转移函数 $\delta(q,a) = s$ 表示在状态 q 接受了一个 a 之后后面会转移到另外一个状态 s, 如何构建这种转移呢？

• 自动机有 m = P.length + 1 个状态，0 为初始状态，m 为匹配成功状态。
• 显然，对于每一个状态，都必须有 $\left|\Sigma\right|$ 种输入的可能，因为任何一个字符表中的字符可能在每一种状态时出现
• 对于这样的每一组合，我们想做的就是不停的用P的前缀去匹配被匹配字符串的后缀 T[0:-q-1] （注：此处的T表示已经顺序输入的被匹配字符串）
• 显然，q 状态和已输入的匹配字符串的长度为 q 的后缀可以与 P[q] 匹配（相等）, 如下：

1
2
3
4
5
6
7
8
9

def compute-transition-func(P:str,sigma):
  m = len(P)
  for q in range(m):
    for a in sigma:
      k = min(m+1,q+2)
      while not p[k]==(P[q]+a)[0:-k]:
        k = k -1;
      delta(q,a) = k
	return delta

自动机的转移函数构造完成之后，剩下的处理就是逐字符读取，直到当前状态为m，这时一次匹配成功

• ← Previous Post
• Next Post →