情報生命科学特別講義

情報生命科学特別講義III
（３）たたみ込みとハッシュに
基づくマッチング
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
講義予定















第１回: 文字列マッチング
第２回：文字列データ構造
第３回：たたみ込みとハッシュに基づくマッチング
第４回：近似文字列マッチング
第５回：配列アラインメント
第６回：配列解析
第７回：進化系統樹推定
第８回：木構造の比較：順序木
第９回：木構造の比較：無順序木
第１０回：文法圧縮
第１１回： RNA二次構造予測
第１２回：タンパク質立体構造の予測と比較
第１３回：固定パラメータアルゴリズムと部分k木
第１４回：グラフの比較と列挙
第１５回：まとめ
たたみ込みによる
文字列マッチング
たたみ込みとFFT
ベクトル a=(a0,…,am-1) と b=(b0,…,bn-1) のたたみ込み a*b は
ck 
aib j を要素とするベクトル c=(c0,…,cn+m-1)

i  j k
（ただし、cn+m-1=0と定義）
２つの多項式
p( x)  a0  a1 x  a2 x 2    am1 x m1
q( x)  b0  b1 x  b2 x 2    bn 1 x n 1
p( x)q( x)  c0  c1x  c2 x2   cnm2 xnm2
の積
の各係数は、たたみ込みベクトルの各成分に等しい
(a0,…,am-1) と (b0,…,bn-1) のたたみ込みはFFTを用いて
(Real-RAM上で） O(n log n) 時間で計算可能（ただし、m≦n）
たたみ込みによる文字列マッチング：アイデア
(a0, a1,a2) と (b0,…,bn-1) のたたみ込みを考える
ここで、 a0, a1,a2 を逆順にすれば、以下のようになる
⇒ パターンを逆順にして、たたみ込みを行えば、
文字列マッチングに使えそう
（Fisher-Patersonアルゴリズム）
たたみ込みによる文字列マッチング
Σ={a,b}, T = abbabbab, P=abb, P-1=bba として、 χa(T)などを次
のように定義
 (T )  10010010,  (T )  01101101
,
a
 a ( P 1 )  001,
すると
b
 b ( P 1 )  110
 a (T )   a ( P 1 )  0010010010
 b (T )   b ( P 1 )  0121121110
この2個のベクトルの和は 0131131120 となり、
値が 3 となる桁がマッチしている場所に対応
定理：文字列マッチングは FFT により O(n log m) 時間で実行可能
（ただし、|Σ|は定数）
Don’t Care記号つき文字列マッチング
Don’t Care記号：任意の１文字とマッチする記号（`*’ で表す）
KMP, BM, ACアルゴリズムを Don’t Care記号つきに拡張するの
は困難。でも、たたみ込み法なら、以下の例のように簡単
T  ab * a * ba , P  a * ba
 a* (T )  1011101,  a ( P 1 )  1001
 b* (T )  0110110,  b ( P 1 )  0100
χa*(...) は、対象の文字が
a か * なら、1 に対応させる
定理：Don’t Care記号つき文字列マッチングは FFT により
O(n log m) 時間で実行可能
（ただし、|Σ|は定数）
Karp-Rabinアルゴリズム
ランダマイズド・アルゴリズム（乱拓アルゴリズム）
同じ入力を与えても、アルゴリズムの動作が内
部で用いた乱数の値により異なるアルゴリズム
 ラスベガス・アルゴリズム


常に正しい解を出力（ただし、計算時間は乱数に
より異なることがある）
モンテカルロ・アルゴリズム

誤った解を出力する可能性がある
Karp-Rabinアルゴリズム：アイデア
ハッシュ関数の利用
長さ m の各部分文字列に対し、以下の性質を満たす
整数値（ハッシュ値） h(ti ti m1 )
を計算
(i)
p1  pm  ti ti  m 1 ならば、
常に
h( p1  pm )  h(ti ti  m 1 )
(ii) p1  pm  ti ti  m 1 ならば、
高確率で h( p1  pm )  h(ti ti  m 1 )
Karp-Rabinアルゴリズム：ハッシュ関数
q を適当に大きな素数とし、b を適当な基数（例： b=2）とすると
h(ti tim1 )  (tibm1  ti 1bm2   ti m1 ) mod q
なお、h()は、毎回計算しなおさなくても、
h(ti 1 ti m )  ((h(ti ti m1 )  tibm1 )b  ti m ) mod q
により、1回あたり O(1) 時間で計算可能
定理： q を適当な範囲内でランダムに選ぶことにより、どのような
入力 P, T に対しても、高い確率で以下が成立
p1  pm  ti ti m1 ならば、 h( p1  pm )  h(ti ti m1 )
Karp-Rabinアルゴリズム
ハッシュ関数を計算し、一致している場所を出力
⇒ 線形時間モンテカルロ・アルゴリズム
Karp-Rabinアルゴリズム：確率の解析
補題: 任意の N について、（異なる）素因数の個数は O(log N)
（証明）素数は2以上なので、t 個の素因数を持てば N≧2t
補題： x,y (x≠y) をそれぞれ m ビットの数とする。τ 以下の素数 p

をランダムに選んだ時、(x = y) mod p となる確率はO( m log
 )
（証明） (x = y) mod p となるのは |x-y| が p の倍数の時のみ。
一方、|x-y| の素因数の個数は上記補題より O(m) 個。
τ 以下の素数の個数は素数定理より≈ τ/ln τ なので、
m log
(x = y) mod p となる確率は O(  ) 。
（Karp-Rabinの定理の証明）
τ = n2m log n2m とすれば、 p1  pm  ti ti m1 なのに、ハッシュ

1
値が一致してしまう i の存在確率は O(n  mlog
)

O
(

n)
ラスベガス・アルゴリズム化
方法１
 マッチが見つかったら O(m) 時間かけてチェック
 誤りであれば、単純なO(mn)時間アルゴリズムを
最初から実行
計算時間の期待値は O((m+n)+(1/n)(mn))=O(m+n)
方法２
 マッチが見つかったら O(m) 時間かけてチェック
 誤りであれば、異なる素数 p を用いて再実行
計算時間の期待値は O(m+n)
( O((m  n)((1  1n )  2  1n  (1  1n )  3  ( 1n )2  (1  1n )  )  O(m  n) )
注意：素数生成のための時間は考慮していないが、考慮しても定理や解析は成立
まとめ

たたみ込みによる文字列マッチング


O(n log m) 時間
Karp-Rabinアルゴリズム


Don’t care 文字が扱える。
ハッシュ関数を用いたランダマイズド・アルゴリズム
補足



たたみ込みマッチングは、文字のミスマッチにも対応可
たたみ込みを用いずに don’t care つき文字列マッチングを効率的に
扱うのは（たぶん）研究課題
Karp-Rabinアルゴリズムは広くは利用されていないが、文字列などの
データをハッシュするという考え方は、第４回に説明する Locality
Sensitive Hashingや埋め込み（Embedding）などの名で盛んに研究・
応用されている
本講義で研究課題としたものはすべて「たぶん」です

Download Report