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

全文

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

(2) 今日の内容正規表現について照合処理のながれ構文木（parse tree）の構築 NFAの構築 NFAのシミュレーション手法. 2.

(3) 正規表現とは？柔軟で強力なテキスト照合のための記法ファイル名の正規表現の例： rm ＊.txt cp Important[0-9].doc. 任意のファイル名.txt にマッチ Important0.doc～ Important9.doc にマッチ. 検索ツールGrepの正規表現の例： grep –E “for.+(256|CHAR_SIZE)” ＊.c. プログラミング言語Perlの正規表現の例： “http://”で始まり、”.jp/”を m|^http://.+¥.jp/.+$| 含む文字列にマッチ. 正規表現は任意の正規集合（正規言語）を表現できる＝有限オートマトンが受理できる言語𝐿𝐿を表現できる 3.

(4) 正規表現の定義正規表現とは、Σ ∪ {ε,|,・,∗,（,）} 上の文字列であり、以下の規則で再帰的に定義される。 (1) 𝜀𝜀とΣの要素は正規表現である (2) 𝛼𝛼と𝛽𝛽が正規表現ならば(𝛼𝛼・𝛽𝛽)も正規表現である (3) 𝛼𝛼と𝛽𝛽が正規表現ならば(𝛼𝛼|𝛽𝛽)も正規表現である (4) 𝛼𝛼が正規表現ならば 𝛼𝛼∗も正規表現である (5) 上から導かれるものだけが正規表現である例： (A・((A・T)|(C・G))∗). → A(AT|CG)∗. 簡略のために、（𝛼𝛼・𝛽𝛽）を単に𝛼𝛼𝛼𝛼と記述する ※ 記号|,・,∗は、オペレータ（operator）と呼ばれるまた、+は、𝛼𝛼を正規表現とすると、𝛼𝛼+ = 𝛼𝛼・𝛼𝛼∗ の意味で使用されることがある. 4.

(5) 正規表現の意味づけ正規表現をΣ*の部分集合（言語L）に写像する (i) (ii) (iii) (iv) (v). ||𝜀𝜀|| = {𝜀𝜀} a ∈ Σ に対して ||a|| = {a} 正規表現𝛼𝛼, 𝛽𝛽に対して ||(𝛼𝛼・𝛽𝛽)|| = ||𝛼𝛼||・||𝛽𝛽|| 正規表現𝛼𝛼, 𝛽𝛽に対して ||(𝛼𝛼|𝛽𝛽)|| = ||𝛼𝛼|| ∪ ||𝛽𝛽|| 正規表現𝛼𝛼に対して 𝛼𝛼 ∗ = 𝛼𝛼 ∗. 例： (a・(a|b) ∗) (a・(a|b) ∗) = a ・ (a|b) ∗ = {a}・ a b ∗ = {a}・ a ∪ b ∗ = a𝑥𝑥 𝑥𝑥 ∈ a, b ∗. 左の例と等価な決定性オートマトン（DFA）. q0. a. q1. a,b. b q2. a,b. 演習： (AT|GA)(TT)* はどのような言語になるだろうか？. 5.

(6) 正規表現を照合するとは？正規表現の照合問題：正規表現𝛼𝛼で定義される言語 𝐿𝐿 𝛼𝛼 ＝ 𝛼𝛼 に含まれる任意の文字列をテキスト中から探し出す問題正規表現と有限オートマトンは言語を定義する能力が等しい！正規表現で表現できる言語を受理する有限オートマトンを構築できる逆に、有限オートマトンが受理する言語を表現する正規表現も存在する ※ 有川節夫・宮野悟著、「オートマトンと計算可能性」参照（2.5 正規表現と正規集合）. 正規表現に対応する（非）決定性オートマトンを作成し、その動きをシミュレートすればよい DFAよりも、NFAへ変換するほうが容易ただし、初期状態は常にアクティブテキストを読んでいく過程で、オートマトンが受理状態に到達したらパタン出現 6.

(7) 照合処理のながれ一般的な方法. Thompson法によるNFA構築. 構文解析 (parsing). 正規表現. テキスト走査構文木. NFA. 出現位置の報告. Glushkov法によるNFA構築. DFA フィルタ法（filtering)による方法. 正規表現. 抽出. 検査複数パタン (verify) 照合文字列集合候補位置決定. 出現位置の報告. 7.

(8) 構文木（parse tree）の構築構文木： NFAを作りやすくするための準備として用いる木構造葉ノードは各々，文字a ∈ Σ もしくは空語 𝜀𝜀 でラベル付けされる内部ノードはオペレータ {|,・,*} でラベル付けされる. 例：正規表現𝑅𝑅𝑅𝑅=(AT|GA)((AG|AAA)*) の構文木 𝑇𝑇𝑅𝑅𝑅𝑅 ・. (AT|GA)((AG|AAA)*). |. *. ・ A. |. ・ T. G. A. ・ A. ・ G. オペレータ. 1. |. 2. |. A. ・ A. 括弧の深さ. A. 8.

(9) 擬似コード Parse (p=p1p2…pm, last) 1 v ← θ; 2 while plast≠$ do /* normal character */ 3 if plast∈Σ or plast=𝜀𝜀 then 4 vr ← Create a node with plast; 5 if v≠θ then v ← [・](v, vr); 6 else v ← vr; 7 last ← last + 1; /* union operator */ 8 else if plast = ‘|’ then 9 (vr, last) ← Parse(p, last + 1); 10 v ← [ | ](v, vr); /* star operator */ 11 else if plast = ‘*’ then 12 v ← [ * ](v); 13 last ← last + 1; 14 else if plast = ‘( ’ then /* open parenthesis */ 15 (vr, last) ← Parse(p, last + 1); 16 last ← last + 1; 17 if v≠θthen v ← [・](v, vr); 18 else v ← vr; 19 else if plast = ‘)’ then /* close parenthesis */ 20 return (v, last); 21 end of if 22 end of while 23 return (v, last); 9.

(10) ThompsonのNFA構築法. K. Thompson. Regular expression search algorithm. Communications of the ACM, 11:419-422, 1968.. アイデア：正規表現𝑅𝑅𝑅𝑅の構文木𝑇𝑇𝑅𝑅𝑅𝑅 をpost-orderで巡回しつつ、各ノード 𝑣𝑣 を頂点とする部分木に対応する言語𝐿𝐿 𝑅𝑅𝐸𝐸𝑣𝑣 を受理するオートマトン 𝑇𝑇𝑇(𝑣𝑣) を構築する各𝑇𝑇𝑇(𝑣𝑣)は、𝑣𝑣の子ノードに対するオートマトンを𝜀𝜀遷移で連結することで得られる. Thompson NFAの性質：. 状態数 < 2𝑚𝑚、状態遷移の数 < 4𝑚𝑚 → O(𝑚𝑚) 𝜀𝜀遷移を含む 𝜀𝜀遷移以外の遷移は必ず 𝑖𝑖番目から 𝑖𝑖 + 1番目に遷移する. 例：正規表現𝑅𝑅𝑅𝑅 = (AT|GA)((AG|AAA)*) に対するThompson NFA 𝜀𝜀. 1. 0. 𝜀𝜀. 4. A. G. 2. 5. T. A. 3. 6. 𝜀𝜀. 𝜀𝜀. 7. 𝜀𝜀. 8. 𝜀𝜀 𝜀𝜀. 9. 𝜀𝜀. 12. A. A. 13. 10. A. G. 14. 11. A. 𝜀𝜀 15. 𝜀𝜀. 𝜀𝜀 16. 𝜀𝜀 10. 17.

(11) NFA構築アルゴリズム構文木 𝑇𝑇𝑅𝑅𝑅𝑅 に対して、post-orderでノードを探索しつつ、各ノードについて次のようにオートマトンを生成・連結する (i) ノード𝑣𝑣が空語𝜀𝜀の場合 I. 𝜀𝜀. (iv) ノード𝑣𝑣が選択”|”の場合 → (𝐿𝐿|𝑅𝑅). F. (ii) ノード𝑣𝑣が文字a ∈ Σの場合 I. a. 𝑣𝑣𝐿𝐿. 𝜀𝜀. F. (iii) ノード𝑣𝑣が連結”・”の場合 → (𝐿𝐿・𝑅𝑅) IL. I. 𝑣𝑣𝑅𝑅. FR. 𝜀𝜀. IL. IR. 𝑣𝑣𝐿𝐿. FL. 𝑣𝑣𝑅𝑅. FR. 𝜀𝜀. F. 𝜀𝜀. (v) ノード𝑣𝑣が繰り返し”*”の場合 → 𝐶𝐶∗. I. 𝜀𝜀. 𝑣𝑣𝑐𝑐. 𝜀𝜀. 𝜀𝜀. 𝜀𝜀. F. 11.

(12) NFA構築アルゴリズムの動作例：正規表現𝑅𝑅𝑅𝑅 =(AT|GA)((AG|AAA)*) の構文木 𝑇𝑇𝑅𝑅𝑅𝑅 7. 3. 1. |. ・. A. T. 4. G. *. 6. ・ 2. ・. 18. 5. | 10. A. 15. ・. ・. A. 9. G. ・. 11. 例：正規表現𝑅𝑅𝑅𝑅 =(AT|GA)((AG|AAA)*) に対するThompson NFA 𝜀𝜀 𝜀𝜀. 1. 0. 𝜀𝜀. 4. G. 2. 5. T. A. 3. 6. 𝜀𝜀. 𝜀𝜀. 7. 𝜀𝜀. 16. 13 8. A. 17. 8. 𝜀𝜀. 9. 𝜀𝜀. 12. A. A. 13. 10. A. A. A A. 12. G. 14. 14. 11. A. 𝜀𝜀 15. 𝜀𝜀. 𝜀𝜀 16. 𝜀𝜀 12. 17.

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

(14) GlushkovのNFA構築法. V-M. Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 16:1-53, 1961.. アイデア：正規表現𝑅𝑅𝑅𝑅中の各文字a ∈ Σ に前から順に番号を振り、これを𝑅𝑅𝑅𝑅𝑅とする（番号付きのアルファベットを Σ′ とする）例： 𝑅𝑅𝑅𝑅 = (AT|GA)((AG|AAA)*) → 𝑅𝑅𝑅𝑅𝑅 = (A1T2|G3A4)((A5G6|A7A8A9)*). 言語𝐿𝐿(𝑅𝑅𝑅𝑅𝑅)を受理するNFAを作り、番号を取り除いて最終的なNFAを得る. Glushkov NFAの性質：状態数はちょうど𝑚𝑚 + 1個、状態遷移の数はO(𝑚𝑚2) 𝜀𝜀遷移を含まない任意のノードについて、そのノードに入ってくる遷移のラベルはすべて等しい例： 𝑅𝑅𝐸𝐸 ′ = (A1T2|G3A4)((A5G6|A7A8A9)*) に対するNFA G3 A7 A1 T2 A4 A5 0. 1. 2. 例：最終的なGlushkov NFA 0. A. 1. T. 3. G 2. 3. A5. A A. 4. 5. G6. 6. 4. A. 5. G A. 7. A7. A5 A. A7. 6. A A. 7. A8 A7. A A. 8. 8. A9. A. A5 9. A 9 14.

(15) NFA構築アルゴリズム(1) 正規表現𝑅𝑅𝑅𝑅中の各文字a ∈ Σ に前から順に番号を振り、これを𝑅𝑅𝐸𝐸 ′ とする 𝑃𝑃𝑃𝑃𝑃𝑃 𝑅𝑅𝐸𝐸 ′ = {1 … 𝑚𝑚}, Σ′ ：番号付けされたアルファベット. 構文木 𝑇𝑇𝑅𝑅𝑅𝑅𝑅 をpost-orderで巡回しながら、各ノード𝑣𝑣を頂点とする部分木に対応する言語𝑅𝑅𝑅𝑅𝑣𝑣’について集合First(𝑅𝑅𝑅𝑅𝑣𝑣’)、Last(𝑅𝑅𝑅𝑅𝑣𝑣’)、関数Empty𝑣𝑣 、および、 𝑅𝑅𝑅𝑅𝑅の位置𝑥𝑥についての関数 Follow 𝑅𝑅𝑅𝑅𝑅, 𝑥𝑥 を計算する ∗ NFAの開始位置 First(𝑅𝑅𝑅𝑅𝑅) = {𝑥𝑥 ∈ 𝑃𝑃𝑃𝑃𝑃𝑃(𝑅𝑅𝑅𝑅𝑅) | ∃𝑢𝑢 ∈ Σ′ , 𝛼𝛼𝑥𝑥𝑢𝑢 ∈ 𝐿𝐿(𝑅𝑅𝑅𝑅𝑅)} ∗ 最終状態の位置 Last(𝑅𝑅𝑅𝑅𝑅) = {𝑥𝑥 ∈ 𝑃𝑃𝑃𝑃𝑃𝑃(𝑅𝑅𝑅𝑅𝑅) | ∃𝑢𝑢 ∈ Σ′ , 𝑢𝑢𝑢𝑢𝑥𝑥 ∈ 𝐿𝐿(𝑅𝑅𝑅𝑅𝑅)} ∗ Follow(𝑅𝑅𝑅𝑅𝑅, 𝑥𝑥) = {𝑦𝑦 ∈ 𝑃𝑃𝑃𝑃𝑃𝑃(𝑅𝑅𝑅𝑅𝑅) | ∃𝑢𝑢, 𝑣𝑣 ∈ Σ′ , 𝑢𝑢𝑢𝑢𝑥𝑥𝛼𝛼𝑦𝑦𝑣𝑣 ∈ 𝐿𝐿(𝑅𝑅𝑅𝑅𝑅)} Empty𝑅𝑅𝑅𝑅 : 𝜀𝜀が𝐿𝐿(𝑅𝑅𝑅𝑅)に属するなら {𝜀𝜀}、そうでないならば𝜑𝜑を遷移関数のつながり返す関数．これは、次のようにして再帰的に計算できる Emptyε = 𝜀𝜀 , Emptya∈Σ = 𝜑𝜑, Empty𝑅𝑅𝐸𝐸1 |𝑅𝑅𝐸𝐸2 = Empty𝑅𝑅𝐸𝐸1 ∪ Empty𝑅𝑅𝐸𝐸2 , Empty(𝑅𝑅𝐸𝐸1 ⋅𝑅𝑅𝐸𝐸2 ) = Empty𝑅𝑅𝐸𝐸1 ∩ Empty𝑅𝑅𝐸𝐸2 , Empty𝑅𝑅𝑅𝑅∗ = 𝜀𝜀 .. NFAの初期状態が終状態かどうか. 上で得られた値をもとに、NFAを構築する. 15.

(16) NFA構築アルゴリズム(2) 言語𝐿𝐿(𝑅𝑅𝑅𝑅𝑅)を受理する（Glushkov）NFA 𝐺𝐺𝐿𝐿′ = 𝑆𝑆, Σ′ , 𝐼𝐼, 𝐹𝐹, 𝛿𝛿 ′ 𝑆𝑆 ：状態の集合. 𝑆𝑆 = 0, 1, … , 𝑚𝑚 Σ′ ：番号付けされたアルファベット 𝐼𝐼 ：初期状態．𝐼𝐼 = 0 𝐹𝐹 ：最終状態 𝐹𝐹 = Last(𝑅𝑅𝐸𝐸 ′ ) ∪ Empty𝑅𝑅𝑅𝑅 ・ 0 . 𝛿𝛿 ′ ：以下で定義される遷移関数 ∀𝑥𝑥 ∈ 𝑃𝑃𝑃𝑃𝑃𝑃 𝑅𝑅𝐸𝐸 ′ , ∀𝑦𝑦 ∈ Follow(𝑅𝑅𝐸𝐸 ′ , 𝑥𝑥), 𝛿𝛿𝛿(𝑥𝑥, 𝛼𝛼𝑦𝑦) = 𝑦𝑦 初期状態からの遷移は次のとおり ∀𝑦𝑦 ∈ First(𝑅𝑅𝐸𝐸 ′ ), 𝛿𝛿 ′ (0, 𝛼𝛼𝑦𝑦) = 𝑦𝑦 例： 𝑅𝑅𝑅𝑅 ′ = (A1T2|G3A4)((A5G6|A7A8A9)*) に対するNFA G3. 0. A1. 1. T2. 2. 3. A4 A5. A7 A5. 4. 5. G6. A5. 6. A7 A7. 7. A8 A7. 8. A9. A5 9. 16.

(17) 擬似コード Glushkov_variables (vRE, lpos) 1 if v=[|](vl,vr) or v=[・](vl,vr) then 2 lpos ← Glushkov_variables(vl, lpos); 3 lpos ← Glushkov_variables(vr, lpos); 4 else if v=[*](v*) then lpos ← Glushkov_variables(v*, lpos); 5 end of if 6 if v=(ε) then 7 First(v)←φ, Last(v)←φ, Emptyv←{ε}; 8 else if v=(a), a∈Σ then 9 lpos ← lpos + 1; 10 First(v)←{lpos}, Last(v)←{lpos}, Emptyv←φ, Follow(lpos)←φ; 11 else if v=[|](vl,vr) then 12 First(v)←First(vl)∪First(vr); 13 Last(v) ←Last(vl)∪Last(vr); 14 Emptyv ←Emptyvl∪Emptyvr; 15 else if v=[・](vl,vr) then 16 First(v)← First(vl)∪(Emptyvl・First(vr)); 17 Last(v) ← (Emptyvr・Last(vl))∪Last(vr); トータルO 𝑚𝑚3 時間 18 Emptyv ← Emptyvl∩Emptyvr; 19 for x∈Last(vl) do Follow(x)←Follow(x)∪First(vr); 20 else if v=[*](v*) then 21 First(v)←First(v*), Last(v)←Last(v*), Emptyv←{ε}; 2 22 for x∈Last(v*) do Follow(x)←Follow(x)∪First(v*); O 𝑚𝑚 時間 23 end of if 24 return lpos; 17.

(18) 擬似コード（続き） Glushkov (RE) 1 /* 正規表現をパースして構文木を作る */ 2 vRE ← Parse(RE$, 1); 3 4 /* 構文木を使って各変数を計算する */ 5 m ← Glushkov_variables(vRE, 0); 6 7 /* 計算した変数を使ってNFA GL(S,∑, I, F,δ)を構築する */ 8 Δ←φ; 9 for i ∈ 0…m do create state I; 10 for x ∈ First(vRE) do Δ←Δ∪ {(0, αx, x)}; 11 for i ∈ 0…m do 12 for i ∈ Follow(i) do Δ←Δ∪ {(i,αx, x)}; 13 end of for 14 for x∈ Last(vRE)∪(EmptyvRE・{0}) do mark x as terminal;. 18.

(19) 照合処理のながれ（再） Thompson法によるNFA構築構文解析 (Parsing). 正規表現. NFAはO(𝑚𝑚𝑚𝑚)時間で模倣できるテキスト走査. 構文木. NFA. 出現位置の報告. Glushkov法によるNFA構築. この変換には𝑂𝑂(2𝑚𝑚 )の時間・領域が必要. DFA. 実はDFAへ直接に変換する方法もある ※ A. V. Aho, R. Sethi, and J. D. Ullman. Compilers – Principles, Techniques and Tools. Addison-Wesley, 1986. （邦訳：コンパイラ原理・技法・ツール）を参照（3.9節） 19.

(20) NFAのシミュレーション手法 Thompson提案のNFAシミュレーション手法最も簡単な手法 O(𝑚𝑚)の大きさのリストでactiveな状態を保持し、文字ごとのNFAの状態更新をO(𝑚𝑚)で行う明らかにO(𝑚𝑚𝑚𝑚)時間かかる. 等価なDFAに変換してシミュレートする手法. 古典的に用いられている手法前処理として変換する → O(2𝑚𝑚)時間・領域かかるテキストを走査する際、必要となったDFAの部分を動的に構築する手法もある. ※ A. V. Aho, R. Sethi, and J. D. Ullman. Compilers – Principles, Techniques and Tools. Addison-Wesley, 1986. （邦訳：コンパイラ原理・技法・ツール）を参照. NFAとDFAを組み合わせて効率をあげるハイブリッドな手法 ThompsonのNFAをO(𝑘𝑘)個のノードのモジュールに分割し、モジュール毎にDFA化する各モジュール間の遷移はNFAとしてシミュレートする ※ E. W. Myers. A four russians algorithm for regular expression pattern matching. Journal of the ACM, 39(2):430-448, 1992.. Bit-parallel手法による高速なNFAシミュレーション ThompsonのNFAをシミュレート： S. Wu and U. Manber[1992]の手法 GlushkovのNFAをシミュレート： G. Navarro and M. Raffinot[1999]の手法、ほか 20.

(21) Bit-parallel Thompson. S. Wu and U. Manber. Fast text searching allowing errors. Communications of the ACM, 35(10):83-91, 1992.. Thompson NFAをbit-parallelでシミュレートする方法： Thompson NFAでは、（𝜀𝜀遷移を除くと） 𝑖𝑖番目の状態の次は必ず 𝑖𝑖 + 1番目 → Shift-And法に似たbit-parallel化ができる！ 𝜀𝜀遷移については、別途シミュレートする → 大きさ2𝐿𝐿 のマスクテーブルが必要（𝐿𝐿はNFAの状態数）前処理全体で O 2𝐿𝐿 + 𝑚𝑚 Σ 時間かかる 𝐿𝐿が十分小さいときはO(𝑛𝑛) 時間でテキストを走査できる. Thompson NFA 𝑄𝑄 = 𝑠𝑠0 , … , 𝑠𝑠 𝑄𝑄 −1 , Σ, 𝐼𝐼 = 𝑠𝑠0 , 𝐹𝐹, Δ のNFAのマスクビット表現： 𝑄𝑄𝑛𝑛 = 0, … , 𝑄𝑄 − 1 , 𝐼𝐼𝑛𝑛 = 0 𝑄𝑄 −1 1, 𝐹𝐹𝑛𝑛 = |𝑠𝑠𝑗𝑗 ∈𝐹𝐹 0 𝑄𝑄 −1−𝑗𝑗 10𝑗𝑗. 各マスクテーブルの定義： 𝐵𝐵𝑛𝑛 [𝑖𝑖, 𝜎𝜎] = | 𝑠𝑠𝑖𝑖 ,𝜎𝜎,𝑠𝑠𝑗𝑗 ∈Δ 0 𝑄𝑄 −1−𝑗𝑗 10𝑗𝑗 𝐸𝐸𝑛𝑛 𝑖𝑖 = |𝑠𝑠𝑗𝑗 ∈𝐸𝐸 𝑖𝑖 0 𝑄𝑄 −1−𝑗𝑗 10𝑗𝑗. （ここで、𝐸𝐸(𝑖𝑖)は状態𝑠𝑠𝑖𝑖 の𝜀𝜀-closure）. 𝐸𝐸𝑑𝑑 𝐷𝐷 = |𝑖𝑖,𝑖𝑖=0 OR 𝐷𝐷&0𝐿𝐿−𝑖𝑖−110𝑖𝑖 ≠0𝐿𝐿 𝐸𝐸𝑛𝑛 𝑖𝑖 𝐵𝐵 𝜎𝜎 = |𝑖𝑖∈0…𝑚𝑚 𝐵𝐵𝑛𝑛 𝑖𝑖, 𝜎𝜎. 21.

(22) 擬似コード BuildEps(N = (Qn,∑,In,Fn,Bn,En) ) 1 for σ∈∑ do 2 B[σ] ← 0L; 3 for i∈0…L–1 do B[σ] ← B[σ] | Bn[i,σ]; 4 end of for 5 Ed[0] ← En[0]; 6 for i∈0…L–1 do 7 for j∈0…2i – 1 do 8 Ed[2i + j] ← En[ i ] | Ed[ j ]; 9 end of for 10 end of for 11 return (B, Ed); BPThompson(N = (Qn,∑,In,Fn,Bn,En), T = t1t2…tn) 1 Preprocessing: 2 (B, Ed) ← BuildEps(N); 3 Searching: 4 D ← Ed[ In ]; /* 初期状態 */ 5 for pos∈1…n do 6 if D & Fn≠ 0L then report an occurrence ending at pos–1; 7 D ← Ed[ (D << 1) & B[tpos] ]; 8 end of for 22.

(23) 第５回まとめ正規表現：有限オートマトンと言語を定義する能力が等しい正規表現の照合処理のながれ • 構文木（parse tree）を構築してからNFAへ変換し、NFAをシミュレートしてテキストを走査 • Filtration+複数パターン照合+検査+NFAシミュレート NFAの構築方法 Thompson NFA： • 状態数 < 2𝑚𝑚、状態遷移の数 < 4𝑚𝑚 → O(𝑚𝑚) • 𝜀𝜀遷移を含む • 𝜀𝜀遷移以外の遷移は必ず 𝑖𝑖番目から 𝑖𝑖 + 1番目に遷移する Glushkov NFA： • 状態数はちょうど𝑚𝑚 + 1個、状態遷移の数はO(𝑚𝑚2) • 𝜀𝜀遷移を含まない • 任意のノードについて、そのノードに入ってくる遷移のラベルはすべて等しい. NFAのシミュレーション手法 Thompsonの手法 → O(𝑚𝑚𝑚𝑚)時間 DFAへ変換 → O(𝑛𝑛)時間で走査、ただしO(2𝑚𝑚)時間・領域の前処理 Bit-parallel手法による高速化： Bit-parallel Thompson、Bit-parallel Glushkov 次回のテーマ圧縮テキスト上のパターン照合. 23.

(24) 付録第一回目の講義で説明していなかった用語の定義について Σ ∗ の部分集合を形式言語（formal language）または単に言語という言語𝐿𝐿1, 𝐿𝐿2 ∈ Σ ∗ に対して、集合 𝑥𝑥 𝑦𝑦 𝑥𝑥 ∈ 𝐿𝐿1 かつ 𝑦𝑦 ∈ 𝐿𝐿2 } を𝐿𝐿1 と𝐿𝐿2 の積（product）といい、𝐿𝐿1・𝐿𝐿2または単に𝐿𝐿1𝐿𝐿2と書く言語 𝐿𝐿 ⊆ Σ ∗ に対して、 𝐿𝐿0 = 𝜀𝜀 , 𝐿𝐿𝑛𝑛 = 𝐿𝐿𝑛𝑛−1 ・𝐿𝐿 (𝑛𝑛 ≥ 1) とする。また 𝐿𝐿∗ = ⋃𝑛𝑛=0…∞ 𝐿𝐿𝑛𝑛 として、これを𝐿𝐿の閉包（closure）という。また 𝐿𝐿+ = ⋃𝑛𝑛=1…∞ 𝐿𝐿𝑛𝑛 とする. 後方参照について. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press, Elsevier, 1990. （邦訳）コンピュータ基礎理論ハンドブックⅠ：アルゴリズムと複雑さ，丸善，1994. 第5章2.3節後退参照付き正規表現、および6.1節後退参照付き正規表現の照合問題これによると、後方参照という考え自体は1964年に既に出現していたらしい正規表現どころか、文脈自由文法の枠組みをも超えているその照合問題は、NP完全（NP-complete）であることが証明されている 24.

(25)