Bitapアルゴリズム
Bitapアルゴリズム(英: Bitap algorithm)とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、shift-andアルゴリズム・shift-orアルゴリズムとも呼ばれる(andとorがあるのは、ブール代数の双対性にもとづくバリエーションである)。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すあいまい検索(英語版)に利用できることが、他の文字列探索アルゴリズムにない特徴である。
Bitapアルゴリズムは、元のアルゴリズムのシフト動作と1のORの直後(shift-orの場合はシフト動作の直後)にビット移動処理を追加することで正規表現に対応させることができる。具体的には、shift-andの場合、シフト動作と1のORを行った直後に以下の操作をそれぞれ必要な回数だけ行なう。
このアルゴリズムの基本的な考え方は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によって長いパターンへ適用する方法が示された。
このアルゴリズムを実装しているプログラムとしては、agrepというユーティリティがある。
Bitapという名前については、agrepの添付文書agrep.chronicleの中に "Feb/91: The approximate pattern matching algorithm called 'bitap' (bit-parallel approximate pattern matching) is designed.
この図は、文字の挿入・置換・除去の全てに対応した本来のshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。
ここまでに説明した挿入・置換・除去それぞれに対応したアルゴリズムで使用したマスクを全てORでまとめた形になっている。state[1] はレーベンシュタイン距離1(挿入・置換・除去のいずれか1回のみ)の変更を許容しており、state[2], state[3], ... で許容するレーベンシュタイン距離を増やした検索が可能になる。
#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。
1文字置換のレーベンシュタイン距離を2としたい場合は、
の行を除去すれば良い。この行の処理がない場合、1文字の置換は1文字挿入の後に1文字除去したものとして扱われ、レーベンシュタイン距離2とすることができる。
注意点としては、ある位置でマッチが検出された場合、その位置の前後でより悪い(レーベンシュタイン距離が長い)マッチが検出されることがある。例えば、"abca" という文字列から "abc" というパターンをレーベンシュタイン距離1以内で探す場合、"ab"(末尾1文字除去), "abc"(完全一致), "abca"(末尾1文字挿入)の3カ所でマッチが検出されることになる。そのため、検出位置が重要な場合は対策が必要になる。また開始位置はわからないので検出位置からパターン文字列の長さ+発見された距離数分戻った位置からやり直して確定することになるが、この場合にも慎重に組まないと直観とは異なる位置が開始位置として算出されることがある。
つまり、state[1] は1文字の除去まで許容した検索となる。
文字の挿入・置換の時と同様に、state[2] では同様の処理を state[1] を参照して行い、これは2文字の除去まで許容した検索となる。以下、state[3], state[4], ... を実装することで、許容する除去文字数を増やした検索が可能になる。
#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。
state の初期値が完全一致・挿入・置換の場合とは異なっている。これは、検索対象文字列先頭にすでに除去された文字がある場合に対応したものである。state[n] なら先頭n文字以内の除去の可能性を考慮して、初期値は下位nビット分を1にしておく。これによって、例えばパターン "acbaca" に対して検索対象文字列 "cbacaccc" なら、state[1], state[2], ... では対象文字列先頭で "a" が除去されていると判定し、パターンとのマッチが検出される。