正規表現対応

ウィキペディア小見出し辞書

正規表現対応

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/12 03:39 UTC 版)

「Bitapアルゴリズム」の記事における「正規表現対応」の解説

Bitapアルゴリズムは、元のアルゴリズムのシフト動作と1のORの直後（shift-orの場合はシフト動作の直後）にビット移動処理を追加することで正規表現に対応させることができる。具体的には、shift-andの場合、シフト動作と1のORを行った直後に以下の操作をそれぞれ必要な回数だけ行なう。 取捨 acb?aca であれば、検索パターンを acXbaca とし、Xのビットが1なら acXbaca の二箇所のビットを1にする。Xのビットは0に戻しておく。 正閉包 acb+aca であれば、検索パターンを acbYaca とし、Yのビットが1なら acbYaca の二箇所のビットを1にする。Yのビットは0に戻しておく。 閉包 acb*aca は ac(b+)?aca と等価なので、検索パターンを acXbYaca とし、Xのビットが1なら acXbYaca の二箇所のビットを1にする。Yのビットが1なら acXbYaca の二箇所のビットを1にする。XとYのビットは0に戻しておく。 選言 ac(ba|ab)ca であれば、検索パターンを acZbaUabca とし、Zのビットが1なら acZbaUabca の二箇所のビットを立てる。またUのビットが立っていたら acZbaUabca のビットを1にする。ZとUのビットは0に戻しておく。 上記X, Y, Z, Uは実際の文字ではなく、ビット移動処理を行う場所を示すマーカーである。これらのビット移動処理はNFAで言えばεによる状態遷移に相当する。 取捨の実装例として、検索対象文字列 acaca からパターン acb?aca を検索する場合の動作を以下の表に示す。 状態遷移0ビットマスク0正規表現用ビットマスクP初期状態acacaa0 1 0 1 1 1 1 0 1 c0 0 1 0 0 0 0 1 0 X0 0 0 1 1 0 0 0 0 b0 0 0 0 1 1 0 0 0 a0 0 0 0 1 1 1 0 1 c0 0 0 0 0 0 0 1 0 a0 0 0 0 0 0 0 0 1 R0R1R2R3' (1)R3' (2)R3' (3)R3R4R5 0 abc1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 XS0000000S00001000 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 上の表では、R2からR3への遷移について説明のために処理フェーズごとに分けて示している。#アルゴリズムの表と比較すると、上記Xの位置を示すビットマスクが追加されている。また、S0000000, S0000100は後述するSの値に応じてビットを1にする位置を示すビットマスクである。 Rに対して元のアルゴリズム通りにシフトと1のORを行う。その値をXのビットマスクとANDした結果をSとする。R3' (1)はR2に対してシフトと1のORを行った値である。R3' (1)とXのビットマスクのAND結果 (つまりS) は 0000100 になる。 Sのビットが1になっている位置に対応したRのビット位置（取捨の場合、取捨対象部分の先頭と取捨対象部分の次の位置）のビットを1にする。Sが0000100だった時にビットを1にする位置はビットマスクS0000100にあらかじめ設定してあるので、RにS0000100をORすればよい。S0000100の1が立っている位置は、パターン acb?aca の取捨対象部分の先頭 (acXbaca) と取捨対象部分の次 (acXbaca) である。R3' (2)はこの段階まで処理した値である。 X用のビットマスクが1になっている位置のRのビットは0にしておく。X用のビットマスクをビット反転 (1111011) してRにANDする。R3' (3)はこの段階まで処理した値である。 元のアルゴリズム通りにマスク処理を行う。R3' (3)にaのビットマスクをANDし、R3が得られる。 同様の処理は他の遷移でも行われているが、上記1.で S = 0000000 の場合、ORされるのはS0000000 (= 0) なので元のアルゴリズムと全く同じ結果になる。（S = 0000000 ならば2.と3.の処理を飛ばしてもよい。）R4からR5への遷移では、Sが0000100なのでR2からR3への遷移と同様の処理が行われ、R4で acXbaca で1になっていたビットがR5では acXbaca に移動している。 正閉包・選言についても同様な処理で実装できる。 取捨の場合、εによる状態遷移を行なうフェーズは、これらの正規表現の演算子によって追加される一組の整数（AND用マスクと、上記実装例でのS0000000, S0000100のようなOR用マスク）を順次処理するだけである。Sは複数の値（Xが一つなら2種類、二つなら4種類など）を取りえるため、ビットを立てる位置を示すビットマスクはSが取りえる全ての値に対応したものをあらかじめ用意しておく。 正閉包でも一組の整数（YのAND用マスクとOR用マスク）、選言であれば二組の整数（ZのAND用マスクとOR用マスク、UのAND用マスクとOR用マスク）が考えられるが、これらX, Y, Z, UのAND用マスクは全てORして一つのAND用マスクにまとめることができる。そして、そのAND用マスクとRをANDした結果（上の例のS）が取りえる全ての値について、対応したOR用マスクを用意しておけばよい。 また、任意の1文字（基本正規表現での "."）への対応は、全ての文字用マスク（上記例でのa, b, c用マスク）の該当位置のビットを1にしておくだけで容易に実現できる。同様に、その他の文字クラス（[ab], \s など）に対応する場合も、該当する文字用マスクの該当位置のビットを1にしておけばよい。