《算法》笔记 16 - 正则表达式

《算法》笔记 16 - 正则表达式

  • 非确定有限状态自动机NFA

  • 模拟NFA的运行

  • NFA的表示

  • 构造与正则表达式相对应的NFA

  • NFA的模拟与可达性

  • 除了查找子字符串,在很多时候并不知道被查找模式的完整信息,这时就需要用到正则表达式了。正则表达式在子字符串查找、合法性校验、网络爬虫等方面有着非常广泛的应用。

    ### 使用正则表达式描述模式

    正则表达式对模式的描述,基于几个基本操作。

    • 连接操作,比如AB,表示由A和B连接而成的模式。

    • 或操作,或操作可以在模式中指定多种可能的匹配,用"|"表示。

    • 闭包操作,闭包操作可以把模式部分重复任意次数,用"*"表示。

    • 括号,括号可以改变默认优先级的顺序。

    • 在编程语言中使用的正则表达式还有很多其它语法,但都是基于这几种基本操作的。

    ### 非确定有限状态自动机

    如何根据正则表达式所描述的模式来匹配文本呢?子字符串查找中使用的有序状态自动机DFA会根据文本中的字符改变自身的状态,但正则表达式匹配比子字符串查找更复杂。因为或操作的存在,自动机无法仅根据一个字符就判断出模式是否出现;再加上闭包的存在,自动机甚至无法知道需要检查多少字符才会匹配失败。为了克服这些困难,需要非确定有限状态自动机NFA。

    根据Kleene定理,任意正则表达式都存在一个与之对应的非确定有限状态自动机,反之亦然。所以任意正则表达式都可以转换为一个非确定有限状态自动机,然后就可以模式NFA的运行轨迹来进行匹配了。

    正则表达式((A*B|AC)D)所对应的NFA如下图:

    NFA具有以下特点:

    • 长度为M的正则表达式中的每个字符在所对应的NFA中都有且只有一个对应的状态。NFA的起始状态为0并含有一个虚拟的接受状态M;

    • 字符表中的字符所对应的状态都有一条从它指出的边,这条边指向模式中的下一个字符所对应的状态(这种边为黑色);

    • 元字符"(" ")" "|" "*"所对应的状态至少含有一条指出的边(这种边为红色),这些边可能指向其它的任意状态;

    • 有些状态有多条指出的边,但一个状态只能有一条指出的黑色边。

    这里约定将所有的模式都包含在括号中,一次NFA中的第一个状态和最后一个状态都对应的是括号。

    在检查文本与模式是否匹配时,NFA需要不断读取文本,直到NFA变为接受状态,或到达文本末尾。由于或操作和闭包操作的存在,NFA从一个状态转换到了一个状态的规则与DFA有所不同,在NFA中有两种转换方式:

    • 匹配转换,即文本中的某个字符与模式中的一个字符相对应,此时NFA可以扫过这个字符,并经过黑色的边转换到下一状态;

    • ε转换,是指NFA经由红色边转换到了一个状态而不扫描文本中的任何字符。

    比如在上图的NFA中,由2->3, 1->6等都是ε转换,ε转换说明很多时候,NFA从一个状态转换到的下一个状态是不确定的,比如从状态3即可以到状态4,也可以回到状态2。正是由于这种不确定性的存在,NFA运行时,需要系统地尝试过所有的可能性后,才能得知是否匹配成功。

    ### 模拟NFA的运行

    使用NFA进行正则表达式匹配的过程与使用DFA进行子字符串查找的整体过程大致相同,也是先根据给定的正则表达式构造NFA,然后模拟NFA在给定文本上的运行轨迹。

    #### NFA的表示

    首先考虑的是该如何表示NFA。正则表达式本身已经给出了所有的状态名,如果正则表达式的长度为M,那么0到M之间的整数就是所有的状态名,于是用char数组re保存正则表达式的每个字符,对于匹配转换,如果re[i]存在于字母表中,那么就存在一个从i到i+1的匹配转换。

    对于ε转换,用有向图表示,它们都是连接0到M之间各个顶点的有向边。

    #### 构造与正则表达式相对应的NFA

    在表示NFA的时候会使用一个char数组,一个有向图,另外还有一个栈来记录所有左括号和或操作符的位置。

    • 连接操作

    连接操作的实现很容易,状态的匹配之后和字母表中字符的对应关系就是连接操作的实现。

    • 括号

    遇到正则表达式中的左括号时,将它的索引压入栈中,在遇到右括号时,再从栈中弹出。

    • 闭包操作

    闭包运算符""如果出现在单个字符之后,就在这个字符和""之间添加相互指向的两条ε转换;如果出现在右括号之后,就在对应的左括号和"*"之间添加相互指向的两条ε转换。

    • 或操作

    遇到或操作也会添加两条ε转换,比如(A|B),一条从左括号所对应的状态指向或操作后面第一个字符B所对应的状态,另一条从或操作符的状态指向右括号对于的状态。将"|"运算符的索引压入栈中,这样在到达右括号时从栈的顶部就可以拿到这个索引了。

    
    public class Regular {
    
    private char[] re;
    
    private Digraph G;
    
    private int M;
    
      
    
    public Regular(String regexp) {
    
    Stack<Integer> ops = new Stack<Integer>();
    
    re = regexp.toCharArray();
    
    M = re.length;
    
    G = new Digraph(M + 1);
    
      
    
    for (int i = 0; i < M; i++) {
    
    int lp = i;
    
    if (re[i] == "(" || re[i] == "|")
    
    ops.push(i);
    
    else if (re[i] == ")") {
    
    int or = ops.pop();
    
    if (re[or] == "|") {
    
    lp = ops.pop();
    
    G.addEdge(lp, or + 1);
    
    G.addEdge(or, i);
    
    } else
    
    lp = or;
    
    }
    
      
    
    if (i < M - 1 && re[i + 1] == "*") {
    
    G.addEdge(lp, i + 1);
    
    G.addEdge(i + 1, lp);
    
    }
    
      
    
    if (re[i] == "(" || re[i] == "*" || re[i] == ")")
    
    G.addEdge(i, i + 1);
    
    }
    
    }
    
    }
    
    

    #### NFA的模拟与可达性

    为了模拟NFA的运行,会记录NFA在检查当前输入字符时可能遇到的所有状态的集合。这里关键的计算是有向图的多点可达性问题,用深度优先搜索实现。

    首先利用有向图查找所有从状态0通过ε转换可达的所有状态,记入一个集合中,这个集合用Bag数据结构来表示。对于集合中的每个状态,检查它是否可以与第一个输入的字符相匹配,如果匹配,在用这些匹配的状态集合继续在有向图中进行查找,就得到了NFA在匹配第一个字符后可达的所有状态的集合。重复这个过程直到可达的状态集合中含有接受状态(匹配成功)或者文本结束(匹配失败)。

    
    public boolean recognize(String txt) {
    
    Bag<Integer> pc = new Bag<Integer>();
    
    DirectedDFS dfs = new DirectedDFS(G, 0);
    
    for (int v = 0; v < G.V(); v++) {
    
    if (dfs.marked(v))
    
    pc.add(v);
    
    }
    
      
    
    for (int i = 0; i < txt.length(); i++) {
    
    Bag<Integer> match = new Bag<Integer>();
    
    for (int v : pc)
    
    if (v < M)
    
    if (re[v] == txt.charAt(i) || re[v] == ".")
    
    match.add(v + 1);
    
    pc = new Bag<Integer>();
    
    dfs = new DirectedDFS(G, match);
    
    for (int v = 0; v < G.V(); v++)
    
    if (dfs.marked(v))
    
    pc.add(v);
    
    }
    
      
    
    for (int v : pc)
    
    if (v == M)
    
    return true;
    
    return false;
    
    }