正規表現の最近のブログ記事

　先日、西麻布で飲んでいたとき、ReplacedDA の話が出た。お懐しい。eimon 氏による ReplaceDA が Palm OS 5 で動かないという話を受け、Replace'd'DA としてリメイクしたものだった。この１文字違っているという事実は、使って下さる人達でも知らないことが多い。洒落のつもりだったのだが、まぁそれはそれとして。

　正規表現エンジンにおける一般的な最適化のひとつに、先頭文字識別がある。これは、その正規表現がマッチに成功するために必要な最初の文字を認識するものだ。例えば、foo|bar という正規表現を使用してマッチを行なう場合、マッチ個所は必ず f または b で始まる必要がある。逆に言えば、f または b で始まる個所だけでマッチの確認をすれば良いことになる。つまり、それが先頭文字識別だ。

　しかし、先頭の文字ならばすぐにマッチ失敗を認識できるのだからやらなくてもいいのでは、と考える人もいるかもしれない。だがそんなことはない。たとえば、以下の正規表現を見てほしい。

　[0-9]?(abc|def)*ghi

　わざとらしい例で申し訳ないが、この場合、先頭の文字とのマッチが試されうる部分表現は全体に散らばっている。具体的には 0 ? 9, a, d, g の各文字が先頭文字として有効である。このような状況では、先頭文字識別は非常に大きな力を発揮することがわかるだろう。

　とはいえ、常に先頭文字識別が使えるとは限らない。最初の文字がなんでもいいような正規表現 （ . で始まるやつとか ） では先頭文字識別などやりようがないからだ。しかし、それが可能ならばやった方がいいことは間違いない。

　で、ここから手前味噌な話になってしまうのだが、ここ数年なんとかリリースにこぎつけようとしている陰郎の自作エンジンでは、かなり込み入った正規表現でも先頭文字候補の導出ができるようになっている（ 先頭文字が不定でない限りは ）。それには自分自身満足しているのだが、１年半ほど前に特殊なケースでメモリを浪費しすぎることに気がついていた。どんなケースかというと、たとえば [\x01-\x{FFFF}] で始まるような正規表現だ。陰郎のエンジンでは 16 ビットエンコーディングまで対象を広げているから、こんな文字クラスが定義できてしまう。文字クラスは適切に実装されているが、先頭文字識別機構はこれを 「 文字のリスト 」 に展開しようとする．．．というわけだ。

　で、今週に入ってからこれを修正していたのだ。基本的には文字クラスの実装と同じように、範囲は範囲として保持することで空間を浪費しないようにしている。まぁ [\x01-\x{FFFF}] みたいなのはまずありえないとは思うが、それでもマズいことになりそうな穴は小さくてもふさいでおかなければならない。

　以前にも書いたとおり、最適化は Version 0.7 には含まれない機能だ。そして、先頭文字識別もまたフライングして実装してしまった最適化のひとつだ。しかし、実装してしまったからにはバグっぽい状態で放り出すわけにはいかない．．．などといってまた手をつけたりしているのだな。そして、「 最適化をオフにする 」 オプション -nooptimize も実装した。ひょっとしたら以前書いたとおり、Version 0.7 では問答無用で最適化をオフにしてしまうかもしれない。

　この日記のカテゴリに 「 正規表現 」 を追加した．．．まぁ自分の正規表現エンジンはいまだに蒸気ウェアなワケだけれども、なんとか近いうちに Version 0.7 alpha を放り出してしまいたい。そうしないと Palmware の作業に取り掛かれないからだ。で、正規表現を知らない人にはつまらないエントリになってしまうのだけれども、今後正規表現エンジンの実装に絡む話題が時々登場することになる．．．

　今回はその記念すべき１回目 ── といっても MovableType 移行前は散々書いてたな ── になるわけだが、いきなりというかなんというか、「 幾何級数マッチ 」 にまつわるお話し。

　幾何級数マッチとは、(=*)+X などという ( いささかマズい ) 正規表現に対して ============ などといった文字列をマッチさせた場合に、「 マッチが存在しない 」 ことをエンジンが検出するのに非常に時間がかかるという状況だ。=* という部分表現がさらに + によって反復されるため、エンジンが試さなければならない組み合わせが幾何級数的に増大するために発生する．．．と。

　陰郎が自分のエンジンで試した限りでは、= の数が１つ増えただけでマッチ失敗に至る時間が２倍になる。= が 30 個並んだだけで、上記の正規表現とのマッチには数十秒かかったのだ （ もちろん環境にもよる ）。

　で、２年近く前にこの調査に使用したテストスクリプトを発見したので、久しぶりに試して見たのだ。それ、どん．．．あれ、一瞬で終わった。おかしいな。PC のスペックが上がってるからか？　マッチ対象の文字列を長くして、どん．．．あれ、やっぱり一瞬で終わる。おかしいな。なんかバグってるのかな．．．？

　調べて見た結果、「 必須文字列認識 」 という最適化が動作しているせいだということがわかった。これは、正規表現文字列を 「 コンパイル 」 するときに、マッチに必要な部分文字列を認識し、それがマッチ対象文字列に含まれていなければエンジンを駆動するまでもなくマッチ失敗を報告するというものだ。先の例で言えば、(=*)+X という正規表現とのマッチが成功するためにはマッチ対象文字列に X が含まれていなければならない。陰郎のエンジンはこれを認識し、====== のような文字列とのマッチでその切り札を使用した．．．というわけだ。

　当然、この最適化は 「 幾何級数マッチキラー 」 にはならない。必須文字列認識が動作できないような正規表現文字列では結局エンジンを吹かすしかないからだ。実際、先の正規表現を (=*)+[XY] としただけで幾何級数マッチは再現した。この場合、X という部分が文字クラス [XY] に変更されたため、（少なくとも）必須文字列認識は動作しなくなる．．．

　しかし、最適化は Version 0.7 には含まれない機能のはず。なんでそれが実装されているかというと．．．陰郎がフライングしたからに決まっているんだな。それもこれもかれこれ１年以上も前の話。これに関連して思い出したのは、「 最適化をオフにする 」 というオプションを実装しなければならないということだ。できればそれは早めに実装して、Version 0.7 では問答無用で最適化をオフにしたほうがいいのかもしれない。