利用有限自动机(finite automata)进行模式匹配

一.有限自动机定义及基本术语：
　　一个有限自动机 M 是一个5元组（Q, $q_{0}$ ，A, Σ, δ），其中：

Q 是所有状态的有限集合;
$q_{0}^{_{}}$ ∈ Q (属于)是初始状态;
A ⊆ Q （子集）是接受状态的集合;
Σ 是有限输入字母表;
δ 是从Q * Σ的转移函数，称为有限自动机M的转移函数;

记号与术语：

Σ* 表示用字母表Σ中所有字符形成的所有有限长度的字符串集合.
n输入字符串(input string)的长度.
m模式字符串(pattern string)的长度；也称作终态m，当状态为m时表示，m长度的模式串匹配成功.
|x| : 字符串x的长度, 如示符号记法.
$w\sqsubset x$ : 字符串w 是字符串x的前缀.
$w\sqsupset x$ : 字符串w 是字符串x 的后缀.
ε：表示空字符串，是所有字符串的后缀，前缀.
a : 下文中的字符a泛指所有字符(a∈Σ).

二.引入的函数定义:
　　转移函数δ.有限自动机开始于初始状态 $q_{0}$ ，每次读入输入字符串的一个字符，如果有限自动机在状态q是读入字符'a', 则M状态从q变成 δ(q, a);
　　终态函数 Φ. 是从Σ*到Q的函数,Φ(w)是永动机M扫描字符串w终止后的状态；M接受字符串w当且仅当Φ(w)∈A, 函数Φ有下列递归关系定义：
　　　　φ(ε) = q0;（空字符串 ε 的终态为q0）

　　　　φ(wa) = δ(φ(w),a) (其中w∈Σ*，a∈Σ)
　　辅助函数，后缀函数σ对应于模式字串P是从Σ* 到{0,1, ..., m}上的映射，σ(x)是字符串x的后缀同时是P的前缀的最大长度；
　　　　σ(x) = max{k: Pk ⊐ x }
　　　　有P0 = ε是所有所有字符串的后缀;
　　注意:后缀函数的主要意义的是求出当前匹配失败时，求出已经匹配过的部分字串x是否是待匹配模式字串P的前缀，即匹配可以跳过x中部分长度(σ(x)),可以用于实现转移过程;同时也表明在接受输入字符串x后的状态(终态)，即也用于实现终态函数。
三、字符串匹配自动机(string-matching automation)
　　下图是依据模式串 P="ababaca" 构建的自动机图表：

　　上图(a)是一个自动机的状态转换图表,接受所有以字符串"ababaca"结尾的字符串。其中状态0是初始状态，状态7是唯一接受状态.

从状态i到状态j的带箭头的有向边表示转移过程: δ(i, a) = j(a∈Σ).
右向边组成了自动机的主要"骨架"，图中粗线部分，对应于输入字符同模式字串匹配成功的转移过程。左向边对应于匹配失败的转移过程(跳转,主要是计算已经匹配的部分字串的后缀子串同时是模式串P的前缀的最大长度).部分匹配失败的过程没有标示出来。
图中部分状态i在接受某字符a(a∈Σ)时，没有标示出对应有向边的情况表明其转移过程为: δ(i, a) = 0(a∈Σ),根据下面字符串模式匹配自动机定义，知当前已经匹配子串没有后缀字串是模式串P的前缀。如在状态3时，输入字符为'c',即在已经匹配了"aba"这时接受字符'c'，知当前已匹配字串为"abac",对应模式字串P="ababaca"，可知这时匹配失败，进行失败跳转求"abac"后缀子串同时是模式串P前缀的最大长度，可知为0.
匹配成功的转移过程(对应状态，以及对应输入字符)均标示为灰色,
表(c)是自动机在处理(接受)输入文本T="abababacaba"的最终状态表。当输入字符T[i]时，此时字串T[0...i]对应的的最终状态 φ(T[0...i]) 同表(c)最后一列一一对应。有T["abababaca"] = P.length = 7(唯一接受状态)，即这时候在T串中匹配成功模式串P，结束位置为9，起始位置为(9-P.length+1)=3。

3.字符串匹配有限自动机定义:
　　给定模式(pattern)字符串 P[1...m],其对应的字符串匹配有限自动机定义如下:

状态集Q = {0,1,...m}，开始状态q0是状态0，state m是唯一的接受状态；
转移函数δ 可以用后缀函数来表示:

　　　 δ(q,a) = σ（Pq,a）
　　假设当前已经读入的字符串为T,为了让T的字串(以T[i]为结尾) 能匹配模式字串Pj,必须满足Pj是Ti的后缀;同时假设q = φ(Ti),说明读取字串Ti后自动机M状态变成q；同时根据转移函数<等式一>可知q是模式字串P最大长度的前缀，同时是Ti的后缀；因此在状态q，有Pq⊐Ti和 q=σ(Ti) （当q 等于m 时，说明模式字串P整个是Ti的后缀，也意味着匹配查找成功了），因此有σ(Ti)= q，得出永动机也支持下面的等式(终态函数也是抽象的，转化为后缀函数表达式后，可以用code表示)：
　　　　φ(Ti) = σ(Ti)（i = 0,1,...n）
　　引理1、后缀函数不等式：
　 σ(xa) ≤ σ(x) + 1 (对于任何字符串x，以及字母a)
　　引理2、后缀函数递归引理：对于任何字符串x，以及字母a，如果q = σ(x),有：
　 σ(xa) = σ(Pqa)
　　从上面可以知道当读入T i 的终态(亦即读入T[i]后转移函数状态)等于模式长度，就匹配成功了，下面是有限自动机机匹配算法伪代码：

　　下面就是根据<等式一>来实现转移函数的伪代码：

代码实现

public class DFA {
    private final int R;       //the radix
    private int[][] dfa;       //the KMP automoton
    private String pat;        //or the pattern string

    public DFA(String pat) {
        this.R = 256;
        this.pat = pat;

        // build DFA from pattern
        int m = pat.length();
        dfa = new int[R][m]; 
        dfa[pat.charAt(0)][0] = 1; 
        for (int x = 0, j = 1; j < m; j++) {
            for (int c = 0; c < R; c++) 
                dfa[c][j] = dfa[c][x];   // Copy mismatch cases. 
            dfa[pat.charAt(j)][j] = j+1; // Set match case. 
            x = dfa[pat.charAt(j)][x];   // Update restart state. 
        } 
    } 

    public int search(String txt) {
        int m = pat.length();
        int n = txt.length();
        int i, j;
        for (i = 0, j = 0; i < n && j < m; i++) {
            j = dfa[txt.charAt(i)][j];
        }
        if (j == m) return i - m;    //found
        return n;                    //not found
    }

    public static void main(String[] args) {
       String pat="ababcab";
       DFA dfa=new DFA(pat);
       System.out.println(dfa.search("aabacababcabacab"));
    }
}

View Code