Bitapアルゴリズム
Bitapアルゴリズム（）とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、Shift-andアルゴリズム・Shift-orアルゴリズムとも呼ばれる（andとorがあるのは、ブール代数の双対性にもとづくバリエーションである）。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すに利用できることが、他の文字列探索アルゴリズムにない特徴である。以下、Shift-and型を前提に説明する。
このアルゴリズムの基本的な考え方は1964年にBálint Dömölkiによって紹介された。1977年にR. K. Shyamasundarによって拡張された。
、らの成果をもとに1991年、、らによってあいまい検索へ適用可能であることが示された のち、1996年にBaeza-Yates、らによって効率化され、1998年にによって長いパターンへ適用する方法が示された。
bitapという名前については、agrepの添付文書agrep.chronicleの中に「Feb/91: The approximate pattern matching algorithm called 'bitap' (bit-parallel approximate pattern matching) is designed. The algorithm is a generalization of Baeza-Yates' "shift-or" algorithm for exact matching.」と書かれている。よって厳密には、あいまい検索に拡張したアルゴリズムに限定してbitapあるいはWuとManberのアルゴリズムとし、それ以外の名前はそれ以外のアルゴリズムも含む総称とすべきかもしれないが、通常特に区別されていない。
このアルゴリズムはマッチさせるパターンの状態遷移を表す決定性有限オートマトン(DFA)をエミュレートする。1つの立っている（shift-orなら降りている）ビットが1つの非決定性有限オートマトン(NFA)に対応し、またその立っている位置が該NFAの状態を示している。これ等複数のNFAの状態を同時管理した一つの整数がDFAの状態となっている。そしてこれ等各々のNFAの状態遷移を連接のみに限ることにより一回のシフト動作で全てのNFAの状態遷移を同時に行なえ、また同様にアトムを文字クラスのみに限ることにより一回のマスク動作で必要な全てのNFAの拒否(reject)を行なえるアルゴリズムとなっている。
（→#正規表現との関係）
例として対象の文字列T=acb"acbaca",パターン文字列P="acbaca"を考える。以下に示す表は横軸にT、縦軸にPを配置し、どのように遷移するかを示すものである。初期状態でRはすべて0で初期化される。
この表で例えばR6=001000からR7=100100への遷移はR6を1ビット右にシフトしたもの(000100)と1とのORを取った後(100100)、aに当たるビットマスク(100101)とのビット単位でのANDを取った値に等しい。
こうして最上位ビットに1がたったとき、それまでの経路がマッチした文字列だと言える。バックトラックが不要なため、パターンに似た配列が含まれるときに高速に動作できる。
このアルゴリズムを実装しているプログラムとしては、agrepというユーティリティがある。
Rubyで実装した例と実行結果を以下に示す。
以上の説明はShift-and型のバリエーションを前提としている。ブール代数の双対性により、このアルゴリズムにはShift-or型のバリエーションがある。Shift-orアルゴリズムでは、Shift-andアルゴリズムにおけるビットを反転させた上でビットごとのORで探索を行う。すなわち、初期状態はパターン文字列Pの長さと同じだけの1が立っているビット列であり、先ほどの実装例で文字列比較をしていた部分であるcodice_1をcodice_2とする。最上位ビットが0になったときに入力Tは受理される。C言語レベルで見ると1をORする操作が必要無くなるが、機械語コードでどの程度性能に影響するかは微妙だろう。実装例などはShift-andとほとんど変わらないのでここでは割愛する。
例えば#アルゴリズムのビットマスクに於いて、二文字目はaでもcでも良いという場合にはaのビットマスク(100101)を110101に変更すればよいだけであるため、容易に大文字小文字を無視する等の拡張ができる。
またレーベンシュタイン距離（以下、距離という）を管理することで、距離がパターン文字列に近い文字列を検索するあいまい検索が可能となる。
本来の状態を管理するビット列（#実装例に於けるstate）を距離ゼロ用とし、他に距離１用、距離２用など任意の検出したい最大の距離までのビット列を用意する。以降、係かる距離 i 用のビット列をstate[i]と表現する。
これにより、本来なら4.で消される（＝rejectされる）はずだったビットが5.により距離+1で（その位置（置換）と直前（挿入）と直後（除去）として）復活することとなり、そのまま生き残り続けるかさらに距離+1に移動されるかして、距離が遠くなり過ぎる（＝最大の距離でも生き残れなくなる）まで生き残り続ける。
注意点としては、より長い一致が存在するにも関わらずパターン文字列の末尾が失われた（＝距離が遠い）一致として発見されるので、検出位置が重要な場合はそれへの対策が必要になる。また開始位置はわからないので検出位置からパターン文字列の長さ＋発見された距離数分戻った位置からやり直して確定することになるが、この場合にも慎重に組まないと直観とは異なる位置が開始位置として算出されることがある。
このアルゴリズムは決定性有限オートマトン(DFA)で実装された正規表現のサブセットであり、このDFAは遷移先が複数ある状態遷移を持たないという特徴を持っている。より具体的には、連接及び文字クラスという（rejectする以外は）単一の遷移先しかない状態遷移のみを持つ。
このことより、単に複数の遷移先を持った状態遷移を管理する機能を具備させるだけで容易にフルセットのDFA正規表現へと変更することが出来る。特に複数の遷移先を持つノードでの遷移をεによる状態遷移のみに限るように構成すれば、シフト動作の後、rejectのマスク動作の前にεによる状態遷移を行なうフェーズを挿入するだけで済むので全体的な構成への影響が少なくて済む。しかしながらこれは「一回のシフト動作と二回のマスク動作だけで同時に全てのNFAの状態遷移とreject、acceptが行なえる」という高速性の由来となる特徴を失った、何等の特徴を持たない教科書的なDFA正規表現の実装の一つに過ぎない。
具体的にはシフト動作の後に
をそれぞれ必要な回数だけ行なうことになる。
これ等は全て、特定のビットのみを立てた整数とANDした結果がゼロでなければそれをビット反転した整数とANDし、対応する整数とORする（shift-andの場合）という処理に統一される。なのでεによる状態遷移を行なうフェーズでは、これ等正規表現の演算子によって追加される二整数（判定用にANDする整数とそれに対応してORする整数）の組の全てを順次処理するだけであり、この組は正閉包／取捨であれば一つ、選言であれば二つが追加される。この追加された二整数の組は、適切に正規化されていれば順不同で一通りを処理するだけで済むが、正規化されていない場合は順序が重要になる。この正規化や順序に関しては、一般的なDFAやNFAの実装に於ける「遷移先がεによる状態遷移を持っていた場合の効率的な実装」に関わる問題でありBitapアルゴリズムの問題ではない。