2006-02-16-01-先頭文字識別 - project-enigma

2006-02-16-01-先頭文字識別

>> Site top >> weblog >> 月別アーカイブ >> 2006年02月のlog >> 2006-02-16-01-先頭文字識別

最終更新日付:2013/12/31 07:39:38


先頭文字識別

2006 年 02 月 16 日

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

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

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

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

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

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

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

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

 

コメント

このページにコメントする

 

このページのタグ

Page tag : 正規表現

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.