SUFARY Hacks (1) 最長の繰り返し文字列を探す
2006-04-24-2
[Programming][Algorithm]
週末に 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 を作りました。
て、先頭からの共通文字列数を計算します。最長の文字列数を持つものを
$longest で保持しています。
準備と実行結果:
日本語でやるときは EUC-JP に変換してから mkary すると良いです。
■参考
- [を] 自分マイニング! - Blogでよく使うフレーズは?[2005-01-18-3]
- [を] Suffix Array の解説文書のリンク集[2006-04-10-3]
- [を] SUFARY のパッケージに付属のドキュメント[2006-04-25-2]
■読者への挑戦
サンプルプログラム中の関数 compare_suffixes は、一文字ずつちまちま
取り出して比較しているので、ちょっと効率が悪いです。一文字ではなく
一気に何文字か get_string で取り出して比較するのが良いですね。
さて、ここで問題です!
そのときの文字数ってどうやって決めたら良いでしょうか?
このタスクに特化した方法がありますよ。
ヒント:最初は何文字かまとめて比較し、その後は一文字ずつ。
あまり使ってない(忘れてる)メソッドがいろいろありました。
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 で保持しています。
準備と実行結果:
最長の繰り返し文字列は「ACAGCTC」で、7文字でした。% cat aaa ACGTTTCGACACAGCTCTAGACAGCTCCCCCCTAGACACCCAAAAAGAGAGAGATTTTGGGAGAGAG % mkary -q aaa % longest_repetition.pl aaa 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 で取り出して比較するのが良いですね。
さて、ここで問題です!
そのときの文字数ってどうやって決めたら良いでしょうか?
このタスクに特化した方法がありますよ。
ヒント:最初は何文字かまとめて比較し、その後は一文字ずつ。
この記事に言及しているこのブログ内の記事