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のアルゴリズムとし、それ以外の名前はそれ以外のアルゴリズムも含む総称とすべきかもしれないが、通常特に区別されていない。

アルゴリズム[編集]

このアルゴリズムはマッチさせるパターンの状態遷移を表す非決定性有限オートマトンをエミュレートする。1つのビットが1つの状態に対応しており、これを対応する状態に対して同時に遷移させることで一度に比較を行える。対象の文字列幅がパターンの幅より小さい場合に高速に動作する。

例として対象の文字列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のどちらかにマッチしている状態はこれらの状態を示すビットマスクのORを取った[ac]=110111に対して演算を行えばよいだけであるため、容易にあいまい検索へ流用できる。文字の長さが違う場合はレーベンシュタイン距離の概念を適用すればよい。

脚注[編集]

  1. ^ 例えばP=acbacaなら初期状態はstate=111111
  2. ^ ~はビット単位のNOT

参考文献[編集]

  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.

関連項目[編集]