Bitapアルゴリズム

Bitapアルゴリズム（英: Bitap algorithm）とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、shift-andアルゴリズム・shift-orアルゴリズムとも呼ばれる（andとorがあるのは、ブール代数の双対性にもとづくバリエーションである）。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すあいまい検索（英語版）に利用できることが、他の文字列探索アルゴリズムにない特徴である。

このアルゴリズムの基本的な考え方は1964年にBálint Dömölkiによって紹介された^[1][2]。1977年にR. K. Shyamasundarによって拡張された^[3]。

Ricardo Baeza-Yates、Gaston Gonnetらの成果^[4]をもとに1991年、Wu、Manberらによってあいまい検索へ適用可能であることが示された^[5][6]のち、1996年にBaeza-Yates、Navarroらによって効率化され^[7]、1998年にEugene Myersによって長いパターンへ適用する方法が示された^[8]。

このアルゴリズムを実装しているプログラムとしては、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^{[注 1]}) と呼ばれる近似的パターンマッチングアルゴリズムが設計された。このアルゴリズムは完全一致マッチング用であるBaeza-Yatesの "shift-or" アルゴリズムの一般化である。）と書かれている。よって厳密には、あいまい検索に拡張したアルゴリズムに限定してbitapあるいはWuとManberのアルゴリズムとし、それ以外の名前はそれ以外のアルゴリズムも含む総称とすべきかもしれないが、通常特に区別されていない。

以下、shift-and型を前提に説明する。

例として対象の文字列 T = acbacbaca, パターン文字列 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. R5を1ビット左にシフトする。処理後の値は100100になる。
2. この値と000001とのビット単位のORを取る（つまり最下位ビットを1にする）。処理後の値は100101になる。
3. この値と、右テーブルの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.に相当）。

ビットシフト演算とマスク演算はコンピュータ上で高速に実行可能であり、また、バックトラックが不要なため、パターンに似た配列が含まれるときに高速に動作できる特長がある。

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-and型のバリエーションを前提としている。ブール代数の双対性により、このアルゴリズムにはshift-or型のバリエーションがある。shift-orアルゴリズムでは、shift-andアルゴリズムにおけるビットを反転させた上でビット単位のORで探索を行う。すなわち、#実装例のRubyコードの state（#アルゴリズムの表のR）の初期状態 (R0) は全て1が立っているビット列になり、文字列比較をしていた部分である

state = (state << 1 | 1) & mask[tc] 

は

state = (state << 1) | ~mask[tc] 

になる^{[注 2]}。state が使用するビット範囲^{[注 3]}の最上位ビットが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に変更すればよいだけであるため、容易に大文字小文字を無視する等の拡張ができる。 またレーベンシュタイン距離^{[注 4]}（以下、距離という）を管理することで、距離がパターン文字列に近い文字列を検索するあいまい検索が可能となる。

本来の状態を管理するビット列（#実装例に於けるstate）を距離ゼロ用とし、他に距離1用、距離2用など任意の検出したい最大の距離までのビット列を用意する。以降、距離 i 用の状態管理ビット列を state[i] と表現する。また、以下の文章と図では、AND・ORは特に注記しないかぎりビット単位のAND・ORを意味する。

この図は、文字の挿入のみに対応したshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。

state[0] は完全一致マッチングなので、#アルゴリズムの表と変わりは無い。一方、state[1] では、まず state[0] と同じ処理を行い、その後 state[0] の更新前の値をORしている^[5]。これは、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している^{[5][注 5]}。これは、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している^[5]。これは、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], ... を実装することで、許容する除去文字数を増やした検索が可能になる。

#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。

  # 実際にtextと照合させる   distance = 2                          # 許容する除去文字数   state = Array.new(distance + 1) {|i| (1 << i) - 1}    # 状態遷移を保持   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) & mask[tc]       state[j] |= rstr_mask       next_rstr = state[j] << 1 | 1     # state[j + 1]のビットを1にする位置       rstr_mask = next_rstr     end     if (state[distance] & finish) == finish # 最上位ビットが1である       ret.push(i)                       # マッチした位置iを配列に追加     end   end 

state の初期値が完全一致・挿入・置換の場合とは異なっている。これは、検索対象文字列先頭にすでに除去された文字がある場合に対応したものである。state[n] なら先頭n文字以内の除去の可能性を考慮して、初期値は下位nビット分を1にしておく。これによって、例えばパターン "acbaca" に対して検索対象文字列 "cbacaccc" なら、state[1], state[2], ... では対象文字列先頭で "a" が除去されていると判定し、パターンとのマッチが検出される。

この図は、文字の挿入・置換・除去の全てに対応した本来のshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。

ここまでに説明した挿入・置換・除去それぞれに対応したアルゴリズムで使用したマスクを全てORでまとめた形になっている。state[1] はレーベンシュタイン距離1（挿入・置換・除去のいずれか1回のみ）の変更を許容しており、state[2], state[3], ... で許容するレーベンシュタイン距離を増やした検索が可能になる。

#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。

  # 実際にtextと照合させる   distance = 2                          # 許容するレーベンシュタイン距離   state = Array.new(distance + 1) {|i| (1 << i) - 1}    # 状態遷移を保持   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       next_rstr |= state[j]             # state[j + 1]のビットを1にする位置 (置換時用)       state[j] &= mask[tc]       state[j] |= rstr_mask       next_rstr |= state[j] << 1 | 1    # state[j + 1]のビットを1にする位置 (除去時用)       rstr_mask = next_rstr     end     if (state[distance] & finish) == finish # 最上位ビットが1である       ret.push(i)                       # マッチした位置iを配列に追加     end   end 

1文字置換のレーベンシュタイン距離を2としたい場合は、

next_rstr |= state[j]             # state[j + 1]のビットを1にする位置 (置換時用) 

の行を除去すれば良い。この行の処理がない場合、1文字の置換は1文字挿入の後に1文字除去したものとして扱われ、レーベンシュタイン距離2とすることができる。

注意点としては、ある位置でマッチが検出された場合、その位置の前後でより悪い（レーベンシュタイン距離が長い）マッチが検出されることがある。例えば、"abca" という文字列から "abc" というパターンをレーベンシュタイン距離1以内で探す場合、"ab"（末尾1文字除去）, "abc"（完全一致）, "abca"（末尾1文字挿入）の3カ所でマッチが検出されることになる。そのため、検出位置が重要な場合は対策が必要になる。また開始位置はわからないので検出位置からパターン文字列の長さ＋発見された距離数分戻った位置からやり直して確定することになるが、この場合にも慎重に組まないと直観とは異なる位置が開始位置として算出されることがある。

Bitapアルゴリズムは、元のアルゴリズムのシフト動作と1のORの直後（shift-orの場合はシフト動作の直後）にビット移動処理を追加することで正規表現に対応させることができる。具体的には、shift-andの場合、シフト動作と1のORを行った直後に以下の操作をそれぞれ必要な回数だけ行なう。

取捨

acb?aca であれば、検索パターンを acXbaca とし、Xのビットが1なら acXbaca の二箇所のビットを1にする。Xのビットは0に戻しておく。

正閉包

acb+aca であれば、検索パターンを acbYaca とし、Yのビットが1なら acbYaca の二箇所のビットを1にする。Yのビットは0に戻しておく。

閉包

acb*aca は ac(b+)?aca と等価なので、検索パターンを acXbYaca とし、Xのビットが1なら acXbYaca の二箇所のビットを1にする。Yのビットが1なら acXbYaca の二箇所のビットを1にする。XとYのビットは0に戻しておく。

選言

ac(ba|ab)ca であれば、検索パターンを acZbaUabca とし、Zのビットが1なら acZbaUabca の二箇所のビットを立てる。またUのビットが立っていたら acZbaUabca のビットを1にする。ZとUのビットは0に戻しておく。

上記X, Y, Z, Uは実際の文字ではなく、ビット移動処理を行う場所を示すマーカーである。これらのビット移動処理はNFAで言えばεによる状態遷移に相当する。

取捨の実装例として、検索対象文字列 acaca からパターン acb?aca を検索する場合の動作を以下の表に示す。

上の表では、R2からR3への遷移について説明のために処理フェーズごとに分けて示している。#アルゴリズムの表と比較すると、上記Xの位置を示すビットマスクが追加されている。また、S0000000, S0000100は後述するSの値に応じてビットを1にする位置を示すビットマスクである。

1. Rに対して元のアルゴリズム通りにシフトと1のORを行う。その値をXのビットマスクとANDした結果をSとする。
   R3' (1)はR2に対してシフトと1のORを行った値である。R3' (1)とXのビットマスクのAND結果 (つまりS) は 0000100 になる。
2. Sのビットが1になっている位置に対応したRのビット位置（取捨の場合、取捨対象部分の先頭と取捨対象部分の次の位置）のビットを1にする。
   Sが0000100だった時にビットを1にする位置はビットマスクS0000100にあらかじめ設定してあるので、RにS0000100をORすればよい。S0000100の1が立っている位置は、パターン acb?aca の取捨対象部分の先頭 (acXbaca) と取捨対象部分の次 (acXbaca) である。R3' (2)はこの段階まで処理した値である。
3. X用のビットマスクが1になっている位置のRのビットは0にしておく。
   X用のビットマスクをビット反転 (1111011) してRにANDする。R3' (3)はこの段階まで処理した値である。
4. 元のアルゴリズム通りにマスク処理を行う。
   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 に移動している。

正閉包・選言についても同様な処理で実装できる。

取捨の場合、εによる状態遷移を行なうフェーズは、これらの正規表現の演算子によって追加される一組の整数（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用マスクを用意しておけばよい^{[注 6]}。

また、任意の1文字（基本正規表現での "."）への対応は、全ての文字用マスク（上記例でのa, b, c用マスク）の該当位置のビットを1にしておくだけで容易に実現できる。同様に、その他の文字クラス（[ab], \s など）に対応する場合も、該当する文字用マスクの該当位置のビットを1にしておけばよい。

1. Dömölki, Bálint (1964). “An algorithm for syntactical analysis”. Computational Linguistics (Hungarian Academy of Science) 3: 29–46. 
2. Dömölki, Bálint (1968). “A universal compiler system based on production rules”. BIT Numerical Mathematics 8 (4): 262–275. doi:10.1007/BF01933436. 
3. Shyamasundar, R. K. (1977). “Precedence parsing using Dömölki's algorithm”. International Journal of Computer Mathematics 6 (2): 105–114. 
4. Wu, Sun; Manber, Udi (June 1991). Fast text searching with errors (Technical report). Department of Computer Science, University of Arizona, Tucson. Technical Report TR 91-11。
5. Wu, Sun; Manber, Udi (October 1992). “Fast text search allowing errors”. Communications of the ACM 35 (10): 83–91. doi:10.1145/135239.135244. 
6. Baeza-Yates, Ricardo A.; Gonnet, Gastón H. (October 1992). “A New Approach to Text Searching”. Communications of the ACM 35 (10): 74–82. doi:10.1145/135239.135243. 
7. Baeza-Yates, R.; Navarro, G. (June 1996). Hirchsberg, Dan; Myers, Gene (eds.). A faster algorithm for approximate string matching. Combinatorial Pattern Matching (CPM'96), LNCS 1075. Irvine, CA. pp. 1–23.
8. Myers, G. (May 1999). “A fast bit-vector algorithm for approximate string matching based on dynamic programming”. Journal of the ACM 46 (3): 395–415. 

• オートマトン
• ビットマスク