線分の等しくない部分のみを取得する

Question

ここでやるべきことは、「最も長い共通部分文字列の問題」とも呼ばれる最も長い共通シーケンス（LCS）を見つけるという非常に一般的な作業です。これは通常、パス名または URI セットに対して最も長い共通ディレクトリを印刷するなどの操作に使用されます。あなたの場合、反対を行うには、各行の一部を出力します。いいえ最も長いシーケンスの一部です。

希望の言語でLCSを見つけるために独自のアルゴリズムを書くことができますが、Perlにはすでにそれを実装するモジュールがあります。アルゴリズム::差。このモジュールはPerl標準ライブラリには含まれておらず、配布パッケージcpanと一緒にインストールするか、配布パッケージからインストールする必要があります（たとえば、DebianとUbuntuとMintなどの派生製品ではパッケージ化するかsudo apt-get install libalgorithm-diff-perlどうかを使用してインストールできます）

次のコードは、各入力行を読み取り、それを単語の配列に分割し、各キーワードの最も長い共通シーケンス（各行の最初の単語）のサイズを計算します。

すべての入力行を読み取った後、入力を最初から読み直し、各入力行のプライベート部分を印刷します。foo入力例のようにキーワードが一度だけ発生する場合は、その行をそのまま印刷します（if出力から一意のキーワードを除外するには、これを実行するブロックを削除またはコメントアウトします）。

#!/usr/bin/perl

use strict;
use Algorithm::Diff qw(LCS_length);

my %keywords;
my %LCS;

# get input filename(s)
my @input_files = @ARGV;

# First read in each line and figure out the longest common
# sequence for each keyword
# NOTE: this code assumes that two samples for each keyword
# is enough (i.e. it compares only the first two input lines
# which have the same keyword)
while(<>) {
  chomp;
  my @words = split;
  my $keyword = $words[0];
  
  if (defined $keywords{$keyword}) {
   if (! defined($LCS{$keyword}) ) {
      $LCS{$keyword} = LCS_length(
         \@{ $keywords{$keyword}->[0] },
         \@words
      );
    };
  } else {
    push @{ $keywords{$keyword} }, \@words;
  };
};

# process the same input file(s) again to print the
# non-common portions of each line
push @ARGV, @input_files;

while(<>) {
  chomp;
  my @words = split;
  my $keyword = $words[0];
  
  # if the keyword is unique, just print the line
  if (! defined($LCS{$keyword})) {
    print $_, "\n";
    next;
  };
  
  my $len = $#words;
  my $lcs = $LCS{$keyword} - 1;
  $lcs++ if $lcs == 1;
  print join(" ", $keyword, @words[$lcs..$len]), "\n";
};

出力例（上記のスクリプトを次に保存しnot-equal.plて実行可能にした後chmod）：

$ ./not-equal.pl input.txt 
foo 123
keyword-a text to show
keyword-a some other arbitrary text
keyword-a 99 more to show
keyword-b 1
keyword-b 2 3 show me

注：スペースで連結された単語の配列を印刷するので、どの入力行の 2 つ以上の空白文字シーケンスは、次のように変換されます。単一のスペース文字。それが望ましくない場合は、独自のLCSアルゴリズムを実装する必要があります。まず、Googleで「最も長い共通シーケンス」（または「最も長い共通部分文字列」）を検索し、両方を調べる必要があります。https://en.wikipedia.org/wiki/Longest_common_substring_problemそしてhttps://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring。

ところで、書かれているように、このスクリプトは入力ファイルを再度読み取る必要があり、標準入力が見つからないため、標準入力を処理できません。それはいstdinを処理するバージョンを書くことが可能です（実際、このスクリプトの最初のバージョンはまさにそれをしました）。ただし、最初のループでは各行を配列として読み取る必要があり、2番目のループでは配列を繰り返す必要があります。強制。入力ファイルのサイズに応じて大量のメモリを消費できます。

ここに最初のエントリを保存する代わりに、各入力行を %keywords ハッシュに保存し続ける最初のバージョンがあります。最も大きな問題は、ハッシュが本質的に順序がないため、出力順序が半ランダムであることです（または私が行ったようにキーごとにソートされます）。そのため、入力ファイルを2回読み込むように変更しました。一度はLCSを見つけ、2番目は出力を生成します（例入力がソートされているにもかかわらず...実際の内容が何であるかわかりません。データに何が起こりますか？）。

#!/usr/bin/perl

use strict;
use Algorithm::Diff qw(LCS_length);

my %keywords;
my %LCS;

while(<>) {
  chomp;
  my @words = split;
  my $keyword = $words[0];

  if (defined $keywords{$keyword} && ! defined($LCS{$keyword}) ) {
    $LCS{$keyword} = LCS_length(
      \@{ $keywords{$keyword}->[0] },
      \@words
    );
  };

  push @{ $keywords{$keyword} }, \@words;
};

foreach my $keyword (sort keys %keywords) {
  foreach my $line (keys @{ $keywords{$keyword} } ) {
    my @words = @{ $keywords{$keyword}[$line] };
    if (!defined($LCS{$keyword})) { 
      print join(" ", @words), "\n"; 
       next
    };

    my $len = $#words;
    my $lcs = $LCS{$keyword} - 1;
    $lcs++ if $lcs == 1;
    print join(" ", $keyword, @words[$lcs..$len]), "\n";
  };
};

Answer 1