sufary の Perl モジュールである SUFARY.pm を使って v-gram による類似文字列検索を実現するサンプル。

コード

vgram.pl

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

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

while (<>) {
    chomp;
    next if /^\s*$/;
    my @chars = split(//, $_);
    my %phrases;
    my %scores;
    my %seen;
    for (my $i = 0; $i < @chars; $i++) {
        for (my $j = $i + $min_ngram - 1; $j < @chars; $j++) {
            my $key = join("", @chars[$i..$j]);
	    next if $seen{$key};
	    $seen{$key} = 1;
            my ($left, $right) = $suf->range_search($key);
            last if not defined $left and not defined $right;
            for (my $k = $left; $k <= $right; $k++) {
                my $pos = $suf->get_position($k);
                my @lis = $suf->get_line_info($pos);
                next if $phrases{$lis[0]}{$key};
                $phrases{$lis[0]}{$key} = 1;
                $scores{$lis[0]}++;
            }
        }
    }
    foreach my $li (sort {$scores{$b} <=> $scores{$a}} keys %scores) {
        my $line = $suf->get_line($li);
        print "$scores{$li} ";
        print decode('utf-8', $line);
        print " vgram:".join(",", sort keys %{$phrases{$li}})."\n";
    }
}

データの準備

辞書ファイル (a.txt)。
各行のフォーマットは「^検索対象文字列\t付加情報$」。

これはゆで卵	卵
あれはカレー	米
カレーな釜玉	卵
焼き鳥はカレー	鶏
ゆで卵は豚カツ	豚
豚カツと豚汁	豚

mkipu8.pl で文字単位でインデックスポイントを出力。
mkary (SUFARYに付属) でインデックスポイントをソートし、suffix arrays を完成させる。

./mkipu8.pl a.txt > a.txt.ary
mkary -so a.txt

実行例

% echo "これはカレー" | ./vgram.pl a.txt
15 あれはカレー 米
 vgram:は,はカ,はカレ,はカレー,れ,れは,れはカ,れはカレ,れはカレー,カ,カレ,カレー,レ,レー,ー
10 焼き鳥はカレー       鶏
 vgram:は,はカ,はカレ,はカレー,カ,カレ,カレー,レ,レー,ー
6 カレーな釜玉  卵
 vgram:カ,カレ,カレー,レ,レー,ー
6 これはゆで卵  卵
 vgram:こ,これ,これは,は,れ,れは
2 ゆで卵は豚カツ        豚
 vgram:は,カ
1 豚カツと豚汁  豚
 vgram:カ

解説

連続一致する部分文字列に高スコアを与えるように検索する手法。
（あとで書く）

参考

- SUFARY.pm で Longest Common Prefix Search[2007-05-15-5]
- SUFARY用インデクサのPerl版の雛形[2007-06-10-3]
- D論 (http://ta2o.net/doc/pub/)
- 富士通研究所時代の学会発表 (http://ta2o.net/doc/pub/)