NFAエンジンのNFAの表現
先ほどの実行結果のデバッグ情報を見ると、なにやらアルファベットと数字の羅列が表示されています。実はこれが、NFAエンジンでのNFAの表現です。これは正規表現をバイトコードに変換したもので、各行はオペコードとなっています。
第1回で述べた通り、NFAエンジンはNFAの非決定性を深さ優先で探索します。失敗するまで突き進み、失敗をしたら処理を巻き戻すと言う動作を、オペコードのBRANCHで表現します。
試しに、和集合演算をオペコードにするとどうなるかを見てみましょう。まず、和集合演算のNFAの表現は、以下のようなものでした。εにより、状態遷移の可能性が2つに分離しています。
それでは、先ほどのtryコマンドを使い、"a|b"をコンパイルしてできるバイトコードを見てみましょう。
% ./try 'a|b' 1:BRANCH(9) 4:EXACTLY(17)a 9:BRANCH(17) 12:EXACTLY(17)b 17:END(0)
BRANCHが、それぞれの分岐の始まりを表しています。この正規表現では、1:と9:のBRANCHから始まる、2つの分岐があります。1:の分岐は'a'、2:の分岐は'b'にマッチします。マッチングが始まると、NFAエンジンはオペコードの順に従って上から下に処理をして行きます。そして、BRANCHが登場すると枝分かれの準備をします。なお、今回参照にしているエンジンでは、枝分かれは関数の再起呼び出しで表現しています。
例えば、'b'という文字列のマッチングを考えてみましょう。NFAエンジンは、まず1:のBRANCHに入り、'b'が'a'にマッチするかを判定します。ここで、マッチは失敗しますので、再起呼び出しされた関数からreturnで失敗を告げると同時に、1:のBRANCHに書かれている9:のブランチにジャンプします。次に、12:にある通り、'b'と'b'をマッチングさせます。これは成功しますので、そのまま12:に指定されている17:にジャンプし、成功として処理を終了します。
スター演算
もう一つ枝分かれがある例として、繰り返し演算を見ます。繰り返し演算のNFA表現は以下のようなものでした。
この状態遷移図だけを見ると、εによる遷移はありますが枝分かれはしていないように見えます。が、受理状態は連結演算の際に、他のフラグメントとεでつなげられます。よって、元のフラグメントの初期状態に戻るε遷移と、この後ろのフラグメントに続くε遷移の2つの遷移可能性があります。
果たしてそうなっているか、再びtryコマンドで表現を見てみます。ただし、このNFAエンジンではa*のように一文字の繰り返しはBRANCHを利用せずに最適化されてしまいます。そこで、(a)*と言うように括弧で括った正規表現を利用します。
% ./try '(a)*' 1:BRANCH(30) 4:BRANCH(24) 7:OPEN1(10) 10:BRANCH(18) 13:EXACTLY(18)a 18:CLOSE1(21) 21:BACK(4) 24:BRANCH(27) 27:NOTHING(30) 30:END(0)
1:と10:と24:はBRANCH命令となっていますが、実際は枝分かれのない一つのノードです（括弧内に書かれている飛び先(30:や18:や27:)がBRANCHではないことから判断します）。着目すべきは、4:と24:のBRANCHであり、ここで2つに分岐しています。
4:のBRANCHを見ると、13:に"a"とのマッチが含まれます。つまり、こちらは"(a)"が表すノードへ遷移すると言う可能性に該当します。一方の24:のBRANCHはNOTHINGを経てENDに向かう分岐であり、ノード内に入らずに次に進むと言う遷移を表しています。
NFAエンジンが遅かった理由
では、先ほどNFAエンジンが"X*X*X*X*X*X*X*X*X*X*XXXXXXXXXX"に苦戦した理由を考えてみましょう。
まず、X*と言う正規表現ですが、この正規表現は分岐の固まりです。先ほど見たように、繰り返し演算は一つしか枝分かれを誘発しません。しかし、この枝分かれは 21:BACK によってマッチすればするほど繰り返されます。文字列"XXXXXXXXXX"をマッチさせる場合、1つのXに対して、それをX*内のXにマッチさせるか、マッチさせずに次に進めるかの２択の選択肢が用意されます。今回は10個のXがありますので、ここだけで10個の取りうる遷移があるわけです。
この正規表現の場合、正規表現の後方に10個分のXが全てありますので、「X*には1文字もマッチさせない」のが正解です。ところが、NFAエンジンはなるべくXをマッチさせようとするため、先ほどの10の選択肢全てで、誤った選択肢（次のノードに進まずにXにマッチさせる）を選んでしまいます。
さらに悪いことに、最初のX*で「1文字もX*にマッチさせない」と言う選択肢をうまく選べても、その後にも次々とX*が待ち構えています。これらの選択肢全てに置いて、NFAエンジンは誤った選択をします。よって、試さなければいけない遷移の数が爆発してしまい、処理が遅くなってしまうのです。
なお、先ほどのマッチングの場合ですと、X10個を、10個のX*と後続のXの計11パターンのどこかに割り振ることになりますので、その組み合わせの数は11パターンから10個のXの行き先を選ぶ重複組み合わせとなります。よって、20!÷(10!×10!)＝184,756通りあります。成功するのは全て後続のXからとる1パターンだけで、前述した通りNFAエンジンは最後まで誤った選択肢を選び続け、分岐をやり直す回数は184,755回ということになります。
以上、NFAエンジンについて簡単に紹介しました。
まとめ
今回は、連載のまとめとして以下の内容を説明しました。
- DFAエンジンの試用
- NFAとDFAのdump
- NFAエンジンの仕組み
今回の連載で、駆け足ではありますが正規表現エンジンの理論の基礎を説明しました。正規表現が用意されてない環境でも、考え方さえ分かってしまえば案外簡単に自分で実装することができます。ツールとしての正規表現は非常に強力ですので、ぜひとも使いこなし、アプリケーションの作成に役立てて頂ければと思います。
参考資料
- Henry Spencer『regex - Henry Spencer's regular expression libraries』
- Russ Cox『Regular Expression Matching Can Be Simple And Fast』
