Bitapアルゴリズム

Bitapアルゴリズム（）とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、shift-andアルゴリズム・shift-orアルゴリズムとも呼ばれる（andとorがあるのは、ブール代数の双対性にもとづくバリエーションである）。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すに利用できることが、他の文字列探索アルゴリズムにない特徴である。
概要.
このアルゴリズムの基本的な考え方は1964年にBálint Dömölkiによって紹介された。1977年にR. K. Shyamasundarによって拡張された。
、らの成果をもとに1991年、、らによってあいまい検索へ適用可能であることが示されたのち、1996年にBaeza-Yates、らによって効率化され、1998年にによって長いパターンへ適用する方法が示された。
このアルゴリズムを実装しているプログラムとしては、agrepというユーティリティがある。
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.""（91年2月: 'bitap' (bit-parallel approximate pattern matching) と呼ばれる近似的パターンマッチングアルゴリズムが設計された。このアルゴリズムは完全一致マッチング用であるBaeza-Yatesの "shift-or" アルゴリズムの一般化である。）と書かれている。よって厳密には、あいまい検索に拡張したアルゴリズムに限定してbitapあるいはWuとManberのアルゴリズムとし、それ以外の名前はそれ以外のアルゴリズムも含む総称とすべきかもしれないが、通常特に区別されていない。
アルゴリズム.
以下、shift-and型を前提に説明する。
例として対象の文字列 T = acb"acbaca", パターン文字列 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 への遷移は以下のようになる。
この処理の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.に相当）。
ビットシフト演算とマスク演算はコンピュータ上で高速に実行可能であり、また、バックトラックが不要なため、パターンに似た配列が含まれるときに高速に動作できる特長がある。
実装例.
Shift-andアルゴリズムをRubyで実装した例と実行結果を以下に示す。このコードでは state が#アルゴリズムの表でのRに相当する。また、変数 pattern が表のパターンPに、変数 text が表のTに相当する。黄色の背景色でハイライトした部分がアルゴリズムの表で示したマッチング処理である。
def shift_and(text, pattern)
 # 必要なビットマスクの数を調べる
 char_table = Array.new # 検索対象文字列に含まれる文字の種類を格納
 text.chars do |tc|
 if not char_table.include?(tc) then
 char_table.push(tc)
 end
 end
 #「適合」したとみなす状態を定義
 finish = 1 « pattern.size-1
 # ビットマスクmaskに必要な領域を確保
 mask = Hash.new
 char_table.each do |ct|
 mask[ct] = 0
 end
 # maskの内容を生成
 pattern.chars do |pc|
 mask.each_key do |mk|
 mask[mk] »= 1
 if pc == mk
 mask[mk] |= finish
 end
 end
 end
 # 実際にtextと照合させる
 state = 0 # 状態遷移を保持
 ret = Array.new # マッチした位置をまとめるための配列
 text.chars.each_with_index do |tc, i|
 state = (state « 1 | 1) & mask[tc]
 if (state & finish) == finish # 最上位ビットが1である
 ret.push(i) # マッチした位置iを配列に追加
 end
 end
 return ret
end
p shift_and("acbacbaca", "acbaca") # => [8]
p shift_and("ababaa", "aba") # => [2, 4]
実行結果（マッチした位置。0オリジンなので、アルゴリズムのセクションで言う9文字目は "8" で表される。）
 [8]
 [2, 4]
Shift-orアルゴリズム.
以上の説明はshift-and型のバリエーションを前提としている。ブール代数の双対性により、このアルゴリズムにはshift-or型のバリエーションがある。shift-orアルゴリズムでは、shift-andアルゴリズムにおけるビットを反転させた上でビット単位のORで探索を行う。すなわち、#実装例のRubyコードの state（#アルゴリズムの表のR）の初期状態 (R0) は全て1が立っているビット列になり、文字列比較をしていた部分である
state = (state « 1 | 1) & mask[tc]
は
state = (state « 1) | ~mask[tc]
になる。state が使用するビット範囲の最上位ビットが0になったときにパターンとマッチする部分が発見されたことになる。
まとめると、shift-orでは実装例のコードの黄色でハイライトした部分が以下のように変更される。
 # 実際にtextと照合させる
 state = ~0 # 状態遷移を保持
 ret = Array.new # マッチした位置をまとめるための配列
 text.chars.each_with_index do |tc, i|
 state = (state « 1) | ~mask[tc]
 if (state & finish) == 0 # 最上位ビットが0である
 ret.push(i) # マッチした位置iを配列に追加
 end
 end
mask[tc] をあらかじめビット反転しておけば、
state = (state « 1) | mask[tc]
としてやや効率化できる。Shift-andと比較すると、1とのビット単位のORを取る操作が減っているが、実際の性能への影響（例えばC言語実装が機械語にコンパイルされた時、実行速度がどの程度改善するか）は微妙だろう。
あいまい検索への適用.
例えば#アルゴリズムのビットマスクに於いて、二文字目はaでもcでも良いという場合にはaのビットマスク(101001)を101011に変更すればよいだけであるため、容易に大文字小文字を無視する等の拡張ができる。
またレーベンシュタイン距離（以下、距離という）を管理することで、距離がパターン文字列に近い文字列を検索するあいまい検索が可能となる。
本来の状態を管理するビット列（#実装例に於けるstate）を距離ゼロ用とし、他に距離1用、距離2用など任意の検出したい最大の距離までのビット列を用意する。以降、距離 i 用の状態管理ビット列を state[i] と表現する。また、以下の文章と図では、AND・ORは特に注記しないかぎりビット単位のAND・ORを意味する。
文字の挿入に対応した検索.
この図は、文字の挿入のみに対応したshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。
state[0] は完全一致マッチングなので、#アルゴリズムの表と変わりは無い。一方、state[1] では、まず state[0] と同じ処理を行い、その後 state[0] の更新前の値をORしている。これは、n - 1文字目まではパターンと完全一致し、n文字目でパターンに一致しない文字が現れた場合に、余計な1文字が挿入されたとみなしてn - 1文字までマッチングした状態に戻しておく（つまり状態更新を1回休みにする）処理と言える。n文字目に来るはずだった文字がn + 1文字目で現れれば、以降は完全一致と同様に状態がアップデートされていく。n文字目がパターンに一致した場合もn - 1文字目のビットが1になるが、これは例えば "acbaca" の "acb" まで一致した時に、実は "acbbaca"と続く場合など、同じ文字が余計に入っている可能性を表すものと解釈できる。
挿入2文字目が現れた場合、state[0]（更新前）のn - 1文字目のビットはすでに0になっているので state[1] のn - 1文字目のビットは1にならない。つまり、state[1] は1文字の挿入まで許容した検索となる。
state[2] は state[1] と同様の処理だが、ORするのは state[1] の更新前の値となる。挿入2文字目が現れた場合、state[1]（更新前）のn - 1文字目のビットはまだ1なので、state[2] のn - 1文字目のビットは1になる。つまり state[2] は2文字の挿入まで許容した検索となる。同様にして state[3], state[4], ... を実装することで、許容する挿入文字数を増やした検索が可能になる。
 # 実際にtextと照合させる
 distance = 2 # 許容する挿入文字数
 state = Array.new(distance + 1) {0} # 状態遷移を保持
 ret = Array.new # マッチした位置をまとめるための配列
 text.chars.each_with_index do |tc, i|
 rstr_mask = 0 # ビットを1にする位置を示すマスク
 state.each_index do |j|
 next_rstr = state[j] # state[j + 1]のビットを1にする位置
 state[j] = (state[j] « 1 | 1) & mask[tc]
 state[j] |= rstr_mask
 rstr_mask = next_rstr
 end
 if (state[distance] & finish) == finish # 最上位ビットが1である
 ret.push(i) # マッチした位置iを配列に追加
 end
 end
state[0] でも rstr_mask とのORを行っているが、この時の rstr_mask の値は0なので state[0] の値は変化しない。
文字の置換に対応した検索.
この図は、文字の置換のみに対応したshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。
state[0] は完全一致マッチングなので、#アルゴリズムの表と変わりは無い。一方、state[1] では、まず state[0] と同じ処理を行い、その後 state[0] の更新前の値を1ビット左シフトして1をORした値をORしている。これは、n - 1文字目まではパターンと完全一致し、n文字目でパターンに一致しない文字が現れた場合に、1文字が置換されたとみなしてn文字目も一致と認める（つまり1回不一致を見逃す）処理と言える。
置換2文字目が現れた場合、state[0]（更新前）のn - 1文字目のビットはすでに0になっているので state[1] のn文字目のビットは1にならない。つまり、state[1] は1文字の置換まで許容した検索となる。
文字の挿入の時と同様に、state[2] では同様の処理を state[1] を参照して行い、これは2文字の置換まで許容した検索となる。以下、state[3], state[4], ... を実装することで、許容する置換文字数を増やした検索が可能になる。
 # 実際にtextと照合させる
 distance = 2 # 許容する置換文字数
 state = Array.new(distance + 1) {0} # 状態遷移を保持
 ret = Array.new # マッチした位置をまとめるための配列
 text.chars.each_with_index do |tc, i|
 rstr_mask = 0 # ビットを1にする位置を示すマスク
 state.each_index do |j|
 state[j] = state[j] « 1 | 1
 next_rstr = state[j] # state[j + 1]のビットを1にする位置
 state[j] &= mask[tc]
 state[j] |= rstr_mask
 rstr_mask = next_rstr
 end
 if (state[distance] & finish) == finish # 最上位ビットが1である
 ret.push(i) # マッチした位置iを配列に追加
 end
 end
文字の除去に対応した検索.
この図は、文字の除去のみに対応した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にならない。つまり、state[1] は1文字の除去まで許容した検索となる。
文字の挿入・置換の時と同様に、state[2] では同様の処理を state[1] を参照して行い、これは2文字の除去まで許容した検索となる。以下、state[3], state[4], ... を実装することで、許容する除去文字数を増やした検索が可能になる。
<syntaxhighlight lang="ruby">
 # 実際にtextと照合させる
 distance = 2 # 許容する除去文字数
 state = Array.new(distance + 1) 
上の表では、R2からR3への遷移について説明のために処理フェーズごとに分けて示している。#アルゴリズムの表と比較すると、上記Xの位置を示すビットマスクが追加されている。また、S0000000, S0000100は後述するSの値に応じてビットを1にする位置を示すビットマスクである。
同様の処理は他の遷移でも行われているが、上記1.で S = 0000000 の場合、ORされるのはS0000000 (= 0) なので元のアルゴリズムと全く同じ結果になる。（S = 0000000 ならば2.と3.の処理を飛ばしてもよい。）R4からR5への遷移では、Sが0000100なのでR2からR3への遷移と同様の処理が行われ、R4で acXbaca で1になっていたビットがR5では acXbaca に移動している。
正閉包・選言についても同様な処理で実装できる。
取捨の場合、εによる状態遷移を行なうフェーズは、これらの正規表現の演算子によって追加される一組の整数（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にしておけばよい。