情報生命科学特別講義

情報生命科学特別講義III
（１）文字列マッチング
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
講義予定















第１回: 文字列マッチング
第２回：文字列データ構造
第３回：たたみ込みとハッシュに基づくマッチング
第４回：近似文字列マッチング
第５回：配列アラインメント
第６回：配列解析
第７回：進化系統樹推定
第８回：木構造の比較：順序木
第９回：木構造の比較：無順序木
第１０回：文法圧縮
第１１回： RNA二次構造予測
第１２回：タンパク質立体構造の予測と比較
第１３回：固定パラメータアルゴリズムと部分k木
第１４回：グラフの比較と列挙
第１５回：まとめ
講義目的、成績、教科書





講義目的
 バイオインフォマティクスにおける主要な離散アルゴリズムについて理解
する
 乱拓アルゴリズム、近似アルゴリズム、固定パラメータアルゴリズムなど、
現代的なアルゴリズム設計技法について理解する
 計算時間および解の最適性もしくは近似精度に理論的保証のあるアルゴ
リズムを主対象とする
成績評価
 出席４割、レポート６割
 レポートは最終日の講義において出題
教科書（主に第5-8回、第11-12回）
 阿久津達也：バイオインフォマティクスの数理とアルゴリズム、共立出版、
2007
参考書
 第１，３回： Crochemore & Rytter: Jewels of Stringology, World Scientific, 2002
 第2回：岡野原大輔：高速文字列解析の世界、岩波書店、2012
その他は講義ノートにおいて該当トピックの最初に参考文献を記載
文字列マッチング問題
文字列マッチング問題（１）


入力
 パターン文字列： P  p1 p2  pm
 テキスト文字列： T  t t t
1 2
n
出力

p1 p2  pm  t j t j 1 t j m1 を満たす、すべての j
例
j=6
j=14
P  acgt T  actgcacgtctgtacgtcat
j=3
P  acac
m4
n  20
j=10 j=12
T  aaacacgctacacacgct
m4
n  18
文字列マッチング問題（２）
単純アルゴリズム
一文字ずつ、ずらしながらチェック
for j  1 to n-m 1 do
if p1 p2  pm  t j t j 1 t j  m1 the noutput j
例
全部で、4+1+1+2+4+1=13 回の比較
文字列マッチング問題（３）
命題：単純アルゴリズムの時間計算量は Θ(mn)
証明：時間計算量が O(mn) なのは明らか。
以下の例の場合、m(n-m+1) 回の比較が必要なの
で、Ω(mn) 時間。
m
n






P  aaaab, T  aaaaaab
for j  1 to n-m 1 do
if p1 p2  pm  t j t j 1 t j  m1 the noutput j
ただし、平均的にはO(m+n)時間で動作することが知られている。
Knuth-Morris-Prattアルゴリズム
KMPアルゴリズム：アイデア

アイデア：以前の結果を利用


j=2 ではグレーのところだけをチェックすれば良い
表 h[i]：次を満たす最大の k （無い時は h[i]=0）
p1  pk 1  pi k 1  pi 1 かつ pk  pi
KMPアルゴリズム：テキスト処理

表 h[i]：次を満たす最大の k （無い時は h[i]=0）
p1  pk 1  pi k 1  pi 1 かつ pk  pi
KMPアルゴリズム（テキスト処理）
i  1; j  1;
wh ile(i  m an d j  n) do
wh ile(i  0 an d pi  t j ) do i  h[i ]; (# )
i  i  1; j  j  1;
if (i  m) th e noutput `yes'e lseoutput `no'
上記はマッチの有無のみを判定。すべての j の出力は宿題
KMPアルゴリズム：実行例（１）

t
表 h[i]：次を満たす最大の k （無い時は h[i]=0）
p1  pk 1  pi k 1  pi 1 かつ pk  pi
i 1
2
3
4
p a
a
a
b
h[i] 0
0
0
3
a a a b
a a a c a a a b
a a a b
a a a c a a a b
a
h[4]=3
a
a
b
a
a
a
h[4]=3
b
a a a b
a a a c a a a b
h[3]=0
KMPアルゴリズム：
実行例（２）
h[5]=0
Match!
h[6]=2
h[2]=1
h[3]=0
KMPアルゴリズム：実行例（３）
h[12]=7
h[7]=4
h[4]=2
h[2]=1
h[1]=0
KMPアルゴリズム：解析
定理： KMPアルゴリズム（テキスト処理）の時間計
算量は O(n)
証明：
明らかに (#) にかかる時間が問題。その時間は
・ j が１増えた時のみ、i も１増える
・ i←h[i] を１回実行すると、i は少なくとも１減る
・ i は増えた回数以上に減ることはない
より、O(n)。よって、全体の計算量も O(n)
解析のアイデア：計算量のならし解析（amortized analysis）
ここでは「稼いだ分しか使えない」が基本的アイデア
KMPアルゴリズム：パターン処理
表 h[i] の作り方
テキスト処理と似た手続き
自分自身とのマッチをとりながら、h[i]
を作っていく
i  0; j  1; h[1]  0;
wh ile( j  m) do
wh ile(i  0 an d pi  p j ) do i  h[i ];
i  i  1; j  j  1;
if ( pi  p j ) th e nh[ j ]  h[i ] e lseh[ j ]  i
定理： KMPアルゴリズムは文字列マッチング
問題を O(m+n) 時間で解く
Boyer-Moore アルゴリズム
BMアルゴリズム：アイデア、例


KMPではテキスト中の文字を全て１回は調べている
BMでは、パターンを後から前に調べることでテキスト中の
一部の文字しか見ないようにする
例
まず、c と d を比較。d は P 中には現れないので、P が d と重なることはない。
よって、次のようにずらして、最後の文字を比較。
P 中の c の位置に T 中の a があるので、P 中の最後の a が重なるようにずらす
BMアルゴリズム：計算量



詳細を工夫することにより、最悪の場合を
O(m+n) とすることができる
平均的には KMP よりずっと速い
BM と似たアルゴリズムでは、平均的に
O((n/m) logkm) 時間を達成（ただし、k はアルフ
ァベットのサイズ（文字種の個数））
Aho-Corasick アルゴリズム
複数文字列マッチング問題


入力
 キーワード集合： W  {w1 , w2 ,, wk }
 テキスト文字列： T  t t t
1 2
n
出力
 (i)(w  t t
を満たす、すべての j
i
h h1 t j )
(m | w1 |  | w2 |  | wk | )


KMPやBMを k 回実行 ⇒ O(kn) 時間
Aho-Corasick アルゴリズムなら、O(m+n) 時間
これ以降の講義では、アルファベットΣ（文字種の集合）は固定と仮定
Aho-Corasick アルゴリズム
アイデア
キーワード集合からDFA（決定性有限オートマトン）を構成
例： W={ he, she, his, hers }
実線：前方遷移関数 f
点線：失敗関数 g
0 に戻る失敗関数
は省略
Aho-Corasick アルゴリズム：実行例
W={ he, she, his, hers }, T = ushers
u
0
s
0
h
3
e
4
r
5
2
s
8
9
0 に戻る失敗関数は省略
Aho-Corasickアルゴリズム：テキスト処理
for i  1 to n do
while( g ( s, ti )  fail) do s  f ( s);
s  g ( s, ti );
if ( s is a matchstate) the noutput i
W={ he, she, his, hers }
T = ushers
O(n)時間
Aho-Corasick アルゴリズム：例題
W={ he, she, his, hers }, T = rhishers
r
0
h
0
i
1
s
6
h
7
3
e
4
r
5
2
s
8
9
0 に戻る失敗関数は省略
Aho-Corasick アルゴリズム： DFAの構成(1)
1.
2.
3.
4.
パターン集合からトライを構成
前方遷移関数 g を作成
幅優先探索を用いて失敗関数 f を作成
最適化された失敗関数 h を作成（これは無くてもOK）
Aho-Corasick アルゴリズム： DFAの構成(2)
for all v (in BFS order) except the root or its children do
for all a such that g(v, a) = u do
s ¬ f (v);
while g(s, a) = fail do s ¬ f (s);
f (u) ¬ g(s, a)
O(m)時間
定理
Aho-Corasickアルゴリズムは
複数文字列マッチング問題を
O(m+n) 時間で解く
まとめ

文字列マッチング：線形時間で可能




KMPアルゴリズム：失敗関数の利用
Boyer-Mooreアルゴリズム：パターンの最後から検索
Aho-Corasickアルゴリズム：オートマトンを構成
補足



平均的には線形時間より高速に可能
近年では圧縮文字列の検索が盛んに研究
Aho-Corasick では O(log |Σ|)だけアルファベットサイズに
依存していたが、前処理（DFAの構成）に関しては依存し
ないアルゴリズムも存在 [Dori & Landau: Inf. Proc. Lett. 2006]

Download Report