スライド 1 - Imai Laboratory

輪講第３回
Chapter 3
Exact Matching: A Deeper Look at Classical Methods
山田崇
2002/10/25
Overview (1)
Apostolico-Giancarlo の方法 (1986)
比較の回数は高々 2m 回．
 BM 法の最悪の計算量に関するおはなし
Cole による証明 (1994)
• 比較の回数は高々 4m 回．
KMP 法の前処理
パターンが複数あるときのマッチング
Aho-Corasick の方法 (1975)
Overview (2)
マッチングの応用
DNA，たんぱく質のマッチング
ワイルドカードを含むマッチング
2 次元のマッチング
正規表現を用いたパターンマッチ
なぜ PowerPoint なのか?
論文構成法でプレゼンの講義がなくなった．
「時間の制約」(マクドナルド先生)
人前でプレゼンする機会の減少
観衆がいらっしゃる中でプレゼンの練習をしたい
研究室のノートPC，プロジェクタの使用方
法の習得
アニメーション
Apostolico-Giancarlo 法
AG 法概要
 T 上のどの文字も，P 上のどれかの文字といったん
マッチしたら，2 度比較されることはない
比較の回数は高々 2m
• すべての比較の結果は「マッチ」か「ミスマッチ」
• ミスマッチは高々 m 回しか発生しない
• マッチも高々 m 回しか発生しない．
全体の計算量も O(m)
 ここでは AG 法をさらに改善したものを紹介
シフトの方法は BM 法をシミュレート
BM 法がみつけるミスマッチはすべて発見
冗長なマッチを減らすことで比較回数を削減
Key Ideas
アルゴリズムを phase ごとに分割(1)
 アルゴリズムを分割
分割したものを compare/shift phase と呼ぶ．
各 compare/shift phase には順番に 1, 2, …, q
(≦ m) と番号をふる．
それぞれのフェーズでの仕事
1. P の右端が T のある文字のところにある
2. P と T を右から左に比較していく
3. 「すべての P がマッチする」か「ミスマッチが見つ
かる」状態まで 2. を繰り返す
4. P を BM 法のルールに従ってシフトし次 phase へ
Key Ideas
アルゴリズムを phase ごとに分割(2)
先週導入した図を今回も利用
T の position
×○○○
1
×○○○○
2
3
○：マッチ
×○○○
×：ミスマッチ
compare/shift
phase
[Nakayama, 2002]
Key Ideas
BM 法からの修正(1)
1. 長さ m の配列 M を用意する
M( j ): P の suffix が T の [ j －M( j )＋1.. j ]の範
囲に現れることを保証
各 phase ごとに M の要素は (少なくとも 1 つ)
書き換えられる


P の suffixj
T
× ○ ○ ○ ○
P
× ○ ○ ○ ○
M( j ) には k ≦ 4 を満たす k を代入
Key Ideas
BM 法からの修正(2)
2. N と M を利用してマッチ・ミスマッチを予
測する

例: M( h ) = α，Ni = β，α > β のとき (下図)
h
α
T
j
i
β
P
この範囲は○
ここで×
比較しなくても (過去の遺産から) 情報を得ることができる
Key Ideas
BM 法からの修正(3)
さらにわかること
Ni = i のとき
ここに P が出現
h
j
α
T
i
β
P
予測により○ 比較により○
ここで×
Ni > i のとき
h
α
T
j
i
P
β
予測により○ 比較により○
ここで×
ミスマッチを
予言できる
One phase in detail
詳細を述べるにあたっての準備
P の右端は T の j の位置にいるものとして，
phase は始まる
h=j
i=n
BM 法と同様に右から左に向かって順番に比
較する
ミスマッチが見つかったら BM 法と同様にシフト
P が T 中に見つかったら BM 法と同様にシフト
シフトしたらその phase は終了
One phase in detail
アルゴリズム(1)
1. M(h) がまだ定義されていない，もしくは
M(h) = Ni = 0 のとき

T(h) と P(i) を下記に従って比較
1. T(h) = P(i) かつ i = 1 のとき
 T [h..j] に P が存在している
 M(j) = n としてシフトし，phase を終了する
j
T
○
P ○
すでに○
One phase in detail
アルゴリズム(2)
1. M(h) がまだ定義されていない，もしくは
M(h) = Ni = 0 のとき

T(h) と P(i) を下記に従って比較
2. T(h)=P(i) かつ i > 1 のとき
 h := h－1，i := i － 1 として同じ phase を繰り返す
j
○
T
P
○
ここはまだわからない
すでに○
One phase in detail
アルゴリズム(3)
1. M(h) がまだ定義されていない，もしくは
M(h) = Ni = 0 のとき

T(h) と P(i) を下記に従って比較
3. T(h)≠P(i) のとき
 ミスマッチが発生していることに他ならない
 M(j) := j － h として BM 法と同様のシフトを行い phase 終
了
P の suffix
j
×
T
P
×
すでに○
One phase in detail
アルゴリズム(4)
2. M(h) < Ni のとき

P は T と [i － M(h) + 1.. n] の範囲でマッチして
いることが予測できる
 i := i － M(h)，h := h － M(h) として繰り返す
予測により○
h
j
M(h)
T
P
Ni
i
ここはまだわからない
すでに○
One phase in detail
アルゴリズム(5)
3. M(h) ≧ Ni かつ Ni = i > 0 のとき

予測によりP は T と [i － Ni + 1.. j] の範囲で
マッチしている(＝ T のその範囲で P が現れる)
ことがわかる
 M(j) := j － h としてシフト，phase 終了
予測により○
h
j
M(h)
T
P
Ni
i
すでに○
One phase in detail
アルゴリズム(6)
4. M(h) > Ni かつ Ni < i のとき

予測によりP は T と [i － Ni +1 .. n] の範囲で
マッチし， i － Ni でミスマッチすることがわか
る
 M(j) := j － h としてシフト，phase 終了
予測により○
h
j
M(h)
T
P
Ni
i
予測により×
すでに○
One phase in detail
アルゴリズム(7)
5. M(h) = Ni かつ 0 < Ni < i のとき

予測によりP は T と [i － Ni +1 .. n] の範囲で
マッチすることがわかる
 h := h － M(h), i := i － M(h) として同じ phase を繰り
返す
予測により○
h
j
M(h)
T
P
Ni
i
ここはまだわからない
すでに○
BM 法の計算量
Cole による解析
概要
BM 法の計算量が worst-case で O(m) となる
ことを示す
シフトは good suffix rule のみ使い，かつ P が T
に現れない場合に O(m) となることを示して
P が T に現れる場合にも O(m) となることを示し
そのあと bad character rule も使った場合にも
O(m) となることを示す
準備(1)
新しい変数の導入
AG 法のときと同様に BM 法を compare/shift
phase に分割
phase i で
si : phase の最後でシフトする量
ti : 比較してマッチした T の substring
gi : 以前のphaseで比較されたことのある文字の
数
g’i : phase i で初めて比較した文字の数
Σi(gi + g’i ) : 比較した延べ文字数→この値が O(m)
であることを示すことが goal
準備(2)
string に関する補題
βi:=βββ…βとおく(β: string)
i個
Lemma 1
γ，δを空ではない string とする．このとき，γδ＝δγが成り立つならば，ある
string ρとある整数 i， j が存在して，δ＝ρi，γ＝ρjとなる．
【証明】|δ|＋|γ| に関する帰納法により示す．
|δ|＋|γ|＝2 のとき: δ＝ρ，γ＝ρ，i ＝ j ＝1 のとき，またそのときのみγδ＝δγが成り立つ．
以下 |δ|＋|γ| > 2 のときについて考える．
|δ| < |γ| ならば γδ＝δγより，δはγの prefix となる．γ＝δδ’ とおけば，γδ＝δγよりδδ’δ＝
δδδ’．両辺左からδを取り除いても等号が成立．すなわちδ’δ＝δδ’．ここで，|δ’|＋|δ|＝|γ|
< |δ| +|γ| であるから，帰納法の仮定よりあるρ，i，j が存在してδ＝ρi，δ’＝ρj．このときγ
＝ρi + j．
|δ|＝|γ| ならばδ＝γ＝ρ，i ＝ j ＝ 1．|δ| > |γ| のときの証明は省略．□
準備(3)
semiperiodic とは
string α が period βについて semiperiodic で
あるとは…
αが string βの (空ではない) suffix (β全体でもOK)
を含み，その後ろに 1 個以上 β が続くこと
例アルファベット Σ ＝ {今，井，浩}
string α＝井浩今井浩今井浩は， period β＝今井
浩に対してsemiperiodic
α
井浩今井浩今井浩
βのsuffix
β
β
準備(4)
prefix semiperiodic とは
string αが period γ に関して prefix
semiperiodic であるとは…
αが 1 個以上の string γ のコピーを含み，その後
ろには (空ではない) γの prefix (全体でもOK) が 1
つ続くこと
例 string α＝今井浩今井浩今井は， period γ＝今
井浩に対して prefix semiperiodic
準備(5)
semiperiodic と prefix semiperiodic
Lemma
ある string α が period βに関して semiperiodic ならば，また，そのときに限っ
て，αはβと同じ長さを持つ period に関して prefix semiperiodic である．
例 string 今井今今井今今井今今井今今井は，priod 今今井に関して
semiperiodic であり，period 今井今に関して prefix semiperiodic である．
Lemma
text T において， pattern P が位置 p, p’(≧ p) の 2 箇所に出現するとき (ただし，
p’ － p ≦ floor (n / 2))，P は period p’－p に関して semiperiodic である．
Cole の証明 (1)
本題に戻る
Goal を再確認
Goal はΣi(gi + g’i ) が O(m) であることを示すこと
• Σi g’i ≦ m を示すのは簡単
– どの文字も最初に比較できるのは 1 回限り
• Σi si ≦ m も定義より自明
– シフト量の合計は高々m
• Σi gi ≦ 3m となることを今から示したい
– si ≧ gi /3 が各 phase i で成り立つことを示せばよい．
Cole の証明(2)
T に P が現れない場合
i 番目の compare/shift phase を考える
T の substring ti が P の suffix とマッチ
P を si だけ右にシフト
si ≧(| ti |＋1)/3のときは
• T のうち phase i で比較される文字すべてが過去に比
較されたことのあるものだったとしても si ≧ gi /3 が成
り立つ
よって， si < (| ti |＋1)/3 のとき，すなわち
| ti |＋1 > 3si のときのことについて以下で考える
Coleの証明(3)
いくつかの約束ごと
α: 長さsi の P の suffix
β: ある j が存在して，α＝βj を満たすような
最小の substring
α＝β，j ＝1，というのもOK
P:＝P[n－ |ti|＋1..n]
長さ|ti|＋1の P の suffix
P のうち，phase i で比較される部分 (結果は問わ
ない)
Coleの証明(4)
good suffix rule のみ＋PはTにない場合
Lemma 2
| ti |＋1 > 3si のとき，P，ti はともにαに関して semiperiodic である．
【証明】 P を右端から順番に |α|＝si 個ずつ左側にはみ出るまで分けていく．
|P|＝| ti |＋1 > 3si より，P にはすくなくとも 3 つの区切りができるはずである
(図)．phase i は si だけ P を右シフトすると終了する(次頁に続く)
P
α
P
区切り
区切り
区切り
Coleの証明(5)
good suffix rule のみ＋PはTにない場合
(前頁から続く) si だけ右シフトしたあとの状態を考えると(図)， si とαの定義から，
αは phase i の P から右シフトしたあとの(phase i + 1の) P の一部分となる．
good suffix rule の定義より，図で phase i + 1 の P のうち，ti の下にある部分は，
phase i において ti の下にある部分とマッチしなくてはならない．
以上の 2 つの事実から，si ごとに区切ったブロックは実は全部αであることがわか
る．
よって，P も ti もαに関して semiperiodic である．□
×
T
α
ti
α
P
α
α
α
α
P
α
P
P
α
Coleの証明(6)
先の補題から言えること
P と ti は αについて semiperiodic → βについ
ても semiperiodic である．
α＝βj より明らか
Coleの証明(7)
さらに補題
Lemma 3
| ti |＋1 > 3si のとき，各 phase h < i では，P の右端は ti 中のどのβの右端にも
そろえられることはない．
【証明】ti はβに関して semiperiodic であることはすでに示した(図)．また，
phase h ではP の右端が ti より右側に来ることはありえない．phase h で P の
右端が ti中のあるβの右端にそろえられていると仮定して矛盾を導く．
このとき，P の右側にあるβの数を q とおく．また，このとき，P は q|β|の位置
にあると呼ぶことにする. (次頁に続く)
ti
T
β
β
β
β
β
β
β
β
Coleの証明(8)
証明
(前頁から続く) phase h において，k’ を ti のジャスト左側の位置とし，その位置に
対応するPの位置を k とする．このとき，P と T の比較は，ti の左側までマッチ
し，T(k’)とP(k)を比較したときにミスマッチする．なぜならば
1. P と ti はβに関して semiperiodic である．
2. 仮定より，phase h において P の右端はβのどらかの右端と位置がそろえられて
いる．
からである．(さらに続く)
ti
β
T
β
β
β
k’
P
k
ここで×
P
ここまで○
β
β
β
β
Coleの証明(9)
さらに証明
(前頁から続く) もっと詳しく言うと，P はβに関して semiperiodic であること，P
の右端がちょうど q|β| にあることから，次の式が成り立つ．
P(k) ＝ P(1) ＝ P(1＋|β|) ＝ … ＝ P(1＋q|β|)
しかし P(k) ＝ P(1) と T(k’) を比較したときにミスマッチするので，
P(k) ＝ P(1) ≠ T(k’)
従って，T(k’) と P(k) を比較したときにミスマッチが発生し，このミスマッチを
もって phase h は終わるはずである．
以下の証明ではこの事実を利用する．(まだまだ続く)
Coleの証明(10)
まだまだ証明
phase h でシフトが終わったあと，P の右端がどこにあるか考えると，次の 2 通り
1. P の右端は q|β|より右側のどれかのβの右端にそろう
2. P の右端はどれかのβの右端ではないどれかの文字にそろう
前者に関しては，シフト後に T(k’) に対応する文字は，ある r を持ってきて P(k
r|β|) とかける．ところが，P はβに関して semiperiodic なので，P(k － r|β|)＝
P(k) が成り立つ．このことは good suffix rule に矛盾する．
後者の場合，下図のように β＝γδ とかける(もっと続く)
ti
β
T
β
β
β
β
β
γ δ
P
β
β
β
Coleの証明(11)
もっと証明
(前頁から続く) γはβの prefix，δはβの suffix であるから |γ|＋|δ|＝|β|．よって，γδ＝
δγが成立し，β＝ρj とかける．これはβの定義に矛盾．
いずれの場合にも矛盾が生じることから，このようは phase h は存在しないことが
示せた．□
Coleの証明(12)
補題はあと2つ
Lemma 4
| ti |＋1 > 3si のとき，各 phase h < i では，P は T 中の ti と高々 |β|－1 文字
マッチする．
【証明】|β| 文字以上マッチしたとすると，P の右端は先の補題によりどのβの右
端にもそろえられていないから，P の右側の |β| 文字はβの prefix γ のあとにβの
suffix δ が続く形となって，|γ|＋|δ|＝|β|となる．先ほどと同様，これはβの定義
に矛盾する．□
Coleの証明(13)
最後の補題
Lemma 5
| ti |＋1 > 3si のとき，各 phase h < i では，もし P の右端が ti に含まれる文字
とそろっていたとすると，P の右端は ti の左側の |β|－1 文字のうちのどれか
か，ti の右側 |β| 文字のどれかにそろえられる．
【証明】石関さんのレジュメを参照してください．
Coleの証明(14)
そしてこれが求めていた定理
Theorem
P が T に現れないと仮定するならば，任意の phase i において si ≧ gi /3
【証明】 | ti |＋1 > 3si のときのみ示せば十分．Lemma 5 より，phase h < i で
は，P の右端は ti の左 |β|－1 文字もしくは右|β|文字のどれかにそろえられる．
また，Lemma 4 より， phase h では高々|β| 回の比較しか行われない．
よって，phase i では以前の phase で比較された可能性のある ti 中の文字は，
左の |β|－1 文字か右の 2|β|文字である．すなわち gi ≦ 3|β| ＝ 3si．□
Coleの証明(15)
以上のことよりいえること
Theorem
P が T に現れないと仮定するならば，BM 法の比較回数は最悪でも高々4m．
【証明】
・Σi g’i ≦ m を示すのは簡単
どの文字も最初に比較できるのは 1 回限り
・Σi si ≦ m も定義より自明
シフト量の合計は高々m
・Σi gi ≦ 3m となることをさっき示した．
よって，全体の比較回数は，
Σi(gi + g’i ) ≦ 4m となる．□
Galilの方法(1)
PがTに現れるときは?
Pのn文字とTのm文字がすべて同じ文字であ
るとき，比較の回数はΘ(mn)
O(m) で抑えられる方法を Galil が考案
• phase i で P の右端が T の位置 k に対応する位置にあ
るとする．
• P と T を右から左に比較していって，比較が位置 s で
終わったとする (結果は不問)
• phase i のシフトで P の左端が s の右となるように
good suffix rule に従って，移動すると，phase i＋1 で
は P の prefix が T(k)までマッチする
– phase i＋１では T(k) まで比較すればよい．
Galilの方法(2)
BM法の計算量
Theorem
Galil の方法を使えば，BM 法の比較回数は P が T に現れるかどうかに関係な
く O(m) となる．
bad character rule を許す場合
計算量はO(m)
Theorem
good suffix rule，bad character rule の両方のシフトを用いたとしても，BM 法
の worst-case の計算量は O(m) となる．
KMP 法の前処理
オリジナル版
前回紹介された前処理
Z-based method
spi の値を Zi を用いて計算していた
Ziを用いる方法は
• 概念的にシンプル
• さまざまな手法の前処理に応用が効く
KMP 法の前処理
オリジナル版概要
sp1 ＝ 0
spi (i = 2,3,4,…n)を計算
spi (i ≦ k) が既知であるとして spk+1 の値を計算
• α: 長さ spk の P のprefix
– αは P [1..k] の suffix と等しい P の prefix のうち最長のもの
P
α’
α
spk
k
準備
βの導入
x ＝ P[k+1] とする
β＝βx とは
長さ spk+1 の P のprefix
• まさにこれから計算しようとしているもの
• βは P[1..k] の suffix とマッチし，その後ろにP(|β|＋1)
が続く最長の P の prefix
• spk+1 を見つけることは string β を見つけることにほか
ならない
P
β
x
β
x
k
The easy case
αの次が x である場合
P(spk+1) ＝ x (＝ P(k+1)) である場合
String αx は P の prefix であり，P[1..k+1] の
suffix でもある
• spk+1 ≧ |αx| ＝ spk+1 は明らか
• spk+1 ＝ spk+1 は成り立つのか？
P
α
x
spk
α’
x
k
The easy case
spk+1 ＝ spk+1
Lemma 6
任意の k について， spk+1 ≦ spk ＋1．さらにいうと，
spk+1 ＝ spk ＋1．iff. P(spk+1) ＝ P(k+1)
【証明】 spk+1 > spk ＋1 だったとすると，βはαよりも長くなる．ところが，定
義より βもP[1..k] の suffix であるから spk の定義に矛盾．よって， spk+1 ≦ spk
＋1．
以上より明らかにαの次の文字が x ならば spk+1 ＝ spk ＋1である．逆も成り立つ．
□
The general case
αの次が x ではない場合
P(spk+1) ≠ x (＝ P(k+1)) である場合
Lemma 6 より spk+1 < spk ＋1，すなわち spk+1 ≦
spk
• βはαの suffix (β＝αはOK)
• βはαの proper suffix (β＝αはNG)
βは位置 k+1 で終わって長さ高々spk のsubstring
• βはα’の suffix
• βはαの suffix でもある
P
α
β
y
spk
α’
β
x
k
The general case
βはαの prefix でもある
P(spk+1) ≠ P(k+1) のとき
βはαの suffix としても，P[|β|+1]＝x となるよう
なαの proper prefix のうち最長のものとしても現
れる
β
P
x
α
拡大
β
β
α’
y
k
spk
x
β
α
再帰的に spk+1 を計算できる
β
y
spk
spk+1 を求めるアルゴリズム
x = P(k+1);
v = spk;
while (P(v + 1) != x && v != 0) {
v := spv;
}
if (P(v + 1) == x)
spk+1 = v + 1;
else
spk+1 = 0;
例
アルファベット Σ＝ {い, ま, ひ, ろ, し}
α
α’
いまひいまろいまひいましいまひいまろいまひいまひ
spk+1
k k+1
spk
パターンが複数の場合
Aho-Corasick 法
概要
exact set maching problem
P がいくつかあるときに，それぞれが T に存在す
るかどうか調べる
• P の数 z
– それぞれの pattern に対してそれぞれ linear time にマッチン
グすると O(n + zm)
– Aho-Corasick 法を用いれば O(n + m + k)
» k: P が T に現れる回数
準備
P ＝ {P1, P2, … Pi}
パターンの集合
keyword tree
P のkeyword tree とは，次の条件を満たす
rooted directed tree K のこと
それぞれの edge はちょうど 1 文字のラベルがつ
けられている
同じ node から出る任意の 2 つの枝には違ったラ
ベルがついている
P 中のすべての pattern Pi は K のある node v に
map される
• K の root からの v への path を辿ることで，Pi をつづ
ることができ，
• K のすべての leaf は，P のある pattern に対応する
例
P ＝ {potato, poetry, pottery, science, school}
s
p
o
t
a
c
i
e
h
h
t
t
e
t
h
e
n
r
o
r
1
h
c
y
5
e
y
2
3
4
keyword tree の作り方
1. root だけの tree を用意する
2. 1. に root から長さ|P1|の path をのばす．これを
K1とする

path の最後には「1」と書く
Ki から Ki+1を作る
3.

Ki の root から始まる path で，Pi+1 の prefix にマッチ
するものを探す


Pi+1 と完全にマッチした path があれば，path の終点となった
node に「i+1」とかく
path がなければ，最後にマッチしたところから新たに枝を伸ば
して path をつくり，終点の node に「i+1」とかく
 木の構築にかかる時間はO(n)
Naïve use of keyword trees
for set matching
 Tにあわせて木を辿る
初期状態
• T の位置は最初の文字
• K の位置は root
T の prefix にマッチするだけ木を辿っていく
• 番号がついている node にたどり着いたら P 発見
• 行き場がなくなったら or T の最後まで行き着いたら発見できな
かったことを意味する
次の状態
• T の位置は 2 文字目
• K の位置は root
最後まで繰り返す
 O(mn) 時間で結果が出る
例
P ＝ {potato, poetry, pottery, science, school}
T＝potpotato
s
p
o
t
a
c
i
e
h
h
t
t
e
t
h
e
n
r
o
r
1
h
c
y
5
e
y
2
3
4
The speed-up:
generalizing KMP
Naïve method では T の初期位置 l を毎回 1
ずつ increment していくのみ
無駄な検索は省きたい
spi をpattern が増えても対応できるように一般化
Aho-Corasick 法
O(n + k + m)
P のどの pattern も P のほかの pattern の proper
substring を持たないという仮定のもとでの方法
仮定を取り除いても計算量が変わらないことを示
す
準備(1)
node にラベルをつける
K の各 node v にラベルをつける
K の root から node v に至る path についている
文字を順番につなげたもの
L(v): node v につけられたラベル
例
P ＝ {potato, poetry, pottery, science, school}
s
p
o
t
a
t
i
e
h
h
t
v
c
t
e
h
e
n
r
o
r
1
L(v) = pott
h
c
y
5
e
y
2
3
4
準備(2)
lp(v)
K 上の各 node v について，
lp(v): P に属する，ある pattern の prefix となって
いる L(v) の proper substring のうち，最長のも
のの長さ
例: 石関さんの資料の p.8
• P＝{potato, tattoo, theater, other}
準備(3)
failure link
K 上の各 node v について，
nv: 長さ lp(v) の L(v) の suffix でラベル付けされ
た K 上の node
directed edge v→nv を failure link と呼ぶ．
例: 石関さんの資料 p.8
The failure links
speed up the search
Tにおいて
j :これから pattern 探そうとしている文字列の最
初の位置
k: まさに今から調べようとしている文字の位置
アルゴリズム
AC 法
j:= 1; k:= 1; w := K の root
do {
while (there is an edge (w, w’) labeled char. T(c)) {
if (w’ is numbered by pattern i) {
report that Pi occurs in T starting at
position l;
}
w:= w’; c++;
}
w:= nw; l:= c – lp(w);
} while (c <= m);
アルゴリズム補足
root で mismatch したら
c を increment して root からやり直す
node v まで探索して行き場がなくなったら
string L(v) は nv の定義よりT[c－lp(v)..c－1]まで
マッチすることを保証
nvに飛んでnvから出る edge とT(c) を比較
例: 石関さんの資料 p.8
時間計算量
O(m) ← KMP 法のときと同様に示せる
Linear Preprocessing
for the failure function
K 上の各 node v について nv を見つける
v が root から 1 文字分しか離れていないとき
• nv ＝ root
ある k について，root から k 文字はなれた node
まですべての nv がすでに計算されているとする
• v’: v の親
• x: edge v’ → v についているラベル
– KMP 法の解析のときと同様に再帰的に調べる
O(n) 時間ですべての探索が終了
The full Aho-Corasick algorithm:
relaxing the substituting assumption
P のどの pattern も P のほかの pattern の
proper substring を持たないという仮定を取
り払う．
次の lemma が成立
Lemma 7
keyword tree K が node v から pattern i の番号がついた failure link を持ってい
るとき，AC 法で node v に到着したら，pattern Pi が T に存在し，その出現の
最後尾の位置は T[c] となる．
アルゴリズムを改良
j:= 1; k:= 1; w := K の root
do {
while (there is an edge (w, w’) labeled char.
if (w’ is numbered by pattern i
|| there is a directed path of falure
from w’ to a node numbered with i)
report that Pi occurs in T starting
position l;
}
w:= w’; c++;
}
w:= nw; l:= c – lp(w);
} while (c <= m);
T(c)) {
links
{
at
さらに改良
前処理に付け加え
ある node v について，
• v からいくつかの failure link を辿ると番号がついた
node に行き着くことがわかる場合には，v から直接リ
ンクをはる
• このリンクを output link と呼ぶ
Output link を付け加えた場合
全体で O(n + m + k) 時間
マッチングの応用
o Matching against a DNA or protein library of
known patterns
o Exact matching with wild cards
o Two-dimensional exact matching
Matching against a DNA or
protein
library of known patterns (1)
Sequence-tagged-site (STS)
Human Genome Project が開発
200 から 300 の長さをもった DNA の両端 (それ
ぞれ 20-30 の長さ) は，ゲノム全体で 1 度しか現
れない
STSs: STS の複数形
100,000 以上の長さを持つゲノムの任意の
substring をみたときに STSs の中の少なくとも
1 つを含んでいる，そういう STS の組を見つけ
たい
Matching against a DNA or
protein
library of known patterns(2)
expressed sequence tags (EST)
遺伝子から得られる STS
• ｍRNA，cDNA から得られる
• 遺伝子の sequence の一部分からコーディングされる
たんぱく質を見つけることができる．
EST や STS には keyword tree, AC 法が有効
• 速い (DNA の長さに比例)
• 実際にはエラーが存在するので考える必要あり
– 詳しいはなしは16 章で
Exact Matching with wild cards
φ: wild card
任意の 1 文字とマッチ
pattern に wild card が入っていても T 中に出現す
る pattern をすべて検索可能
例: abφφcφ は，テキスト xabvcbababcax に2 度
マッチする
DNA transcription factor
DNA の特定の場所に bind するたんぱく質を
transcription factor(転写因子)と呼ぶ
DNA を RNA に転写
• enhancing
• suppressing
Zinc Finger: transcription factor のひとつ
例: CYS**CYS*************HIS**HIS
• CYS: アミノ酸シスチン(1文字)
• HIS: アミノ酸ヒスチジン(1文字)
Leucine Finger: これも transcription factor
アルゴリズム
Exact Matching with wind cards
1. 長さ |T| の配列 C を用意し,0で初期化
2. wild card を含まない P の substring の集合P
＝{P1,P2,…Pk}，各 Pi の出現位置の左端を
li とおく．
3. AC 法を用いて, P の各Pi を探す

T に Pi が位置 j を開始位置として出現するとき
は，C(j－li＋1)++
4. C の中で値が k になっているものを探す

C(p) ＝k iff. P が T[p..] に出現している
Two-dimensional exact matching
 こんなときに使います
長方形の絵 T
T より小さな長方形の絵 P
• T, P ともにデジタル化されている
T 中の P の出現をすべて見つけたい
 準備
m: T の総ポイント数
• 例: 640*480＝307,200
n: P の点の数
n’: P の列の数
• それぞれの列は異なっていると仮定
– のちにこの仮定は取り払う
アルゴリズム(1)
2 つの phase に分ける
T の列(複数)の中のPの列(単数)の出現を探索
• 列ごとに終端記号をくっつけてTを1列にする．これを
T’ とする
• AC 法で P の各列がT’ に出現するか探索 O(m+n)時間
• P の i 列目がT’中から発見されたら
– 開始位置(p, q)
– T と同じ次元の配列 Mの位置(p, q)にi を書き込む
– 仮定より，M の各要素には高々1回しか値が書き込まれない
アルゴリズム(2)
M を行ごとに scan
• 値 1,2,…,n’ が順番に入っているセルの群を探す.
• linear exact matching algorithm を各行に対して適用
• O(n’+m)＝O(n+m)
仮定を取り払う
重複のある行は同じ行だとみなしてラベルをつけ
れば解決
正規表現のマッチング
Formal definitions
正規表現とは(アルファベット Σ)
Σに属する文字1文字は正規表現
εは正規表現
正規表現のあとに他の正規表現が続く表現は正規
表現
＋で正規表現をくっつけたものも正規表現
regexp*は正規表現
これ以外のものは正規表現ではない
*のことを Kleene closure と呼ぶ
正規表現のマッチング
正規表現 R にマッチするT中の部分文字列を
求めたい
有向グラフG(R)を作る
• 例土井さんの資料 p.3
• s が始点，終点は t
• R の文字数を n とすれば G(R) の枝数は高々 2n．
考え方
N(i): N(i－1)からラベルT(i)の枝1本と0回以上
のε遷移でいくことのできるnode の集合
N(0)
s
s からε遷移可能なノード
T のprefix T[1..i] が R とマッチ
iff. N(i) が Node t を含む
計算量(結果のみ)
 N(i) i=0..mを計算する
G(R) の枝数を e とすれば，O(me)時間
全体の計算量はO(mn)
後ろの部分も調べたい
R にマッチする T の non-prefix substring を
調べたい場合には，
Σ*R に対してマッチングを行う
おしまい

Download Report