Bitapアルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

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.」と書かれている。よって厳密には、あいまい検索に拡張したアルゴリズムに限定してbitapあるいはWuとManberのアルゴリズムとし、それ以外の名前はそれ以外のアルゴリズムも含む総称とすべきかもしれないが、通常特に区別されていない。

アルゴリズム[編集]

このアルゴリズムはマッチさせるパターンの状態遷移を表す決定性有限オートマトン(DFA)をエミュレートする。1つの立っている(shift-orなら降りている)ビットが1つの非決定性有限オートマトン(NFA)に対応し、またその立っている位置が該NFAの状態を示している。これ等複数のNFAの状態を同時管理した一つの整数がDFAの状態となっている。そしてこれ等各々のNFAの状態遷移を連接のみに限ることにより一回のシフト動作で全てのNFAの状態遷移を同時に行なえ、また同様にアトムを文字クラスのみに限ることにより一回のマスク動作で必要な全てのNFAの拒否(reject)を行なえるアルゴリズムとなっている。

(→#正規表現との関係

例として対象の文字列T=acbacbaca,パターン文字列P=acbacaを考える。以下に示す表は横軸にT、縦軸にPを配置し、どのように遷移するかを示すものである。初期状態でRはすべて0で初期化される。

状態遷移 0 ビットマスク
P 初期状態 a c b a c b a c a
a 0 1 0 0 1 0 0 1 0 1
c 0 0 1 0 0 1 0 0 1 0
b 0 0 0 1 0 0 1 0 0 0
a 0 0 0 0 1 0 0 1 0 0
c 0 0 0 0 0 1 0 0 1 0
a 0 0 0 0 0 0 0 0 0 1
R0 R1 R2 R3 R4 R5 R6 R7 R8 R9
0
a b c
1 0 0
0 0 1
0 1 0
1 0 0
0 0 1
1 0 0
0 0

この表で例えばR6=001000からR7=100100への遷移はR6を1ビット右にシフトしたもの(000100)とcに当たるビットマスク(100100)とのビット単位でのANDを取った値に等しい。 こうして最上位ビットに1がたったとき、それまでの経路がマッチした文字列だと言える。バックトラックが不要なため、パターンに似た配列が含まれるときに高速に動作できる。

実装例[編集]

このアルゴリズムを実装しているプログラムとしては、agrepというユーティリティがある。

Rubyで実装した例と実行結果を以下に示す。

#すべてのマッチした位置の末尾が配列として戻る
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 #最上位ビットが1である
      ret.push(i)
    end
  end

  return ret
end

shift_and("acbacbaca","acbaca") # => [8]
shift_and("ababaa", "aba") # => [2, 4]

Shift-orアルゴリズム[編集]

以上の説明はShift-and型のバリエーションを前提としている。ブール代数の双対性により、このアルゴリズムにはShift-or型のバリエーションがある。Shift-orアルゴリズムでは、Shift-andアルゴリズムにおけるビットを反転させた上でビットごとのORで探索を行う。すなわち、初期状態はパターン文字列Pの長さと同じだけの1が立っているビット列であり[注 1]、先ほどの実装例で文字列比較をしていた部分であるstate=(state << 1|1) & mask[tc]state=state | ~mask[tc][注 2]とする。最上位ビットが0になったときに入力Tは受理される。C言語レベルで見ると1をORする操作が必要無くなるが、機械語コードでどの程度性能に影響するかは微妙だろう。実装例などはShift-andとほとんど変わらないのでここでは割愛する。

あいまい検索への適用[編集]

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

本来の状態を管理するビット列(#実装例に於けるstate)を距離ゼロ用とし、他に距離1用、距離2用など任意の検出したい最大の距離までのビット列を用意する。以降、係かる距離 i 用のビット列をstate[i]と表現する。

  1. 全てのstate[i]に対して初期化を行なう。(state[i] = ( 1 << i ) - 1)
  2. 全てのstate[i]に対して、アルゴリズム通りにshift動作を行なう。
  3. 全てのstate[i]に対して、それとそれを左右にぞれぞれ1ビットシフトした値をorで合成した値を退避しておく。(saved_state[i] = state[i] | state[i] << 1 | state[i] >> 1)
  4. 全てのstate[i]に対して、アルゴリズム通りに取得した文字に基づいてand動作を行なう。
  5. i≠0である全てのstate[i]に対して、3.で退避した一つ前の値を合成する。(state[i] |= saved_state[i-1])
  6. 全てのstate[i]に対して、アルゴリズム通りにstate[i]の最上位ビットに1が立っているか調べて、立っていればその距離i(かそれより近い距離)の文字列が見付かったことになる。
  7. 2.から6.を対象の文字列が尽きるまで繰り返す。

これにより、本来なら4.で消される(=rejectされる)はずだったビットが5.により距離+1で(その位置(置換)と直前(挿入)と直後(除去)として)復活することとなり、そのまま生き残り続けるかさらに距離+1に移動されるかして、距離が遠くなり過ぎる(=最大の距離でも生き残れなくなる)まで生き残り続ける。

注意点としては、より長い一致が存在するにも関わらずパターン文字列の末尾が失われた(=距離が遠い)一致として発見されるので、検出位置[注 4]が重要な場合はそれへの対策が必要になる。また開始位置はわからないので検出位置からパターン文字列の長さ+発見された距離数分戻った位置からやり直して確定することになるが、この場合にも慎重に組まないと直観とは異なる位置が開始位置として算出されることがある。

正規表現との関係[編集]

このアルゴリズムは決定性有限オートマトン(DFA)で実装された正規表現のサブセットであり、このDFAは遷移先が複数ある状態遷移を持たないという特徴を持っている。より具体的には、連接及び文字クラス[注 5]という(rejectする以外は)単一の遷移先しかない状態遷移のみを持つ[注 6]

このことより、単に複数の遷移先を持った状態遷移を管理する機能を具備させるだけで容易にフルセットのDFA正規表現へと変更することが出来る。特に複数の遷移先を持つノードでの遷移をεによる状態遷移のみに限るように構成すれば、シフト動作の後、rejectのマスク動作の前にεによる状態遷移を行なうフェーズを挿入するだけで済むので全体的な構成への影響が少なくて済む。しかしながらこれは「一回のシフト動作と二回のマスク動作だけで同時に全てのNFAの状態遷移とreject、acceptが行なえる」という高速性の由来となる特徴を失った、何等の特徴を持たない教科書的なDFA正規表現の実装の一つに過ぎない。

具体的にはシフト動作の後に

取捨
acb?aca であれば acXbaca とし、Xのビットが立っていたらそのビットを消して acXbaca の二箇所のビットを立てる。
正閉包
acb+aca であれば acbXaca とし、Xのビットが立っていたらそのビットを消して acbXaca の二箇所のビットを立てる。
閉包
acb*aca は ac(b+)?aca と等価であるので割愛。
選言
ac(ba|ab)ca であれば acXbaYabca とし、Xのビットが立っていたらそのビットを消して acXbaYabca の二箇所のビットを立てる。またYのビットが立っていたらそのビットを消して acXbaYabca のビットを立てる。

をそれぞれ必要な回数だけ行なうことになる。

これ等は全て、特定のビットのみを立てた整数とANDした結果がゼロでなければそれ[注 7]をビット反転した整数とANDし、対応する整数とORする(shift-andの場合)という処理に統一される。なのでεによる状態遷移を行なうフェーズでは、これ等正規表現の演算子によって追加される二整数(判定用にANDする整数とそれに対応してORする整数)の組の全てを順次処理するだけであり、この組は正閉包/取捨であれば一つ、選言であれば二つが追加される。この追加された二整数の組は、適切に正規化されていれば順不同で一通りを処理するだけで済むが、正規化されていない場合は順序が重要になる[注 8]。この正規化や順序に関しては、一般的なDFAやNFAの実装に於ける「遷移先がεによる状態遷移を持っていた場合の効率的な実装」に関わる問題でありBitapアルゴリズムの問題ではない[注 9]

脚注[編集]

  1. ^ 例えばP=acbacaなら初期状態はstate=111111
  2. ^ ~はビット単位のNOT
  3. ^ この場合のレーベンシュタイン距離は、挿入、除去、置換の全てを距離1として計測したものとなる。記載のアルゴリズムに幾許かの変更を施すことで、置換の距離を2にすることもできる。
  4. ^ DFAはその性質上検出した開始位置の記録能力を持たないが、この場合はさらに終了位置も不明瞭になる
  5. ^ #あいまい検索への適用にある通り、同じ位置のビットを複数の文字に対して持たせることで文字クラスを実現出来る
  6. ^ 実際にはグループ化もそれ自身は複数の遷移先を持たないが、これは選言や閉包等の複数の遷移先を持つ状態遷移表現と組み合わせない場合には存在しないのと等価なので事実上持っていない。また唯一のεによる状態遷移のみを持つ状態遷移も考えられるが、これは存在しないのと等価なのでやはり持っていない。
  7. ^ ANDする前の整数でもANDした結果の整数でもどちらでもよい
  8. ^ 全通りを変化しなくなるまで繰り返すならば正規化されていなくても順序は問題にならない
  9. ^ BitapアルゴリズムのDFAは複数の遷移先を持たないDFAであるので、有意なεによる状態遷移が存在し得ないのでそもそもこの問題は存在しない。

参考文献[編集]

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

関連項目[編集]