週末に SUFARY.pm や SUFARY.xs のソースを見てたら(ref.[2006-04-23-2])、
あまり使ってない（忘れてる）メソッドがいろいろありました。
suffix array をトライとして使うためのメソッド(range_search)や、
開始・終了文字列を指定してリージョンを取得するメソッド(get_region)
なんかもあります。SUFARY 自体、なんか途中で投げ出してしまった感が
ありありなので、この際ちょっとサンプルプログラムを作ってみます。
SUFARY Hacks としてシリーズ化していきます！
（なお SUFARY.pm のオフィシャルなドキュメントは、
sufary-2.3.8/doc/ReferenceP.txt にあります。）

必要なもの：
- SUFARY http://ta2o.net/tools/sufary/ および、
  その Perl モジュール。


今回使用するメソッドは以下の二つ：

■ get_position(INT)
suffix array（配列）の添字を index point（文字列のoffset）に
変換します。

■ get_string(OFFSET, LEN)
検索対象テキストの OFFSET バイト目から LEN バイト取り出して文字列
として返します。

これらを用い、「2回以上現れる部分文字列のうち最長のもの」つまり
「最長の繰り返し文字列を探す」を取り出すサンプルプログラム
longest_repetition.pl を作りました。

#!/usr/bin/perl
use strict;
use warnings;
use SUFARY;

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

my $asz = $suf->{'arraysize'};  # 配列の大きさ
my $tsz = $suf->{'textsize'};   # テキストの長さ

my %longest = (len => 0, posi => -1); # 結果が入る
my $pre_posi = -1;
for (my $i = 0; $i < $asz; $i++) {
   my $posi = $suf->get_position($i);
   if ($pre_posi != -1) {
       my $common = compare_suffixies($suf, $pre_posi, $posi);
       if ($common > $longest{len}) {
           $longest{len} = $common;
           $longest{posi} = $pre_posi;
       }
   }
   $pre_posi = $posi;
}

printf "%s (%d)\n",
   $suf->get_string($longest{posi}, $longest{len}),
   $longest{len};

# 二つのsuffixを比較し先頭から何文字共通かを返す
sub compare_suffixies {
   my ($suf, $p1, $p2) = @_;
   my $len = 0;
   for (; $len + $p1 < $tsz and $len + $p2 < $tsz; $len++) {
       if ($suf->get_string($p1 + $len, 1) ne
           $suf->get_string($p2 + $len, 1)) {
           last;
       }
   }
   return $len;
}

ソートされた文字列を上から順番に取り出し、直前の文字列とつきあわせ
て、先頭からの共通文字列数を計算します。最長の文字列数を持つものを
$longest で保持しています。

準備と実行結果：

% cat aaa
ACGTTTCGACACAGCTCTAGACAGCTCCCCCCTAGACACCCAAAAAGAGAGAGATTTTGGGAGAGAG
% mkary -q aaa
% longest_repetition.pl aaa
ACAGCTC (7)

最長の繰り返し文字列は「ACAGCTC」で、7文字でした。

日本語でやるときは EUC-JP に変換してから mkary すると良いです。


■参考

- [を] 自分マイニング！ - Blogでよく使うフレーズは？[2005-01-18-3]
- [を] Suffix Array の解説文書のリンク集[2006-04-10-3]
- [を] SUFARY のパッケージに付属のドキュメント[2006-04-25-2]

■読者への挑戦

サンプルプログラム中の関数 compare_suffixes は、一文字ずつちまちま
取り出して比較しているので、ちょっと効率が悪いです。一文字ではなく
一気に何文字か get_string で取り出して比較するのが良いですね。
さて、ここで問題です！
そのときの文字数ってどうやって決めたら良いでしょうか？
このタスクに特化した方法がありますよ。

ヒント：最初は何文字かまとめて比較し、その後は一文字ずつ。