古い記事
ランダムジャンプ
新しい記事
例えば、巨大なコーパスに対して出現する単語の共起情報を計算するときなどに、
(1) 各単語をあらかじめ ID (例えば整数) に変換して、
(2) その ID で内部処理を行い、結果をその ID で出力し、
(3) 出力結果 の ID を元の単語に戻す、
というロジックをよく使う。
機械学習の学習データの feature や、ログデータ分析なんかもこのロジックでやったりする。

SUFARY を用いてこの作業を効率的に行う方法をメモ。
速度よりも省ディスクスペースを優先する人向け。
巨大な単語集合(例えば100万とか1000万とか1億とか)に有効。
小規模なら、ありもののDBやハッシュで良いかと。

まず準備。
各行はキー文字列と付加情報をスペースでつないだもの。
mkary でインデックスを作成しておく。
% cat a.txt
foo フー
bar バー
hoge ほげ
uhyo うひょ
% mkary -l a.txt

コード (idstr.pl)。
#!/usr/bin/perl
use strict;
use warnings;
use SUFARY;

my $fn = shift @ARGV;
my $sa = SUFARY->new($fn);

# convert (demo)
for (my $i = 0; $i < $sa->{arraysize}; $i++) {
    my $str = id2str($sa, $i);
    my ($key, $info) = split(' ', $str, 2);
    print qq(id:$i => key:"$key", info:"$info"\n);
    my $id = str2id($sa, $key." ");
    print qq(key:"$key" => id:$id\n);
}

# error
my $str = id2str($sa, 100);
print qq(error1: "$str"\n); # empty
my $id = str2id($sa, "dummy");
print qq(error2: $id\n); # -1

sub id2str {
    my ($sa, $id) = @_;
    return "" unless 0 <= $id and $id < $sa->{arraysize};
    my $str = $sa->get_line($sa->get_position($id));
    chomp $str;
    return $str;
}

sub str2id {
    my ($sa, $key) = @_;
    my ($left, $right) = $sa->range_search($key);
    return -1 if not defined $left or $left != $right;
    return $left;
}

実行結果。
% ./idstr.pl a.txt
id:0 => key:"bar", info:"バー"
key:"bar" => id:0
id:1 => key:"foo", info:"フー"
key:"foo" => id:1
id:2 => key:"hoge", info:"ほげ"
key:"hoge" => id:2
id:3 => key:"uhyo", info:"うひょ"
key:"uhyo" => id:3
error1: ""
error2: -1
fooとbarの順番が入れ替わっているのは、suffix array の性質上アルファベティカルにソートされてるため。

もうちょっと実用的なスクリプト id2str.pl と str2id.pl も作ってみた。
#!/usr/bin/perl
# id2str.pl
use strict;
use warnings;
use SUFARY;
my ($id, $fn) = @ARGV;
my $sa = SUFARY->new($fn);
print id2str($sa, $id), "\n";
sub id2str {
    my ($sa, $id) = @_;
    return "" unless 0 <= $id and $id < $sa->{arraysize};
    my $str = $sa->get_line($sa->get_position($id));
    chomp $str;
    return $str;
}
#!/usr/bin/perl
# str2id.pl
use strict;
use warnings;
use SUFARY;
my ($key, $fn) = @ARGV;
my $sa = SUFARY->new($fn);
print str2id($sa, $key." "), "\n";
sub str2id {
    my ($sa, $key) = @_;
    my ($left, $right) = $sa->range_search($key);
    return -1 if not defined $left or $left != $right;
    return $left;
}

実行結果。
% ./id2str.pl 0 a.txt
bar バー
% ./id2str.pl 3 a.txt
uhyo うひょ
% ./str2id.pl foo a.txt
1
% ./str2id.pl uhyo a.txt
3

- SUFARY 臨時復旧ページ
http://ta2o.net/tools/sufary/