「テキストから辞書にある文字列をすべて取り出す簡単なプログラム (Pure Perl)」[2014-05-09-1]の話の続きです。事情により Pure Perl で書きましたが、今回は SUFARY.pm (suffix arrays) を使ったバージョン。suffix arrays による擬似 TRIE です。

結論から言うと、手元の実験環境においては Pure Perl 版よりも 3.5 倍も時間がかかっています。実装がアレなのかもしれませんが、まあたいていの場合は Pure Perl 版で OK ということで。

■実験：
- 辞書とテキスト
-- 辞書：2万3千エントリ（平均文字列長4）
-- テキスト：2500行（平均文字列長71）
- 実行速度（3回平均）
-- Pure Perl 版：2.3秒
-- SUFARY.pm 版：8.2秒

■コード (fesa.pl)：

#!/usr/bin/perl
use strict;
use warnings;
use Encode;
use utf8;
use open ':utf8';
binmode STDIN, ':utf8';
binmode STDOUT, ':utf8';

use SUFARY;

use Getopt::Long;
my $answer_mode = 0; # input with answer?
my $debug_mode = 0;
GetOptions (
    "answer" => \$answer_mode,
    'debug' => \$debug_mode,
    );

my $wordset_fn = shift;
my $sa = SUFARY->new($wordset_fn);

while (<>) {
    print "[INPUT] $_" if $debug_mode;
    chomp;
    $_ = Encode::decode_utf8($_) if not utf8::is_utf8($_);
    my $ans = ($_ =~ s/^((.+?)\t)//) ? $2 : ""  if $answer_mode;

    my @c = split(//, $_);
    my %m;
    for (my $i = 0; $i < @c; $i++) {
        my $key;
	my ($left, $right) = (0, $sa->{'arraysize'}-1);
        for (my $j = $i; $j < @c; $j++) {
            $key .= $c[$j];
            my $ekey = Encode::encode('utf8', $key);
            ($left, $right) = $sa->range_search($ekey, $left, $right);
            last if not defined $left and not defined $right;
            my ($l, $r) = $sa->range_search($ekey."\t", $left, $right);
            next if not defined $left and not defined $right;
            if ($r - $l >= 0) {
                my $li = $sa->get_position($l);
                my $s = Encode::decode_utf8($sa->get_line($li));
                my ($k, $v) = $s =~ /^(.+)\t(.+)$/;
                print "[MATCH] $k ($v)\n" if $debug_mode;
                $m{$v}++;
            }
        }
    }
    
    print "$ans "if $answer_mode;
    print join(" ", map {"$_:$m{$_}"} sort {$a <=> $b} keys %m)."\n";
#    print join(" ", map {"$_:1"} sort {$a <=> $b} keys %m)."\n";
}

■実行例：辞書とテキストは前回[2014-05-09-1]と同じ。

% mkary -l -q fepp-dic.txt
% ./fesa.pl -a fepp-dic.txt < fepp-test.txt
1 1:1 2:1 3:1
0 2:1 3:1 4:1
1 5:1 6:1 7:1 8:1
0 7:1 9:1