Bitapアルゴリズム
処理後の値は100100になる。
この値と000001とのビット単位のORを取る(つまり最下位ビットを1にする)。処理後の値は100101になる。
この値と、右テーブルのb用のビットマスク000100とのビット単位のANDを取る(文字列Tの6文字目は "b" なのでb用のビットマスクを使用する)。こうして R6 = 000100 が得られる。
この処理の1.と2.では、マッチング(文字列の一致判定)を後回しにして、R6で1になる可能性があるビットは全て1にしている。3.で行われているのがマッチング処理であり、b用のビットマスクとのANDにより、パターンと一致しなかった部分のビット(この例ではビット100000)が0になる。bのビットマスク000100は、検索済み範囲の最後が "b" の場合、前回が先頭2文字 ("ac") まで一致が確認された状態の時だけパターンと一致することを示すと解釈できる。こうして、ビット演算によって複数のマッチング処理が同時に進行する。
文字列T上を1文字ずつ進みながらこの処理を繰り返して、Rが使用する6ビット範囲の最上位ビットに1が立った時、それまでの経路がマッチした文字列だと言える。
上の表ではR9の時に最上位ビット(表の一番下の行)に1が立っており、4文字目から9文字目までがマッチしたと判定されている。
このアルゴリズムはマッチングするパターンの状態遷移を表す非決定性有限オートマトン (NFA) をエミュレートする。
上記のパターンに対応するNFAはこの図のようになる。図のS1からS6の状態がRの各ビットに相当する。S0は、仮にRに含めても常に1が立っている状態になるため、明示的にRに含めて処理する必要はない。
S0の "?" を除けば、このNFAは分岐がない一本道である。また、状態遷移はS6により近い状態(図で言えば一つ右隣)への一方方向に限られる。そのため、一回のシフト処理と1とのビット単位のORによってNFAの全ての状態遷移先の候補を立て(上記処理の1.と2.に相当)、それらの候補のうち拒否 (reject) されるべきもの全てを一回のマスク処理で拒否することができる(上記処理の3.に相当)。
ビットシフト演算とマスク演算はコンピュータ上で高速に実行可能であり、また、バックトラックが不要なため、パターンに似た配列が含まれるときに高速に動作できる特長がある。
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 に移動している。