NFA->DFA変換
NFAエンジンは、最悪の場合はバックトラックが発生しまくって性能が著しく劣化するというのはよく書かれているけれども、それはNFAを深さ優先探索で実行するからで、NFAの問題と言うより、NFAの実装の問題。うまくDFAを生成しながら実行していけば、入力長の線形時間のオーダーで安定して動作するNFAの実装もありえる。とかいうことを思いついたけど、調べてみると、それはThompson NFAという古からよく知られた技法だったっぽい(dragon bookとかに書いてあるらしい)
誰でも考え付きそうなものではあるけど、
Regular Expression Matching Can Be Simple And Fast
http://swtch.com/~rsc/regexp/regexp1.html
なんかには、Thompson NFAは簡単で速いのに、メジャーな言語の正規表現が軒並み(ある種のケースでは)遅いとあるし、折角なので、Thompson NFAに辿り着いた思考プロセスを書き残しておく。あと、Russ Coxは、Cで実装を書いてるけど、もうちょっと高級な言語で書いた方が本質は見えやすくなると思う
非決定的なパターンマッチングがあれば、NFAを書くのもDFAを書くのも大差ない。例えば以下はCurryで適当なNFAを書いた例
data Symbol = A | B | C data State = S1 | S2 | S3 | S4 nfa :: State -> Symbol ->State nfa S1 A = (S2 ? S1) nfa S2 A = S2 nfa S2 B = (S3 ? S2 ? S4) nfa S2 C = S2 nfa S3 A = S1 nfa S4 A = S1
#Curryのインストールは面倒くさいけど、以下にWebインターフェースがある
http://www-ps.informatik.uni-kiel.de/~mh/pakcs/curryinput_c2p.cgi
(a ? b)は"aでもbでもよい"という非決定性を表す記法。例えば、foldl nfa S1 [A,B,A,A]を定義に従って簡約していくと
foldl nfa S1 [A,B,A,A] = foldl nfa (nfa S1 A) [B,A,A] = foldl nfa (S2 ? S1) [B,A,A] = foldl nfa ((nfa S2 B) ? (nfa S1 B)) [A,A] = foldl nfa (S3 ? S2 ? S4) [A,A] = foldl nfa (S1 ? S2 ? S1) [A] = nfa (S1 ? S2 ? S1) A = (S2 ? S1 ? S2 ? S2 ? S1)
のようになるので、普通にfoldl nfa S1 [A,B,A,A]を実行すると、とりあえずS2が返ってくるはず。全部の結果を得たかったら、findall (\x -> foldl nfa S1 [A,B,A,A] =:= x)とか
(S2 ? S1)のような状態を考えるのは、正規表現の教科書に書いてあるNFA->DFA変換でやってることでもある。nfa (S2 ? S1) Bなんかを、毎回展開して( (nfa S2 B) ? (nfa S1 B) )とかして計算していくと、同じ部分を何度も読むことになって、効率がよくないけれども、(S2 ? S1)それ自体一個のオブジェクトのように取り扱うことができるなら、実行時に一回目だけ定義通り計算してメモ化するとかすれば、バックトラックのないDFAのように動作するようになる。というのが、Thompson NFA。DFAとThompson NFAの違いは、(S2 ? S1)のような状態に対する遷移ルールを実行前に計算するか実行中に計算するかの違いしかない
#非決定性はリストと違って、重複は無視できるし、順序も関係ないので、(S1 ? S2)と(S2 ? S1)と(S1 ? S2 ? S2)は同じものであるべき。おかげで、合成されたDFAの状態数は、最大でも2^N(Nは元のNFAの状態数)で有限個に収まる。なのだけど、Curryの場合は、(S1 ? S2)と(S2 ? S1)と(S1 ? S2 ? S2)はfindallした時に、それぞれ違う結果を返すので同じとは思えない。ので、ちょっとまずい
残念ながら、Curryでは(S2 ? S1)をそのまま扱うということができないんで、以下はpythonに逃げる。上にCurryで書いたNFAと同じものをpythonで書いたら以下のような感じだと思う。nfa関数の方は本質的に同じであるけれども、foldlに相当するものが、reducexとreducezの2種類あって(xとzに特に意味はない)、それぞれ深さ優先探索するNFAと、Thompson NFAに対応する。ここ10年くらいで、コルーチン/ジェネレータのような機能を備えた言語も増えてきたので、そのへんの言語なら同じように書けるはず
#generator version of reduce/foldl
#再帰限界については気にしない
#DFS or naive NFA
def reducex(g , init , ls):
if len(ls)==0:
yield init
else:
for it in g(init , ls[0]):
for ret in reducex(g , it , ls[1:]):
yield ret
#reduce/foldl for Thompson NFA
def reducez(g , init , ls):
def memoize(f):
__memo__ = {}
def __f__(*args):
if not args in __memo__:
__memo__[args] = apply(f,args)
return __memo__[args]
return __f__
@memoize
def next(states , s):
ret = set([])
for st in states:
for it in g(st,s):
ret.add(it)
return tuple(ret) #set型はhashableでないのでtupleで持つ
__state__ = (init,)
for sym in ls:
__state__ = next(__state__ , sym)
for st in __state__:
yield st
#面倒なので
#symbolは文字"a"/"b"/"c"のどれか
#stateは、1,2,3,4とする
def nfa(state,symbol):
if state==1 and symbol=="a":
yield 2;yield 1
elif state==2 and symbol=="a":
yield 2
elif state==2 and symbol=="b":
yield 3;yield 2;yield 4
elif state==2 and symbol=="c":
yield 2
elif state>=3 and symbol=="a":
yield 1
#テスト
if __name__=="__main__":
def genstring(n):
def __aux__(n):
if n==0:
yield []
else:
for it in __aux__(n-1):
for c in ["a","b","c","d","e"]:
it.append(c)
yield it
it.pop()
for ls in __aux__(n):
yield ("".join(ls))
for s in genstring(6):
assert( set(reducex(nfa , 1 ,s)) == set(reducez(nfa , 1 , s)) ),("test failed at:%s" % s)
print("all test passed")
しかし、こういう最適化を、人間が何も分かってなくても処理系が全自動で空気読んでやってくれる世界というのは、無理ゲーという気がしなくもない。
あと、正規表現->NFAの変換とか受理状態の扱いとかは、まあ、どうやっても難しくない
class Counter:
def __init__(self):
self.count = 0
def __call__(self):
self.count += 1
return (self.count)
gensym = Counter()
#固定文字列を受理するオートマトン
#(nfaジェネレータ、開始状態、開始状態が受理状態でもあるかどうか)を返す
def literal(s):
__states__ = [gensym() for c in s]
__states__.append(gensym())
def __nfa__(state , symbol):
try:
idx = __states__.index(state)
if symbol==s[idx]:
yield(__states__[idx+1] , len(s)==idx+1)
except:
pass
return (__nfa__ , __states__[0] , len(s)==0)
def option(r):
def __nfa__(state , symbol):
for it in r[0](state,symbol):yield it
return (__nfa__, r[1] , True)
def iterate(r):
def __nfa__(state , symbol):
for (st,cont) in r[0](state , symbol):
if cont:
yield r[1],True
else:
yield st,False
return (__nfa__, r[1], True)
def either(r1 , r2):
__states__ = [gensym()]
def __nfa__(state , symbol):
if state==__states__[0]:
for it in r1[0](r1[1] , symbol):yield it
for it in r2[0](r2[1] , symbol):yield it
else:
for it in r1[0](state , symbol):yield it
for it in r2[0](state , symbol):yield it
return (__nfa__ , __states__[0] , r1[2] or r2[2])
def sequence(*args):
def __nfa__(state , symbol):
for n,r in enumerate(args):
for st,cont in r[0](state,symbol):
if cont and n!=len(args)-1:
yield args[n+1][1],args[n+1][2]
else:
yield st,cont
if len(args)>1:
return (__nfa__ , args[0][1] , all([r[2] for r in args]))
#正規表現に(先頭から)マッチした残りの部分を返す
#greedyではなく、可能な全ての候補をジェネレータで返す
def deriv(nfa , s):
def reducex(g , init , s):
if len(s)>0:
for st,cont in g(init , s[0]):
if cont:
yield s[1:]
for ret in reducex(g , st , s[1:]):
yield ret
def reducez(g , init , s):
__state__ = (init,)
__memo__ = dict()
__accept__ = dict()
for n,sym in enumerate(s):
if not __memo__.has_key((__state__ , sym)):
next = set([])
acc = False
for st in __state__:
for nextst,cont in g(st,sym):
next.add( nextst )
acc = acc or cont
if len(next)==0:break
__memo__[ (__state__ , sym) ] = tuple(next)
__accept__[ tuple(next) ] = acc
__state__ = __memo__[ (__state__ , sym) ]
if __accept__[__state__]:
yield s[n+1:]
if nfa[2]:yield s
for it in reducez(nfa[0] , nfa[1] , s):
yield it
if __name__=="__main__":
#"(aa|bb?)*"
reg = iterate(either(sequence(literal("a"),literal("a")) , option(literal("bb"))))
assert(list(deriv(reg , "aabbaaaabbc")) == ['aabbaaaabbc', 'bbaaaabbc', 'aaaabbc', 'aabbc', 'bbc' , 'c'])
assert(list(deriv(reg , "ssab"))==['ssab'])
