Bitapアルゴリズム

Bitapアルゴリズムとは

Bitapアルゴリズムは、ビット演算の並列性を利用した文字列探索アルゴリズムです。Baeza-Yates-Gonnetアルゴリズムやshift-and/shift-orアルゴリズムとしても知られています。特に、レーベンシュタイン距離などの編集距離に基づく「似た」文字列を検索するあいまい検索において、他のアルゴリズムにはない優れた特徴を持っています。

歴史

Bitapアルゴリズムの基本的な考え方は、1964年にBálint Dömölkiによって紹介されました。その後、1977年にR. K. Shyamasundarによって拡張され、1991年にはWuとManberによってあいまい検索への応用が示されました。1996年にはBaeza-YatesとNavarroによって効率化され、1998年にはEugene Myersによって長いパターンへの適用方法が示されました。

名前について

Bitapという名前は、agrepというユーティリティの添付文書に記述された「bit-parallel approximate pattern matching」に由来します。正確には、あいまい検索に拡張されたアルゴリズムをBitapあるいはWuとManberのアルゴリズムと呼ぶべきですが、一般的には区別されていません。

アルゴリズムの詳細

ここでは、shift-and型のBitapアルゴリズムを例に、その動作原理を説明します。

基本的な考え方

文字列T = "acbacbaca" から、パターンP = "acbaca" を検索する例を考えます。アルゴリズムでは、文字列TとパターンPを縦横に配置した表を考え、各位置でのマッチング状態をビットで表現します。初期状態では、全て0で初期化されたビット列Rを用意します。また、パターンP内の各文字（a, b, c）の出現位置をビットで表したビットマスクを作成します。

各Rのビットが1である箇所は、パターンPの対応する位置まで文字列の一致が確認されたことを意味します。例えば、R7のビット列が "001001" である場合、先頭1文字("a")と先頭4文字("acba")が、それぞれ対応するTの末尾1文字、4文字と一致していることを示します。

Rの遷移

Rの遷移は、ビットシフトとビット単位のAND、OR演算のみで行われます。

例として、R5: "010010" から R6: "000100" への遷移を見てみましょう。

1. R5を1ビット左にシフトし、"100100" になります。
2. この値と "000001" とのOR演算を行い、最下位ビットを1にして "100101" にします。
3. この値と、文字列Tの6文字目 ("b") に対応するビットマスク "000100" とのAND演算を行い、R6 = "000100" を得ます。

この処理では、1,2でマッチの可能性のある箇所を全て立てて、3でマッチしなかった箇所を0にします。ビット演算によって、複数のマッチング処理が並行して進みます。そして、Rの最上位ビットが1になった時、パターンとのマッチが検出されます。

このアルゴリズムは、パターンに対応する非決定性有限オートマトン (NFA) をエミュレートしています。NFAの状態遷移は一方向であるため、1回のシフト処理とOR演算で状態遷移の候補を立て、マスク処理で不適切なものを排除できます。ビットシフトとマスク演算は高速に実行でき、バックトラックが不要なため、パターンに似た配列が含まれる場合に高速に動作します。

Rubyによる実装例

ruby
def shift_and(pattern, text)
m = pattern.size
n = text.size
matches = []

mask = {}
(0...m).each do |i|
mask[pattern[i]] ||= 0
mask[pattern[i]] |= (1 << i)
end

state = 0
(0...n).each do |i|
state = (state << 1 | 1) & (mask[text[i]] || 0)
if (state & (1 << (m - 1))) != 0
matches << i - m + 1
end
end
matches
end

pattern = "acbaca"
text = "acbacbaca"
puts shift_and(pattern, text)

pattern = "a"
text = "abababa"
puts shift_and(pattern,text)


実行結果


[4]
[0, 2, 4]

Shift-orアルゴリズム

Shift-andアルゴリズムの他に、双対性を持つShift-orアルゴリズムがあります。Shift-orアルゴリズムでは、ビットを反転させ、OR演算を使用します。初期状態では、全てのビットが1になり、文字列比較部分がANDからORになります。最上位ビットが0になった時にパターンマッチが検出されます。Shift-orアルゴリズムでは、1とのOR演算を省略でき、効率化が可能です。

あいまい検索への適用

Bitapアルゴリズムは、あいまい検索に容易に拡張できます。例えば、ビットマスクを拡張することで、大文字小文字を無視したり、特定の文字の置換を許容したりできます。また、レーベンシュタイン距離を管理することで、編集距離が近い文字列を検索できます。

挿入、置換、削除に対応した検索

レーベンシュタイン距離を管理するために、距離ゼロ用の状態を管理するビット列に加え、距離1用、距離2用といったビット列を用意します。各距離用のビット列をそれぞれ state[i] と表現します。

挿入に対応した検索
state[0] は完全一致の検索を行います。state[1] は、state[0] と同じ処理を行い、加えてstate[0] の更新前の値をORします。これにより、1文字の挿入を許容した検索が可能になります。
置換に対応した検索
state[1] では、state[0] と同じ処理を行い、state[0] の更新前の値を1ビット左にシフトして1をORした値をORします。これにより、1文字の置換を許容した検索が可能になります。
削除に対応した検索
state[1] では、state[0] と同じ処理を行い、state[0] の更新後の値を1ビット左にシフトして1をORした値をORします。これにより、1文字の削除を許容した検索が可能になります。

これらの処理を組み合わせることで、挿入、置換、削除のすべてに対応した検索が可能になります。また、各stateに対応するビット列を用意することで、許容するレーベンシュタイン距離を増やした検索ができます。

実装例

以下に、挿入、置換、削除の全てに対応した検索を行うrubyコードのハイライト部分を示します。

ruby
state_new = []
(0..max_distance).each do |i|
state_new[i] = (state[i] << 1 | 1) & (mask[text[ti]] || 0)
end

(1..max_distance).each do |i|
state_new[i] = state_new[i] | state[i - 1] |
(state[i-1] << 1 | 1) | (state[i-1] >> 1)
end

正規表現への対応

Bitapアルゴリズムは、ビット移動処理を追加することで正規表現に対応させることができます。具体的には、シフト動作と1のORの直後に以下の操作を行います。

取捨 ( `?` ): オプションの文字に対応
正閉包 ( `+` ): 1回以上の繰り返しに対応
閉包 ( `` ): 0回以上の繰り返しに対応
選言 ( `|` ): いずれかのパターンにマッチに対応

これらの処理は、NFAのε遷移に相当します。

例：取捨

文字列 "acaca" からパターン "acb?aca" を検索する例を考えます。

1. Rに対してシフトと1のORを行います。
2. 1の結果とXのビットマスクとのANDを取り、Sを計算します。
3. Sが1である位置に対応するRのビットを1にします。
4. X用のビットを0に戻します。
5. 元のアルゴリズム通り、マスク処理を行います。

これらの処理を繰り返すことで、正規表現に対応した検索が可能になります。

まとめ

Bitapアルゴリズムは、ビット演算の並列性を利用した強力な文字列探索アルゴリズムです。あいまい検索、正規表現への拡張が容易であり、多くの分野で活用されています。

参考文献

Dömölki, Bálint (1964). “An algorithm for syntactical analysis”. Computational Linguistics (Hungarian Academy of Science) 3: 29–46.
Shyamasundar, R. K. (1977). “Precedence parsing using Dömölki's algorithm”. International Journal of Computer Mathematics 6 (2): 105–114.
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。
Wu, Sun; Manber, Udi (October 1992). “Fast text search allowing errors”. Communications of the ACM 35 (10): 83–91.
Baeza-Yates, Ricardo A.; Gonnet, Gastón H. (October 1992). “A New Approach to Text Searching”. Communications of the ACM 35 (10): 74–82.
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.
* 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.

もう一度検索