2007年04月19日 15:00 [Edit]

perl - Regexp::Assembleのススメ

というわけで、Regexp::Assembleのご紹介。

asin:4873113148
PERL HACKS
(日本語版)
[英語版]
odz buffer - それ Regexp::Assemble
ん?ループ云々を抜きにして、こういうのは Regexp::Assemble の出番じゃないの?

すでにPerl Hackers御用達のモジュールとなっていますが、まだ知らない方もいらっしゃるかも知れないので。


何をするモジュールか、といえば、以下を見れば一目瞭然でしょう。

Regexp::Assemble - Assemble multiple Regular Expressions into a single RE - search.cpan.org
  use Regexp::Assemble;
  
  my $ra = Regexp::Assemble->new;
  $ra->add( 'ab+c' );
  $ra->add( 'ab+-' );
  $ra->add( 'a\w\d+' );
  $ra->add( 'a\d+' );
  print $ra->re; # prints a(?:\w?\d+|b+[-c])

要は、qr/(?:ab+c|ab+-|a\w\d+|a\d+)/と書くよりも、qr/(?:\w?\d+|b+[-c])/と書いた方が高速な正規表現になるので、それを自動化しようというものです。

例えば、0から255まで厳密にマッチする正規表現というのは、trivialにqr/(?:0|1|2|..|255)/と書いても出来るのですが、これは凄く低速なわけです。これを高速化するためには、今までフクロウ本とにらめっこしたりして理想の正規表現を手で追い求めていたのですが、その状況に一石を投じたのがRegex::PreSufでした。Perl 5.8開発のpumpkingだったjhiが作ったこのモジュールは共通のprefixとsuffixをまとめたRegexpを作ることが出来たのです。ただし、まだこの頃はまだProof of Concept程度でした。

その次に表れたのが、Regexp::Optimizer。作者は実は私。これはかなり実用性を考えて作ったモジュールで、少なからぬ反響が来ました。これを使うと、/usr/bin/dict/wordsにexact matchする正規表現でも作る事が出来たり、何よりも単純文字列ではなく正規表現から正規表現を再構成することが出来たのです。

とはいうものの、このモジュールはRegex::PreSufと同じ問題を抱えていました。速度です。このモジュールはRegex::PreSufと同じく、prefixだけではなくsuffixもまとめます。しかし実のところ、TRIEを作るにはprefixだけまとめればよく、表現は短くなるもののsuffixをまとめなくてもmatchの高速性は損なわれないのです。そしてTRIEを作るだけなら、より高速なアルゴリズムが使えます。

それをやったのが、まさにRegexp::Assembleです。作者がメンテナンスに熱心で、さまざまな機能を追加してきた事もあって、今ではこれが業界標準になっています。私も今ではこちらのユーザーです;-)。ただ、単純文字列から正規表現を作るときの速度に不満があったので、404 Blog Not Found:TRIE-Optimized Regexpを元にそのケースだけ高速化したRegexp::Trieをリリースしていますが。

先ほどの0から255までの数字に厳密にマッチする正規表現は、今ではこれほど手軽に手に入ります。

% perl -MRegexp::Assemble \
    -le '$r=Regexp::Assemble->new; $r->add(0..255); print $r->re'
(?-xism:(?:1(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:[6789]|5[012345]?|0\d?|1\d?|2\d?|3\d?|4\d?)?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?|0))

さらにPerl 5.9には、Perl自身がこれと同等のことをやる機能が組み込まれました。しかし、今はRegexp::Assembleの機能は、単にTRIE Optimizeするに留まりません。その格好の例が、odzさんの例です。以下、解説のため少し書き直してコメントで解説。

use Regexp::Assemble;

my %analyze = (
    qr/Pattern 1/ => 'Pattern 1',
    qr/Pattern 2/ => 'Pattern 2',
    qr/Pattern 3/ => 'Pattern 3',
    # ...
);
my $re = Regexp::Assemble->new; 
$re->track;              # ->track で、後の ->match で正規表現を取り出せるよう準備。
$re->add(keys %analyze); # 正規表現を追加
while (my $log = $logs->readline) {
    next unless $log->{ua} 
    my $matched = $re->match($log->{ua})); # $matched には、matchの結果ではなく
    next unless defined $mached;           # match した正規表現が入る。
    my $pattern = $analyze{$matched};
    # do something for pattern
}

こういう使い方が出来るので、もはやRegexp::Assembleは単なる正規表現高速化モジュールの域を超えています。なお、この用法はHACK #98としてPERL HACKSにも登場しています。

Regexp::Assembleもそうですが、ここで紹介した正規表現関連ツールは、いずれもPerlを使わない人にさえご利益があります。なにしろRegexp::Assembleが生成する正規表現は、PCRE互換なので、RubyやPythonやJavaなどでも動く事が期待できるからです。

正規表現を正規に使っている人も非正規に使っている人も、Regexp::Assembleをお忘れなく。

Dan the Yet Another Regexp Hacker


この記事へのトラックバックURL

この記事へのトラックバック
追記: バグだなんだ言ってねーで手動かせうんこ野郎。 ということで正規表現リテラル(?)じゃなく文字列で渡せばうまくいきました。 でも正規表現リテラルでもできなかったっけ? コメント欄で紹介させてもらった弾さんの記事でも正規表現リテラル使ってるし。 自分でも前使
[Perl]Regexp::Assembleのバグ?【おつあり】at 2010年01月26日 22:24
ソース読んでみるとチョロいミスがあるみたい。せっかくだからバグ報告しておこうかと思ったんだけど、そういえば作者は dankogai さん。本当は CPAN にバグとして登録するのが正しい手順なんだろうけど、日本語...
Perl の Regexp::List で capture => 1 が効かない件【miau's blog?】at 2009年04月01日 20:21
Regexp::Assemble を使うと、正規表現をほぼ自動的に生成できます。 perl - Regexp::Assemble のススメも参考になります。 use Regexp::Assemble; my $ra = Regexp::Assemble->new; $ra->add( ’ab+c’ ); $ra->add( ’ab+-’ ); $ra->add( ’a¥w¥d+’ );...
[開発][Memo] 正規表現を組み立てるモジュール【アジャイルプログラマの日常】at 2007年07月30日 19:54
スーパー便利。 cpan 要は正規表現の最適化。 こういうコード生成・最適化的な...
Regexp::Assemble【polog】at 2007年04月19日 15:26