<4D F736F F F696E74202D208FEE95F1926D8EAF836C F815B834E93C1985F817595B68E9A97F18FC68D B A E

Size: px

Start display at page:

Download "<4D F736F F F696E74202D208FEE95F1926D8EAF836C F815B834E93C1985F817595B68E9A97F18FC68D B A E"

あけなおいんそん
4 years ago
Views:

1 北海道大学 Hokkido Uiversity 1 情報知識ネットワーク特論情報検索とパターン照合情報科学研究科コンピュータサイエンス専攻情報知識ネットワーク研究室喜田拓也

2 第 3 回 Suffix 型アルゴリズム Boyer-Moore アルゴリズム Glil アルゴリズム Horspool アルゴリズム Sudy アルゴリズム

3 3 Nïve アルゴリズムテキスト T: bbbbbcbbbc パターン P: bbc パターン出現パターン出現!! t positio t positio 6 of T13 of T 一文字づつずらしてマッチングしていくもっと大雑把にいえば O(m) 時間 Nïve-Strig-Mtchig (T, P) テキスト上のポインタ 1 legth[t]. ( 比較する文字の現在 2 m legth[p]. 位置 ) が前後する! 3 for s 0 to m 4 do if P[1..m] = T[s+1 s+m] 5 the report occurrece t s. 最悪の場合 O((-m+1)m) 時間かかる演習 :T= 8, P= 4 b の場合を文字比較の回数は何回か? P=b の意味

4 4 Kuth-Morris-Prtt アルゴリズム D. E. Kuth, J. H. Morris, Jr, d V. R. Prtt. Fst ptter mtchig i strigs. SIAM Jourl o Computig, 6(1): , テキスト T: bbbbbcbbbc パターン P: ext[5] = 3 ext[3] = 0 bbc bbc bc bbc パターン出現! t positio 6 of T KMP-Strig-Mtchig (T, P) ext 関数によって次にPの何文字目とテキストを 1 legth[t]. 比較するかがわかる ( シフト量は q-ext[q]) 2 m legth[p]. 値が0のときはテキストの次の文字と比較する 3 q 1. テキストの各文字との比較はO(1) 回ずつである 4 ext ComputeNext(P). 5 for i 1 to do 6 while q>0 かつ P[q] T[i] do q ext[q]; 7 if q=m the report occurrece t i-m; 8 q q+1. 最悪の場合でも O(+m) 時間 (ext はあらかじめ配列として計算 )

5 5 効率的照合アルゴリズムの一般形 MtchigAlgorithm (P, T) 1 m legth[p]. 2 legth[t]. 3 i 1. 4 while i m +1 do 5 i が出現位置であるか否かを決定する ; 6 if i が出現位置 the report occurrece t i; 7 パタンを右へシフトする量 Δ を求める ; 8 i i + Δ. KMP 法 BM 法をはじめとする多くの効率的パタン照合アルゴリズムがこの枠組みに入る竹田正幸全文テキスト処理のための高速パターン照合アルゴリズム情報学シンポジウム 1991 年 1 月. アルゴリズムの高速化のために大事なこと : 5 行目をいかに最小の手間で決定できるか 7 行目においてシフト量をどれだけ大きくできるか

6 6 Boyer-Moore アルゴリズム R. S. Boyer d J. S. Moore. A fst strig serchig lgorithm. Commuictios of the ACM, 20(10): , 特徴 : パタンの右から左へ文字を比較していく二つの関数 (delt1 と delt2) の値を比較しより大きいほうを使ってパタンをシフトする最悪 O(m) 時間だが平均的には O(/m) 時間となる (sub lier!!) delt1(chr) := パタン内の chr の最右の出現位置に合わせるようにシフトした際のポインタ ( 文字比較位置 ) のとび幅 ( 出現しない場合はパタン長 ) delt1(c) = 5 (bd-chrcter heuristic) テキスト T: パタン P: b c d c b c b c c b c b b b b c b b b c の位置を合わせるようにシフトする Δ=delt1(chr) j + 1 = 5 0 = 5

7 7 delt2(j) delt2(j) := パタンPの長さ j-1 のsuffixのP 中の他の出現位置 ( あるいは最長一致する Prefix) に合わせた際のポインタのとび幅 ( 出現しない場合はパタン長 ) (good-suffix heuristic) delt2(3) = 8 テキスト T: b c d b b c b c c パタン P: b c b b b b c b b b b の位置を合わせるようにシフトする delt2(3) の候補としては 1 と 5 の二つあるしかし 5 の出現位置の左隣は b で既に一致しないことが分かっているのでこの場合は 1 となる Δ=delt2(3) = 8 2 = 6 delt2(5) = 10 テキスト T: パタン P: b c b b b c b c c b c b b b b c b b b b の位置を合わせるようにシフトする Δ=delt2(5) = 10 4 = 6

8 8 BM 法の問題点 delt 関数を計算するのが難しい単純なやり方だと O(m 2 ) 時間かかる O(m) 時間の手法はひと手間かかる KMPの裏返し delt1 と delt2 の値をいちいち比較するので手間がかかりすぎる delt1 だけを用いる方法が一般的 ( ただしそのままではパタンがうまくシフトできないことがあるので工夫が必要 ) 最悪の場合には O(m) 時間かかってしまう T =, P = b m の場合を考えよアルファベットのサイズが小さいときには効率が悪いテキストもパタンも ={0,1} の場合はほとんどシフトできない! つまりバイナリテキスト

9 9 Glil アルゴリズム Z. Glil. O improvig the worst cse ruig time of the Boyer-Moore strig serchig lgorithm. Commuictios of the ACM, 22(9): , 元の BM 法では一致した文字列の情報を忘れてしまうので O(m) 時間かかる Prefix が何文字一致しているかを記憶しておけばよい理論的にはテキスト走査を O() 時間で行える実際には処理が煩雑になり遅くなる delt2(5) = 10 テキスト T: パタン P: b c b b c b b b b c b b b b c b b b テキストの各文字はせいぜい 2 回しか比較されなくなる! これ以降はすでに比較ずみであることを記憶しておく比較する残りの部分はここだけ

10 10 Horspool アルゴリズム R. N. Horspool. Prcticl fst serchig i strigs. Softwre Prctice d Experiece, 10(6): , が十分に大きい場合は delt1 関数 (bd-chrcter heuristic) が大抵の場合一番よいシフト量を与える少しの変更を加えることでよりとび幅を増やすことができる! delt1(c) = 5 テキスト T: パタン P: b c d c d b c b c c b c b c b b d b c b b d delt1 (d) = 10 delt1 (b) = 3 テキスト T: b c d c d b c b c c b c パタン P: b c b b d b c b b d 常にパタンの最後の位置に対応するテキストの文字でとび幅を決定する

11 11 擬似コード Horspool (P, T) 1 m legth[p]. 2 legth[t]. 3 Preprocessig: 4 For ech c do delt1 [c] m. 5 For j 1 to m 1 do delt1 [ P[j] ] m j. 6 Serchig: 7 i 0. 8 while i m do 9 j m; 10 while j > 0 かつ T[i+j] = P[j] do j j 1; 11 if j = 0 the report occurrece t i+1; 12 i i + delt1 [ T[i+m] ].

12 12 Sudy アルゴリズム D. M. Sudy. A very fst substrig serch lgorithm. Commuictios of the ACM, 33(8): , 基本は BM 型アルゴリズムと同じ異なる点パタンが一致するか否かをパタン中の任意の文字順で比較する例えば統計的に出現頻度の低い文字から順次比較を行う delt1 を引く際パタンの最後の位置の右隣に対応するテキスト上の文字を使う (BM における delt2 も計算し長いほうを選択する ) Horspool よりもとび幅は長くなる傾向があるただしメモリ消費量は Horspool より大きいまたとび幅を計算する手間が Horspool よりかかる delt1 (d) = 9 delt1 (c) = 6 テキスト T: b c d c b d c b c c b c パタン P: b c b b b b c b b b 常にパタンの最後の位置の右隣に対応するテキストの文字で delt1 を計算する

13 Fctor 型アルゴリズム BDM アルゴリズム BOM アルゴリズム BNDM アルゴリズム

14 14 Bckwrd Dwg Mtchig (BDM) アルゴリズム M. Crochemore, A. Czumj, L. Gsieiec, S. Jromiek, T. Lecroq, W. Pldowski, d W. Rytter. Speedig up two strig mtchig lgorithms. Algorithmic, 12(4/5): , 基本は BM 型アルゴリズムと同じ異なる点パタンの Suffix と一致しているかではなく Fctor と一致しているかどうかでパタンの出現を判定する Fctor かどうかの判定は Suffix Automto を使う (suffix tree でも可 ) Suffix utomto (SA) の特徴文字列 u がパタン P の Fctor であるかどうかが O( u ) 時間で分かる文字列 u がパタン P の Suffix であるかどうかも判定できる P=p 0 p 2 p m に対して O(m) 時間のオンラインアルゴリズムがあるテキスト T: Fctor serch Prefixかどうかは SAの σ u 2 番目の特徴からわかる b c d c b d c b c c b c パタン P: b c b b b b c b b b cc は Fctor ではないしまた c は Prefix でもないので次の文字までパタンをずらせる b c b b b

15 15 Suffix Automto A. Blumer, J. Blumer, D. Hussler, A. Ehrefeucht, M. T. Che d J. Seifers. The smllest utomtio recogizig the subwords of text. Theoreticl Computer Sciece (40):31-55, e c u o c u o u o u o o e c u o c u o u o u o o Suffix tree Suffix trie Suffix utomto パタン P = ouce の反転 P R の fctor を受理する決定性オートマトン u o e c 9 u o c u

16 16 O-lie 構築アルゴリズム SuffixAutomto(P=p 1 p 2 p m ) 1 Crete the oe-ode grph G=DAWG(e). 2 root sik the ode of G. suf[root] θ. 3 for i 1 to m do 4 crete ew ode ewsik; 5 mke solid edge (sik, ewsik) lbeled by ; 6 w suf[sik]; 7 while w θ かつ so(w,)=θ do 8 mke o-solid -edge (w, ewsik); 9 w suf[w]; 10 v so(w,); 11 If w=θthe suf[ewsik] root 12 else if (w,v) is solid edge the suf[ewsik] v 13 else 14 crete ode ewode; とっても複雑なので構築するのは結構たいへん! 15 ewode hs the sme outgoig edges s v except tht they re ll o-solid; 16 chge (w,v) ito solid edge (w, ewode); 17 suf[ewsik] ewode; 18 suf[ewode] suf[v]; suf[v] ewode; 19 w suf[w]; 20 while w θかつ (w,v) is o-solid -edge do 21 redirect this edge to ewode; w suf[w]. 22 sik ewsik.

17 17 BNDM アルゴリズム G. Nvrro d M. Rffiot. Fst d flexible strig mtchig by combiig bit-prllelism d suffix utomt. ACM Jourl of Experimetl Algorithmics (JEA), 5(4), 基本は BDM と同じ異なる点パタンの fctor かどうかを調べるため非決定性 (odetermiistic) の Suffix utomt を用いるその NFA の状態遷移を Bit-prllel 手法でシミュレートするパタン P = ouce の反転 P R の suffix を受理する非決定性オートマトン I ε ε ε ε ε ε ε ε ε e c u o 初期状態 :R 0 = 1 m 状態遷移 :R = (R << 1) & M[ T[i] ] Shift-Adと同じ Msk tble この NFA をシミュレートする

18 18 擬似コード BNDM (P, T) 1 m legth[p]. 2 legth[t]. 3 Preprocessig: 4 for c do M[c] 0 m. 5 for j 1 to m do M[ P[j] ] M[ P[j] ] 0 m j 10 j 1. 6 Serchig: 7 s 0. 8 while s m do 9 j m, lst m, R 1 m ; 10 while R 0 m do 11 R (R << 1) & M[ T[s+j] ]; 12 j j 1; 13 If R & 10 m-1 0 m the 14 If j > 0 the lst j; 15 else report occurrece t s+1; 16 R R << 1; 17 s s + lst.

19 19 Bckwrd Orcle Mtchig (BOM) アルゴリズム C. Alluze, M. Crochemore, d M. Rffiot. Efficiet experimetl strig mtchig by wek fctor recogitio. I Proceedigs of the 12 th Aul Symposium o Combitoril Ptter Mtchig, LNCS2089:51-72, BDM とアイデアは同じ異なる点複雑な Suffix utomto ではなく Fctor orcle を使う BDM において必要なことは文字列 u が Fctor であることではなく σu が Fctor ではないこと Fctor orcle の性質パタン P の Fctor 以外の文字列も受理してしまう可能性がある例 : 下の図で c は P R の Fctor ではない O(m) 時間で構築できるうえに実装が容易で少メモリ状態数 m+1 個遷移関数の実現サイズ 2m-1 P=ouceの場合の P R に対するFctor orcle c e c u o u o

20 20 Fctor orcle の構築アルゴリズム Orcle-o-lie (P=p 1 p 2 p m ) 1 Crete Orcle(ε) with 2 Oe sigle iitil stte 0, S(0) θ. 3 for i 1 m do 4 Orcle(P=p 1 p 2 p j ) 5 Orcle_dd_letter (Orcle(P=p 1 p 2 p j-1 ), p j ). Orcle_dd_letter (Orcle(P=p 1 p 2 p m ),σ) 1 Crete ew stte m+1. 2 δ(m,σ) m+1. 3 k S(m) 4 while k θ かつ δ(k,σ)=θ do 5 δ(k,σ) m+1; 6 k S(k). 7 If k =θthe s 0; 8 else s δ(k,σ). 9 S(m+1) s. 10 retur Orcle(P=p 1 p 2 p m σ).

21 21 ちょっとひといきここまでのまとめ Suffix 型アルゴリズムパターンを右から左へ照合する! テキストの文字を飛び飛びで照合できる! Fctor 型アルゴリズムパターンのすべての Fctor と比較しつつテキストの文字を飛び飛びで照合できる! ~ トリビア ~ 二つの整数 x と y の内容を余計な変数を用いずに交換できるか? (x,y) = (y,x) Perlだとリストを使える! いわとびペンギン ( 旭山動物園にて )

22 Suffix Fctor 型の複数パターンへの拡張 Set Horspool アルゴリズム Wu-Mber アルゴリズム

23 23 Suffix Fctor 型複数パターン照合 Commetz-Wlter アルゴリズム B. Commetz-Wlter. A strig mtchig lgorithm fst o the verge. I Proceedigs of the 6th Itertiol Colloquium o Automt, Lguges d Progrmmig, LNCS71: , BM アルゴリズムの直接的な拡張 Set Horspool アルゴリズム Commetz-Wlter のアルゴリズムを Horspool のアイデアに基づいて簡略化したもの Urti-Tked アルゴリズム AC アルゴリズムのアイデアを BM 型に転用したもの CW より高速 Set Bckwrd Orcle Mtchig (SBOM) アルゴリズム C. Alluze d M. Rffiot. Fctor orcle of set of words. Techiicl report 99-11, Istitut Gsprd-Moge, Uiversite de Mre-l-Vllee, Fctor orcle を複数文字列に拡張したものを利用 Wu-Mber アルゴリズム S. Wu d U. Mber. A fst lgorithm for multi-ptter serchig. Report TR-94-17, Deprtmet of Computer Sciece, Uiversity of Arizo, Tucso, AZ, 実用的に高速なアルゴリズム Agrep にも用いられている

24 24 Set Horspool アルゴリズムパタン集合の各要素を反転 (reverse) した文字列の trie を作るあとは Horspool と同じ Suffix serch をしながら trie をたぐるどのパタンの Suffix でもないことが判ったら delt1 でパタンをシフトする α パタンのリバース trie Cf. Urti-Tked アルゴリズムでは trie のかわりに AC マシンを使い filure 関数によってとび幅を決定するテキスト T: σ suffix serch テキスト T: β どのパタンの中にも β が出現しない部分 delt1

25 25 パフォーマンスが悪くなる理由 delt ( lmi) テキスト T: パタン P: 可能なとび幅の最大値は lmi に制限される lmx lmi パターンの個数が多くなると各文字の出現頻度が高くなり bd-chrcter heuristic がうまく働かない!

26 26 Wu-Mber アルゴリズム S. Wu d U. Mber. A fst lgorithm for multi-ptter serchig. Report TR-94-17, Deprtmet of Computer Sciece, Uiversity of Arizo, Tucso, AZ, テキストの照合位置から B 文字分 (T[i-B+1 i]) を用いてパタンが出現する可能性を調べる SHIFT[ T[i-B+1 i] ] : T[i-B+1 i] があるパタンの接尾辞であるとき 0 そうでなければ可能な最大シフト長を返す HASH[ T[i-B+1 i] ] : SHIFT が 0 ( すなわち T[i-B+1 i] があるパタンの接尾辞 ) だった場合出現の可能性があるパタンのリストを返すパタン P: o u c e u l u l l y パタン出現の可能性あり! SFHIT[l]=0 HASH[l]=2, シフト1 テキストT: C P M u l c o f e r e c e o u c e SFHIT[]=4 SFHIT[l ]=5 SHIFT[Bl] = 文字列シフト量 ll 1 o ou 3 4 u c 1 u l 0 ly 0 u 2 ce 0 * 5 HASH[Bl] = 文字列パタン番号 ce ly 3, 1 u l 2 * φ

27 27 擬似コード Costruct_SHIFT (P={p 1,p 2,,p r }) 1 iitilize SHIFT tble by lmi B+1. 2 For ech Bl=p i [j B+1 j] do 3 If SHIFT[h1(Bl)] > m i j do SHIFT[h1(Bl)] = m i j. grep ver4.02 の実装 (mgrep.c) では SFHIT HASH B はそれぞれとなっている ( ようだ ) Wu-Mber (P={p 1,p 2,,p r }, T=T[1 ]) 1 Preprocessig: 2 Computtio of B. 3 Costructio of the hsh tbles SHIFT d HASH. 4 Serchig: 5 pos lmi. 6 while pos do 7 i h1( T[pos B+1 pos] ); 8 If SHIFT[i] = 0 the 9 list HASH[ h2( T[pos B+1 pos] ) ]; 10 Verify ll the ptters i list oe by oe gist the text; 11 pos pos + 1; 12 else pos pos + SHIFT[i].

28 28 第 3 回まとめ Suffix 型アルゴリズムパターンを右から左へ照合する最悪 O(m) 時間だが平均的には O(/m) 時間 Boyer-Moore Glil Horspool Sudy らのアルゴリズム Fctor 型アルゴリズムパターンの Fctor かどうかを判定してテキストを飛び飛びに照合する BDM BNDM BOM アルゴリズム Suffix 型 Fctor 型アルゴリズムの複数パターンへの拡張パターンの個数が多くなると各文字の出現頻度が高くなり bd-chrcter heuristic がうまく働かない Set Horspool Wu-Mber アルゴリズム次回のテーマ近似文字列照合アルゴリズム : 誤りを許したパターン照合

文字列照合アルゴリズム

文字列照合アルゴリズム講義情報知識ネットワーク特論 ~ 情報検索とパターン照合第 3 回 Suffix Fctr 型アルゴリズム情報理工学専攻情報知識ネットワーク研究室喜田拓也講義資料 2018/11/22 今日の内容 Byer-Mre アルゴリズム Glil アルゴリズム Hrspl アルゴリズム Sudy アルゴリズム BDM アルゴリズム BOM アルゴリズム BNDM アルゴリズム 2 効率的照合アルゴリズムの一般形