BITAPアルゴリズム

Bitapアルゴリズム（Bitap algorithm）とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、Shift-andアルゴリズム・Shift-orアルゴリズムとも呼ばれる（andとorがあるのは、ブール代数の双対性にもとづくバリエーションである）。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すに利用できることが、他の文字列探索アルゴリズムにない特徴である。以下、Shift-and型を前提に説明する。このアルゴリズムの基本的な考え方は1964年にBálint Dömölkiによって紹介された。1977年にR. K. Shyamasundarによって拡張された。Ricardo Baeza-Yates、Gaston Gonnetらの成果をもとに1991年、Wu、Manberらによってあいまい検索へ適用可能であることが示された のち、1996年にBaeza-Yates、Navarroらによって効率化され、1998年にEugene Myersによって長いパターンへ適用する方法が示された。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のアルゴリズムとし、それ以外の名前はそれ以外のアルゴリズムも含む総称とすべきかもしれないが、通常特に区別されていない。