グループ化アルゴリズム

提供: dococo wiki
2017年9月10日 (日) 07:08時点におけるimported>Webmasterによる版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

素人的には「グループ化アルゴリズム」とか言ってしまいますが、数学的には「素集合データ構造」や「同値類の分類」や「同値関係」と言うらしいが正しい使い方かどうかは不明なので、用語は作者が勝手に名付けるとする。

課題

Yahoo知恵袋にも出したが、必要な情報が入手出来なく結局自己解決したのでその内容を書き残しておきたい。
やりたかったこと。
以下のサンプル例のように2つの関係する要素から関連性を持つ情報でグルーピングを行うプログラムを作成したい

(サンプル例)
データ
  1. A1000=B1000
  2. A1000=B1001
  3. A2000=B1000
  4. A2000=B1010
  5. A3000=B1012
  6. A3000=B1030
  7. A4000=B2000
  8. A4000=B2001
  9. A3000=B1000

考え方だが、1.と2.は左辺にA1000という共通のキーを持つのでB1000=B1001が成り立つ。同様に3.と4.はA2000で共通化するのでB1000=B1010となる。
ここから
B1000、B1001、B1010、B1012、B1030とB2000、B2001にグループ分けするアルゴリズムを考える

Perl実装

	use strict;
	use warnings;
	use utf8;
	use Encode;

	open (FILE, "<test.csv") or die "$!";
	
	my @union_a;#
	my @union_b;#
	my %count;

	while (my  $line = <FILE>) {
	$line = decode('cp932', $line);
	my @data =&ReturnCSV($line);
		push(@union_b, $data[1]);
	}
	@union_b = grep( !$count{$_}++, @union_b ) ;
	@union_b = sort {$a cmp $b} @union_b;
	for (0..@union_b-1){push(@union_a, $_);}
	
	my $Progress_End = @union_b-1;
	for (0..@union_b-1){
		my $Progress = $_;
		my $Parent_Node_Name = $union_b[$Progress];#

		seek(FILE, 0, 0);
		<FILE>;
		while (my  $line = <FILE>) {
		$line = decode('cp932', $line);
		my @data =&ReturnCSV($line);
		
			if ($Parent_Node_Name eq $data[1]){
				my $Search_Link_Info = $data[0];
				my $File_point = tell(FILE);
				seek(FILE, 0, 0);
				<FILE>;
				while (my  $line = <FILE>) {
				$line = decode('cp932', $line);
				my @data =&ReturnCSV($line);
					if ($Parent_Node_Name eq $data[1]){next;}
					if($Search_Link_Info eq $data[0]){
						my $Child_Node;
						for (0..@union_b-1){
							if($data[1] eq $union_b[$_]){$Child_Node = $_;}
						}
						if ($union_a[$Progress] <= $union_a[$Child_Node]){
							for (0..@union_a-1){
								if ($union_a[$_] eq $union_a[$Child_Node]){
									$union_a[$_] = $union_a[$Progress];
								}
							}
							$union_a[$Child_Node] = $union_a[$Progress];
						}
						else{
							
							for (0..@union_a-1){
								if ($union_a[$_] eq $union_a[$Progress]){
									$union_a[$_] = $union_a[$Child_Node];
								}
							}
							$union_a[$Progress] = $union_a[$Child_Node];
						}
					}
				}
				
				seek(FILE, $File_point, 0);
			}
		}

	print "$Progress/$Progress_End\n";
	}

	
	for (0..@union_b-1){print OUT "$union_b[$_], $union_a[$_]\n";}
	close (FILE);



sub ReturnCSV
{
	my (@RETURN)=();
	my ($CSV_DATA) = @_;
	$CSV_DATA =~ tr/"//d;
	chomp($CSV_DATA);
	@RETURN = split (/,/ , $CSV_DATA);
	return(@RETURN);
}