1

だから私はPerlとPythonの両方でいくつかの練習問題を行ってきました（2つから選択するようなものです）、Githubと同じように独自の差分アルゴリズムを作成する必要があるという問題がありました。最長共通部分列問題が解決策の大きな部分を占めていることを知るところまで来ました。LCSのウィキペディアのページを参考にしましたが、まだ差分部分がわかりません。

また、Algorithm:Diff のようなモジュールが CPAN に既に存在することも認識していますが、これはほとんど練習用であり、ごまかしのように感じます。

私はアルゴリズムの python/pseudocode バージョンを理解しましたが、Perl にはないように見える多次元配列でそれを行う予定です。

これで、Perl で Longest Common Subsequence の長さを正常に取得できるところまで来ました。

基本的に、私が考えることができる疑似コード (ほぼ Python に似ていますが、Perl 用であると想定されています) は次のようなものです。

function lengthOfLCS(string1, string2){
    if length(string1) == 0 or length(string2) == 0:
         return 0
    else if string1[0] eq string2[0]: 
         return 1+ lengthOfLCS(stringA[1:], stringB[1:])
    return max(lengthOfLCS(string1, string2[1:], lengthOfLCS(string1[1:], string2))

まだ実装していませんが、基本的には2つの文字列のLCSの長さを計算する方法だと思いますか?

出力に関しては、"HUMAN" & "CHIMPANZEE" (LCS = HMAN) に対して 4 を返す必要があります。

だから私が求めているのは、この時点から Perl を使用して Diff を印刷するにはどうすればよいかということです。LCSの長さだけではなく、代わりにリスト/配列を返す必要があることを認識しています。これは、LCS関数で多次元リストを返し、後で別のdiff関数で処理することで実行できます.

私はPerlを初めて使用するので、ポインタ/ヒントをいただければ幸いです。ありがとう。

4

1 に答える 1

0

入力として 2 つの配列参照を必要とし、一致する要素のインデックスを含む 2 つの要素配列の配列を返す、Perl でのLCSの参照実装を使用できます。

use LCS;
my $lcs = LCS->LCS( [qw(a b)], [qw(a b b)] );
# $lcs now contains an arrayref of matching positions
# same as
$lcs = [
  [ 0, 0 ],
  [ 1, 2 ]
];

LCS は従来のアルゴリズムを使用し、LCS を反復的に読み取ります (wollmers-perl.blogspot.de の私のブログ投稿 Loopify Recursions を参照してください)。したがって、コードから学びたい場合は、subs LCS() と _lcs() を調べてください。

差分、つまり編集スクリプトが必要な場合は、LCS 配列から再構築できます。

メソッド lcs2align() はほぼこれを行います。

use Data::Dumper;
use LCS;
print Dumper(
  LCS->lcs2align(
    [qw(a   b)],
    [qw(a b b)],
    LCS->LCS([qw(a b)],[qw(a b b)])
  )
);
# prints
$VAR1 = [
          [
            'a',
            'a'
          ],
          [
            '',
            'b'
          ],
          [
            'b',
            'b'
          ]
];

sdiff() 形式の差分 ( Algorithm::Diff を参照) は次のようになります。

[
  [ 'u', 'a', 'a'  ],
  [ '+', '',  'b'  ],
  [ 'u', 'b', 'b'  ],
]

アラインメントから編集スクリプトを取得する方法は簡単なので、演習として残します。

より高速な実装が必要な場合は、LCS::Tiny、または最速の純粋な Perl 実装 LCS::BV、または大規模な場合は最速の Algorithm::Diff::XS を使用できます (私のブログ記事 Tuning Algorithm::Diff at wollmers-perl を参照してください)。 .blogspot.de)

LCS に基づく編集スクリプトは、SES (最短編集スクリプト) を自動的に提供しないことに注意してください。LCS は、挿入と削除のみを許可する編集操作に基づいています (単純な編集距離)。SES アルゴリズムは通常、レーベンシュタイン距離 (挿入、削除、不一致) を最小化します。

于 2015-06-18T08:32:26.973 に答える