正規表現による単語リストの圧縮 (1)
たとえば
apache_child_terminate apache_get_modules apache_get_version apache_getenv
こういうリストを
apache_(child_terminate|get_(modules|version)|getenv)
こういう形で表現したいという話。
PHP 用の強調表示定義ファイル*1を作ろうとしたら関数が3200個ほどあって、単純に羅列すると 32KB の容量制限を超えちゃう。全体のバイト数が最小となるように共通部分を括り出すにはどうすればよいか？
最初は素朴なヒューリスティクスをあれこれ考えてたんだけど、突き詰めるとデータ圧縮理論にたどり着く。データ圧縮は圧縮アルゴリズムと展開アルゴリズムの両方を考えるのに対し、今回は「展開アルゴリズム＝正規表現のマッチングアルゴリズム」という縛りがあるので、圧縮アルゴリズムをどこまで最適化できるかという話になる。
まずは素朴なやつから。 PHP の関数はプレフィクス付きの長い名前が多い。そこで、上の例で示したように先頭一致部分を括り出して
├apache_ │├child_terminate │├get_ ││├modules ││└version │├getenv
こういうツリー構造に還元すればうまく行きそうだ。だが最適ではない。次のようなケースがある。
fprintf sprintf vfprintf vprintf vsprintf
これらは先頭ではなく末尾に共通部分を含むので単純なツリー構造では集約できない。あえて描けば
printf f┤ φ┤│ v┘│ s┤ φ┤│ v┤│ v┘
こんな感じ？（φは空文字列を表す） 正規表現にすると
((|v)f|(|v)s|v)printf
こんな感じ。うーむ。
共通部分は先頭一致と末尾一致だけ考えればいいか。中間一致は簡単に括り出すわけには行かない。もしやるなら、前部分と後部分の組合せがすべて存在しなくてはならない。このチェックは大変そうだ。
いい具合に眠くなってきたので今日はここまで〜
