32.字符串匹配

2018-10-14 本文已影响0人暮落晴空

研究问题：

在文本T中找到某个模式P所出现的位置。
定义文本是一个长为 n 的数组T[0..n-1]，而模式P是一个长为 m 的数组P[0..m- 1],m≤n
并且若T[s..s+(m-1)]=P[0..(m-1)]则称模式P在T中出现且偏移为 s (P在文本T中的位置是从第 s+1 个开始的)

常见算法的时间：

算法	预处理时间	匹配时间
朴素算法	0	O((n-m+1)m)
Rabin-Karp	$\Theta$ (m)	O((n-m+1)m)
有限自动机算法	O(m\| $\Sigma$ \|)	$\Theta$ (n)
Knuth-Morris-Pratt	$\Theta$ (m)	$\Theta$ (n)

朴素算法

对 n-m+1 个可能的 s 值做检测，看是否满足T[s..s+(m-1)]=P[0..(m-1)]

实现代码：

int naiveStringMatcher(string T, string P){
    int n = T.length();
    int m = P.length();
    for (int s = 0; s < n - m; s++){
        int i;
        for (i = 0; i < m; i++){
            if (T[s + i] != P[i])
            break;
        }
        if (i == m) return s; //返回下标s
    }
    return -1; //这里找不到合适的值就返回-1
}

最坏情况下，运行时间为 O((n-m+1)m) 如果 m=floor(n/2.) 则运行时间为 $\Theta(n^2)$

Rabin-Karp 算法

Rabin-Karp 算法的预处理时间是 $\Theta$ (m)，最坏情况下运行时间是O((n-m+1)m），但是平均运行时间比较快。

对于每个字符串，可以用长度为 k 的十进制数来表示由 k 个连续的字符组成的字符串，例如字符串31415可以对应十进制数31415。给定一个模式 P[0..(m-1)]，假设 p 表示其十进制值，对应的文本 T[0..(n-1)]中，假设 $t_s$ 表示长度为 m 的子字符串 T[s..(s+m-1)] 的十进制值，当且仅当 P[0..(m-1)]=T[s..(s+m-1)] 时，有 p= $t_s$ 。如果能在时间 $\Theta$ (m) 内计算出 p 值，并在总时间 O(n-m+1) 内计算出所有 $t_s$ 值，那么通过比较所 p 和所有 $t_s$ 值就可以在 $\Theta$ (n) 时间内计算出所有偏移 s 。

p 可以运用霍纳法则在 $\Theta$ (m) 时间内计算得到：
$p = P[m]+10(P[m-1]+10(P[m-2]+...+10(P[2]+10P[1])))$

$t_s$ 可以迭代得到，因为：
$t_{s+1} = 10(t_s-10^{m-1}T[s+1])+T[s+m+1]$
每次去掉高位数字，然后乘以10，再加上低位数字。

到目前为止的问题是 p 和 $t_s$ 的值可能过大，因此可以选取一个合适的模 q 来计算 p 和 $t_s$ 的模，我们可以在 $\Theta$ (m) 时间内计算出模 q 的 p 值，并且可以在 $\Theta$ (n-m+1) 时间内计算出模 q 的所有 $t_s$ 值。

递推式：

$t_{s+1} = (d(t_s-T[s+1]h)+T[s+m+1])\ mod\ q$
d为字母表{0, 1, ..., d-1}的进制， $t_s \equiv d^{m-1}\ (mod\ q)$ 是一个具有 m 数位的文本窗口的高位数位上的数字“1”的值。

但是， $t_s \equiv p\ (mod\ q)$ 并不能说明 $t_s = p$ ，反之若 $t_s \neq p\ (mod\ q)$ ，则一定有 $t_s \neq p$ 。求余的结果可以用于快速检测无效偏移 s，但是对于有效偏移，还需要重新对该偏移逐个检测，否则就是一个伪命中点。

实现代码：

int mod(int a, int b){ //求余运算
    return (a % b >= 0) ? (a % b) : (a % b + b);
}

void RabinKarpMatcher(string T, string P, int d, int q){
    int n = T.length();
    int m = P.length();
    int h = int(pow(d, m - 1)) % q;
    int p = 0;
    vector<int> t(n - m + 1, 0);
    for (int i = 0; i < m; i++){   // processing 
        p = mod((d * p + P[i]), q);
        t[0] = mod((d * t[0] + T[i]), q);
    }
    for (int s = 0; s <= n - m; s++){  // matching
        if (p == t[s]){
            if (P == T.substr(s, m))
                cout << "s: " << s << endl;
            else
                cout << "error match!" << endl;
        }
        if (s < n - m)
            t[s + 1] = mod((d * (t[s] - T[s] * h) + T[s + m]), q);
    }
}

如果模 q=11，那么当 Rabin-Karp 算法在文本 T = 3141592653589793 中寻找模式 P = 26 时，会遇到 3 个伪命中点。即 RabinKarpMatcher(T, P, 10, 11) 时，会遇到3个 error match！

有限自动机算法

有限自动机是一个处理信息的简单机器，通过对文本字符串 T 进行扫描，找出模式 P 的所有出现位置。这些字符串匹配的自动机只对文本字符检查一次，并且检查每个字符的时间为常数，因此模式预处理和建立自动机的时间为 $\Theta(n)$ 。但是如果字符集 $\Sigma$ 很大的话，建立自动机的时间也较多。

有限自动机的定义：

一个有限自动机是5个类型的元组： $(Q,\ q_0,\ A,\ \Sigma,\ \delta)$
$Q$ 是状态的有限集合
$q_0\in Q$ 是初始状态
$A\subseteq Q$ 是一个特殊的接受状态集合
$\Sigma$ 是有限输入字母表
$\delta$ 是一个从 $Q \times \Sigma$ 到 $Q$ 的函数，称为M的转移函数

为了便于说明给定模式 P[0...(m-1)] 的字符串匹配自动机，定义一个辅助函数 $\sigma$ ，称为对应 P 的后缀函数。其中 $\sigma(x)$ 是 $x$ 的后缀 P 的最长前缀的长度。
$\sigma(x) = max\{k:\ P_k\sqsupset x\}$
对于模式 P=ab，有 $\sigma(\varepsilon)=0$ ， $\sigma(ccaca)=1$ , $\sigma(ccab)=2$ 。
给定模式 P[0..(m-1)]，相应的字符串匹配自动机定义如下：
1)状态集合Q为{0, 1, ..., m}。开始状态 $q_0$ 是0状态，并且只有状态m是唯一被接受的状态。
2)对任意的状态q和字符a，转移函数 $\delta$ 定义如下：
$\delta(q,a)=\sigma(P_qa)$

一个自动机的例子：

输入模式 P = ababaca，长度为7个字符，因此有状态0, 1, ..., 7，假设字母表为{a, b, c}
则有:
$\delta(0,a)=\sigma(P_0a)=\sigma(a)=1$
$\delta(0,b)=\sigma(P_0b)=\sigma(b)=0$
$\delta(0,c)=\sigma(P_0c)=\sigma(c)=0$
$\delta(1,a)=\sigma(P_1a)=\sigma(aa)=1$
$\delta(1,b)=\sigma(P_1a)=\sigma(ab)=2$
$\delta(1,c)=\sigma(P_1a)=\sigma(ac)=0$
...
$\delta(6,a)=\sigma(P_6a)=\sigma(ababaca)=7$

因此可以有如下字符串匹配的状态转换图：

状态	a	b	c
0	1	0	0
1	1	2	0
2	3	0	0
3	1	4	0
4	5	0	0
5	1	4	6
6	7	0	0
7	1	2	0

其中状态7是仅有的接受状态

实现代码：

vector<vector<int>> computeTransFunc(string P, int len){  //预处理，计算delta
    int m = P.size();
    vector<int> temp(len, 0);
    vector<vector<int>> delta(m + 1, temp);
    for (int q = 0; q <= m; q++){
        int k;
        for (int a = 0; a < len; a++){  // 遍历字母表，这里是数字0到(len-1),如果是小写字母，可以通过-'a'操作得到对应的0到25
            string Pqa = P.substr(0, q) + to_string(a);
            k = (m + 1 <= q + 2) ? (m + 1) : (q + 2);
            string Pqasub = Pqa;  
            //这里借助一个Paqsub来存储Pqa串的长度为k的后缀，因为k可能大于Pqa.size()，直接调用Pqa.substr(Pqa.size()-k)会报错
            do {
                k--;
                int lenPqa = Pqa.size() - k;
                Pqasub = (lenPqa >= 0) ? Pqa.substr(lenPqa) : Pqa;
            } while (P.substr(0, k) != Pqasub);  // k--直到P的k前缀是Pqa的后缀为止，循环必然会停止，因为空串是任何字符串的后缀
            delta[q][a] = k;
        }
    }
    return delta;
}
void finiteAutomationMatcher(string T, vector<vector<int>> delta, int m){  //匹配过程
    //m是唯一接受状态，例如上面例子中的7
    int n = T.size();
    int q = 0;
    for (int i = 0; i < n; i++){
        q = delta[q][T[i] - '0'];
        if (q == m)
            cout << "Pattern occurs with shift" << i + 1 - m << endl;
    }
}
int main(){
    string T("0201010102010");
    string P("0101020");
    vector<vector<int>> delta = computeTransFunc(P, 3);
    finiteAutomationMatcher(T, delta, 7);
    return 1;
}

本算法需要O(m| $\Sigma$ |)的预处理时间以及 $\Theta$ (n)的匹配时间。

Knuth-Morris-Pratt算法

本算法无需计算 $\delta$ ，匹配时间也同样是 $\Theta$ (n)，只需要用到一个辅助函数 $\pi$ ，它在 $\Theta$ (m)时间内根据模式预先计算出来，并存储在数组 $\pi[0..(m-1)]$ 中。
模式的前缀函数 $pi$ 包含模式与其自身的偏移进行匹配的信息。这些信息可以用于在朴素的字符串匹配算法中避免对无用偏移进行检测，也可以避免在字符串匹配自动机中，对整个转移函数 $\delta$ 的预先计算。如果q个字符已经匹配成功，那么可以根据这q个已知的字符，我们能够立即确定某些偏移是无效的。

一个例子：

对于模式P=ababaca，目前已经在T中匹配到了ababa，q=5个字符已经匹配成功，同时发现T中的下一位不匹配。根据5个匹配字符的有用信息，这里我们发现 $P_3$ (aba)是P(ababaca)的最长前缀的同时，也是 $P_5$ (ababa)的一个真后缀，即 $\pi[5]=3$ 。在偏移s有q个字符成功匹配，则下一个可能有效的偏移为 $s'=s+(q-\pi[q])$ 。

函数定义：

已知一个模式P[0..(m-1)]，模式P的前缀函数是函数 $\pi:\ \{0,1,..,m-1\}\rightarrow\{0,1,..,m-1\}$ ,满足
$\pi[q]=max\{k:k<q\ and\ P_k \sqsupset P_q \}$
即 $\pi[q]$ 是 $P_q$ 的真后缀P的最长前缀长度。

具体程序实现：

vector<int> computePrefixFunc(string P){
    int m = P.size();
    vector<int> pi(m, 0);
    pi[0] = -1;
    int k = -1;
    for (int q = 1; q <= m - 1; q++){
        while (k > -1 && P[k + 1] != P[q])
            k = pi[k];
        if (P[k + 1] == P[q])
            k++;
        pi[q] = k;
    }
    return pi;
}
void kmpMatcher(string T, string P){
    int m = P.size();
    int n = T.size();
    vector<int> pi = computePrefixFunc(P);
    int k = -1;
    for (int i = 0; i < n; i++){
        while (k >-1 && P[k + 1] != T[i])//ptr和str不匹配，且k>-1（表示P和T有部分匹配）
            k = pi[k];//往前回溯
        if (P[k + 1] == T[i])
            k = k + 1;
        if (k == m - 1){ //说明k移动到ptr的最末端
            cout << i - m + 1 << endl;//返回相应的位置
        }
    }
}
int main()
{
    string T("0201010102010");
    string P("0101020");
    kmpMatcher(T, P);
｝

该算法的预处理时间减少为 $\Theta(m)$ ，匹配时间为 $\Theta(n)$