アルゴリズム超重要
はてなダイアリーには、あるキーワードに対して自動的にリンクがはられる機能があります(ユルさんはこの機能が嫌いなのだそうです)。キーワードがはてなでは20万以上も存在しているので、ブログの記事の中にその20万のキーワードのどれかが存在しているかどうかを調べるなんてすごく大変そう（というか時間がすごくかかりそう）な印象を受けます。
で、はてなではキーワード検索用の正規表現を公開していたりします。ためしに6000文字程度の記事に検索をかけてみます。
#!/usr/bin/perl
use strict;
use warnings;
use IO::File;
use Time::HiRes;
my $k_f = IO::File->new("hatena_keywordlist", "r") or die $!;
my $keyword = $k_f->getline;
$k_f->close;
my $fh = IO::File->new("blog.txt", "r") or die $!;
my @f_lines = $fh->getlines;
$fh->close;
my $str = "";
$str .= $_ for (@f_lines);
my @list;
my $s_time = Time::HiRes::time();
$str =~ s|
($keyword)
|
push @list, $1;
|egiox;
my $e_time = Time::HiRes::time();
print "$_ " for @list;
print "\n";
print "time: ", $e_time - $s_time, "\n";
ひさしぶりに稚拙なPerlです(はてなの正規表現がRubyで使えなかったので)。で、計測結果は、
time: 0.810735940933228
でした。
正規表現は非決定性有限オートマトンを使っているそうなので、DFAで検索するようにすれば速くなりそうです。
で、Rubyで作ってみました。仕事で使うことになりそうなので、とりあえずソースの公開はやめておきます。別にすごいことをやっているわけじゃなくて、ただの決定性オートマトンだけど。20万件のキーワード、6000字ほどの記事という、Perlと同条件でやってみた計測結果は
time: 0.010049
となりました。めちゃめちゃ速くなって一安心。
たぶん、はてなも正規表現は使ってないんじゃないかなあ、という気もします。