Bitapアルゴリズム
以下、shift-and型を前提に説明する。
例として対象の文字列 T = acbacbaca, パターン文字列 P = acbaca を考える。以下に示す表は横軸にT、縦軸にPを配置し、どのように遷移するかを示すものである。初期状態でRはすべて0で初期化される。右のビットマスクは、パターンP内に a, b, c それぞれが存在する場所が1に、存在しない場所が0になっている。
各R (R0, R1, R2, ...) のビットが1になっている部分は、パターンPの該当位置までマッチ(文字列の一致)が確認されたことを示す。例えば、R7: 001001 は、ビット000001でPの先頭1文字 ("a") とTの検索済み範囲 ("acbacba") の末尾1文字がマッチしている事を示し、ビット001000でPの先頭4文字 ("acba") とTの検索済み範囲の末尾4文字がマッチしていることを示している。
Rの遷移はビットシフトとビット単位のAND・ビット単位のORのみで行われる。例えば R5: 010010 から R6: 000100 への遷移は以下のようになる。
R5を1ビット左にシフトする。
この図は、文字の除去のみに対応したshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。
state[0] は完全一致マッチングなので、#アルゴリズムの表と変わりは無い。一方、state[1] では、まず state[0] と同じ処理を行い、その後 state[0] の更新後の値を1ビット左シフトして1をORした値をORしている。これは、n文字目まで完全一致で進行した場合、n文字目までをn + 1文字の最後の1文字が除去されたものとみなし、n + 1文字目まで一致と認める処理と言える。これにより、次に現れた文字がパターンのn + 2文字目と一致する文字だった場合も、アルゴリズムの表と同じ処理で一致と判定される。
除去2文字目が現れた場合、state[0](更新後)のn文字目のビットはすでに0になっているので state[1] のn + 1文字目のビットは1にならない。
正閉包・選言についても同様な処理で実装できる。
取捨の場合、εによる状態遷移を行なうフェーズは、これらの正規表現の演算子によって追加される一組の整数(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にしておけばよい。