// DPmatch.v DPマッチングを用いた最長共通部分系列の抽出

module DPmatch(temp,String_A,String_B:input,value,arrow:output)
int temp on pixel;    // 並列処理のためのダミー画像
int String_A on all;  // 入力文字系列1
int String_B on all;  // 入力文字系列2
int value on pixel;   // DPマッチングによる共通系列長の表
int arrow on pixel;   // 共通系列長の表においてたどる方向
#vios divtype DPmatch column
{
    parallel{
	int my_x,my_y; // ワーキングセットの持つ画素の座標
	int pre_x,pre_y,pre_xy;  // 依存データを格納する変数

	// 注目要素の座標を取得
	my_x = hotx(value);
	my_y = hoty(value);

	// 表の注目要素の上もしくは左隣に要素がない場合
	if(my_x == 0 || my_y == 0){
	    value[][] = 0;
	    arrow[][] = 3;
	}
	// 表の注目要素の上もしくは左隣に要素ある場合
	else{
	    // 通信ストリームを用いて処理結果データを取得
	    com(my_x-1, my_y) >> pre_x;
	    com(my_x, my_y-1) >> pre_y;
	    com(my_x-1, my_y-1) >> pre_xy;

	    // 2つの系列の比較を行ない、表の該当位置の値を決める
	    if(String_A[[my_x]][[0]] == String_B[[0]][[my_y]]){
		value[][] = pre_xy + 1;
		arrow[][] = 0;
	    }
	    else{
		if(pre_x > pre_y){
		    value[][] = pre_x;
		    arrow[][] = 2;
		}
		else{
		    value[][] = pre_y;
		    arrow[][] = 1;
		}
	    }
	}
	// このワーキングセットでの処理結果データを必要とする
	// ワーキングセットにデータを転送
	com(my_x+1, my_y) << value[][];
	com(my_x, my_y+1) << value[][];
	com(my_x+1, my_y+1) << value[][];
    }
}

DPマッチングメインフローへ戻る

VIOS トップページ