1

北海道大学
Hokkaido University

情報知識ネットワーク特論「情報検索とパターン照合」
情報科学研究科 コンピュータサイエンス専攻
情報知識ネットワーク研究室

喜田拓也

2005/11/8

情報知識ネットワーク特論 講義資料

第５回
正規表現の照合
正規表現について照合処理のながれ構文木（parse tree）の構築
NFAの構築NFAのシミュレーション手法

北海道大学 Hokkaido University

3

正規表現とは？


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

正規表現は任意の正規集合（正規言語）を表現できる– 有限オートマトンが受理できる言語（文字列の集合）Lを表現

2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University4

正規表現の定義


定義：

正規表現とは、Σ∪{ε, |, ・, *, （, ）} 上の文字列であり、以下の規則で再帰的に定義される。
– (1) εとΣの要素は正規表現である– (2) αとβが正規表現ならば (α・β)も正規表現である– (3) αとβが正規表現ならば (α|β)も正規表現である– (4) αが正規表現ならば α* も正規表現である– (5) 上から導かれるものだけが正規表現である
例： (A・((A・T)|(C・G))*)→ A(AT|CG)*

簡略のために、（α・β）を単にαβと記述する※ ‘| ’, ‘・’, ‘*’は、オペレータ（operator）と呼ばれる
また、“+”は、αを正規表現とすると、α+ =α・α* の意味で使用されることがある
2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

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})*= { ax | x∈{a, b}* }左の例と等価な決定性オートマトン（DFA）

q0

aa,bq1bq2a,b

演習： (AT|GA)(TT)* はどのような言語になるだろうか？
2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

6

正規表現を照合するとは？
正規表現の照合問題：– 正規表現αで定義される言語L(α)＝||α||に含まれる任意の文字列をテキスト中から探し出す問題

正規表現と有限オートマトンは言語を定義する能力が等しい！

– 正規表現で表現できる言語を受理する有限オートマトンを構築できる– 逆に、有限オートマトンが受理する言語を表現する正規表現も存在する※ 有川節夫・宮野悟著、「オートマトンと計算可能性」参照（2.5 正規表現と正規集合）



正規表現に対応する（非）決定性オートマトンを作成し、その動きをシミュレートすればよい。

– DFAよりも、NFAへ変換するほうが容易– ただし、初期状態は常にアクティブ– テキストを読んでいく過程で、オートマトンが受理状態に到達したらパタン出現

2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

7

照合処理のながれ
一般的な方法Thompson法によるNFA構築

構文解析(Parsing)

テキスト走査正規表現

構文木

出現位置の報告

NFA

テキスト性化走査

決定
Glushkov法によるNFA構築

DFAFilter手法による方法
正規表現

2005/11/8

抽出

複数パタン
Verify照合
文字列集合
候補位置決定出現位置の報告

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

8構文木（parse tree）の構築
構文木： NFAを作りやすくするための準備として用いる木構造– 葉ノードは各々アルファベット∑上の文字a∈Σもしくは空語εでラベル付けされる– 内部ノードはオペレータ {|, ・, *} でラベル付けされる– LexやFlexなどの構文解析ツールでも変換できるが、正規表現のパーサとしては大げさすぎる （→ 次のスライドの擬似コードで十分）
例： 正規表現RE=(AT|GA)((AG|AAA)*) の構文木 TRE・(AT|GA)((AG|AAA)*)|*・A・TG|A・A・G・A

2005/11/8

括弧の深さ

オペレータ

1|2|AA
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

9

擬似コード

2005/11/8

Parse (p=p1p2…pm, last)
1 v ← θ;2 while plast≠$ do3
if plast∈Σ or plast=ε then /* normal character */4vr ← Create a node with plast;5
if v≠θthen v ← [・](v, vr);
6else v ← vr;
7last ← last + 1;/* union operator */8else if plast = ‘|’ then9(vr, last) ← Parse(p, last + 1);
10v ← [ | ](v, vr);/* star operator */11else if plast = ‘*’ then12v ← [ * ](v);13last ← last + 1;/* open parenthesis */14
else if plast = ‘( ’ then15(vr, last) ← Parse(p, last + 1);
16
last ← last + 1;
17if v≠θthen v ← [・](v, vr);
18
else v ← vr;/* close parenthesis */19
else if plast = ‘)’ then20
return (v, last);21
end of if
22 end of while
23 return (v, last);

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

10ThompsonのNFA構築法

K. Thompson. Regular expression search algorithm. Communications of the ACM, 11:419-422, 1968.

アイデア– 正規表現RE の構文木 TRE をpost-orderで巡回しながら、各ノードvを頂点とする部分木に対応する言語L(REv)を受理するオートマトン Th(v) を構築していく– Th(v)は、vの子供を頂点とする部分木に対するオートマトンどうしを、ε遷移で連結することで得られるのがポイントThompson NFAの性質– 状態数 < 2m、状態遷移の数 < 4m →O(m)– ε遷移を含む– ε遷移以外の遷移は必ず i番目から i+1番目に遷移する

例： 正規表現RE = (AT|GA)((AG|AAA)*)に対するThompson NFA
ε10ε
2005/11/84AG25TA3ε εε

789εε12εAA1310AG14ε11εAε1516ε176
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

11NFA構築アルゴリズム
構文木 TREに対して、post-orderでノードを探索しつつ、各ノードについて次のようにオートマトンを生成・連結する(i) ノードvが空語εの場合
I

ε(iv) ノードvが選択”|”の場合 → (vL| vR)Fεa

2005/11/8vL

FL

εF

εIRvR

FR

ε

F(iii) ノードvが連結”・”の場合→ (vL・vR)
ILvLI(ii) ノードvが文字aの場合
IILvR

FR(v) ノードvが繰り返し”*”の場合 → v*
εεIv

εε

F

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

12NFA構築アルゴリズムの動作
例： 正規表現RE=(AT|GA)((AG|AAA)*)の構文木 TRE
731|・A・6・218T4G

510A

例： 正規表現RE = (AT|GA)((AG|AAA)*)に対するThompson NFAε0ε
2005/11/84G25TA3ε εε7|1615・・A9G・11A

171381*89εε12εAA

1310AA

A12G

1414A

ε11εA

ε1516ε176
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

13

擬似コード
Thompson_recur (v)1 if v = “|”(vL, vR) or v = “・”(vL, vR) then2Th(vL) ← Thompson_recur(vL);
3Th(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);
2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

14GlushkovのNFA構築法

V-M. Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 16:1-53, 1961.

アイデア– 正規表現RE中の各文字a∈∑ に前から順に番号を振り、これをRE’とする（番号付きのアルファベットを∑’とする）
 例： RE = (AT|GA)((AG|AAA)*)→ RE’ = (A1T2|G3A4)((A5G6|A7A8A9)*)– 言語L(RE’)を受理するNFAを作り、番号を取り除いて最終的なNFAを得る
Glushkov NFAの性質– 状態数はちょうどm+1個、状態遷移の数はO(m2)– ε遷移を含まない– 任意のノードについて、そのノードに入ってくる遷移のラベルはすべて等しい
例： RE’ = (A1T2|G3A4)((A5G6|A7A8A9)*)に対するNFA
G3A7T2A4
A5A10

12

例： 最終的なGlushkov NFA0
2005/11/8A1T3A5G
23AA

45G664A5GA

7A7A5AA76AA

7A8A7AA

88A9AA59A9

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University15NFA構築アルゴリズム(1)

構築手順：– 正規表現RE中の各文字a∈∑ に前から順に番号を振り、これをRE’とする
Pos(RE’) = {1…m}、∑’：番号付けされたアルファベット– 構文木 TRE’ をpost-orderで巡回しながら、各ノードvを頂点とする部分木に対応する言語REv’について集合First(REv’)、Last(REv’)、関数Emptyv、および、RE’の位置xについての関数Follow(RE’, x)を計算する
NFAが開始される位置

First(RE’) = {x∈Pos(RE’) | ∃u∈∑’*, αxu∈L(RE’)}NFAの最終状態の位置
 Last(RE’) = {x∈Pos(RE’) | ∃u∈∑’*, uαx∈L(RE’)} Follow(RE’, x) = {y∈Pos(RE’) | ∃u, v∈∑’*, uαxαyv∈L(RE’)} 遷移関数のつながり
 EmptyRE : εがL(RE)に属するなら {ε}、そうでないならばφを返す関数
これは、次のようにして再帰的に計算できる
NFAの初期状態がEmptyε= {ε},終状態かどうか
Emptyα∈∑= φ,EmptyRE1|RE2= EmptyRE1 ∪ EmptyRE2,EmptyRE1・RE2 = EmptyRE1 ∩ EmptyRE2,EmptyRE*= {ε}.
– 上で得られた値をもとに、NFAを構築する
2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

16

NFA構築アルゴリズム(2)言語L(RE’)を受理する（Glushkov）NFA GL’= (S, ∑’, I, F,δ’)– S ：状態の集合. S = {0, 1, …, m}– ∑’：番号付けされた∑– I ：初期状態、I = 0– F ：最終状態
F = Last(RE’)∪(EmptyRE・{0}).
– δ’：以下で定義される遷移関数∀x∈ Pos(RE’), ∀y∈ Follow(RE’, x), δ’(x, αy) = y
初期状態からの遷移は次のとおり∀y∈ First(RE’), δ’(0, αy) = y

例： RE’ = (A1T2|G3A4)((A5G6|A7A8A9)*)に対するNFA
G30

2005/11/8

A11T2

23A4A5A7A545G6A56A7A77A88A9A59A7
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University17

擬似コード
Glushkov_variables (vRE, lpos)
1 if v = [ | ](vl,vr) or v = [・](vl,vr) then2lpos ← Glushkov_variables(vl, lpos);3lpos ← Glushkov_variables(vr, lpos);
4 else if v = [ * ](v*) then lpos ← Glushkov_variables(v*, lpos);
5 end of if
6 if v = (ε) then7First(v) ← φ, Last(v) ← φ, Emptyv ← {ε};8 else if v = (a), a∈Σ then9lpos ← lpos + 1;
10First(v) ← {lpos}, Last(v) ← {lpos}, Emptyv ← φ, Follow(lpos) ← φ;
11 else if v = [ | ](vl,vr) then
12First(v) ← First(vl)∪First(vr);
13Last(v) ← Last(vl)∪Last(vr);14
Emptyv ← Emptyvl∪Emptyvr;
15 else if v = [・](vl,vr) then
16First(v) ← First(vl)∪(Emptyvl・First(vr));
17
Last(v) ← (Emptyvr・Last(vl))∪Last(vr);18
Emptyv ← Emptyvl∩Emptyvr;
19
for x∈Last(vl) do Follow(x) ← Follow(x)∪First(vr);
トータルO(m3)時間
20 else if v = [ * ](v*) then
21First(v) ← First(v*), Last(v) ← Last(v*), Emptyv ← {ε};22for x∈Last(v*) do Follow(x) ← Follow(x)∪First(v*);O(m2)時間かかる
23 end of if
24 return lpos;
2005/11/8
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

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
12for i ∈ Follow(i) do Δ←Δ∪ {(i,αx, x)};
13 end of for
14 for x∈ Last(vRE)∪(EmptyvRE・{0}) do mark x as terminal;

2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

19

ちょっと、ひといき・・・

ここまでのまとめ– 正規表現： 有限オートマトンと言語を定義する能力が等しい– 正規表現の照合処理のながれ 構文木（parse tree）を構築してからNFAへ変換
 NFAをシミュレートしてテキストを走査– NFAの構築方法

 ThompsonのNFA→ 状態数 < 2m、状態遷移数 < 4m
 GlushkovのNFA → 状態数 = m+1、状態遷移数 O(m2)～トリビア～POSIX準拠の正規表現は正規表現？
現在、正規表現を処理するプログラムの多くはNFAの動作を「バックトラック」を使って実装している。「後方参照」は、大抵の場合この技法の上で実現されるが、明らかに「正規表現」の枠組みからは逸脱している。→ 例： (a+)b¥1
フンボルトペンギン （旭山動物園にて ’05.3.13）
2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

20

照合処理のながれ（再）NFAはO(mn)時間で模倣できる

Thompson法によるNFA構築
構文解析(Parsing)

出現位置の報告

NFA
決定性化

Glushkov法によるNFA構築

この変換にはO(2m)の時間・領域が必要

走査

構文木

テキスト

正規表現

テキスト走査DFA

実はDFAへ直接に変換する方法もある※A. V. Aho, R. Sethi, and J. D. Ullman. Compilers – Principles, Techniques andTools. Addison-Wesley, 1986. （邦訳：コンパイラ 原理・技法・ツール）を参照 （3.9節）
2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

21

NFAのシミュレーション手法
Thompson提案のNFAシミュレーション手法– 最も簡単な手法– O(m)の大きさのリストでactiveな状態を保持し、文字ごとのNFAの状態更新をO(m)で行う。
– 明らかにO(mn)時間かかる

等価なDFAに変換してシミュレートする– 古典的に用いられている手法– A. V. Aho, R. Sethi, and J. D. Ullman. Compilers – Principles, Techniques and Tools.
Addison-Wesley, 1986. （邦訳：コンパイラ 原理・技法・ツール）を参照– 前処理として変換する → O(2m)時間・領域かかる– テキストを走査する際、動的に構築する手法もある

ハイブリッドな手法– E. W. Myers. A four russians algorithm for regular expression pattern matching. Journalof the ACM, 39(2):430-448, 1992.
– NFAとDFAを組み合わせて効率をあげる手法– ThompsonのNFAをO(k)個のノードのモジュールに分割し、モジュール毎にDFA化する。各モジュール間の遷移はNFAとしてシミュレートする。

Bit-parallel手法による高速なNFAシミュレーション– ThompsonのNFAをシミュレート： S. Wu and U. Manber[1992]の手法– GlushkovのNFAをシミュレート： G. Navarro and M. Raffinot[1999]の手法、ほか

2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

22

等価なDFAに変換してシミュレートする
例： RE = (AT|GA)((AG|AAA)*)に対するGlushkov NFAから変換したDFA
02

TC

C,T

GT

A

G01
A

C,T

T

T

A

C018

A

G0157
GC,T
03

C,T
GA

A
04
GC,T036
GT

GCC
GA

019

AC0GA

C C
01457

TT

CTA01578

A01579A0189
GAGG

DFA Classical (N = (Q,∑, I, F,Δ), T = t1t2…tn)
1 Preprocessing:
2for σ∈∑ do Δ←Δ∪ (i, σ, I);3(Qd,∑, Id, Fd,δ) ← BuildDFA(N); /* NFA Nと等価なDFAを作成 */4 Searching:5s ← Id;
6for pos ∈ 1…n do
7
if s∈Fd then report an occurrence ending at pos – 1;
8s ← δ(s, tpos);9
end of for2005/11/8

情報知識ネットワーク特論 講義資料

23

Bit-parallel Thompson

北海道大学 Hokkaido University

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では、（ε遷移を除くと）i番目の状態の次はi+1番目→ Shift-And法に似たbit-parallel化ができる！
– ε遷移については、別途シミュレートする

大きさ 2L のマスクテーブルが必要 （LはNFAの状態数）– 前処理全体で O(2L + m|∑|) 時間かかる– Lが十分小さいときは O(n) 時間でテキストを走査できる

NFA GL=(Q={s0,…,s|Q|-1}, ∑, I = s0, F, Δ)について– NFAのマスクビット表現： Qn={0,…,|Q-1|}, In = 0|Q|-11, Fn = |sj∈F 0|Q|-1-j10j– 各マスクテーブルの定義：

2005/11/8



Bn[i,σ] = |(si,σ,sj)∈Δ 0|Q|-1-j10j

En[ i ] = |sj∈E(i) 0|Q|-1-j10j

Ed[D] = |i, i=0 OR D&0L-i-110i ≠ 0L En[ i ]B[σ] = |i∈0…m Bn[i, σ]（ここで、E(i)は状態siのε-closure）

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

24

擬似コード
BuildEps (N = (Qn,∑,In,Fn,Bn,En) )1 for σ∈∑ do
2B[σ] ← 0L;
3for 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
7for j∈0…2i – 1 do
8
Ed[2i + j] ← En[ i ] | Ed[ j ];9end 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 ];5for pos∈1…n do
6
if D & Fn≠ 0L then report an occurrence ending at pos–1;
7
D ← Ed[ (D << 1) & B[tpos] ];8end of for2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

25

Bit-parallel Glushkov

G. Navarro and M. Raffinot. Fast regular expression search. In Proc. of WAE99, LNCS1668, 199-213, 1999.

Glushkov NFAをbit-parallelでシミュレートする– Glushkov NFAでは、任意の状態について、そこに入る状態遷移のラベルがすべて等しいことに着目→ Shift-And法的なbit-parallelはできないが、状態遷移は Td[D]&B[σ]で計算可能– マスクテーブルは 2|Q| でよい （BPThompsonの場合は 2L）– 前処理全体で O(2m + m|∑|) 時間かかる– mが十分小さいときは O(n) 時間でテキストを走査できる– ほとんどの場合において、BPThompsonより効率が良い

NFA GL=(Q={s0,…,s|Q|-1}, ∑, I = s0, F, Δ)について– NFAのマスクビット表現： Qn={0,…,|Q-1|}, In = 0|Q|-11, Fn = |sj∈F 0|Q|-1-j10j– 各マスクテーブルの定義：

2005/11/8



Bn[i,σ] = |(si,σ,sj)∈Δ 0|Q|-1-j10j

B[σ] = |i∈0…m Bn[i, σ]

Td[D] = |(i,σ), D&0m-i10i ≠ 0m+1, σ∈∑ Bn[i,σ]
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

26

擬似コード
BuildTran (N = (Qn,∑,In,Fn,Bn,En) )1 for i∈0…m do A[ i ] ← 0m+1;
2 for σ∈∑ do B[σ] ← 0m+1;
3 for i∈0…m, σ∈∑ do
4
A[ i ] ← A[ i ] | Bn[I,σ];5B[σ] ← B[σ] | Bn[i,σ];
6 end of for7 Td[0] ← 0m+1;
8 for i∈0…m do
9for j∈0…2i – 1 do
10Td[2i + j] ← A[ i ] | Td[ j ];11
end of for
12 end of for
13 return (B, Ed);
BPGlushkov (N = (Qn,∑,In,Fn,Bn,En), T = t1t2…tn)
1 Preprocessing:/* initial self-loop */2for σ∈∑ do Bn[0,σ] ← Bn[0,σ] | 0m1;
3(B, Ed) ← BuildTran(N);4 Searching:/* 初期状態 */5
D ← 0m1;
6for pos∈1…n do
7
if D & Fn≠ 0m+1 then report an occurrence ending at pos–1;
8
D ← Td[D] & B[tpos];end of for2005/11/89
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

27

その他のトピックス


拡張正規表現について– 連結、選択、繰り返しに加えて、積（intersection）と否定（complementation）の演算を加えたもの。
￢(UNIX)∧(UNI(.)* | (.)*NIX)– 俗に言う（POSIX定義の）拡張正規表現とは意味が異なる
H. Yamamoto, An Automata-based Recognition Algorithm for Semi-extended
Regular Expressions, Proc. MFCS2000, LNCS1893, 699-708, 2000.
 O. Kupferman and S. Zuhovitzky, An Improved Algorithm for the Membership
Problem for Extended Regular Expressions, Proc. MFCS2002, LNCS2420, 446458, 2002.


高速化に関する研究– BNDMを用いたFiltration手法＋検査

2005/11/8

G. Navarro and M. Raffinot, New Techniques for Regular Expression Searching,Algorithmica, 41(2): 89-116, 2004.
※ この論文には、O(m2m) bits のマスクテーブルでGlushkov NFAをシミュレートする方法も併せて記されている
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

28

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



次回のテーマ– 圧縮テキスト上のパターン照合： 喜田の研究紹介 （本分野における90年代のトレンド！）

2005/11/8

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University29

付録

第一回目の講義で説明していなかった用語の定義について– ∑*の部分集合を形式言語（formal language）または単に言語という– 言語L1, L2∈∑* に対して、集合{ xy | x∈L1 かつ y∈L2 }をL1とL2の積（product）といい、L1・L2または単にL1L2と書く– 言語L⊆∑* に対して、
L0 = {ε}, Ln = Ln-1・L(n≧1)とする。また
L* = ∪n=0…∞ Lnとして、これをLの閉包（closure）という。またL+ = ∪n=1…∞ Ln とする

後方参照について– 講義の中で、「後方参照については、探してみたが、きちんとした定義がみあたらない」と述べたが、次の文献に記述があることが判明した

2005/11/8

Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity,
The MIT Press, Elsevier, 1990.
（邦訳）コンピュータ基礎理論ハンドブックⅠ：アルゴリズムと複雑さ，丸善，1994.
– 第５章2.3節 後退参照付き正規表現、および6.1節 後退参照付き正規表現の照合問
題– これによると、後方参照という考え自体は1964年に既に出現していたらしい– 正規表現どころか、文脈自由文法の枠組みをも超えている– その照合問題は、NP完全（NP-complete）であることが証明されている

情報知識ネットワーク特論 講義資料