namazu-dev(ring)

[Satoru Takabayashi <satoru-t@xxxxxxxxxxxxxxxxxx>]

knok@xxxxxxxxxxxxx (NOKUBI Takatsugu) wrote:

>> のようにすればよいですよね。使えないなら対応した方がよいので
>> はないかと。:)
>
>  そのように改造してみました。ついでに%SPECIAL評価方法もちょっと変更し
>てます。今までは最初にpattern matchするとそこで即評価を打ち切っていた
>のを、先頭から最も近い位置でmatchしたものをもって判別するようにしたの
>で、誤認する率が下がりました。そのかわり、全ての%SPECIALを評価するので
>速度が低下しているはずです。

%SPECIAL の処理ですが、

            foreach $type (keys %SPECIALS) {
-                foreach $token (@{$SPECIALS{$type}}) {
-                    # we could do \b word boundaries if the end chars in
-                    # $token were always \w, but they're not.  this is
-                    # crude guessing anyway.
-                    if ($data =~ /\Q$token\E/m) {
-                        $mtype = $type;
-                        goto ALLDONE;
-                    }
+                my $regex = join '|',   # ここがみそ
+			map  {quotemeta} 
+                       sort {length($b) <=> length($a)} 
+			@{$SPECIALS{$type}};
+                if ($data =~ /$regex/m) {
+                        $mtype = $type;
+                        break;
+                }
            }
            
-         ALLDONE:

のように修正すれば、一段ループを外して高速化できると思います。 
alternation の正規表現を作って apply するところがミソです 
(私が好きなテクニック)。メイル末尾におまけのメモを添付してお
きます。

それから、細かいことですが、

            my ($type,$token);
            foreach $type (keys %SPECIALS) {
                foreach $token (@{$SPECIALS{$type}}) {
 
は

           for my $type (keys %SPECIALS) {
                for $my token (@{$SPECIALS{$type}}) {

の方が好ましいですね。
 

>  先頭から一定バイト数のみを評価するようにしたほうがよいのかもしれませ
>ん。問題は、その閾値をどれくらいにするべきかですが... これはもう実験的
>に確かめるしかなさそうです。せいぜい数KB程度でいいと思うんですけどね。

ですね。直感的に 4,096バイト、多くても 8,192バイトくらいかな。


>  ところで、RFCの中には先のように/^Request for Comments:/等の書式にし
>たがっていないものが一部あるようです(rfc822とか)。この辺りはどうしましょ
>う? まあ、書式がことなるので他のRFCと同じように処理できないかもしれな
>いので、判別できないままの方がいいのかもしれませんけど...

いいえ、heuristicのかぎりを尽くして、判別してくださいませ。:)

# RFCならファイル名を /rfc\d+\.txt$/ でマッチするだけでほぼ
# 間違いなしなんですけどね


>> ># ファイル名による判別も合わせて行ったほうが良いのかもしれません...
>> 
>> RFCなんかは特にそうですね。お願いします。
>
>  checktype_byfilenameを作ればいいかな。filter.plを参考にして実装して
>みます。

よろしくお願いします。

-- Satoru Takabayashi

alice と bob を atomic に交換するプログラム。この方法は変換
表のエントリが増えるにつれて線形に遅くなる。

#!/usr/bin/perl

# 変換表を定義 (資源の許す限り好きなだけ定義できる)
my %table = (
    'alice' => 'bob',
    'bob'   => 'alice',
);

# 変換表を元に置換用の正規表現を作成 (オア記号で結ぶだけ)
# 念のため長い順にソートする (job と jo を交換するときのため)
my $regex = join '|', sort {length($b) <=> length($a)} keys %table;

# 変換 & 出力を行う
while (<>) {
    s/($regex)/$table{$1}/g;
    print;
}


変換を行う対象となるテキストが次の条件を満たすならば、変換表
のエントリ数が増えても、遅くならない方法があります。

  1. 置換する文字列は単語単位
  2. 単語と単語が white space で区切られる

#!/usr/bin/perl

# 変換表を定義する
my %table = (
    'alice' => 'bob',
    'bob'   => 'alice',
);

# 変換と出力を行う
while (<>) {
    s/(\S+)/defined $table{$1} ? $table{$1} : $1/ge;
    print;
}