文字列照合アルゴリズム 情報知識ネットワーク特論 喜田拓也 参考文献： Flexible pattern matching in strings: Practical on-line search algorithm for texts and biological sequences, Gonzalo Navarro and Mathieu Raffinot, Cambridge University Press, 2002, ISBN 0-521-81307-7. 2018/11/7 情報知識ネットワーク特論 授業資料

Prefix, Factor, Suffix 有限オートマトン 文字列照合問題とは 準備 Prefix, Factor, Suffix 有限オートマトン 文字列照合問題とは 2018/11/7 情報知識ネットワーク特論 授業資料

Prefix, Factor (Substring), Suffix － 接頭辞、部分文字列、接尾辞 ∑：有限なアルファベット ある文字列 w∈∑* に対して、 w = xyz suffix Prefix 接尾辞 接頭辞 factor (substring) 部分文字列

Prefix, Factor, Suffix の例 w = cocoa factor c co coc coco cocoa a oa coa ocoa o oc oco prefix suffix 演習：w=cacao のprefix, factor, suffix を列挙せよ。

文字列照合問題 （Pattern Matching Problem）とは？ テキストT中に含まれるパタンPの出現を求める問題 有名なアルゴリズム： KMP法 (Knuth&Morris&Pratt[1974]) BM法 (Boyer&Moore[1977])とその変種 Karp-Rabin法 (Karp&Rabin[1987]) compress パタン P We introduce a general framework which is suitable to capture an essence of compressed pattern matching according to various dictionary based compressions. The goal is to find all occurrences of a pattern in a text without decompression, which is one of the most active topics in string matching. Our framework includes such compression methods as Lempel-Ziv family, (LZ77, LZSS, LZ78, LZW), byte-pair encoding, and the static dictionary based method. Technically, our pattern matching algorithm extremely extends that for LZW compressed text presented by Amir, Benson and Farach [Amir94].　 テキスト T

Existence problem と All-occurrences problem Yes! All-occurrences problem テキスト T: テクマクマヤコンテクマクマヤコン パタン P: クマクマ 2 10 全文検索で文書を単位として検索する場合は、Existence problemで充分 しかし、一般的にはAll-Occurrences problemを指すことが多い

索引データ構造を用いた検索との違い 文字列照合による検索 索引データ構造を用いた検索 O(mlog n) O(n) 長所 余計なデータ構造が不要 DBの更新に対して柔軟 短所 検索がおそい スケーラビリティが低い 索引データ構造を用いた検索 長所 検索がはやい スケーラビリティが高い 短所 索引構造を構築する手間がかかる DBの更新に対して柔軟性に欠ける 索引構造のためのスペースが必要 O(mlog n) O(n) 小規模文書群に対する検索向き (例：UNIX の grep) 中・大規模DBに対する検索向き (例：mg, namazu, Google) ※ 文字列照合ベースの大規模全文検索システムもある！ （富士通の瞬索システム）

Naïve アルゴリズム KMP アルゴリズム Aho-Corasick アルゴリズム Prefix型アルゴリズム Naïve アルゴリズム KMP アルゴリズム Aho-Corasick アルゴリズム 2018/11/7 情報知識ネットワーク特論 授業資料

テキスト上のポインタをバックする必要がある！ Naïve アルゴリズム Naïve-String-Matching (T, P) n ← length[T]. m ← length[P]. for s ← 0 to n – m do if P[1..m] = T[s+1…s+m] then report an occurrence at s. テキストT: ababbabcabbaa… パタンP: ababc 一文字づつずらして マッチングしていく ababc ababc テキスト上のポインタをバックする必要がある！ ababc 最悪の場合 O((n-m+1)m) 時間かかる。（T=an, P=am の場合を考えよ）

Knuth-Morris-Pratt アルゴリズム D. E. Knuth, J. H. Morris, Jr, and V. R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(1):323-350, 1977. KMP-String-Matching (T, P) n ← length[T]. m ← length[P]. q ← 1. next ← ComputeNext(P). for i ← 1 to n do while q>0 かつ P[q]≠T[i] do q ← next[q]; if q=m then report an occurrence at i-m; q ← q+1. テキストT: ababbabcabbaa… パタンP: next関数によって次にPの何文字目とテキストを 比較するかがわかる。（シフト量は q-next[q]） 値が0のときは、テキストの次の文字と比較する。 テキストの各文字との比較はO(1)回ずつである。 ababc ababc next[5] = 3 ababc next[3] = 0 最悪の場合でも O(n+m) 時間 （nextはあらかじめ配列として計算）

next関数の計算 ComputeNext (P) m ← length[P]. next[1] ← 0. k ← 0. for q ← 1 to m do while k>0 かつ P[q]≠P[k] do k ← next[k]; k ← k+1; if P[q+1]=P[k] then next[q+1] ← next[k] else next[q+1] ← k; パタンのどこまで一致していたかを記録している q+1 パタンをずらしながら比較し、 next[q]を計算 パタンP: ababc ababc q 1 2 3 4 5 6 P[q] a b c next(q) ababc k ababc ababc

決定性オートマトンによる照合 a b a b b abababba 1 2 3 4 3 4 5 1 2 7 : goto関数 パタン P = ababb を受理する決定性有限オートマトン （KMPオートマトン） a b a b b 1 2 3 4 5 任意の 文字 -1 7 : goto関数 : failure関数 Next関数に対応 abababba テキスト： 状態： 1 2 3 4 3 4 5 1 2 前処理は O(m|∑|) 時間かかる。走査時間はKMPと同じ O(n)

Aho-Corasick(AC) アルゴリズム A. V. Aho and M. J. Corasick. Efficient string matching: an aid to bibliographic search. Communications of the ACM, 18(6):333-340, 1975. パタン集合 ={AC,BA,BB,BAA,BACD} を受理する（ε遷移付き）順序機械 （AC照合機械） 1 2 4 3 5 6 7 8 9 AC BA BAA BACD BB A C B D ￢{A,B} 7 : goto関数 : failure関数 ※状態1へのfailureは省略 KMPオートマトンは、パタンが一つの場合のAC照合機械に等しい ※ 初期状態のとりかたが違うように見えるが、原理的には同じように構成できる

構成アルゴリズム 7 : goto関数 : failure関数 パタン集合 ={AC,BA,BB,BAA,BACD} を受理するAC照合機械 （ε遷移付きの）順序機械 2 3 AC A C 7 : goto関数 : failure関数 4 5 BA B A 7 BAA A 1 ￢{A,B} 6 BB B 8 9 BACD C D AC 1. パタンを処理しながらtrie(gotoグラフ)を作る 2. 幅優先探索しfailure関数を求めつつ、出力関数を補完する 3. 最適化する ※ 詳細は配布資料を参照

擬似コード MatchingAlgorithm (P, T) m ← length[P]. n ← length[T]. i ← 1. while i ≦ n – m +1 do i が出現位置であるか否かを決定する; if i が出現位置 then report an occurrence at i; パタンを右へシフトする量Δを求める; i ← i + Δ.

クエリをまとめて 一つのAC照合機械を構築 瞬索システム（富士通） http://software.fujitsu.com/jp/shunsaku/ AC照合機械をフルに活用 分散処理・フォールトトレラント機構 複数のクエリをまとめて処理することで 高速なレスポンスを確保（山手線方式） クエリ テキストDBを一括走査 クエリをまとめて 一つのAC照合機械を構築 クエリ

Boyer-Moore アルゴリズム Galil アルゴリズム Horspool アルゴリズム Sunday アルゴリズム Suffix型アルゴリズム Boyer-Moore アルゴリズム Galil アルゴリズム Horspool アルゴリズム Sunday アルゴリズム 2018/11/7 情報知識ネットワーク特論 授業資料

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

(bad-character heuristic) Boyer-Moore アルゴリズム R. S. Boyer and J. S. Moore. A fast string searching algorithm. Communications of the ACM, 20(10):762-772, 1977. 特徴： パタンの右から左へ文字を比較していく 二つの関数（delta1とdelta2）の値を比較し、より大きいほうを使ってパタンをシフトする 最悪 O(mn) 時間だが、平均的には O(n/m) 時間となる （sub linear!!） delta1(char) := パタン内のcharの最右の出現位置に合わせるようにシフトした際の ポインタ（文字比較位置）のとび幅 （出現しない場合はパタン長） (bad-character heuristic) delta1(c) = 5 テキストT: a a b c d a a c b c a b c c a ・・・ パタンP: a b c b a b a b a b c b a b a b ‘c’の位置を合わせるようにシフトする Δ=delta1(char) – j + 1 = 5 – 0 = 5

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

BM法の問題点 delta関数を計算するのが難しい delta1 と delta2 の値をいちいち比較するので、手間がかかりすぎる 単純なやり方だと O(m2) 時間かかる O(m) 時間の手法は結構複雑 　→ 実はKMP（の裏返し）に対応している delta1 と delta2 の値をいちいち比較するので、手間がかかりすぎる delta1 だけを用いる方法が一般的 （ただしそのままでは、パタンがうまくシフトできないことがあるので、工夫が必要） 最悪の場合には、O(mn) 時間かかってしまう T = an, P = am の場合を考えよ アルファベット∑のサイズが小さいときには効率が悪くなる テキストもパタンも0,1の列の場合は、ほとんどシフトできない！

この部分は「すでに比較ずみ」 であることを記憶しておく Galil アルゴリズム Z. Galil. On improving the worst case running time of the Boyer-Moore string searching algorithm. Communications of the ACM, 22(9):505-508, 1979. 元のBM法では、一致した文字列の情報を「忘れてしまう」ので、O(mn)時間かかる Prefixが何文字一致しているかを記憶しておけばよい 理論的には、テキスト走査をO(n)時間で行える 実際には処理が煩雑になり、遅くなる delta2(5) = 10 テキストT: a a b c a b a b c b a b a b a ・・・ パタンP: a b c b a b a b テキストの各文字はせいぜい 2回しか比較されなくなる！ a b c b a b a b 比較する残りの部分はここだけ この部分は「すでに比較ずみ」 であることを記憶しておく

Horspool アルゴリズム R. N. Horspool. Practical fast searching in strings. Software Practice and Experience, 10(6):501-506, 1980. ∑が十分に大きい場合は、delta1（bad-character heuristic）が大抵の場合一番よいシフト量を与える → 少しの変更を加えることで、よりとび幅を増やすことができる！ delta1(c) = 5 テキストT: a a b c d c a d b c a b c c a b a c a・・・ パタンP: a b c b a b a d a b c b a b a d delta1’(d) = 10 delta1’(b) = 3 テキストT: a a b c d c a d b c a b c c a b a c a・・・ パタンP: a b c b a b a d 常にパタンの最後の位置に 対応するテキストの文字で とび幅を決定する a b c b a b a d

擬似コード Horspool (P, T) m ← length[P]. n ← length[T]. Preprocessing: For each c∈∑ do delta1’[c] ← m. For j←1 to m – 1 do delta1’[ P[j] ] ← m – j . Searching: i ← 0. while i ≦ n – m do j ← m; while j > 0 かつ T[i+j] = P[j] do j ← j – 1; if j = 0 then report an occurrence at i+1; i ← i + delta1’[ T[i+m] ].

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

Factor型アルゴリズム BDM アルゴリズム BOM アルゴリズム 2018/11/7 情報知識ネットワーク特論 授業資料

Backward Dawg Matching (BDM)アルゴリズム M. Crochemore, A. Czumanj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski, and W. Rytter. Speeding up two string matching algorithms. Algorithmica, 12(4/5):247-267, 1994. 基本はBM型アルゴリズムと同じ 異なる点 パタンのSuffixと一致しているかではなく、 Factorと一致しているかどうかでパタンの出現を判定する Factorかどうかの判定はSuffix Automatonを使う(suffix treeでも可) Suffix automatonの特徴 文字列uがパタンPのFactorであるかどうかがO(|u|)時間で分かる 文字列uがパタンPのSuffixであるかどうかも判定できる P=p0p2…pm に対して、O(m)時間のオンラインアルゴリズムがある Prefixかどうかは、SAの2番目の特徴からわかる Factor search σ u テキストT: a a b c d c a b d c a b c c a b a c a・・・ パタンP: a b c b a b a b cc はFactorではないし、 また、cはPrefixでもないので 次の文字までパタンをずらせる a b c b a b a b a b c b a b a b

Suffix Automaton u o n e c a Suffix trei Suffix tree 3 4 5 7 8 6 1 2 9 A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen and J. Seiferas. The smallest automation recognizing the subwords of a text. Theoretical Computer Science (40):31-55, 1985. u o n e 3 4 5 7 8 6 1 2 c a 9 e c n u o a e c n u o a Suffix trei Suffix tree

とっても複雑なので、構築するのは 結構たいへん！ On-line 構築アルゴリズム とっても複雑なので、構築するのは 結構たいへん！ SuffixAutomaton(P=p1p2…pm) Create the one-node graph G=DAWG(e). root ← sink ← the node of G. suf[root] ←θ. for i ← 1 to m do create a new node newsink; make a solid edge (sink, newsink) labeled by a; w ← suf[sink]; while w≠θ かつ son(w,a)=θ do make a non-solid a-edge (w, newsink); w ← suf[w]; v ← son(w,a); If w=θthen suf[newsink] ← root else if (w,v) is a solid edge then suf[newsink] ← v else create a node newnode; newnode has the same outgoing edges as v except that they are all non-solid; change (w,v) into a solid edge (w, newnode); suf[newsink] ← newnode; suf[newnode] ← suf[v]; suf[v] ← newnode; while w≠θかつ (w,v) is a non-solid a-edge do redirect this edge to newnode; w ← suf[w]. sink ← newsink.

Backward Oracle Matching (BOM)アルゴリズム C. Allauzen, M. Crochemore, and M. Raffinot. Efficient experimental string matching by weak factor recognition. In Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, LNCS2089:51-72, 2001. BDMとアイデアは同じ 異なる点 複雑なSuffix automatonではなく、Factor oracleを使う BDMにおいて必要なことは、文字列uがFactorであることではなく、 σuがFactorではないこと。 Factor oracleの性質 パタンPのFactor以外の文字列も受理してしまう可能性がある 例：下の図で、cnnはPrvのFactorではない O(m)時間で構築できるうえに、実装が容易で少メモリ 状態数m+1個、遷移関数の実現サイズ2m-1 u o n e 3 4 5 7 8 6 1 2 c a P=announceの場合の、PRvに対するFactor oracle

Factor oracleの構築アルゴリズム Oracle-on-line (P=p1p2…pm) Create Oracle(ε) with One single initial state 0, S(0) ←θ. for i∈1…m do Oracle(P=p1p2…pj) ← Oracle_add_letter (Oracle(P=p1p2…pj-1), pj). Oracle_add_letter (Oracle(P=p1p2…pm),σ) Create a new state m+1. δ(m,σ) ← m+1. k ← S(m) while k≠θかつδ(k,σ)=θ do δ(k,σ) ← m+1; k ← S(k). If k =θthen s ← 0; else s ← δ(k,σ). S(m+1) ← s. return Oracle(P=p1p2…pmσ).

Suffix・Factor型アルゴリズムの 複数パタン照合への拡張 Commentz-Walterアルゴリズム B. Commentz-Walter. A string matching algorithm fast on the average. In Proceedings of the 6th International Colloquium on Automata, Languages and Programming, LNCS71:118-132, 1979. BMアルゴリズムの直接的な拡張 Set Horspoolアルゴリズム Commentz-WalterのアルゴリズムをHorspoolのアイデアに基づいて簡略化したもの Uratani-Takedaアルゴリズム ACアルゴリズムのアイデアをBM型に転用したもの。CWより高速 Set Backward Oracle Matching (SBOM)アルゴリズム C. Allauzen and M. Raffinot. Factor oracle of a set of words. Techinical report 99-11, Institut Gaspard-Monge, Universite de Marne-la-Vallee, 1999. Factor oracleを複数文字列に拡張したものを利用。 Wu-Manberアルゴリズム S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ, 1994. 実用的に高速なアルゴリズム。Agrepにも用いられている

BM型複数パタン照合アルゴリズムの パフォーマンスが悪い理由 delta (≦ ℓmin) テキストT: 可能なとび幅の最大値は ℓmin に制限される パタンP: ℓmin ℓmax パタンの個数が多くなると、 各文字の出現頻度が高くなり bad-character heuristicが うまく働かない！

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

Wu-Manberアルゴリズム テキストの照合位置からB文字分（T[i-B+1…i]）を用いて、 パタンが出現する可能性を調べる S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ, 1994. テキストの照合位置から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]があるパタンの接尾辞）だった場合、出現の可能性があるパタンのリストを返す。 パタン出現の 可能性あり！ a n o u c e パタンP: a n u l SFHIT[al]=0 a n u l y HASH[al]=2, → シフト1 テキストT: C P M a n n u a l c o n f e r e n c e a n n o u n c e SFHIT[an]=4 SFHIT[l ]=5 文字列 ll no ou an un nc ua al ly nn nu ce ＊ シフト量 1 3 4 2 5 SHIFT[Bl] = 文字列 ce ly ua al ＊ パタン番号 3, 1 2 φ HASH[Bl] =

擬似コード Construct_SHIFT (P={p1,p2,…,pr}) ※agrep ver4.02 の実装(mgrep.c)では、SFHIT・HASH・Bはそれぞれ、4096、8192、3となっている（ようだ） Construct_SHIFT (P={p1,p2,…,pr}) initialize SHIFT table by ℓmin–B+1. For each Bl=pi[j–B+1…j] do If SHIFT[h1(Bl)] > mi – j do SHIFT[h1(Bl)] = mi – j. Wu-Manber (P={p1,p2,…,pr}, T=T[1…n]) Preprocessing: Computation of B. Construction of the hash tables SHIFT and HASH. Searching: pos ← ℓmin. while pos≦n do i ← h1( T[pos–B+1…pos] ); If SHIFT[i] = 0 then list ← HASH[ h2( T[pos–B+1…pos] ) ]; Verify all the patterns in list one by one against the text; pos ← pos + 1; else pos ← pos + SHIFT[i].

その他の手法 Karp-Rabin アルゴリズム 2018/11/7 情報知識ネットワーク特論 授業資料

Karp-Rabinアルゴリズム Hashingを使ったRandomizedアルゴリズム O(mn)時間でテキストを走査する KARP R.M., RABIN M.O., Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2):249-260, 1987. Hashingを使ったRandomizedアルゴリズム 文字列を一個の整数とみなして照合する！ O(mn)時間でテキストを走査する 平均時間計算量はO(n+m) Extra spaceがO(1)！ パタン： 3 1 4 1 5 7 mod 13 ∑ = { 0,1,2,…,9 } テキスト： 2 3 5 9 2 3 1 4 1 5 2 6 7 3 9 9 2 1 ・・・ ・・・ ・・・ mod 13 8 9 3 11 1 7 8 4 5 10 11 7 9 11 正しい！ 間違い！ 3 1 4 1 5 2 14152 ≡ (31415 – 3×10000)×10 + 2 (mod 13) ≡ (7 – 3×3)×10 + 2 (mod13) ≡ 8 (mod 13) 以前の高位の 数字（文字） 新たな低位の 数字（文字） 7 8

擬似コード Karp-Rabin (P, T, d, q) m ← length[P]. n ← length[T]. h ← dm–1 mod q. p ← 0. t0 ← 0. for i ← 1 to m do p ← (d・p + P[i]) mod q; t0 ← (d・t0 + T[i]) mod q. for s ← 0 to n – m do if p = ts then if P[1…m] = T[s+1…s+m] then report an occurrence at s; else if s < n – m then ts+1 ← (d・(ts – T[s+1]・h)+T[s+m+1]) mod q. 正しい出現かどうかを確認

参考： FFTを利用した確率的近似文字列照合 K. Baba, A. Shinohara, M. Takeda, S. Inenaga, and S. Arikawa. A Note on Randomized Algorithm for String Matching with Mismatches. Nordic Journal of Computing, 10(1):2-12, 2003. Fast Fourier Transform (FFT)は ハードウェア上で高速に計算可能 文字列を数値に置き換え、スコアベクトルの列をFFTにより高速に計算することで、（近似）文字列照合を行う 馬場（九州大） i 1 2 3 4 5 6 7 8 9 10 T a c b a b b a c c b P a b b a c a b b a c ci 3 1 1 5 2 0 スコアベクトル

Shift-And アルゴリズム Shift-Or アルゴリズム BNDM アルゴリズム Bit-parallel手法 Shift-And アルゴリズム Shift-Or アルゴリズム BNDM アルゴリズム 2018/11/7 情報知識ネットワーク特論 授業資料

Shift-And アルゴリズム a b a b a b b レジスタ長のビット演算が並列に計算されることを利用 R. A. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Proceedings of the 12th International Conference on Research and Development in Information Retrieval, 168-175. ACM Press, 1989. S. Wu and U. Manber. Fast text searching allowing errors. Communications of the ACM, 35(10):83-91, 1992. レジスタ長のビット演算が並列に計算されることを利用 パタン長mがワード長wよりも短い場合には、 O(n)時間で非常に高速に動作する 一般には O(n・m/w)時間、前処理はO(m+|∑|) パタン P = ababb を受理する決定性有限オートマトン a 1 2 4 5 b 3 任意の 文字 -1 このNFAを シミュレートする パタン P = ababb を受理する非決定性有限オートマトン a b a b b 1 2 3 4 5 任意の 文字

NFAの動き（状態遷移の様子） a b a b b abababba 1 2 3 4 5 1 1 1 1 1 1 1 1 1 パタン P = ababb を受理する非決定性有限オートマトン a b a b b 1 2 3 4 5 任意の 文字 テキストT= abababba 状態番号 1 2 3 4 5 1 1 1 1 1 1 1 1 1 1: アクティブ 0: 非アクティブ

Ri = (Ri-1<<1 | 1) & M(T[i]) Bit-parallel手法のアイデア Mask table M ab 1 a b パタン P: ababb テキスト T: abababba 1 2 3 4 5 1 & Ri = (Ri-1<<1 | 1) & M(T[i]) O(1)時間で 計算可能 ※つまり、マスクビット列Mと「＆」をとることで、 正しい遷移だけを残している！

擬似コード Shift-And (P, T) m ← length[P]. n ← length[T]. Preprocessing: for c ∈ ∑ do M[c] ← 0m . for j ← 1 to m do M[ P[j] ] ← M[ P[j] ] | 0m–j10j–1. Searching: R ← 0m. for s ← 1 to n do R ← ((R << 1) | 0m-11) & M[ T[s] ]; If R & 10m-1 ≠ 0m then report an occurrence at s.

Ri = (Ri-1<<1) | M(T[i]) Shift-Or アルゴリズム Shift-Andにおけるビット列を反転させたもの 利点： Shift-Andよりも演算が少なくなる パタン P: ababb Mask table M ab 1 a b テキスト T: abababba 1 2 3 4 5 Ri = (Ri-1<<1) | M(T[i])

Bit-parallel手法の文字クラスへの拡張 ab[ab]bb Mask table M ab 1 a b [ab] パタン P: テキスト T: ababbbba 1 2 3 4 5 これだけ！ 1 & ここは同じ Ri = (Ri-1<<1 | 1) & M(T[i])

Shift-Andと同じMask table BNDM アルゴリズム G. Navarro and M. Raffinot. Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithmics (JEA), 5(4), 2000. 基本はBDMと同じ 異なる点 パタンのfactorかどうかを調べるため、 非決定性（nondeterministic）のSuffix automataを用いる そのNFAの状態遷移をBit-parallel手法でシミュレートする パタンP = announce の反転Prvのsuffixを受理する非決定性オートマトン e 1 2 4 c u n o 3 7 8 a 6 5 I ε このNFAを シミュレートする 初期状態：R0 = 1m 状態遷移：R = (R << 1) & M[ T[i] ] Shift-Andと同じMask table

擬似コード BNDM (P, T) m ← length[P]. n ← length[T]. Preprocessing: for c ∈ ∑ do M[c] ← 0m. for j ← 1 to m do M[ P[j] ] ← M[ P[j] ] | 0m–j10j–1. Searching: s ← 0. while s ≦ n – m do j ← m, last ← m, R ← 1m; while R ≠ 0m do R ← (R << 1) & M[ T[s+j] ]; j ← j – 1; If R & 10m-1 ≠ 0m then If j > 0 then last ← j; else report an occurrence at s+1; R ← R << 1; s ← s + last.

正規表現について 照合処理のながれ 構文木（parse tree）の構築 Thompson’s NFA Glushkov’s NFA 正規表現の照合 正規表現について 照合処理のながれ 構文木（parse tree）の構築 Thompson’s NFA Glushkov’s NFA 2018/11/7 情報知識ネットワーク特論 授業資料

正規表現とは？ ファイル名の正規表現 検索ツールGrepの正規表現 プログラミング言語Perlの正規表現 > rm ＊.txt > cp Important[0-9].doc 検索ツールGrepの正規表現 > grep –E “for.+(256|CHAR_SIZE)” ＊.c プログラミング言語Perlの正規表現 $line = m|^http://.+\.jp/.+$|

簡略のために、（α・β）を単にαβと記述する 正規表現の定義 アルファベットΣ上の正規表現とは、 A={ε,|,・,*,（,）} を用いて次のように定義される。 (1) εとΣの要素は正規表現である (2) αとβが正規表現ならば (α・β)も正規表現である (3) αとβが正規表現ならば (α|β)も正規表現である (4) αが正規表現ならば α* も正規表現である (5) 上から導かれるものだけが正規表現である 例： (a・(a|b)*) “+”は、αを正規表現とすると、α+ =α・α*の意味で使用されることがある。 簡略のために、（α・β）を単にαβと記述する

正規表現の意味づけ 正規表現をΣ*の部分集合（言語L）に写像する 例： a b a,b (i) ||ε|| ={ε} (ii) a∈Σに対して || a || = {a} (iii) 正規表現α,βに対して ||(α・β)|| = ||α||・||β|| (iv) 正規表現α,βに対して ||(α|β)|| = ||α||∪||β|| (v) 正規表現αに対して ||α*|| = ||α||* 例： ||(a・(a|b)*)|| = {ax | x∈{a,b}*} a q1 q0 q2 b a,b

正規表現と有限オートマトンの関係 正規表現の照合問題とは、 正規表現に対応する有限オートマトンを作成し、 その動きをシミュレートすればよい。 正規表現αで定義される言語L(α)＝||α||の任意の要素を 探し出す問題 正規表現で表現できる言語は有限オートマトンでも表現できる。 またその逆も真。 正規表現と有限オートマトンは言語を定義する能力が等しい！ 正規表現に対応する有限オートマトンを作成し、 その動きをシミュレートすればよい。 初期状態は常にアクティブ テキストを読んでいく過程で、オートマトンが受理状態に 到達したらパタン出現

照合処理のながれ NFAはO(mn)時間で模倣できる 一般的な方法 テキスト走査 正規表現 構文木 NFA 出現位置の報告 決定性化 Thompson法によるNFA構築 構文解析 (Parsing) テキスト走査 正規表現 構文木 NFA 出現位置の報告 決定性化 テキスト走査 Glushkov法によるNFA構築 DFA DFAはO(2m)のスペースが必要 Filter手法による方法 複数パタン 照合 抽出 Verify 正規表現 文字列集合 候補位置決定 出現位置の報告

Thompson’s NFA 用語の定義 NFAの性質 正規表現 RE を表す構文木 ThRE vを頂点とするThRE の部分木Th(v) K. Thompson. Regular expression search algorithm. Communications of the ACM, 11:419-422, 1968. 用語の定義 正規表現 RE を表す構文木 ThRE vを頂点とするThRE の部分木Th(v) NFAの性質 状態数 < 2m、　遷移関数の大きさ<4m　→O(m) ε遷移を含む ε遷移以外の遷移は必ず i番目から i+1番目に遷移する RE = (AT|GA)((AG|AAA)*) のNFA ε A G ε 9 10 11 ε A T 1 2 3 8 ε ε 16 ε ε ε A A A ε 12 13 14 15 7 17 ε ε G A ε 4 5 6

NFA構築アルゴリズム 構文木ThREに対して、ボトムアップにノードを探索（post order traverse）しつつ、各ノードについて以下を実行 (i) ノードvが空語εの場合 (iv) ノードvが連結”|”の場合 → (vL| vR) ε vL I F ε ε I F (ii) ノードvが文字aの場合 ε vR ε a I F (v) ノードvが閉包”*”の場合 → v* (iii) ノードvが連結”・”の場合 → (vL・vR) ε v* ε ε I vL vR F I F ε

擬似コード Thompson_recur (v) if v = “|”(vL, vR) or v = “・”(vL, vR) then Th(vL) ← Thompson_recur(vL); Th(vR) ← Thompson_recur(vR); else if v=“*”(vC) then Th(v) ← Thompson_recur(vC); /* ここまでが再帰的な処理 (post order traverse) */ if v=(ε) then return construction (i); if v=(α), α∈Σ then return construction (ii); if v=“・”(vL, vR) then return construction (iii); if v=“|”(vL, vR) then return construction (iv); if v=“*”(vC) then return construction (v); Thompon(RE) vRE ← Parse(RE$, 1); /* 構文木を構築する */ Th(vRE) ← Thompson_recur(vRE);