2011/10/20

O(n^2)正規表現

Javaで、 /[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+/ という正規表現のマッチが 入力文字列長nに対してO(n^2)かかるのはエンジンがNFAのせいって話なんだけれど、 これNFA関係無くないかな。

メールアドレスの正規表現がめちゃめちゃ遅くなることがある件について - Mi manca qualche giovedi?

このコードは「空白の入っていない長い文字列」を作って、それにメールアドレスの正規表現をマッチさせてみるというものである。

このコードを実行すると、文字列の長さと、match 20 回にかかったミリ秒を出力する。

80 : 38 ms
400 : 59 ms
800 : 264 ms
4000 : 6650 ms
8000 : 26331 ms

おわかりのとおり、文字列長の二乗オーダーになっている。

どうしてこんなことになるのか？

サイボウズ・ラボユースで来てくれている、正規表現オタク(褒めてますｗ)の新屋さんによると、これは正規表現のエンジンが「NFAベースのバックトラック実装」を採用している場合に起こりうる問題で、件の正規表現の先頭部分 /[-_.0-9A-Za-z]+/ が文字列の任意の部分にマッチする可能性を保留したまま判定を進めることにより、N^2 のオーダーになるのだろうということ。

確かに、NFAのバックトラックにより試行回数がn^2やn^3のオーダーになるパターンはあるのだけれど、 この正規表現はそのパターンではない。

(A+)B

といった正規表現 (A, B はそれぞれ正規表現)で、 Aの先頭にマッチし得る文字の集合と、Bの先頭にマッチし得る文字の集合に 共通部分が無い場合、Bの前の式はバックトラックする必要がないのだ。なぜなら、

• Bの先頭にマッチする文字に出会ったら、そこからAの繰り返しになってる可能性はない。
• Bの先頭にマッチする文字列に出会わずに入力が終了してしまったら、バックトラックしてもマッチする可能性はない。

Gaucheのregexpはこのパターンを見つけてバックトラックを全くしないコードを生成するけれど、 たとえナイーブにNFAを実装したとしても、全てのバックトラックは直ちに失敗するため、 実行時間のオーダーはO(n)で変わらない (バックトラック用のメモリをO(n)で消費することになるが)。

では何故O(n)かかっているように見えるのかというと、それは元のJavaコードが、 入力文字列の「どこか」にあるマッチする部分を探すようになっているから。

• 入力の0文字目からregexがマッチするか調べる → 失敗
• 入力の1文字目からregexがマッチするか調べる → 失敗
• 入力の2文字目からregexがマッチするか調べる → 失敗
• …

とやっているので、個々のマッチング自体はO(n)なんだけど、 それを約n回繰り返して全体でO(n^2)になっている。 これはエンジンがNFAであるかDFAであるかに関わらない。 (この、入力に対する繰り返しも織り込み済みでFAを作るなら別だけど)。

(追記2011/10/21 00:56:10 UTC: あーでも、DFAの場合、このパターンの前に/.*?/ (non-greedyな任意文字へのマッチ) をつけてDFAを作れば入力の先頭からマッチかけるだけでO(n)でチェックできることになりそうだな。元ブログはそういう話をしていたのかも)

元記事ではPythonでもやってみて線形オーダになっているとあるが、 Pythonのregexエンジンもソースを見る限りはNFAのようだ。 ではなぜO(n)になっていたかというと、Pythonのmatchメソッドは「入力の先頭にマッチするかどうか」 しか調べない、とマニュアルにある。Javaのコードと同じようにするにはsearchメソッドを 使う必要があって、それだと確かにO(n^2)になる。(Python 2.6.5。もしかして3.xでは改善されてるかも。)

In [4]: s1 = 'abcdefgh' * 10
In [5]: s2 = 'abcdefgh' * 50
In [6]: s3 = 'abcdefgh' * 100
In [7]: s4 = 'abcdefgh' * 500
In [8]: s5 = 'abcdefgh' * 1000

In [9]: %timeit r1.match(s1)
1000000 loops, best of 3: 999 ns per loop
In [10]: %timeit r1.match(s2)
100000 loops, best of 3: 2.84 us per loop
In [11]: %timeit r1.match(s3)
100000 loops, best of 3: 5.18 us per loop
In [12]: %timeit r1.match(s4)
10000 loops, best of 3: 23.5 us per loop
In [13]: %timeit r1.match(s5)
10000 loops, best of 3: 46.4 us per loop

In [14]: %timeit r1.search(s1)
10000 loops, best of 3: 22.6 us per loop
In [15]: %timeit r1.search(s2)
1000 loops, best of 3: 477 us per loop
In [16]: %timeit r1.search(s3)
1000 loops, best of 3: 1.92 ms per loop
In [17]: %timeit r1.search(s4)
10 loops, best of 3: 46.5 ms per loop
In [18]: %timeit r1.search(s5)
10 loops, best of 3: 186 ms per loop

ちなみにGaucheでの計測例。gauche.time の time-this 手続きが使える (refj:time-this)。

(use gauche.time)
(use srfi-13)

(define rx1 #/[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+/)

(define (regex-test rx text runs)
  (print (string-length text)
         ":\t"
         (time-this runs (^[] (regexp-replace-all rx text " ")))))

(define (repeat s c) (string-concatenate (make-list c s)))

(print rx1)
(regex-test rx1 (repeat "abcdefgh" 10) 20)
(regex-test rx1 (repeat "abcdefgh" 50) 20)
(regex-test rx1 (repeat "abcdefgh" 100) 20)
(regex-test rx1 (repeat "abcdefgh" 500) 20)
(regex-test rx1 (repeat "abcdefgh" 1000) 20)

#|
#/[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+/
80:     #<time-result 20 times/  0.001 real/  0.000 user/  0.000 sys>
400:    #<time-result 20 times/  0.010 real/  0.000 user/  0.000 sys>
800:    #<time-result 20 times/  0.037 real/  0.030 user/  0.000 sys>
4000:   #<time-result 20 times/  0.890 real/  0.890 user/  0.000 sys>
8000:   #<time-result 20 times/  3.513 real/  3.510 user/  0.000 sys>
|#

★ ★ ★

では、NFAでもDFAでもO(n^2)は避けられないのか、というとこの正規表現については 高速化の可能性はある。

まずこのパターンは、"@"が入っていない文字列にはマッチしようがない。 したがってあらかじめ"@"を入力文字列中から探して、見つからなければ マッチ無しと断定できるので、真面目に入力をひとつづつずらしながらマッチを試みる 必要はない。一般的には、パターン中に「必ずマッチしなければならない部分文字列」 がある場合に、それを取り出してBoyer-Mooreなどの高速な部分文字列検索を 行うことで、マッチしない場合を高速に除外できる。 これをやってるエンジンを見たことはあるんだけど、Perlだったかな。

Gaucheのregexpでも一応そのためのフィールドは用意してあるんだけど、 まだ実装してない。そういう部分文字列が取り出せるケースが現実的にどのくらいあるか わからないのと、入力によってはプレスキャンするオーバヘッドが逆に性能を 低下させる恐れもあるので。必要を感じたら入れるかも。

CL-PPCREやAllegro Common Lispのregexpではこの変形として、 「パターンが固定文字列で終わる場合」について、その固定文字列をプレスキャンしている。 これだと、その固定文字列が見つからなければもちろん直ちにマッチ無しと断定できるだけではなく、 固定文字列が見つかった場合も、「一番右の見つかった固定文字列まで入力を考慮すれば良い」 と言えるので、見る必要のある入力文字列の範囲を絞れることが多いからだ。 これは現実のベンチマークで結構効果があった。ただ、今回のケースは パターンが固定文字列で終わってないので、この手法の対象外になる。

もう一つ考えられる手法。/A+B/ のようなパターンに対して ある入力がマッチするならば、その入力の前に/A/にマッチする 任意の文字列を好きなだけ付け加えたものにも、元のパターンはマッチする。対偶を取れば、 もし入力の先頭から調べて/A+B/がマッチしなかったら、 その入力から/A/にマッチするプリフィクスを好きなだけ取り除いた 入力文字列にもマッチしないはずである。今回はAの部分が /[-_.0-9A-Za-z]/なので、最初に先頭からマッチかけて失敗したなら、 入力文字列の先頭から[-_.0-9A-Za-z]なる文字が出てくる限りは 再マッチを試みる必要がない。abcdefghの繰り返し入力に対しては 結局先頭から一度だけマッチを試みて失敗したらそれで失敗と断定できることになる。

★ ★ ★

ところで、この記事を書きながら、ついでにAllegro Common Lispの ベンチマークも取ってみようと思ってやってみたら、謎な結果が。 (繰り返し回数、文字列長は上のベンチマークよりかなり増やしてある)。

cl-user> (require :regexp2)
; Fast loading /home/shiro/src/acl82.64/code/regexp2.fasl
;   Fast loading from bundle code/regexp2-s.fasl.
;   Fast loading /home/shiro/src/acl82.64/code/yacc.fasl
t
cl-user> (defun regexp-test (n)
           (let ((rx (compile-re "[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+"))
                 (s (apply #'concatenate 'string (make-list n :initial-element "abcdefgh"))))
             (time (dotimes (i 1000) (match-re rx s)))))
regexp-test
cl-user> (compile 'regexp-test)
regexp-test
nil
nil
cl-user> (regexp-test 100)
; cpu time (non-gc) 0.000000 sec user, 0.000000 sec system
; cpu time (gc)     0.000000 sec user, 0.000000 sec system
; cpu time (total)  0.000000 sec user, 0.000000 sec system
; real time  0.006873 sec
; space allocation:
;  0 cons cells, 2,080 other bytes, 0 static bytes
nil
cl-user> (regexp-test 1000)
; cpu time (non-gc) 0.060000 sec user, 0.000000 sec system
; cpu time (gc)     0.000000 sec user, 0.000000 sec system
; cpu time (total)  0.060000 sec user, 0.000000 sec system
; real time  0.066369 sec
; space allocation:
;  0 cons cells, 0 other bytes, 0 static bytes
nil
cl-user> (regexp-test 10000)
; cpu time (non-gc) 0.660000 sec user, 0.000000 sec system
; cpu time (gc)     0.000000 sec user, 0.000000 sec system
; cpu time (total)  0.660000 sec user, 0.000000 sec system
; real time  0.661164 sec
; space allocation:
;  0 cons cells, 2,080 other bytes, 0 static bytes
nil
cl-user> (regexp-test 100000)
; cpu time (non-gc) 6.610000 sec user, 0.000000 sec system
; cpu time (gc)     0.000000 sec user, 0.000000 sec system
; cpu time (total)  6.610000 sec user, 0.000000 sec system
; real time  6.610055 sec
; space allocation:
;  0 cons cells, 2,080 other bytes, 0 static bytes
nil

あれ、O(n)だなあ。

おかしい。

Allegroのregexpは、マッチ失敗したら入力をひとつ進めて再試行するので、 O(n^2)になるはずなんだ (先頭の文字によってはスキップすることはあるけど、 今回の入力とパターンでは当たらないはず)。 入力が小さすぎてO(n)の効果が見えないだけってことも無さそうだしなあ。

すんごく気になるんだが、追求してる暇が無いのでとりあえずメモだけ。

(追記2011/10/21 11:30:50 UTC): 多分わかった。Allegroの開発版のバイナリについてる regexp2がおかしい。リリース版で試すとちゃんとO(n^2)になってる。 両者の、コンパイル後の正規表現のdisassembleを比較したら1インストラクション だけ違ってた。前者では初期化されるべきレジスタが初期化されてない。 ソースからビルドするとどちらも正常に動くので、開発版のビルド時の 問題ではないかな。上のベンチマークはやっぱりtoo good to be trueだった。

(追記2011/10/21 18:47:24 UTC): 結局、開発版にregexp2のパッチが反映されてなかったというオチだった。ブクマに反応:

MagnesiumRibbon: 手元のACL8.1/8.2 (共にx86-64) で試したら、8.1だとO(n)だった…どういうこと？/ユーザレベルだと、単に8.2になったら正規表現が遅くなったように見えるんですが…

8.1だとコンパイラの最適化バグがありまして、そのためにO(n)になってるように見えたんです。ちょっと正規表現を変えると出なくなるので、再現条件は微妙。8.2のregexp2パッチ001でfixされてます。

Tags: Programming, Gauche, Lisp, Python, Java