2011/10/24

これどうやってたんだっけな (正規表現・続々)

http://twitter.com/k_takata/status/128592744414318592

http://swtch.com/~rsc/regexp/regexp1.html ではバックトラックNFAでの処理が指数関数的に増える例として、/(?:a?){n}a{n}/ が挙げられているが、鬼車だとそうはならないようだ。n=40でも一瞬で終わる。どの最適化が効いているのだろう。

Gaucheでも確かに指数時間になる。鬼車すげえ。と思ったら、Allegro CLでも一瞬で終わった。あれ? Allegro CLで実装してGaucheでは入れてなかったアルゴリズム的な最適化って何があったっけな。

確かにGaucheの{n,m}の実装は手抜きで、すんごくナイーブなスタックマシン上のバックトラックのコードを生成する。Allegro CLの方は一種のレジスタマシンになってて、しかも与えられた正規表現に最適化されたレジスタマシンを正規表現コンパイル時に生成するようになってるので、定数係数で差が出るのは当然なんだが、アルゴリズムの複雑性は変わらないはずなんだけどな (バックトラックの部分にはスタックを使ってるし)。

またバグのせいで速くなってるなんてことじゃなけりゃいいんだが…いろいろ正規表現を変えて試してみたが、ちゃんと最長一致で結果が出てるので、動作自体は正しいように見える。むむむ…

(追記:2011/10/25 12:54:54 UTC): あ、わかった。思い出した。Allegro CLでは、「繰り返しの中身が空文字列とマッチする可能性がある場合」について特別扱いしてた。

空文字列をεと書くと、 /(?:a?){3}a{3}/ =~ "aaa" は素直なNFAだと、前半部分の繰り返しで a-a-a, a-a-ε, a-ε-a, a-ε-ε, ε-a-a, ε-a-ε, ε-ε-a, ε-ε-ε という全ての組み合わせを試すことになる。

けれど a-a-ε がマッチしなかったら、a-ε-a も ε-a-a も 当然マッチしない。なのでAllegro CLでは a-a-a, a-a-ε, a-ε-ε, ε-ε-ε しか試さない。 これで O(2^n) のパターンが O(n) になる。

したがって、/(?:aa?){n}a{n}/ というパターンにするとこの最適化が効かず、指数時間かかることになる。n=25を過ぎたあたりから急速に重くなる。 鬼車も同じパターンだったので (ruby 1.9.2p290で確認)、多分同じ最適化をやってるんじゃないかと推測。

Tags: Programming, Gauche, Lisp