アルゴリズム#20--正規表現マッチング原理

本文は正規表現の文法を紹介することはできなくて、重点的に正規表現の整合原理を紹介して、アルゴリズムは実現します.正規表現の応用の強さもよく知られていると思いますが、ここではその応用範囲を紹介しません.
1.正規エンジン
前のKMPアルゴリズムを,パターン文字列で構成されたテキストをスキャンできる有限状態オートマトンと見なすことができる.正規表現については、この考えを広くしなければならない.
KMPの有限状態は自動的にテキストの中の文字によって自身の状態を変える.オートマチックが停止状態に達した場合にのみ一致が見つかります.アルゴリズム自体がこの自動機をシミュレートしており、この自動機の動作がシミュレートしやすいのは、各状態の変換がテキストの文字によって完全に決定されるためである.
正規表現には、より抽象的な自動機(エンジン)、非確定有限状態自動機(NFA)が必要である.正則エンジンは大きく異なる2種類に分けることができる:DFAとNFA、NFAは基本的に伝統的なNFAとPOSIX NFAに分けることができる.
DFA–Deterministic finite automaton確定型有窮自動機
NFA–Non-deterministic finite automaton非確定型有窮自動機

Traditional NFA

POSIX NFA

2.エンジンの違い

DFA:

DFAエンジンは、遡及を必要としないため、線形時に実行されます(したがって、同じ文字を2回テストすることはありません).DFAエンジンは、最も長い可能性のある文字列に一致することも保証します.ただし、DFAエンジンには限られた状態しか含まれていないため、逆参照を持つモードに一致することはできません.また、表示拡張子を構築しないため、サブエクスプレッションをキャプチャすることはできません.

NFA:

従来のNFAエンジンは、いわゆる「貪欲」マッチング遡及アルゴリズムを実行し、正規表現のすべての可能な拡張を指定された順序でテストし、最初のマッチングを受け入れます.従来のNFAは正規表現の特定の拡張を構築してマッチングを成功させるため、サブ表現のマッチングとマッチングの逆参照をキャプチャすることができる.しかしながら、従来のNFAは遡及するため、全く同じ状態に複数回アクセスすることができる(異なる経路を介してその状態に到達する場合).
したがって、最悪の場合、その実行速度は非常に遅い可能性があります.従来のNFAは、発見された最初のマッチングを受け入れるため、他の(より長いかもしれない)マッチングが発見されない可能性がある.
NFAの最も重要な部分:遡及(backtracking).遡ると、道の分岐点ごとにパンのくずが山積みになっているようだ.死の道を行けば、パンくずの標識の未試行の道に出会うまで元の道に戻ることができる.もしその道が通じないならば、あなたは引き続き帰って、次のパンのくずを見つけて、このように繰り返して、道を見つけて、あるいは試したことのない道を歩き終えることができます.

POSIX NFA:

POSIX NFAエンジンは、従来のNFAエンジンと同様であり、異なる点は、可能な最長のマッチングが見つかったことを保証できる前に、遡及を継続することである.そのため、POSIX NFAエンジンの速度は従来のNFAエンジンより遅い.また、POSIX NFAを使用する場合、長いマッチング検索ではなく、遡及検索の順序を変更して短いマッチング検索をサポートすることはできません.
DFAとNFAの比較:

DFAは、テキスト列の各文字を1回スキャンするだけで、比較的速いが、特性は少ない.

NFAは文字を食べたり吐いたりして、スピードが遅くなりますが、特性が豊富なので、逆に広く使われています.Perl、Ruby、Pythonのreモジュール、Java、などの現在の主要な正規表現エンジン.NETのregexライブラリは、すべてNFAです.

NFAのみがlazy、backtracking、backreferenceをサポートし、NFAはデフォルトでgreedyモードを適用し、NFAは再帰的な危険に陥り、性能が極めて悪い可能性があります.

DFAには、サブエクスプレッション(パケット)のペアのペアのマッチング結果をキャプチャできない、貧しい状態のみが含まれているため、backreferenceもサポートされません.
DFAでは、カッコの取得と逆参照はサポートされていません.
POSIX NFAは引き続きbacktrackingを試み、試写画像DFAと同じように最長左サブ正規式を見つける.そのため、POSIX NFAの速度はもっと遅い.

NFAは最左サブマッチングであり、DFAは最長左サブマッチングである.

NFAのコンパイルプロセスは通常速く、必要なメモリも少なくなります.

「通常」の場合の単純なテキストマッチングテストでは、2つのエンジンの速度差は多くありません.一般に,DFAの速度は正規表現とは無関係であり,NFAでは両者は直接相関している.

正規表現への依存性が比較的強いオペレーティングシステム(正規表現を大量に応用して検索マッチングを行う)は、NFA->DFAアルゴリズムを完全に把握し、応用した正規表現エンジンの思想と特性を十分に理解することが望ましい.

3.照合プロセス
まずNFAを構築します.以下の図です.
エンジンマッチング時の運転軌跡を示す方向図です.開始状態0から、1の位置(すなわち「(」の後)に到達するには、2つの選択肢があり、2つの選択肢を歩くこともできるし、6つの選択肢を歩くこともできるし、...最後の受け入れ状態まで行くこともできる.
有向図が得られると,マッチング実装はずっと簡単になる.ここでは,図面への多点到達性の問題であるDirectedDFSアルゴリズムを用いた.

まず状態0からε-到達可能な頂点(ステータス)を変換してセットを初期化します.セットの各頂点について、最初の入力文字と一致するかどうかを確認します.チェックすると、NFAが最初の文字に一致した後に到達する可能性のある他の頂点が得られます.ここでは,その集合にその集合から任意の状態をすべて加える必要がある.ε-到達可能な頂点を変換します.

この最初の文字に一致した後に到達する可能性のあるすべての頂点の集合があり、ε-図中のマルチポイント到達性の問題に変換する答えは、2番目の入力文字の頂点セットに一致する可能性があることです.

このプロセスをテキストが終わるまで繰り返し、2つの結果を得た:最後のセットは許容可能な頂点を含む;含まない.

コメントε-変換します.
4.NFAの構造
正規表現をNFAに変換するプロセスは、Dijkstraのデュアルスタックアルゴリズムが式を評価するプロセスとある程度似ている.
構築ルール:
論理は分かりやすいので、次のコードと軌跡図を参照してください.
5.コード実装
DirectedDFSとDigraphクラスを添付します.

public class NFA 
{ 
    private Digraph graph;     // digraph of epsilon transitions
    private String regexp;     // regular expression
    private int m;             // number of characters in regular expression

    /**
     * Initializes the NFA from the specified regular expression.
     *
     * @param  regexp the regular expression
     */
    public NFA(String regexp) 
    {
        this.regexp = regexp;
        m = regexp.length();
        Stack ops = new Stack(); 
        graph = new Digraph(m+1); 
        for (int i = 0; i < m; i++) 
        { 
            int lp = i; 
            if (regexp.charAt(i) == '(' || regexp.charAt(i) == '|') 
            {
                ops.push(i); 
            }
            else if (regexp.charAt(i) == ')') 
            {
                int or = ops.pop(); 

                // 2-way or operator
                if (regexp.charAt(or) == '|') 
                { 
                    lp = ops.pop();
                    graph.addEdge(lp, or+1);
                    graph.addEdge(or, i);
                }
                else if (regexp.charAt(or) == '(')
                {
                    lp = or;
                }
                else assert false;
            } 

            // closure operator (uses 1-character lookahead)
            if (i < m-1 && regexp.charAt(i+1) == '*') 
            { 
                graph.addEdge(lp, i+1); 
                graph.addEdge(i+1, lp); 
            } 
            if (regexp.charAt(i) == '(' || regexp.charAt(i) == '*' || regexp.charAt(i) == ')') 
            {
                graph.addEdge(i, i+1);
            }
        }
        if (ops.size() != 0)
        {    
            throw new IllegalArgumentException("Invalid regular expression");        
        }
    } 

    /**
     * Returns true if the text is matched by the regular expression.
     * 
     * @param  txt the text
     * @return {@code true} if the text is matched by the regular expression,
     *         {@code false} otherwise
     */
    public boolean recognizes(String txt) 
    {
        DirectedDFS dfs = new DirectedDFS(graph, 0);
        Bag pc = new Bag();
        for (int v = 0; v < graph.V(); v++)
        {
            if (dfs.marked(v)) pc.add(v);
        }

        // Compute possible NFA states for txt[i+1]
        for (int i = 0; i < txt.length(); i++) 
        {
            if (txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')')
            {
                throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'");
            }

            Bag match = new Bag();
            for (int v : pc) 
            {
                if (v == m) 
                {
                    continue;
                }
                if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.')
                {
                    match.add(v+1); 
                }
            }
            dfs = new DirectedDFS(graph, match); 
            pc = new Bag();
            for (int v = 0; v < graph.V(); v++)
            {
                if (dfs.marked(v)) pc.add(v);
            }

            // optimization if no states reachable
            if (pc.size() == 0) 
            {
                return false;
            }
        }

        // check for accept state
        for (int v : pc)
        {
            if (v == m) return true;
        }
        return false;
    }

    /**
     * Unit tests the {@code NFA} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        String regexp = "(" + "(A*B|AC)D" + ")";
        String txt = "AABD";
        NFA nfa = new NFA(regexp);
        System.out.println(nfa.recognizes(txt));
    }
}