講義「情報知識ネットワーク特論」

全文

(1)講義「情報知識ネットワーク特論」～情報検索とパターン照合第４回近似文字列照合. 情報理工学専攻情報知識ネットワーク研究室喜田拓也. 講義資料. 2018/11/22.

(2) 今日の内容近似文字列照合問題とは？動的計画法によるアルゴリズム NFAに基づくアルゴリズムビットパラレル手法フィルタリング手法. 2.

(3) つっこみのできるコンピュータ！？. バロック時代のあの画家、そうそう！そう！フェルメールなんて言ったっけ？レンブラント！光と影が効果的な彼と同時代に彼らはどちらも風俗画を多く書いた，「夜警」っていうオランダ出身らしいね日本でも人気のある有名な絵を描いたそういえば同時代にえーっと・・・・・・え～とテラスゲースって画家確か、レンブライト・・・ウェブメールいなかった？だったかな？じゃなくて. ひょっとして！レンブラントベラスケスだろフェルメール？ヽ(`Д´)ノ（怒）ですね.

(4) 近似文字列照合問題とは？テキスト中から、パターンとの編集距離が 𝑘𝑘 以内の部分文字列の位置を求める問題. 編集距離 ed 𝑥𝑥, 𝑦𝑦 ：文字列 𝑥𝑥 に文字の挿入・削除・置換の操作を施して文字列 𝑦𝑦 へ変換するために要する最小のコスト 𝑑𝑑 CARRIAGE. MARRIAGE 𝑘𝑘 = 2 ed(MARRIAGE, MASSAGE)=3. MASSAGE. OK. 𝑑𝑑 = 1 𝑑𝑑 = 3. 0<k<m. MARRIAGE. 置換. 削除. MASS AGE Bad.

(5) 編集距離（Edit distance）二つの文字列がどのくらい似ているか？類似度 ⇔ 文字列間の編集距離（非類似度）. 以降の話は、すべて Levenshtein距離. 編集距離の種類 Levenshtein距離：挿入・削除・置換のコストがすべて 1 Hamming距離：置換だけを許した編集距離 Weighted-cost編集距離：変換操作ごとにコストが違う Unrestricted-cost編集距離：文字対ごとに操作コストが違う Damerau距離：挿入・削除・置換の操作に加え、前後の文字の入れ替えも許す Indel距離：挿入と削除だけを許した距離 insertion+deletionでindelらしい（Heikki Hyyröの[SOFSEM2005]の論文より）.

(6) 応用例 DNA配列間の類似度の計算スペル・チェッカーシソーラスを用いたあいまい検索検索は別もの  表記ゆれを補助：カラヴァッジョ ⇔ カラバッジョ類似文章の検索  自然言語処理との組み合わせで高度な検索を実現する  文章＝形態素の並び各形態素をメタ文字と考える類似音楽検索 DTW法  似ているフレーズを探す (Dynamic Time Warping)  鼻歌検索 OCR後のテキストに対する検索  対象テキストデータ自体に誤りが含まれている！実データのマイニングへの応用  近似文字列照合アルゴリズムを用いたウェブマイニング手法の研究（九州大学中藤哲也先生のグループ）.

(7) 動的計画法によるアルゴリズム動的計画法（Dynamic programming）によるストリームデータのマッチング動的計画法に基づく解法は1960年代にはすでに知られていた（迫江博昭）現在知られているパターン照合用のアルゴリズムはSellersによる P. H. Sellers, The theory and computation of evolutionary distances: Pattern recognition. Journal of Algorithms, 1(4):359-373,1980. H. Sakoe and S. Chiba, A Dynamic Programming Algorithm Optimization for Spoken Word Recognition, IEEE Trans. on Acoust., Speech and Signal Proc., Vol. ASSP- 26, No. 1, pp. 43-49, 1978.. 二つの文字列 𝑥𝑥, 𝑦𝑦 の編集距離の求め方：. すなわち 𝑀𝑀|𝑥𝑥|,|𝑦𝑦| = 𝑒𝑒𝑒𝑒(𝑥𝑥, 𝑦𝑦) 𝑀𝑀𝑖𝑖,𝑗𝑗 = 𝑒𝑒𝑒𝑒(𝑥𝑥 1: 𝑖𝑖 , 𝑦𝑦 1: 𝑗𝑗 ) とすると， 𝑀𝑀0,0 ← 0, 𝑀𝑀𝑖𝑖,𝑗𝑗 ← min 𝑀𝑀𝑖𝑖−1,𝑗𝑗−1 + 𝛿𝛿 𝑥𝑥 𝑖𝑖 , 𝑦𝑦 𝑗𝑗 , 𝑀𝑀𝑖𝑖−1,𝑗𝑗 + 1, 𝑀𝑀𝑖𝑖,𝑗𝑗−1 + 1 . ここで、𝛿𝛿 𝑎𝑎, 𝑏𝑏 は 𝑎𝑎 = 𝑏𝑏 なら0，そうでなければ1をとる関数．同等の計算をするより効率の良い再帰式は次のとおり．. 𝑀𝑀𝑖𝑖,𝑗𝑗 ←. 𝑀𝑀𝑖𝑖,0 ← 𝑖𝑖, 𝑀𝑀𝑖𝑖−1,𝑗𝑗−1. 𝑀𝑀0,𝑗𝑗 ← 𝑗𝑗. 1 + min 𝑀𝑀𝑖𝑖−1,𝑗𝑗−1 , 𝑀𝑀𝑖𝑖−1,𝑗𝑗 , 𝑀𝑀𝑖𝑖,𝑗𝑗−1. (𝑗𝑗 = 0 or 𝑖𝑖 = 0のとき) (𝑥𝑥 𝑖𝑖 = 𝑦𝑦 𝑗𝑗 のとき) (それ以外).

(8) どうしてそれで計算できるのか？帰納法で証明できる．便宜的に，𝑀𝑀0,0 = 0 は空語𝜀𝜀どうしの編集距離とする．いま，編集距離𝑒𝑒𝑒𝑒 𝑥𝑥[1: 𝑖𝑖], 𝑦𝑦[1: 𝑗𝑗] = 𝑀𝑀𝑖𝑖,𝑗𝑗 を求めたい．ただし，𝑥𝑥 1: 𝑖𝑖 と𝑦𝑦 1: 𝑗𝑗 より短いprefixどうしの編集距離は既に計算済みであると仮定する．このとき，𝑥𝑥[1: 𝑖𝑖] から𝑦𝑦[1: 𝑗𝑗]への変換コストについて考える．もし 𝑥𝑥 𝑖𝑖 = 𝑦𝑦[𝑗𝑗]なら，𝑥𝑥[1: 𝑖𝑖 − 1]から𝑦𝑦[1: 𝑗𝑗 − 1]へ最小コスト𝑀𝑀𝑖𝑖−1,𝑗𝑗−1 で変換すればよいので，𝑀𝑀𝑖𝑖,𝑗𝑗 = 𝑀𝑀𝑖𝑖−1,𝑗𝑗−1 となる． 𝑥𝑥[𝑖𝑖] ≠ 𝑦𝑦[𝑗𝑗]のときは，以下の３通りが考えられる：. 置換: 𝑥𝑥[𝑖𝑖]を𝑦𝑦[𝑗𝑗]で置き換え，𝑥𝑥[1: 𝑖𝑖 − 1]を𝑦𝑦[1: 𝑗𝑗 − 1]へ変換する → コスト 𝑀𝑀𝑖𝑖−1,𝑗𝑗−1 + 1 削除: 𝑥𝑥[𝑖𝑖]を削除し，𝑥𝑥[1: 𝑖𝑖 − 1]を 𝑦𝑦[1: 𝑗𝑗]へ変換する → コスト 𝑀𝑀𝑖𝑖−1,𝑗𝑗 + 1 挿入: 𝑦𝑦[𝑖𝑖]を𝑥𝑥[1: 𝑖𝑖]の後ろに挿入し，𝑥𝑥[1: 𝑖𝑖]を𝑦𝑦[1: 𝑗𝑗 − 1]へ変換する → コスト 𝑀𝑀𝑖𝑖,𝑗𝑗−1 + 1. 以上の中で最小のものをとればよい．置換. 削除. 𝑥𝑥[1: 𝑖𝑖– 1] 𝑥𝑥[𝑖𝑖]. 𝑀𝑀𝑖𝑖−1,𝑗𝑗−1. +1. 𝑦𝑦[1: 𝑗𝑗– 1] 𝑦𝑦[𝑗𝑗]. 𝑥𝑥[1: 𝑖𝑖– 1] 𝑥𝑥[𝑖𝑖] +1 𝑀𝑀𝑖𝑖−1,𝑗𝑗 𝑦𝑦[1: 𝑗𝑗– 1] 𝑦𝑦[𝑗𝑗]. 挿入 𝑥𝑥[1: 𝑖𝑖– 1] 𝑥𝑥[𝑖𝑖]. 𝑀𝑀𝑖𝑖,𝑗𝑗−1. +1. 𝑦𝑦[1: 𝑗𝑗– 1] 𝑦𝑦[𝑗𝑗]. 𝑀𝑀𝑖𝑖−1,𝑗𝑗−1. 𝑀𝑀𝑖𝑖−1,𝑗𝑗. 𝑀𝑀𝑖𝑖,𝑗𝑗−1. 𝑀𝑀𝑖𝑖,𝑗𝑗. +𝛿𝛿(𝑥𝑥[𝑖𝑖], 𝑦𝑦[𝑗𝑗]). +1. +1.

(9) テキスト中の出現を検出するには？. 𝑀𝑀0,0. ed(annual, annealing) の 𝑀𝑀𝑖𝑖,𝑗𝑗. a n n u a l. 0 1 2 3 4 5 6. a 1 0 1 2 3 4 5. n 2 1 0 1 2 3 4. n 3 2 1 0 1 2 3. e 4 3 2 1 1 2 3. a 5 4 3 2 2 1 2. l 6 5 4 3 3 2 1. i 7 6 5 4 4 3 2. n 8 7 6 5 5 4 3. 𝑀𝑀 𝑥𝑥 , 𝑦𝑦 = ed(annual, annealing) = 4. 𝑀𝑀𝑖𝑖−1,𝑗𝑗−1. 𝑀𝑀𝑖𝑖−1,𝑗𝑗. 𝑀𝑀𝑖𝑖,𝑗𝑗−1. 𝑀𝑀𝑖𝑖,𝑗𝑗. +𝛿𝛿(𝑥𝑥[𝑖𝑖], 𝑦𝑦[𝑗𝑗]). +1. +1. g 9 8 7 6 6 5 4. 𝑃𝑃 =annual, 𝑇𝑇 =annealing, 𝑘𝑘 = 2 のときの近似文字列照合 a n n u a l. 0 1 2 3 4 5 6. a 0 0 1 2 3 4 5. n 0 1 0 1 2 3 4. n 0 1 1 0 1 2 3. e 0 1 2 1 1 2 3. a 0 0 1 2 2 1 2. l 0 1 1 2 3 2 1. i 0 1 2 2 3 3 2. n 0 1 1 2 3 4 3. 任意の𝑗𝑗 = 0 … 𝑛𝑛 について、 𝑀𝑀0,𝑗𝑗 = 0 と置くだけでよい！. 空文字列εは、テキストの任意の位置に誤り0でマッチする！ 𝑂𝑂(𝑚𝑚𝑚𝑚)時間、𝑂𝑂(𝑚𝑚)領域. g 0 1 2 2 3 4 4.

(10) 平均時の計算量を改善する方法パターンはテキスト中にあまり出現しないと考える各縦列の上から下へ進む計算過程において、たいていの場合、すぐ 𝑘𝑘 + 1 に達してしまう（つまりミスマッチする）各セルが 𝑘𝑘 + 1 より大きいものは、その実際の値は照合結果と無関係 k よりも小さい値が入るセルを active と呼び、一番下方にあるactive なセルまでの領域を計算することで、平均時の計算量をO(𝑘𝑘𝑘𝑘)へ落とすことができる（これをDPアルゴリズムと名づける by 黄色本） E. Ukkonen. Finding approximate patterns in strings. Journal of Algorithms, 6(1-3):132-137, 1985.. 𝑃𝑃 =annual, 𝑇𝑇 =annealing, 𝑘𝑘 = 2 のときの近似文字列照合最悪時𝑂𝑂(𝑚𝑚𝑚𝑚)時間、平均時𝑂𝑂(𝑘𝑘𝑘𝑘)時間. a n n u a l. 0 1 2 3 4 5 6. a 0 0 1 2 3 4 5. n 0 1 0 1 2 3 4. n 0 1 1 0 1 2 3. e 0 1 2 1 1 2 3. a 0 0 1 2 2 1 2. l 0 1 1 2 3 2 1. i 0 1 2 2 3 3 2. n 0 1 1 2 3 4 3. g 0 1 2 2 3 4 4.

(11) DPアルゴリズムの擬似コード DP (P=p1p2…pm, T=t1t2…tn, k) 1 Preprocessing: 2 For i∈0…m Do Ci ← i 3 lact ← k + 1 /* last active cell */ 4 Searching: 5 For pos∈1...n Do 6 pC ← 0, nC ← 0 7 For i ∈ 1…lact Do 8 If pi = tpos Then nC ← pC 9 Else 10 If pC < nC Then nC ← pC 11 If Ci < nC Then nC ← Ci 12 nC ← nC + 1 13 End of if 14 pC ← Ci, Ci ← nC 15 End of for 16 While Clact > k Do lact ← lact – 1 17 If lact = m Then report an occurrence at pos 18 Else lact ← lact + 1 19 End of for.

(12) オートマトンに基づくアルゴリズム E. Ukkonen. Finding approximate patterns in strings. Journal of Algorithms, 6(1-3):132-137, 1985.. パターン 𝑃𝑃 =annual を誤り2以下で受理する非決定性有限オートマトン任意の文字∑. a. ∑ ε ∑ ε. ∑ a ∑ a. n. n. ∑ ε ∑ ε. ∑ n ∑ n. ∑ ε ∑ ε. 𝑇𝑇 = anneal. u. ∑ n ∑ n. ∑ ε ∑ ε. ∑ u ∑ u. l. a. ∑ ε ∑ ε. ∑ a ∑ a. ∑ ε ∑ ε. ∑ l ∑ l. no error. ∑. 1 error ∑. 2 error. を読み込んだときの状態. このNFAをDFAに変換して、照合を行う．オリジナルはUkkonen[1985]．後にいくつかの改良が提案された．古典的な方法で変換するため、状態数が (min(3𝑚𝑚, 𝑚𝑚(2𝑚𝑚|∑|)𝑘𝑘)) 個に膨れ上がる．パターン長が20より大きくなると、現実的ではない. 一致 Σ. L. 挿入 Σ ε Σ. L. 削除. Σ. 置換 Σ.

(13) NFAのRow-wiseビットパラレル (BPR). S. Wu and U. Manber. Fast text searching allowing errors. Communications of the ACM, 35(10): 83-91,1992.. 左右が逆転するパターン 𝑃𝑃 =annual を誤り2以下で受理する非決定性有限オートマトンことに注意任意の文字∑. a. ∑ ε ∑ ε. ∑ a ∑ a. n. n. ∑ ε ∑ ε. ∑ n ∑ n. ∑ ε ∑ ε. 𝑇𝑇 = anneal. u. ∑ n ∑ n. ∑ ε ∑ ε. ∑ u ∑ u. l. a. ∑ ε ∑ ε. ∑ a ∑ a. ∑ ε ∑ ε. ∑ l ∑ l. 000000 no error. ∑. 100011 1 error ∑. 110111 2 error. を読み込んだときの状態. 横一列の状態を一つのビット列で表現（activeな状態を1、非activeを0）し、ビットパラレル手法で全体の状態遷移をシミュレートする．ビット長mのビットマスクが 𝑘𝑘 + 1 個必要 𝑖𝑖番目の段の状態𝑅𝑅𝑖𝑖 を新しい状態𝑅𝑅′𝑖𝑖 へ更新する式 𝑂𝑂(𝑘𝑘𝑚𝑚/𝑤𝑤𝑛𝑛)時間 R’0 ← ((R0<<1)|0m-11) & B[tj] 𝑚𝑚 ≦ 𝑤𝑤の時は𝑂𝑂(𝑘𝑘𝑘𝑘)時間 R’i ← ((Ri<<1)&B[tj])|Ri-1| 複数の列を一度に計算できない (Ri-1<<1)|(R’i-1 << 1)|0m-11.

(14) 擬似コード BPR (P=p1p2…pm, T=t1t2…tn, k) 1 Preprocessing: 2 For c∈∑ Do B[c] ← 0m 3 For j ∈1…m Do B[pj ] ← B[pj ] | 0m-j 10j-1 4 Searching: 5 For i ∈0...k Do Ri ← 0m-i 1i 6 For pos ∈ 1…n Do 7 oldR ← R0 8 newR ← ((oldR<<1)|0m-1 1)&B[tpos] 9 R0 ← newR 10 For i ∈1...k Do 11 newR ← ((Ri<<1)&B[tpos])|oldR|((oldR|newR)<<1)|0m-11 12 oldR ← Ri, Ri ← newR 13 End of for 14 If newR & 10m-1≠0m Then report an occurrence at pos 15 End of for.

(15) NFAのDiagonal-wiseビットパラレル (BPD) R. A. Baeza-Yates and G. Navarro. Faster approximate string matching. Algorithmica, 23(2):127-158, 1999.. D0. D1 ∑. D2 a. ∑ ε ∑ ε. D=. ∑ a ∑ a. 0. D3 n. n ∑ ε ∑ ε. ∑ n ∑ n. D1 001 k+1ビット. D4. ∑ ε ∑ ε. ∑ n ∑ n. u ∑ ε ∑ ε. D2 0 111 k+1ビット. l. a ∑. u ∑ u. ∑ ε ∑ ε. ∑ a ∑ a. ∑ ε ∑ ε. ∑ l ∑ l. D3 0. ∑. no error 1 error. ∑. 2 error D4. 011 k+1ビット. 0. 011 k+1ビット. 𝐷𝐷𝑖𝑖 = 3 =[111] は，activeな状態がないとき. 斜めの列（Diagonal）を基準に、各列においてactiveな状態の深さ𝐷𝐷𝑖𝑖 を unaryで保持し（k+1ビット必要）、それらを連結したもので全体を表す境界に0をはさむため、全体では(𝑚𝑚 − 𝑘𝑘)(𝑘𝑘 + 2)ビット必要第１項目は置換第２項目は挿入 𝑖𝑖番目のテキスト 𝑡𝑡𝑗𝑗 を読み込んだときの新しい𝐷𝐷’𝑖𝑖 の値：第３項目は一致 D’i ← min(Di+1, Di+1+1, g(i-1, tj )) g(i,c) = min({k+1}∪{r|r≧Di and pi+1+r=c}) Shift-Or的マスク.

(16) 擬似コード BPD (P=p1p2…pm, T=t1t2…tn, k) 1 Preprocessing: 2 For c∈∑ Do B[c] ← 1m 3 For j ∈1…m Do B[pj ] ← B[pj ] & 1m-j 01j-1 4 For c∈∑ Do 5 BB[c] ← 0 sk+1(B[c],0) 0 sk+1(B[c],1)… 0 sk+1(B[c],m-k-1) 6 End of for 7 Searching: 8 D ← (01k+1)m-k 9 For pos ∈ 1…n Do 10 x ← (D >> (k+2)) | BB[tpos] 𝐷𝐷𝑖𝑖 + 1 11 D ← ((D << 1) | (0k+11)m-k) 𝐷𝐷𝑖𝑖+1 + 1 12 & ((D << (k+3)) | (0k+11)m-k-101k+1) clean up 13 & (((x + (0k+11)m-k) ∧ x) >> 1) & (01k+1)m-k 14 If D & 0(m-k-1)(k+2)010k = 0(m-k)(k+2) Then 𝑔𝑔(𝑖𝑖 − 1, tpos) 15 Report an occurrence at pos (m-k-1)(k+2) k+1 16 D ← D | 0 01 17 End of If 18 End of for.

(17) フィルタリング手法：パターン分割方式 S. Wu and U. Manber. Fast text searching allowing errors. Communications of the ACM, 35(10): 83-91,1992.. フィルタリング手法の考え方：「テキストの現在位置がパターンの出現位置である」ということよりも、「出現位置ではない」ことを調べるほうが簡単 → 出現位置の候補を高速に見つけてから、詳細に検査する！フィルタリング手法は平均時の計算量を改善する → 実際、エラー率（𝛼𝛼 = 𝑘𝑘/𝑚𝑚）が小さいときはうまくいく. パターン分割方式： Multiple Shift-Andやパタンを 𝑘𝑘 + 1 個の小片に分割 Set Horspoolを使う各小片を複数パターン照合アルゴリズムで高速に照合小片が出現した近辺を、通常用いられる近似文字列照合アルゴリズムを用いて検査する 𝑘𝑘 = 2 の場合. パターン: TAAATCACGGCATACT 分割後の小片: TAAAT, CACGG, CATACT テキスト:. ACCCTGTTTAGATCACGGCACTACTGTAAAC.

(18) 階層的検証による高速化. G. Navarro and R. Baeza-Yates. Very fast and simple approximate string matching. Information Processing Letters, 72:65-70, 1999.. 検査を階層的に行うことで、正しくない候補を少ない労力で見分けられる. ここでは，𝑗𝑗 = 𝑘𝑘 + 1 = 2𝑟𝑟 と仮定する．パターンを半分に分割し，それぞれ 𝑘𝑘/2 個の誤りを許すパターンとする．これを再帰的に誤りが0になるまで繰り返す． 2𝑟𝑟 でない場合は，適当分割したパターンを複数パターン照合アルゴリズムで照合し，な詰め物をする出現の候補を階層的に検査する aaabbbcccddd 𝑘𝑘 = 3 errors cccddd aaabbb 𝑘𝑘 = 1 errors b b b c c c d d d a a a 𝑘𝑘 = 0 errors CreateTree (P=p1p2…pm, k, myParent, idx, plen) 1 Create new node 2 from(node) ← i 3 to(node) ← j 4 left ← (k+1)/2 5 parent(node) ← myParent 6 err(node) ← k 7 If k = 0 Then leafidx ← node 8 Else 9 CreateTree(pi…i+left・plen–1, (left・k)/(k+1), node, idx, plen) 10 CreateTree(pi+left・plen…j,((k+1–left)・k)/(k+1),node,idx+left,plen) 11 End of If.

(19) 擬似コード(PEX) PEX (P=p1p2…pm, T=t1t2…tn, k) 1 Preprocessing: 2 CreateTree(p, k,θ, 0, m/(k+1) ) 3 Preprocess multipattern search for 4 {pfrom(node)…pto(node) | node = leafi , i∈{0…k} } 5 Searching: 6 For (pos, i) ∈ output of multipattern search Do 7 node ← leafi 8 in ← from(node) 9 node ← parent(node) 10 cand ← TRUE 11 While cand = TRUE and node ≠θ Do 12 p1 ← pos – (in – from(node)) – err(node) 13 p2 ← pos + (to(node) – in + 1) + err(node) 14 Verify text area Tp1…p2 for pattern piece pfrom(node)…to(node) 15 allowing err(node) errors 16 If pattern piece was not found Then cand ← FALSE 17 Else node ← parent(node) 18 End of while 19 If cand = TRUE Then 20 Report the positions where the whole p was found 21 End of If 22 End of for.

(20) フィルタリング手法：ABNDMアルゴリズム G. Navarro and R. Baeza-Yates. Very fast and simple approximate string matching. Information Processing Letters, 72:65-70, 1999.. ε. l ∑ ε. a ∑. l ∑. ∑ ε l. ε. ε. ε. ∑ ε. u ∑. a ∑. ∑ ε a. ∑ ε. n ∑. u ∑. ∑ ε u. ε. ∑ ε. n ∑. n ∑. ∑ ε n. ∑ ε. ε. ε. a ∑. n ∑. ∑ ε n. ∑ ε. ∑ a ∑. ∑ ε. no error ∑. 1 error ∑. a. 2 error. パターン𝑃𝑃に対して、𝑃𝑃𝑅𝑅の任意のfactorに𝑘𝑘以下の誤りを許した文字列を受理するNFAを構築 → BNDMの拡張このNFAは、𝑃𝑃𝑅𝑅の誤り𝑘𝑘以下のprefixを認識できる BNDMはアルファベットサイズが小さいときはBoyer-Mooreよりも高速このNFAで出現の候補を特定する BNDMと同じく、テキストを飛ばし読みしながら動作する DNAのようなテキストに対してはPEXよりもうまく動作する.

(21) 擬似コード(ABNDMアルゴリズム) ABNDM (P=p1p2…pm, T=t1t2…tn, k) 1 Preprocessing: 2 For c∈∑ Do B[c] ← 0m 3 For j ∈1…m Do B[pj ] ← B[pj ] | 0m-j 10j-1 4 Searching: 5 pos ← 0 6 While pos ≦ n – (m – k) Do 7 j ← m – k – 1, last ← m – k – 1 8 R0 ← B[tpos+m–k ] 9 newR ← 1m 10 For i ∈1…k Do Ri ← newR 11 While newR ≠ 0m and j ≠ 0 Do 12 oldR ← R0 13 newR ← (oldR << 1) & B[tpos+j ] 14 R0 ← newR 15 For i ∈1…k Do 16 newR ← ((Ri<<1)&B[tpos+j])|oldR|((oldR|newR)<<1) 17 oldR ← Ri, Ri ← newR 18 End of for 19 j ← j – 1 20 If newR & 10m-1 ≠ 0m Then /* prefix recognized */ 21 If j > 0 Then last ← j 22 Else check a possible occurrence starting at pos+1 23 End of if 24 End of while 25 pos ← pos + last 26 End of while.

(22) 第４回まとめ近似文字列照合とは？編集距離が𝑘𝑘以下の部分文字列を見つける問題動的計画法によるアルゴリズム O(𝑚𝑚𝑚𝑚)時間、O(𝑚𝑚)領域 → 平均時O(𝑘𝑘𝑘𝑘)時間に改良するアルゴリズム(DP) オートマトンに基づくアルゴリズム 𝑘𝑘以下の誤りを許してパターンを受理するNFAを構築 → DFAに変換して計算ビットパラレル手法 Row-wiseビットパラレル（BPR）： O(𝑘𝑘 𝑚𝑚/𝑤𝑤 𝑛𝑛)時間 Diagonal-wiseビットパラレル(BPD)： O( 𝑘𝑘(𝑚𝑚 − 𝑘𝑘)/𝑤𝑤 𝑛𝑛)時間 DP表をビットパラレル(BPM)： O( 𝑚𝑚/𝑤𝑤 𝑛𝑛)時間. フィルタリング手法テキストの大部分を調べずに済ませるパターン分割方式(PEX)、BNDM方式(ABNDM). 次回のテーマ正規表現の照合：柔軟・便利な検索キーワードの記述ができる.

(23)