Location : Home > Languages > Perl > Package Title : Algorithm::LCSS

名称

　Algorithm::LCSS - 最長共通部分列の抽出

概要

use Algorithm::LCSS qw( LCSS CSS CSS_Sorted );

my $lcss_ary_ref = LCSS( \@SEQ1, \@SEQ2 );  # 配列への参照
my $lcss_string  = LCSS( $STR1, $STR2 );    # 文字列
my $css_ary_ref = CSS( \@SEQ1, \@SEQ2 );    # 配列の配列への参照
my $css_str_ref = CSS( $STR1, $STR2 );      # 文字列の配列への参照
my $css_ary_ref = CSS_Sorted( \@SEQ1, \@SEQ2 );  # 配列の配列への参照
my $css_str_ref = CSS_Sorted( $STR1, $STR2 );    # 文字列の配列への参照

説明

　本モジュールは LCSS を実装するために Algoritm::Diff を利用しており、String::LCSS よりも圧倒的に速い。
　メソッドに配列参照を渡せば配列参照を取得する。文字列を渡せば文字列または文字列への配列の参照を取得する。

メソッド

LCSS

　最長共通部分列を返す。複数ある場合（同じ長さを持つ）、替わりに CSS を使うとよい。

my $lcss_ary_ref = LCSS( \@SEQ1, \@SEQ2 );  # 配列への参照
my $lcss_string  = LCSS( $STR1, $STR2 );    # 文字列

CSS

　（ソートせずに）全ての共通部分列を返す。

my $css_ary_ref = CSS( \@SEQ1, \@SEQ2 );  # 配列の配列への参照
my $css_str_ref = CSS( $STR1, $STR2 );    # 文字列の配列への参照

CSS_Sorted

　最長のものから最短のものへと長さの順にソートして全ての共通部分列を返す。

my $css_ary_ref = CSS_Sorted( \@SEQ1, \@SEQ2 );  # 配列の配列への参照
my $css_str_ref = CSS_Sorted( $STR1, $STR2 );    # 文字列の配列への参照

エクスポート

　デフォルトではなし。

著者

　Dr James Freeman, <james.freeman@id3.org.uk>

参考資料

　Perl

【解説】

1. 複数の文字列の間で共通に含まれる部分列を共通部分列と言い、共通部分列のなかで最長のものを最長共通部分列という。通常は英語では longest common subsequence なので LCS と略されることが多いと思うのだが。

Updated : 2006/11/16