blog.nomadscafe.jp

にわかににぎわっているはてなキーワードを高速に付与なのですが、dankogaiさんのRegexp::Trieをちょっとさわってみた。

Trieを利用したRegexpのオプティマイズという理解で間違っていないですよね。

#キーワードリスト
my @src = qw(1U 2ch amazon apache apple atom blog cdbi CentOS cgiapp colinux cpan csrf css dashboard db firefox flash foaf ftp google hacker hard httpd intrablog ipod);
my $rt = Regexp::Trie->new();
map{$rt->add($_)} @src;
my $regexp = $rt->as_regexp;
print $regexp,"?n";

とすると、

(?-xism:(?:1U|2ch|CentOS|a(?:mazon|p(?:ache|ple)|tom)|blog|c(?:dbi|giapp|olinux|pan|s(?:rf|s))|d(?:ashboard|b)|f(?:irefox|lash|oaf|tp)|google|h(?:a(?:cker|rd)|ttpd)|i(?:ntrablog|pod)))  

こういう正規表現が得られる。使う時は、

#キーワードの前後に「"」をつける
$text =~ s/$regexp/"$&"/go;

これのソースをみていて、やっぱりすげぇなぁと思った。

sub add{
    my $self = shift;
    my $str  = shift;
    my $ref  = $self;
    for my $char (split //, $str){
        $ref->{$char} ||= {};
        $ref = $ref->{$char};
    }
    $ref->{''} = 1; # { '' => 1 } as terminator
    $self;
}

なにげないように見える上のコードなんだけど。
この部分だけで動くようにしてみると、

$ perl -e '
> use Data::Dumper;
> my $self = {};
> my $ref = $self;
> foreach my $char (split //,"perl"){
> $ref->{$char} ||= {};
> $ref=$ref->{$char};
> }
> $ref->{""}=1;
> print Dumper($self);
> '
$VAR1 = {
          'p' => {
                   'e' => {
                            'r' => {
                                     'l' => {
                                              '' => 1
                                            }
                                   }
                          }
                 }
        }; 

こうなる。
これがなぜこうなるのかがすぐに分からなくて悩んだ。$refだけを見ているとわからない。リファレンスと$selfの動きをちゃんと追って行けばよかった。

こんな作り方(コード)ができるようになりたい。