4

私はPerlに比較的慣れていないので、比較的高度な行列計算を行う必要があり、使用するデータ構造がわかりません。

これがこれに適したフォーラムであるかどうかはわかりませんが、Perlの多次元配列に次の行列があるとします。

0.2    0.7    0.2 
0.6    0.8    0.7
0.6    0.1    0.8
0.1    0.2    0.9
0.6    0.3    0.0
0.6    0.9    0.2

このマトリックスで、特定のしきい値（ 0.5など）よりも高い連続値に対応する列セグメントを特定しようとしています。

たとえば、このマトリックスをしきい値設定すると、次のようになります。

0    1    0 
1    1    1
1    0    1
0    0    1
1    0    0
1    1    0

ここで最初の列に焦点を当てると、次のようになります。

0 
1 
1
0 
1 
1

2つの連続したセグメントがあることがわかります。

0 1 1 0 1 1

  • 最初のトラック（1つのシーケンス）はインデックス1で始まり、インデックス2で終わります。
  • 2番目のトラック（1つのシーケンス）は、インデックス4で始まり、インデックス5で終わります。

元のマトリックスでそのようなトラックをすべて検出したいのですが、どのように進めるか、またはどのPerlデータ構造がこれに最も適しているかわかりません。

理想的には、インデックス付けが簡単なものが必要です。たとえば、変数を使用すると仮定するとtracks、最初の列（インデックス0）のインデックスを次のように格納できます。

# First column, first track
$tracks{0}{0}{'start'} = 1; 
$tracks{0}{0}{'end'}   = 2;

# First column, second track
$tracks{0}{1}{'start'} = 4; 
$tracks{0}{1}{'end'}   = 5;

# ...

Perlでこの問題に取り組むために使用できる優れたデータ構造やライブラリは何ですか？

4

3 に答える 3

2

私はアルゴリズムの答えを出しているだけで、好きな言語でコーディングできます。

問題をサブ問題に分割します。

  1. しきい値処理：入力の保存方法に応じて、これは$ n $次元の行列に対する反復、または行列がスパースの場合はツリー/リストの走査のように単純になります。これは簡単なことです。

  2. 連続セグメントを見つけるためのアルゴリズムは、「ランレングスエンコーディング」と呼ばれます。1 0 0 1 1 1 1 0 1のような重複の可能性があるシーケンスを取り、次の要素とその要素の数を示す別のシーケンスを返します。したがって、たとえば、上記のシーケンスは1 1 0 2 1 4 0 1 1 1になります。エンコーディングは一意であるため、反転したい場合は問題ありません。

最初の1は、元の入力が1で始まるために存在し、最初の0は、1の後に0が存在するために存在し、4番目の数値は2つの連続するゼロがあるため、2になります。自分でやりたくない場合は、無数のrleエンコーダがあります。その主な目的は圧縮であり、同じアイテムを長期間実行している場合は、その目的に適度に機能します。ニーズによっては、水平、垂直、さらには斜めに実行する必要がある場合があります。

正確なアルゴリズムは、データ構造とアルゴリズムに関するすべての古典的な本にあります。Cormen-Leiseron-Rivest-Stein：'Introduction to Algorithms'を最初に提案し、次にKnuthを提案します。

要点を理解したら、しきい値をRLEと安全に「融合」して、入力を2回繰り返すことを回避できます。

于 2012-09-12T21:13:41.437 に答える
1

これはあなたが望むことをするようです。理想的な形式は結果で何をしたいかに完全に依存するため、私はあなたが提案した形式でデータを表現しました

これは、各列から0と1のリストを計算し、両端にゼロのバリア値（リスト$prevに1つと1つfor）を追加してから、リストをスキャンして1と0の間の変化を探すことで機能します。

変更が見つかるたびに、トラックの開始または終了が記録されます。が未定義の場合$start、現在のインデックスはセグメントの開始として記録されます。それ以外の場合、現在のセグメントは現在のインデックスより1つ少ない値で終了します。ハッシュはキーstartを使用して作成され、配列endにプッシュされます。@segments

ネストされたループの最後のセットは、計算されたデータを質問で示した形式でダンプします

use strict;
use warnings;

use constant THRESHOLD => 0.5;

my @data = (
  [ qw/ 0.2    0.7    0.2 / ],
  [ qw/ 0.6    0.8    0.7 / ],
  [ qw/ 0.6    0.1    0.8 / ],
  [ qw/ 0.1    0.2    0.9 / ],
  [ qw/ 0.6    0.3    0.0 / ],
  [ qw/ 0.6    0.9    0.2 / ],
);

my @tracks;

for my $colno (0 .. $#{$data[0]}) {

  my @segments;
  my $start;
  my $prev = 0;
  my $i = 0;

  for my $val ( (map { $_->[$colno] > THRESHOLD ? 1 : 0 } @data), 0 ) {
    next if $val == $prev;
    if (defined $start) {
      push @segments, { start => $start, end=> $i-1 };
      undef $start;
    }
    else {
      $start = $i;
    }
  }
  continue {
    $prev = $val;
    $i++;
  }

  push @tracks, \@segments;
}

# Dump the derived @tracks data
#
for my $colno (0 .. $#tracks) {
  my $col = $tracks[$colno];
  for my $track (0 .. $#$col) {
    my $data = $col->[$track];
    printf "\$tracks[%d][%d]{start} = %d\n", $colno, $track, $data->{start};
    printf "\$tracks[%d][%d]{end} = %d\n", $colno, $track, $data->{end};
  }
  print "\n";
}

出力

$tracks[0][0]{start} = 1
$tracks[0][0]{end} = 2
$tracks[0][1]{start} = 4
$tracks[0][1]{end} = 5

$tracks[1][0]{start} = 0
$tracks[1][0]{end} = 1
$tracks[1][1]{start} = 5
$tracks[1][1]{end} = 5

$tracks[2][0]{start} = 1
$tracks[2][0]{end} = 3
于 2012-09-12T22:34:19.447 に答える
1

Perlによる多次元配列のサポートが不十分であることを嘆き、私はすぐに自分自身の小さな解決策をまとめていることに気づきました。アルゴリズムはボロディンのアイデアにかなり似ていますが、構造が少し異なります。

sub tracks {
  my ($data) = @_; # this sub takes a callback as argument
  my @tracks;      # holds all found ranges
  my @state;       # is true if we are inside a range/track. Also holds the starting index of the current range.
  my $rowNo = 0;   # current row number
  while (my @row = $data->()) { # fetch new data
    for my $i (0..$#row) {
      if (not $state[$i] and $row[$i]) {
        # a new track is found
        $state[$i] = $rowNo+1; # we have to pass $rowNo+1 to ensure a true value
      } elsif ($state[$i] and not $row[$i]) {
        push @{$tracks[$i]}, [$state[$i]-1, $rowNo-1]; # push a found track into the @tracks array. We have to adjust the values to revert the previous adjustment.
        $state[$i] = 0; # reset state to false
      }
    }
  } continue {$rowNo++}
  # flush remaining tracks
  for my $i (0..$#state) {
    push @{$tracks[$i]}, [$state[$i]-1, $rowNo-1] if $state[$i]
  }
  return @tracks;
}

@stateトラック内にいるかどうかを示すフラグとして、またトラック開始インデックスのレコードとしても機能します。状態および追跡配列では、インデックスは現在の列を示します。

データソースとして外部ファイルを使用しましたが、これは既存のアレイなど、あらゆるものに簡単に接続できます。唯一の契約は、それ以上のデータが利用できない場合に、true値とfalse値の任意のシーケンスと空のリストを返さなければならないということです。

my $limit = 0.5
my $data_source = sub {
  defined (my $line = <>) or return (); # return empty list when data is empty
  chomp $line;
  return map {$_ >= $limit ? $_ : 0} split /\s+/, $line; # split the line and map the data to true and false values
};

入力としてコピーして貼り付けたデータを使用すると、出力として次の印刷出力が得られます（印刷コードは省略）。

[ [1 2], [4 5] ]
[ [0 1], [5 5] ]
[ [1 3] ]

あなたの構造では、これは

$tracks[0][0][0] = 1;
$tracks[0][0][1] = 2;

$tracks[0][1][0] = 4;
...;

これをハッシュに変更すると、元の値などのデータがさらに組み込まれる可能性があります。

于 2012-09-12T23:09:58.763 に答える