« 筋弛緩の夜 | メイン | 久方振りに Perl をイジって »
2006年02月10日
幾何級数マッチと必須文字列認識
この日記のカテゴリに 「 正規表現 」 を追加した．．．まぁ自分の正規表現エンジンはいまだに蒸気ウェアなワケだけれども、なんとか近いうちに Version 0.7 alpha を放り出してしまいたい。そうしないと Palmware の作業に取り掛かれないからだ。で、正規表現を知らない人にはつまらないエントリになってしまうのだけれども、今後正規表現エンジンの実装に絡む話題が時々登場することになる．．．
今回はその記念すべき１回目 ── といっても MovableType 移行前は散々書いてたな ── になるわけだが、いきなりというかなんというか、「 幾何級数マッチ 」 にまつわるお話し。
幾何級数マッチとは、(=*)+X などという ( いささかマズい ) 正規表現に対して ============ などといった文字列をマッチさせた場合に、「 マッチが存在しない 」 ことをエンジンが検出するのに非常に時間がかかるという状況だ。=* という部分表現がさらに + によって反復されるため、エンジンが試さなければならない組み合わせが幾何級数的に増大するために発生する．．．と。
陰郎が自分のエンジンで試した限りでは、= の数が１つ増えただけでマッチ失敗に至る時間が２倍になる。= が 30 個並んだだけで、上記の正規表現とのマッチには数十秒かかったのだ （ もちろん環境にもよる ）。
で、２年近く前にこの調査に使用したテストスクリプトを発見したので、久しぶりに試して見たのだ。それ、どん．．．あれ、一瞬で終わった。おかしいな。PC のスペックが上がってるからか？ マッチ対象の文字列を長くして、どん．．．あれ、やっぱり一瞬で終わる。おかしいな。なんかバグってるのかな．．．？
調べて見た結果、「 必須文字列認識 」 という最適化が動作しているせいだということがわかった。これは、正規表現文字列を 「 コンパイル 」 するときに、マッチに必要な部分文字列を認識し、それがマッチ対象文字列に含まれていなければエンジンを駆動するまでもなくマッチ失敗を報告するというものだ。先の例で言えば、(=*)+X という正規表現とのマッチが成功するためにはマッチ対象文字列に X が含まれていなければならない。陰郎のエンジンはこれを認識し、====== のような文字列とのマッチでその切り札を使用した．．．というわけだ。
当然、この最適化は 「 幾何級数マッチキラー 」 にはならない。必須文字列認識が動作できないような正規表現文字列では結局エンジンを吹かすしかないからだ。実際、先の正規表現を (=*)+[XY] としただけで幾何級数マッチは再現した。この場合、X という部分が文字クラス [XY] に変更されたため、（少なくとも）必須文字列認識は動作しなくなる．．．
しかし、最適化は Version 0.7 には含まれない機能のはず。なんでそれが実装されているかというと．．．陰郎がフライングしたからに決まっているんだな。それもこれもかれこれ１年以上も前の話。これに関連して思い出したのは、「 最適化をオフにする 」 というオプションを実装しなければならないということだ。できればそれは早めに実装して、Version 0.7 では問答無用で最適化をオフにしたほうがいいのかもしれない。
投稿者 kagelow : 2006年02月10日 21:50