たつをの ChangeLog : 2007-05-15

正規表現でCommon Prefix Searchを行う力技な方法のPerlによるサンプル。
ちょっと試すとき用のコピペ用コード片、といった感じのものです。
TRIEとかオートマトンとかでちゃんとやるのが王道ですよ。

コード：

use strict;
use warnings;
use utf8;
binmode STDOUT, ":utf8";
my $str = "あうえういあおういいういああ";
my $key = "ういあ";
my @chars = split("", $key);
my $pat = join("(", @chars).(")?" x $#chars);
while ($str =~ /($pat)/g) {
    print "$1\n";
}

実行例：

% perl a.pl
う
ういあ
うい
ういあ

「女子大生会計士の事件簿」[2004-04-27-2]でメジャーになった山田真哉氏の本を図書館で２冊借りて読みました。

■山田真哉 / さおだけ屋はなぜ潰れないのか? 身近な疑問からはじめる会計学


言わずと知れた超ベストセラー。
「どうやって稼いでいるんだろう」などの身近な謎をベースに進行しつつ、会計の概要について分かりやすく解説しています。

説教的な話を一つだけ引用：

　「普段はケチケチしてもいいけど、たまにはパッとした」という人もいるが、これはかなり危険な思想である。
　たとえば、毎日100円節約して、たまにパッと5万円使った場合、次のようになる。

100円 x 365日 - 5万円 = -1万3500円

　残念ながら赤字である。こういう人は非常に赤字を出しやすい性質なので、経営者には向いていない。要は、節約した気になっているだけで会計を見ていないのである。(p.42)

そうなんですよねえ。
小さいことだけケチケチすると「ちゃんと節約してるじゃん、オレ」と思えちゃって大きなときに危険。
心の会計[2004-02-22-3]、ですね。

■山田真哉 / 世界一感動する会計の本です[簿記・経理入門]


複式簿記の入門。
借方＝自分、貸方＝他人、と考えればいいのか。なるほどー。

タンブリン(Tumblring)、タンブリン、オーイェー♪

…と言ってみたかっただけです。

ちなみに「全ての朝にブログでポストるのだ」はネタフル。

■サンボマスター / 全ての夜と全ての朝にタンバリンを鳴らすのだ


ref.
- へーい、ミスタータンブリングマン♪:[mi]みたいもん！
http://mitaimon.cocolog-nifty.com/blog/2007/05/post_c617.html
- [を] サンボマスターを聴いてみた[2007-03-18-3]

これ、いまだにすごく混乱。

• 誤った判定 - 学校では教えてくれないバッドノウハウ英語 #13 - いやなブログ
  http://0xcc.net/blog/archives/000176.html
  • false positive
    • 「本当はスパムじゃないのにスパムと判定された」
    • 「誤った警告メッセージが出た」
    • 「誤ったパターンにマッチした」
  • false negative
    • 「本当はスパムなのにスパムじゃないメールとして判別された」

否定表現が混じると混乱の元だなあ。
専門分野でありながら、Recall/Precisionもよく混乱しがちな私です。

sufary の Perl モジュールである SUFARY.pm を使って
longest common prefix search をするサンプル。

コード：

use strict;
use warnings;
use SUFARY;

my $wordset_fn = shift @ARGV;
my $suf = SUFARY->new($wordset_fn);

while (<>) {
    chomp;
    next if /^\s*$/;
    my @chars = split(//, $_);
    for (my $i = 0; $i < @chars; $i++) {
        my $longest;
        my $key;
        for (my $j = $i; $j < @chars; $j++) {
            $key .= $chars[$j];
            my ($left, $right) = $suf->range_search($key);
            last if not defined $left and not defined $right;
            ($left, $right) = $suf->range_search($key."\n");
            next if not defined $left and not defined $right;
            if ($right - $left == 0) {
                my $li = $suf->get_position($right);
                $longest = $suf->get_line($li);
            }
        }
        print $longest if defined $longest;
    }
}

実行例：

% cat a.txt
pen
th
this
lov
love
% mkary -q -l a.txt
% echo 'this is a pen which I love' | ./lcps.pl a.txt
this
pen
love

ref.
- [を] 正規表現でCommon Prefix Search[2007-05-15-1]