標準モジュールreとのベンチマーク
今回作った正規表現エンジンは、速度の最適化を何もしていませんし、Pythonで書かれているために動作速度は非常に遅いです。しかし、特殊なシチュエーション（ただし実用的ではない）においては、標準モジュールであるreよりも高速に動作します。
まず、ごく普通の正規表現のマッチ速度を比べてみましょう。"(f|F)(o|O)(o|O)"と言う正規表現に、"FoO"と言う文字列をマッチさせる時の速度を、reとdfaregで比べてみます。計測には、Pythonに標準でバンドルされているtimeitモジュールを使いました。
>>> from timeit import Timer >>> import dfareg >>> import re >>> reg = dfareg.compile(ur"(f|F)(o|O)(o|O)") >>> Timer(setup='from __main__ import reg', stmt='reg.matches(ur"FoO")').timeit(number=1000) 0.12528085708618164 >>> reg = re.compile(ur"^(f|F)(o|O)(o|O)$") >>> Timer(setup='from __main__ import reg', stmt='reg.search(ur"FoO")').timeit(number=1000) 0.0014719963073730469
reモジュールのsearchは部分一致してしまうので、正規表現の先頭と末尾に「^～$」をつけていることに注意して下さい。
それぞれ1,000回ずつマッチングを実行していますが、reモジュールは1ミリ秒で処理が終わっているのに対し、dfaregは125ミリ秒かかっています。標準モジュールよりも100倍以上も遅く、まったく使い物にならないと言うことが分かると思います。
自作した正規表現エンジンが遅い理由の一つに、DFAの遷移関数が重いと言うことが上げられます。この遷移関数はNFAの遷移関数をラップしただけなので、実際はNFA上で遷移を行っています。DFAの遷移関数は、本来は遷移先を一つ返すだけなので非常に単純で高速なはずです。
そこで、この高速性をとりもどすためにmemoizeデコレータを実装し、nfa2dfa関数内で使ってみます。memoizeデコレータは、関数の計算結果をキャッシュし、2度目以降の呼び出しを高速化する機能を持ちます。
def memoize(func):
cache = dict()
def memoized_func(*args):
if args not in cache:
res = func(*args)
cache[args] = res
return cache[args]
return memoized_func
これをnfa2dfaで利用します。なお、サンプルコードでは@memoizeはコメントにしてありますので、試したい場合はこの部分を有効にして下さい。
def nfa2dfa(nfa):
@memoize
def transition(set_, alpha):
ret = set()
for elem in set_:
ret |= nfa.transition(elem, alpha)
return nfa.epsilon_expand( frozenset(ret) )
return DeterministicFiniteAutomaton(
transition,
nfa.epsilon_expand( frozenset([ nfa.start ]) ),
NonDisjointSets(nfa.accepts)
)
ベンチマークの結果は以下のようになります。
>>> reg = dfareg.compile(ur"(f|F)(o|O)(o|O)") >>> Timer(setup='from __main__ import reg', stmt='reg.matches(ur"FoO")').timeit(number=1000) 0.11726808547973633
>>> reg = dfareg.compile(ur"(f|F)(o|O)(o|O)") >>> Timer(setup='from __main__ import reg', stmt='reg.matches(ur"FoO")').timeit(number=1000) 0.014580965042114258
memoizeによって約8倍速くなりました。
さて、次は非常に特殊な正規表現をマッチングさせてみましょう。"X*X*X*X*X*X*X*X*X*X*XXXXXXXXXX"と言う、X*を10個とXを10個並べた正規表現を用意します。この正規表現は、10個以上のXからなる文字列に対してマッチします。これに対して、"XXXXXXXXXX"と言うXを10個並べた文字列をマッチさせてみましょう。
>>> reg = dfareg.compile(ur"X*X*X*X*X*X*X*X*X*X*XXXXXXXXXX") >>> Timer(setup='from __main__ import reg', stmt='reg.matches(ur"XXXXXXXXXX")').timeit(number=1000) 2.216724157333374 >>> reg = re.compile(ur"^X*X*X*X*X*X*X*X*X*X*XXXXXXXXXX$") >>> Timer(setup='from __main__ import reg', stmt='reg.search(ur"XXXXXXXXXX")').timeit(number=1000) 16.579116106033325 >>>
さきほどと同じく1,000回マッチングさせていますが、今度はreモジュールがが17秒なのに対して、dfaregは2秒で終わっています。pure Pythonで最適化も一切していないdfaregモジュールが、reモジュールより8倍速い計算です。どうしてこのようなことが起こるのでしょう？
NFAエンジン
この速度の違いは、DFAエンジンとNFAエンジンの違いによるものです。第1回で述べた通り、今回の連載で作成した正規表現エンジンは、DFAエンジンと呼ばれるタイプの物でした。一方で、PythonやPerl、Java、Rubyなどで広く利用されている正規表現エンジンは、NFAエンジンと呼ばれるタイプです。
先ほどのベンチマークでわかった通り、NFAエンジンはある種の正規表現に対して極端な性能劣化を示します。ただし、先ほどの正規表現は"XXXXXXXXXXX*"と書き直すことができ、この正規表現に対しては速度劣化が起きません。このように、NFAエンジンでは書き方によってマッチングの速度が大きく変わってしまうため、パフォーマンス悪化を起こさないためにはある程度の知識が必要です。これは、RDBMSにおいて、SQLやインデクスに十分な知識がないと速度劣化を起こしてしまうのと似ています。さらに、正規表現を自動生成するようなコードがある場合は、意図せずこのような正規表現が生成される可能性があるので十分に注意が必要です。なお、速度劣化を起こさない正規表現の書き方に関しては、『詳説 正規表現』（Jeffrey E.F. Friedl 著）が大変参考になります。
さてそれでは、このような特徴のあるNFAエンジンは、いったいどのように実装されているのでしょうか？ 連載の締めくくりとして、NFAエンジンの仕組みを簡単に説明しておきます。
NFAエンジン実装の祖先
Regular Expression Matching Can Be Simple And Fastによると、Henry Spencerさんが書いたライブラリがNFAエンジンの実装として広まった、と解説されています。この正規表現エンジンを動かし、NFAエンジンがどのように動作するのかを見てみます。
UNIX系のOSをお持ちの方であれば、実際に動作させることができます。Henry Spencerさんのサイトにて公開されている、regexp.old.tar.Zをダウンロードし、以下のようにmakeして下さい。
% mkdir regexp % cd regexp % wget http://arglist.com/regex/regexp.old.tar.Z % tar zxvf regexp.old.tar.Z % vi Makefile # デバッグしたいので、以下のように修正 # TEST=-I. → TEST=-I. -DDEBUG % make
実行にはtryコマンドを使います。第1引数に正規表現、第2引数に文字列を渡します。DEBUGモードでコンパイルしているのでデバッグ情報が表示され、出力の最後にマッチ結果が0か1で表示されます。
% ./try 'p(erl|hp)' 'php' 1:BRANCH(34) 4:EXACTLY(9)p 9:OPEN1(12) 12:BRANCH(22) 15:EXACTLY(31)erl 22:BRANCH(31) 25:EXACTLY(31)hp 31:CLOSE1(34) 34:END(0) start `p' 1 \1
