TransFreeBSDの日記 このページをアンテナに追加 RSSフィード

2007-02-12

[] spamかどうかを判別するやつ。 - くれすのPerl日記 - Hatena::Group::Perl の勝手改定版  [http://perl.g.hatena.ne.jp/Cress/20070212/1171244924:title] の勝手改定版 - TransFreeBSDの日記 を含むブックマーク

ちょうどタイムリーだったので、勝手ではありますが自分用に改定版作りました。

これで複数ファイルや標準入力から読めるようになりました。

ただ出力形式は1考の余地ありですかね。

使い方は以下のような感じで。

perl spamlookup.pl listfile1 listfile2
perl spamlookup.pl --rbl bsb.spamlookup.net --rbl niku.2ch.net listfile
awk '{print $3}' logfile | sort | uniq | perl spamlookup.pl --rbl niku.2ch.net

ソースは以下

#!/usr/bin/perl
# original http://perl.g.hatena.ne.jp/Cress/20070212/1171244924

use strict;
use Getopt::Long;
my @DEFAULT_RBL_HOST = qw(bsb.spamlookup.net);

my @RBL_HOST = ();
GetOptions('rbl=s' => \@RBL_HOST) or die;
@RBL_HOST or @RBL_HOST = @DEFAULT_RBL_HOST;

print "spamlookup server is @RBL_HOST\n";
print "\n";

while( <> ) {
    chomp;
    if( /^(\d+)\.(\d+)\.(\d+)\.(\d+)$/ ) {
        foreach my $RBL_HOST (@RBL_HOST) {
            my $query = "$4.$3.$2.$1.$RBL_HOST";
            my $addr = join( '.', unpack( 'C*', gethostbyname( $query ) ) );
            if( $addr eq '127.0.0.2' ) {
                print "[!] $_ is spam at $RBL_HOST.\n";
            } else {
                print "    $_ is not spam at $RBL_HOST.\n";
            }
        }
    }
}

print "\n";
print "done.\n";

CressCress2007/02/12 19:13あ、コマンドライン引数ってこうやって取るんだ(汗)。CGIばっかり作ってたので全然知りませんでした。。。
spamのアドレスだけ(あるいはその逆)だけ出力できるオプションがあるともっと便利かもしれないですね。[!] は、自分で見やすいように適当に付けちゃったので。

TransFreeBSDTransFreeBSD2007/02/12 19:48複数RBL問い合わせ時も1行にまとめるとか色々ありそうだけど、とりあえずこれで。どっちかといえば精度チェックとかだと思うし(笑)

トラックバック - http://freebsd.g.hatena.ne.jp/TransFreeBSD/20070212

2006-11-24

[]ModPerl::{PerlRun,Registry,RegistryPrefork}でのカレントディレクトリBEGINブロック、@INCの扱いメモ ModPerl::{PerlRun,Registry,RegistryPrefork}でのカレントディレクトリ、BEGINブロック、@INCの扱いメモ - TransFreeBSDの日記 を含むブックマーク

まとめると

cdBEGINブロック実行フェーズでuse libプラグマが反映されない可能性
ModPerl::PerlRunなしCGI呼び出し時ない
ModPerl::Registryなしスクリプト読み込み時ある
ModPerl::RegistryPreforkありスクリプト読み込み時ある

というわけで

  • BEGINでcdしても実行フェーズでは変っている可能性がある。
  • use libした場合に、実行フェーズでuseやrequireすると@INCに反映されていなくて失敗する可能性がある。

KGKG2006/11/26 00:28Wiki.pm の process_plugin 内で $parser を渡すところに制限がかかりましたので、プラグイン内で parser を使えるのが include と help だけになってしまいました。この制限を外せば使えるようになると思います。

TransFreeBSDTransFreeBSD2006/11/26 13:17あー、ソース読んでないのがバレバレだ(笑)
coreプラグインなので変更してコミットしておきます。
コメントありがとうございました。

KGKG2006/11/27 12:19$parser_including_plugin{$name}って?(w

KGKG2006/11/27 12:21途中で投稿してしまった(笑)。$self->{parser_including_plugin}->{$name} とかの方がよさそう。

KGKG2006/11/27 12:25というか、個人的には制限なんて無い方が良いのだが・・・竹添氏の意向がそうでないようなので制限が入るのは仕方が無い。拙作プラグインの関係上、個人仕様では制限なしにせざるを得ないのだが・・・。

TransFreeBSDTransFreeBSD2006/11/27 20:55一応バグフィクス扱いで、paragraphプラグインを加えるだけだけど、ただ、ifにズラズラ並べるのはあれなので、ハッシュ変数で判定という流れです。
元が固定値なので、ハッシュ変数を公開するのはとりあえず止めました。いまの所は定数扱いで、今後は要相談ってところですか。
コメントに裏技とあるだけあって、竹添さんとしては、出来れば渡したくないけどしかたなく、というところなのでしょう。
#少しパーサの方も見直した方が良いかも

トラックバック - http://freebsd.g.hatena.ne.jp/TransFreeBSD/20061124

2005-10-11

[]Hatenize再び Hatenize再び - TransFreeBSDの日記 を含むブックマーク

id:TransFreeBSD:20050920:p1にて行なったベンチマークの続報です。今回はキーワード数との相関を中心に調べました。

結論

  • キーワード検索自体はおよそ100ワード程度を境にキーワード数が多くなるほど効率がよくなる。
  • 正規表現生成コストも含めた損益分岐点は、1回の正規表現生成によって検索するテキストサイズとなり、

使用データ

使用したサンプルデータは前回使った物を流用しています。入手先等は前回記事を参照してください。

略名ファイル名バイト
bnchbenchmark.pl1,371
hotwhotwired.txt5,612
nytmnytimes.txt6,746
helphelp.txt73,153

使用キーワード

キーワードはhatena2list.plにより生成したファイルから、ベンチマーク時に任意数のキーワードランダムに抽出して使用しています。

正規表現生成

flat

sub mkflat {
	return join "|", map {quotemeta($_)} @_;
}

trie

sub mktrie {
	my $trie = Regexp::Trie->new;
	$trie->add($_) foreach (@_);
	return $trie->as_regexp;
}

結果

キーワード数と正規表現生成にかかる時間(msec.)

キーワード10100100010000100000
flat0.02380.2032.0021.5256
trie3.1030.62982,75323,640

正規表現マッチの処理時間(msec.)

使用テキスト使用正規表現10100100010000100000
bnchflat1.169.8198.11,2399,956
bnchtrie0.9915.118.3514.118.8
hotwflat6.6443.74264,25935,295
hotwtrie4.5223.240.968.687.5
nytmflat6.3150.34884,97149,392
nytmtrie4.8825.241.369.596.1
helpflat70.85635,51656,190470,440
helptrie57.22945158651,112

グラフ

f:id:TransFreeBSD:20051010022559p:image:small

考察

正規表現生成時間はおおよそ比例関係にあり、その近似式は次のようになります。(以下単位はいずれもμ秒)

flat版
キーワード数×2.22
trie版
キーワード数×285

flat版正規表現処理時間もおおよそ比例関係に近く、その近似式は次のようになります。

キーワード数×テキストサイズ×0.0741

trie版では、キーワード数がおよそ100以上の場合に、次のような近似式となります。

(キーワード数-64)^0.1714 ×テキストサイズ×2.13

以上から、次のような近似が成り立ちます。

trie版とflat版の正規表現生成時間差
キーワード数×(285-2.22)
trie版とflat版の正規表現処理時間差
テキストサイズ×(キーワード数×0.0741ー((キーワード数-64)^0.1714)×2.13)

そして、この処理時間差が等しくなるのは

テキストサイズ=キーワード数×(285-2.22)/{(キーワード数×0.0741ー((キーワード数-64)^0.1714)×2.13)}

=((285-2.22)/2.13)/(0.0741/2.13ー(キーワード数-64)^0.1714/キーワード数)

=129/(0.0348-(キーワード数-64)^0.1714/キーワード数) ー (A)

さらにキーワード数が数百以上となる場合、次の式に近くなる。

≒129/(0.0348-キーワード数^-0.8286) ー (B)

いずれの場合も、キーワード数が大きくなると3,820に近付いていきます。

この近似式をグラフ化すると次のようになります。

f:id:TransFreeBSD:20051011225125p:image:small

トラックバック - http://freebsd.g.hatena.ne.jp/TransFreeBSD/20051011

2005-09-28

[] hatena2list.plのバグ発見  hatena2list.plのバグ発見 - TransFreeBSDの日記 を含むブックマーク

以前、Click'n Hatenizeに関してベンチマークをやったわけですが、そのときの「trie版ではマッチ数が多い場合がある」理由を調べてみました。

すると原因がhatena2list.plにある事がわかり、Click'n Hatenize Rivisitedにコメントしようとしたら、パッチが長くて弾かれちゃった。そんなわけでここに書いて、初めてはてな外へトラックバックする。

はじめまして。hatena2list.plとmk_trie_regexp.plを有難く使用させていただいています。

で、hatena2list.plに3つほどバグ見つけました。以下パッチです。

--- hatena2list.pl.orig Tue Sep 13 15:01:21 2005
+++ hatena2list.pl      Wed Sep 28 22:49:14 2005
@@ -15,15 +15,16 @@
     close $in;
     return $retval;
 }
-my %ent =    (amp => '&', gt => '>', lt => '>', quot => q('));
+my %ent =    (amp => '&', gt => '>', lt => '<', quot => q('));
 my $re_ent = join '|', keys %ent;
 my $str = decode eucjp => fetch($url);
 my @words;
-for (split /(?!\\)\|/, $str){
+for (split /\|/, $str){
     s/\\s/ /g;
-    s/\\//g;
+    s/\\(?!$)//g;
     s/&($re_ent);/$ent{$1}/g;
-    s/\A\s+//; s/\s+\z//;
+    s/\A\s+//; s/\s+\Z//;
+    @words and $words[-1] =~ s/\\$/|$_/ and next;
     /^$/ and next;
     push @words, $_;
 }
  1. 「lt => '>'」→「lt => '<'」
  2. 「s/\s+\z//」→「s/\s+\Z//」
  3. 「/(?!\\)\|/」は先読みが前にあるから「\」にマッチしない「|」って意味になり「(?!\\)」の意味がなくなっています。うまくsplitする方法を思いつかないので、末尾の「\」は残して、次のループでくっつけてみました。

それで、これが本題かも知れませんが、この2つのスクリプトからコードを借用した物を公開しても良いですか?問題があったらその旨、明言してください。

自分的には最後の1文が重要だったり。そんなわけで宜しくお願いします>小飼さん

以下、検証方法

基本的にはhatena2list.plの出力の各行がオリジナルのkeywordlist(flat版)と、そのtrie版にマッチするか確認する方法で行なった。

この時、flat版がEUCである事、「&」などのエスケープ処理がされている事から、hatena2list.plに以下のパッチをあてた状態で行なう。

--- hatena2list.pl.orig Wed Sep 28 22:49:14 2005
+++ hatena2list.pl      Wed Sep 28 23:16:58 2005
@@ -17,18 +17,15 @@
 }
 my %ent =    (amp => '&', gt => '>', lt => '<', quot => q('));
 my $re_ent = join '|', keys %ent;
-my $str = decode eucjp => fetch($url);
+my $str = fetch($url);
 my @words;
 for (split /\|/, $str){
     s/\\s/ /g;
     s/\\(?!$)//g;
-    s/&($re_ent);/$ent{$1}/g;
-    s/\A\s+//; s/\s+\Z//;
     @words and $words[-1] =~ s/\\$/|$_/ and next;
     /^$/ and next;
     push @words, $_;
 }
-binmode STDOUT, 'utf8';
 for (sort @words){
     print $_, "\n";
 }

最初はflat版で、なにも表示されなければ成功である。

% echo -n 'qr{' | cat - keywordlist > keyword.tmp
% echo -n '}' | cat keyword.tmp - > keyword.rx
% perl -e 'my $regexp = do "keyword.rx";while (<>) {/^$regexp$/o or print}' hatena

次にtrie版でも検証する。

% perl hatena2list.pl keywordlist > hatena
% perl mk_trie_regexp.pl hatena

以上、出力がなければOKと判断。

弾2005/09/29 13:28Thanks, applied.

トラックバック - http://freebsd.g.hatena.ne.jp/TransFreeBSD/20050928

2005-09-20

[][]idea:6032 を肴に idea:6032 を肴に - TransFreeBSDの日記 を含むブックマーク

この前の連休Click'n Hatenizeをfswikiに実装すべくゴソゴソやっていた。で、ついでにベンチマークもやってみよう。などといいつつベンチマークなど滅多にやらないのでBenchmarkモジュールの存在を知らなかったのは内緒<もってる青ラクダにも書いてあるのに

さて、まずは結果から。詳細は省略記法のあとで。

結論

この手法は、http://d.hatena.ne.jp/images/keyword/keywordlistの様な巨大な正規表現最適化手法として非常に有効であり、今回の結果(環境)からは、正規表現生成コストを入れても5-6kbyteの検索でペイする。

結果

使用キーワード
118,801
キーワード合計サイズ
1,407,841 - 118,801(改行分) = 1,289,040 byte
trie版正規表現生成時間
11.73 + 33.91 = 45.64 sec.(CPU)
使用テキストテキストサイズマッチサイズflat版CPU時間trie版CPU時間flat/trieテキストサイズ/flat版CPU時間
null.txt000.4800.7990.6160
benchmark.pl1,37113312.50.90813.7110
hotwired.txt5,6121,57047.70.99747.9118
nytimes.txt6,74677261.60.99162.2110
help.txt73,15320,1375272.01262139

検索対象が大きくなればなるほど効果が大きい事がわかる。flat版では線形的に*1処理時間が増えるのに対し、trie版では(正規表現コンパイルを含む)他の処理時間に比べ、実際にマッチ処理を行なう時間が少なく、テキストサイズの影響を受けにくいためと思われる。

使用テキストテキストサイズマッチサイズflat版CPU時間trie版CPU時間flat/trieテキストサイズ/trie版CPU時間
null.txt000.4800.7990.6160
benchmark.pl1,37113312.00.10911012.6k
hotwired.txt5,6121,57047.20.19823828.3k
nytimes.txt6,74677261.10.19231835.1k
help.txt73,15320,1375271.2143560.5k

CPU時間を、null.txtの結果を引いた値にして再計算した物である。これにより実際にマッチ処理を行なっている時間に近似できる。(正規表現コンパイルを除くが)マッチ処理部分だけでみれば数百倍の効率といえる。


使用テキスト使用正規表現タイキーワードマッチキーワードマッチ合計サイズテキストサイズ
null.txtflat000
null.txttrie000
benchmark.plflat341331,371
benchmark.pltrie601851,371
hotwired.txtflat1951,5705,612
hotwired.txttrie1971,5735,612
nytimes.txtflat2197726,746
nytimes.txttrie2197686,746
help.txtflat2,32620,13773,153
help.txttrie2,36120,22873,153

trie版ではマッチ数が多い場合がある。幾らかの誤検出があるようだ。これについては詳細を追っていきたい所。

事前準備

ベンチマーク用に特徴の異なる幾つかのテキストファイルを用意した。なお、リンクで示した物はw3mを用いて取得している。

help.txt
一般的な長文としてはてなダイアリーヘルプ
hotwired.txt
日本語としてHotwiredの記事
nytimes.txt
英文としてNew York Timesの記事
benchmark.pl
通常の文ではない物としてベンチマークに使用しているperlスクリプト
null.txt
長さ0の空文

対して正規表現は、はてなの提供するhttp://d.hatena.ne.jp/images/keyword/keywordlistを元に作成した以下のファイルを用意した。

keyword.rx
qr{」と「}」で囲っただけのflat版
hatena.rx
eucjpで出力するようにしたhatena2list.plとmk_trie_regexp.plを使って作成したtrie版

ベンチマーク

ベンチマークはflat版とtrie版の正規表現を、それぞれ用意した5つのテキストファイルに適用し、標準のBenchmarkモジュールのcmptheseを使用して比較した。また、trie版作成に付いてもtimethisを使用し実行時間を求めた。

実際のコードは実行結果の生出力と共に次に示した。

コード、実行結果

benchmark.pl

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(timethis timethese cmpthese);
undef $/;

print "benchmark: hatena2list.pl\n";
timethis( 1, 'system("perl hatena2list.pl keywordlist > hatena")' );
print "benchmark: mk_trie_regexp.pl\n";
timethis( 1, 'system("perl mk_trie_regexp.pl hatena")' );

my %info;
timethese( 100, {
	null_flat => 'regexp("keyword.rx", "null.txt")',
	null_trie => 'regexp("hatena.rx",   "null.txt")',
});
cmpthese( -300, {
	help_flat => 'regexp("keyword.rx", "help.txt")',
	help_trie => 'regexp("hatena.rx",   "help.txt")',
});
cmpthese( -300, {
	bnch_flat => 'regexp("keyword.rx", "benchmark.pl")',
	bnch_trie => 'regexp("hatena.rx",   "benchmark.pl")',
});
cmpthese( -300, {
	hotw_flat => 'regexp("keyword.rx", "hotwired.txt")',
	hotw_trie => 'regexp("hatena.rx",   "hotwired.txt")',
});
cmpthese( -300, {
	nytm_flat => 'regexp("keyword.rx", "nytimes.txt")',
	nytm_trie => 'regexp("hatena.rx",   "nytimes.txt")',
});

sub regexp {
	my ($rx_file, $src_file) = @_;
	my $regexp = do $rx_file;
	open DATA, "<$src_file" or die "open $src_file: $!";
	$_ = <DATA>;
	close DATA;
	my @match = /$regexp/g;
	$info{$src_file.$rx_file} = join "|",
		"", $src_file, $rx_file, scalar(@match), length("@match"), length($_), "";
}

print "|source file|regexp file|matched words|matched length|source length|\n";
print join "\n", sort(values %info), "";

実行結果

% w3m -dump http://d.hatena.ne.jp/help > help.txt
% w3m -dump http://hotwired.goo.ne.jp/news/print/20050916304.html > hotwired.txt
% w3m -dump 'http://www.nytimes.com/2005/09/19/business/19cnd-tyco.html?ei=5094&en=e973f8852e727c2c&hp=&ex=1127188800&partner=homepage&pagewanted=print' > nytimes.txt
% w3m -dump http://d.hatena.ne.jp/higepon/20050913/1126604345 > higepon.txt
% touch null.txt 
% fetch http://d.hatena.ne.jp/images/keyword/keywordlist
keywordlist                                   100% of 1387 kB  558 kBps
% echo -n 'qr{' | cat - keywordlist > keyword.tmp
% echo -n '}' | cat keyword.tmp - > keyword.rx
% wc help.txt hotwired.txt nytimes.txt higepon.txt benchmark.pl null.txt hatena keyword.rx hatena.rx
    2570    2187   73153 help.txt
     125     123    5612 hotwired.txt
     125    1045    6746 nytimes.txt
     127     246    2747 higepon.txt
      46     149    1371 benchmark.pl
       0       0       0 null.txt
  118801  126227 1407841 hatena
       0       1 1420535 keyword.rx
       0    5539 1611127 hatena.rx
  121794  135517 4529132 total
% perl benchmark.pl
benchmark: hatena2list.pl
timethis 1: 12 wallclock secs ( 0.00 usr  0.00 sys +  3.50 cusr  8.23 csys = 11.73 CPU)
            (warning: too few iterations for a reliable count)
benchmark: mk_trie_regexp.pl
118801
  PID STAT      TIME  SL  RE PAGEIN   VSZ   RSS   LIM TSIZ %CPU %MEM COMMAND
58673 S+     0:18.89   0  19      0 91156 90452     -   12 96.6 14.0 perl mk_trie_regexp.pl hatena
  PID STAT      TIME  SL  RE PAGEIN   VSZ   RSS   LIM TSIZ %CPU %MEM COMMAND
58673 S+     0:32.78   0  33      0 121084 120404     -   12 96.2 18.6 perl mk_trie_regexp.pl hatena
timethis 1: 35 wallclock secs ( 0.00 usr  0.00 sys + 24.71 cusr  9.20 csys = 33.91 CPU)
            (warning: too few iterations for a reliable count)
Benchmark: timing 100 iterations of null_flat, null_trie...
 null_flat: 49 wallclock secs (46.20 usr +  1.77 sys = 47.98 CPU) @  2.08/s (n=100)
 null_trie: 82 wallclock secs (75.34 usr +  4.53 sys = 79.88 CPU) @  1.25/s (n=100)
            (warning: too few iterations for a reliable count)
          s/iter help_flat help_trie
help_flat    527        --     -100%
help_trie   2.01    26120%        --
          s/iter bnch_flat bnch_trie
bnch_flat   12.5        --      -93%
bnch_trie  0.908     1274%        --
          s/iter hotw_flat hotw_trie
hotw_flat   47.7        --      -98%
hotw_trie  0.997     4686%        --
          s/iter nytm_flat nytm_trie
nytm_flat   61.6        --      -98%
nytm_trie  0.991     6122%        --
|source file|regexp file|matched words|matched length|source length|
|benchmark.pl|hatena.rx|60|185|1371|
|benchmark.pl|keyword.rx|34|133|1371|
|help.txt|hatena.rx|2361|20228|73153|
|help.txt|keyword.rx|2326|20137|73153|
|hotwired.txt|hatena.rx|197|1573|5612|
|hotwired.txt|keyword.rx|195|1570|5612|
|null.txt|hatena.rx|0|0|0|
|null.txt|keyword.rx|0|0|0|
|nytimes.txt|hatena.rx|219|768|6746|
|nytimes.txt|keyword.rx|219|772|6746|

*1:実際は線形ではない。マッチ部分が多いほど効率は良くなる様に見受けられる。

トラックバック - http://freebsd.g.hatena.ne.jp/TransFreeBSD/20050920