カスタム検索

メタキャラクタ「.」の一処理法

1998/01/08

正規表現をε遷移を取り除いた NFA に変換して処理する際の、 不確定な要素の処理方法についての報告をする。 規模の大きな正規表現で大量のパターンマッチをする場合、 NFA を参照しながら DFA をシミュレートするよりも、 NFA を DFA に一括変換して DFA を参照しながらパターンマッチを行う方が、 変換のオーバヘッドがあっても効率が良いとされている。 ここでは、任意の一文字を表すメタキャラクタ「.」をε遷移を 取り除いた NFA の枠組みの中で、処理する方策を述べる。

正規表現を構文解析し NFA、さらに DFA へ変換 すると、NFA の不確定要素であるε遷移が無くなるので、DFA での遷 移は文字が与えられたら、一つだけ遷移先が決まる。ε遷移は、文字 を必要とせず、複数の遷移先を持つことが可能であるが(よって、遷移 先をすぐには決められない)、通常の遷移は一つの文字に対し、一つの 遷移先しか持てないためである。ここで、メタキャラクタ「.」を導入 し、「.」が含まれている

(a|.b)*a

という正規表現をε遷移を取り除いた NFA 遷移表に変換すると 以下のようになる。数字は、状態番号である。 左の状態から上の状態へと遷移することにする。 初期状態は 0、終了状態は 2 である。「.」は、 内部コード(1 文字 4 バイト)の使われていない領域に割り当て、 特殊な文字として扱うことにする。今回は 4 バイト文字を扱うため、 単純に任意の文字に展開して処理できないためである。 

 |0 1 2 3
-+-------
0|  . a
1|      b
2|  . a
3|  . a

繰り返すが、メタキャラクタ「.」は任意の一文字を表すので、 上記の正規表現では入力文字の先頭が「a」の場合、「a」と 「.b」のどちらに分岐したら良いか、即座に判別できない。 次の入力文字も判断材料にする必要が出てくる。このように、 即座に分岐を判断できない分岐箇所を、単に「分岐点」と呼ぶ ことにする（一般的な用語ではない、独自の用語である）。 言い方を変えると、上の表の横の列を見て「.」と通常の文字が、 並んでいる状態が分岐点である。状態 0, 2, 3 が分岐点であると言える。 分岐点は何ヵ所も出現する可能性がある。「.」の導入によって、 上述の「DFA での遷移は文字が与えられたら、 一つだけ遷移先が決まる」という前提が崩れてしまったことになるのである。 ε遷移を取り除いても、上の表は DFA とは言えないのである。

そこで、分岐点をスタックに覚えておき、分岐先をしらみつぶしに 探索する際に分岐した先が間違っていたら後戻り(バックトラック) するような実装を施してみた。実際には [^abc] なども実装して あるが、以下のアルゴリズムの自然な拡張になっている。

基本アルゴリズム

  1. スタックを初期化する。
  2. 入力された文字で遷移を試みる。 この際に、その文字で遷移できるのであれば、その遷移を選ぶ。 スタックに状態をPUSH。
  3. 成功なら次の文字で試みる。 入力文字が無くなったら終了( マッチした) 。
  4. 失敗ならPOP して「. 」で遷移を試みる。 スタックに状態をPUSH。入力文字が無くなったら終了( マッチした) 。
  5. 「. 」でも失敗したら、入力された文字で分岐しているところまで POP し て「. 」で遷移を試みる。すべてPOP したら終了( マッチしなかった) 。
  6. スタックをクリアする。

スタックにPUSHする条件

保存する状態は、「分岐点の状態番号( 分岐状態) 」、「文字へのポインタ」、 そして「通過フラグ」である。ある分岐点のすべての分岐先を探索し終えたら、 「通過済み」とする。保存する条件は、以下の通りである。 スタックが空でない時の条件は、無限ループを防ぐための条件である。

スタック・トップの書き換え

例えば、入力文字列が ababa の場合、0->1->(3)->1->(3)->2 の ように遷移する。状態 3 に括弧を付けたのは、同じ分岐点を 2 回 通過するのを強調するためである。2 回の通過とは、 スタック・トップに記録されている「通過済み」の同じ番号の状態に、 再び遷移してきたことを言う。 2 回目の通過時にも 1 回目と同じように探索できるように条件を 等しくする必要がある。

具体的には、スタックが空でない時に、スタック・トップの分岐 状態が現在の状態と同じであり、スタック・トップの通過フラグが 「通過済み」である場合に、スタック・トップの通過フラグを 「未通過」に書き換えることで実現できる。PUSH する時点で スタック・トップと現在の状態から判断して、PUSH 操作をこの 「書き換え」操作に置き換えるのである。これは上述の、 無限ループを防ぐ条件を満たしながら、探索を遂行するための工夫である。

スタックから POP する条件

スタックが空でないとき、以下の処理を行う。「通過済み」とは、 探索が終了している分岐点のことを表している。 「未通過」の分岐点にまで戻るか、スタックが空になるまで、 POP し続けることを意味している。 

rollback()
{
    for (;;){
        if (スタック・トップの通過フラグが「通過済み」の場合){
            POP();
            if (スタックが空の場合){
                return;
            }
        }else{
            break;
        }
    }
    スタック・トップの内容をコンテクストに反映;
    POP();

    return;
}

今後の予定

現状では、DFA に近い状態まで変換しているのに不確定な処理を しなければならないことを述べた。今後は、上記のような正規 表現を変換して、不確定要素である「. 」を消し去る方法を 考えていきたい。実現すればバックトラックが不必要になるので 本物の DFA になり、NFA から変換する利点が強調できるだろう。

謝辞

動作の検証時には、伝法谷秀有氏に協力して頂きました。 また、ProgWin0 ML の皆さんからは、文章の誤りや理解困難な点をご指摘下さるなど、 多大な貢献がありました。御礼申し上げます。

HOME

Valid XHTML 1.0!