Bitapアルゴリズム

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

1. 概要
-----

このアルゴリズムの基本的な考え方は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'  is designed. The algorithm is a generalization of Baeza-Yates' "shift-or" algorithm for exact matching.//"と書かれている。よって厳密には、あいまい検索に拡張したアルゴリズムに限定してbitapあるいはWuとManberのアルゴリズムとし、それ以外の名前はそれ以外のアルゴリズムも含む総称とすべきかもしれないが、通常特に区別されていない。

2. アルゴリズム
---------

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

例として対象の文字列 T = acb//acbaca//, パターン文字列 P = //acbaca// を考える。以下に示す表は横軸にT、縦軸にPを配置し、どのように遷移するかを示すものである。初期状態でRはすべて0で初期化される。右のビットマスクは、パターンP内に a, b, c それぞれが存在する場所が1に、存在しない場所が0になっている。



各R  のビットが1になっている部分は、パターンPの該当位置までマッチが確認されたことを示す。例えば、R7: 001001 は、ビット000001でPの先頭1文字  とTの検索済み範囲  の末尾1文字がマッチしている事を示し、ビット001000でPの先頭4文字  とTの検索済み範囲の末尾4文字がマッチしていることを示している。Rの遷移はビットシフトとビット単位のAND・ビット単位のORのみで行われる。例えば R5: 010010 から R6: 000100 への遷移は以下のようになる。

R5を1ビット左にシフトする。処理後の値は100100になる。
この値と000001とのビット単位のORを取る。処理後の値は100101になる。
この値と、右テーブルのb用のビットマスク000100とのビット単位のANDを取る。こうして R6 = 000100 が得られる。この処理の1.と2.では、マッチングを後回しにして、R6で1になる可能性があるビットは全て1にしている。3.で行われているのがマッチング処理であり、b用のビットマスクとのANDにより、パターンと一致しなかった部分のビットが0になる。bのビットマスク000100は、検索済み範囲の最後が "b" の場合、前回が先頭2文字  まで一致が確認された状態の時だけパターンと一致することを示すと解釈できる。こうして、ビット演算によって複数のマッチング処理が同時に進行する。

文字列T上を1文字ずつ進みながらこの処理を繰り返して、Rが使用する6ビット範囲の最上位ビットに1が立った時、それまでの経路がマッチした文字列だと言える。上の表ではR9の時に最上位ビットに1が立っており、4文字目から9文字目までがマッチしたと判定されている。

このアルゴリズムはマッチングするパターンの状態遷移を表す非決定性有限オートマトン  をエミュレートする。

上記のパターンに対応するNFAはこの図のようになる。図のS1からS6の状態がRの各ビットに相当する。S0は、仮にRに含めても常に1が立っている状態になるため、明示的にRに含めて処理する必要はない。S0の "?" を除けば、このNFAは分岐がない一本道である。また、状態遷移はS6により近い状態への一方方向に限られる。そのため、一回のシフト処理と1とのビット単位のORによってNFAの全ての状態遷移先の候補を立て、それらの候補のうち拒否  されるべきもの全てを一回のマスク処理で拒否することができる。

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

3. 実装例
------

Shift-andアルゴリズムをRubyで実装した例と実行結果を以下に示す。このコードでは state が#アルゴリズムの表でのRに相当する。また、変数 pattern が表のパターンPに、変数 text が表のTに相当する。黄色の背景色でハイライトした部分がアルゴリズムの表で示したマッチング処理である。

すべてのマッチした位置の末尾が配列として戻るdef shift_and

必要なビットマスクの数を調べるchar_table = Array.new # 検索対象文字列に含まれる文字の種類を格納 text.chars do |tc| if not char_table.include? then char_table.push 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 =  & mask[tc] if  == finish # 最上位ビットが1である ret.push # マッチした位置iを配列に追加 end end

return ret end

p shift_and # => [8] p shift_and # => [2, 4]<WtXmlEndTag />

実行結果

[8] [2, 4]

4. Shift-orアルゴリズム
-----------------

以上の説明はshift-and型のバリエーションを前提としている。ブール代数の双対性により、このアルゴリズムにはshift-or型のバリエーションがある。shift-orアルゴリズムでは、shift-andアルゴリズムにおけるビットを反転させた上でビット単位のORで探索を行う。すなわち、#実装例のRubyコードの stateの初期状態  は全て1が立っているビット列になり、文字列比較をしていた部分である state =  & mask[tc] は state =  | ~mask[tc] になる。state が使用するビット範囲の最上位ビットが0になったときにパターンとマッチする部分が発見されたことになる。

まとめると、shift-orでは実装例のコードの黄色でハイライトした部分が以下のように変更される。

実際にtextと照合させるstate = ~0 # 状態遷移を保持 ret = Array.new # マッチした位置をまとめるための配列 text.chars.each_with_index do |tc, i| state =  | ~mask[tc] if  == 0 # 最上位ビットが0である ret.push # マッチした位置iを配列に追加 end end<WtXmlEndTag /> mask[tc] をあらかじめビット反転しておけば、 state =  | mask[tc] としてやや効率化できる。Shift-andと比較すると、1とのビット単位のORを取る操作が減っているが、実際の性能への影響は微妙だろう。

5. あいまい検索への適用
-------------

例えば#アルゴリズムのビットマスクに於いて、二文字目はaでもcでも良いという場合にはaのビットマスクを101011に変更すればよいだけであるため、容易に大文字小文字を無視する等の拡張ができる。 またレーベンシュタイン距離を管理することで、距離がパターン文字列に近い文字列を検索するあいまい検索が可能となる。

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

5.1. 文字の挿入に対応した検索
-----------------

この図は、文字の挿入のみに対応したshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。state[0] は完全一致マッチングなので、#アルゴリズムの表と変わりは無い。一方、state[1] では、まず state[0] と同じ処理を行い、その後 state[0] の更新前の値をORしている。これは、n - 1文字目まではパターンと完全一致し、n文字目でパターンに一致しない文字が現れた場合に、余計な1文字が挿入されたとみなしてn - 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 {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] =  & mask[tc] state[j] |= rstr_mask rstr_mask = next_rstr end if  == finish # 最上位ビットが1である ret.push # マッチした位置iを配列に追加 end end<WtXmlEndTag /> state[0] でも rstr_mask とのORを行っているが、この時の rstr_mask の値は0なので state[0] の値は変化しない。

5.2. 文字の置換に対応した検索
-----------------

この図は、文字の置換のみに対応したshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。state[0] は完全一致マッチングなので、#アルゴリズムの表と変わりは無い。一方、state[1] では、まず state[0] と同じ処理を行い、その後 state[0] の更新前の値を1ビット左シフトして1をORした値をORしているgroup="注"。これは、n - 1文字目まではパターンと完全一致し、n文字目でパターンに一致しない文字が現れた場合に、1文字が置換されたとみなしてn文字目も一致と認める処理と言える。

置換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 {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  == finish # 最上位ビットが1である ret.push # マッチした位置iを配列に追加 end end<WtXmlEndTag />

5.3. 文字の除去に対応した検索
-----------------

この図は、文字の除去のみに対応した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], ... を実装することで、許容する除去文字数を増やした検索が可能になる。#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。

実際にtextと照合させるdistance = 2 # 許容する除去文字数 state = Array.new i # 状態遷移を保持 ret = Array.new # マッチした位置をまとめるための配列 text.chars.each_with_index do |tc, i| rstr_mask = 0 # ビットを1にする位置を示すマスク state.each_index do |j| state[j] =  & mask[tc] state[j] |= rstr_mask next_rstr = state[j] << 1 | 1 # state[j + 1]のビットを1にする位置 rstr_mask = next_rstr end if  == finish # 最上位ビットが1である ret.push # マッチした位置iを配列に追加 end end<WtXmlEndTag /> state の初期値が完全一致・挿入・置換の場合とは異なっている。これは、検索対象文字列先頭にすでに除去された文字がある場合に対応したものである。state[n] なら先頭n文字以内の除去の可能性を考慮して、初期値は下位nビット分を1にしておく。これによって、例えばパターン "acbaca" に対して検索対象文字列 "cbacaccc" なら、state[1], state[2], ... では対象文字列先頭で "a" が除去されていると判定し、パターンとのマッチが検出される。

5.4. 文字の挿入・置換・除去に対応した検索
-----------------------

この図は、文字の挿入・置換・除去の全てに対応した本来のshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。ここまでに説明した挿入・置換・除去それぞれに対応したアルゴリズムで使用したマスクを全てORでまとめた形になっている。state[1] はレーベンシュタイン距離1の変更を許容しており、state[2], state[3], ... で許容するレーベンシュタイン距離を増やした検索が可能になる。#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。

実際にtextと照合させるdistance = 2 # 許容するレーベンシュタイン距離 state = Array.new i # 状態遷移を保持 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  == finish # 最上位ビットが1である ret.push # マッチした位置iを配列に追加 end end<WtXmlEndTag /> 1文字置換のレーベンシュタイン距離を2としたい場合は、 next_rstr |= state[j] # state[j + 1]のビットを1にする位置  の行を除去すれば良い。この行の処理がない場合、1文字の置換は1文字挿入の後に1文字除去したものとして扱われ、レーベンシュタイン距離2とすることができる。

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

6. 正規表現対応
---------

Bitapアルゴリズムは、元のアルゴリズムのシフト動作と1の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?aca と等価なので、検索パターンを acXbYaca とし、Xのビットが1なら acXbYaca の二箇所のビットを1にする。Yのビットが1なら acXbYaca の二箇所のビットを1にする。XとYのビットは0に戻しておく。選言:acca であれば、検索パターンを 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にする位置を示すビットマスクである。
Rに対して元のアルゴリズム通りにシフトと1のORを行う。その値をXのビットマスクとANDした結果をSとする。
R3' はR2に対してシフトと1のORを行った値である。R3' とXのビットマスクのAND結果  は 0000100 になる。
Sのビットが1になっている位置に対応したRのビット位置のビットを1にする。
Sが0000100だった時にビットを1にする位置はビットマスクS0000100にあらかじめ設定してあるので、RにS0000100をORすればよい。S0000100の1が立っている位置は、パターン acb?aca の取捨対象部分の先頭  と取捨対象部分の次  である。R3' はこの段階まで処理した値である。
X用のビットマスクが1になっている位置のRのビットは0にしておく。
X用のビットマスクをビット反転  してRにANDする。R3' はこの段階まで処理した値である。
元のアルゴリズム通りにマスク処理を行う。
R3' にaのビットマスクをANDし、R3が得られる。同様の処理は他の遷移でも行われているが、上記1.で S = 0000000 の場合、ORされるのはS0000000  なので元のアルゴリズムと全く同じ結果になる。R4からR5への遷移では、Sが0000100なのでR2からR3への遷移と同様の処理が行われ、R4で acXbaca で1になっていたビットがR5では acXbaca に移動している。

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

取捨の場合、εによる状態遷移を行なうフェーズは、これらの正規表現の演算子によって追加される一組の整数を順次処理するだけである。Sは複数の値を取りえるため、ビットを立てる位置を示すビットマスクはSが取りえる全ての値に対応したものをあらかじめ用意しておく。

正閉包でも一組の整数、選言であれば二組の整数が考えられるが、これらX, Y, Z, UのAND用マスクは全てORして一つのAND用マスクにまとめることができる。そして、そのAND用マスクとRをANDした結果が取りえる全ての値について、対応したOR用マスクを用意しておけばよいgroup="注"。

また、任意の1文字への対応は、全ての文字用マスクの該当位置のビットを1にしておくだけで容易に実現できる。同様に、その他の文字クラスに対応する場合も、該当する文字用マスクの該当位置のビットを1にしておけばよい。

7. 脚注
-----

8. 出典
-----

9. 参考文献
-------

10. 関連項目
--------

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