≪シーケンス比較｜Sequence Comparison｜oem_src≫:1つのシーケンスを別のシーケンスに変更する最小限の変更手順

≪シーケンス比較｜Sequence Comparison｜oem_src≫:1つのシーケンスを別のシーケンスに変更する最小限の変更手順
配列比較問題は分子生物学への応用のため、今年は多くの注目を集めている.シーケンス比較の問題は、ファイル比較やバージョン管理にも適用できます.たとえばローカルファイルがあります(またはプログラム)前後のバージョンを修正し、その中の異なる部分を簡単に抽出できるようにする必要がある.同じプログラムにも複数のバージョンがある場合があり、バージョン間の差が大きくなければ、ファイル全体を保存するのではなく、保存時に異なる部分だけを保存する必要がある.これらの場合は挿入と削除操作のみになり、他の場合は異なる修正に支払う必要がある異なる代価を払う.A=a 1 a 2...an,B=b 1 b 2...bnを2つの文字列にします.ここで、文字は有限集合(英語のアルファベット表など)から取られる.AをBにするには、(1)文字を挿入し、ある文字を文字列に挿入するには、(2)文字列からある文字を削除するには、(3)文字を置換し、ある文字を別の文字に置き換えるには、3つの方法がある.例えば、abbcをbabbに変えると、abbc->bbc->babc->babbとなり、合計2ステップの修正が必要になる.
質問:最小限の変更手順を求めます.
分析:通常、1つの文字列を別の文字列に変えるには多重の方法があり、いったいどれが最適なのかは定説しにくい.以下,帰納法を用いてこの問題の解を探索する.接頭辞サブ列a 1 a 2...ai(b 1 b 2..bi)はA(i)B(i)に、問題は最小限の修正ステップでA(n)をB(m)に変更することに変換される.まとめ:A(n-1)をB(m)に変更する最適な方法が知られていると仮定すると(複数の異なる最適な方法があるかもしれないが、ここではそのうちの1つを知っていると仮定する)、anを削除すればA(n)をB(m)に変更することができるのが最適なのか.では、私たちはどんな情報を知る必要がありますか?A(n−1)をB(m−1)に変更する修正回数と,A(n)をB(m−1)に変更する修正回数,すなわち,A,Bを最小に変更する条件で修正回数が最も少ないステップを構築する可能性を知る必要がある.
C(i,j)はA(i)がB(j)になる最小の代価であり、注目すべきはその最小の代価であり、それ自体を変えるのではない.我々が興味を持っているのは,i,jがn,mより小さいC(n,m)とあるC(i,j)の関係をどのように確立するかである.4つの可能性が3つの操作と1つのマッチングに対応していることは容易ではない.
削除:anを削除するには、A(n-1)をB(m)にしてから、C(n,m)=C(n-1,m)+1という文字を削除するのがベストです.
挿入:AからBへの最小変更がbmに一致する文字を挿入する必要がある場合、C(n,m)=C(n,m-1)+1があります.すなわち,A(n)を最小の代価でB(m−1)とし,bmと同じ文字を挿入する.
置換:bmをanで置換する場合は、まずA(n-1)からB(m-1)への最小変更を見つけ、次にanがbmに等しくない場合は、もう1つ追加します.
マッチング:anとbmが同じ場合、C(n,m)=C(n-1,m-1)
記C(i,j)={0(ai=bi),1(ai≠bi}
C(n,m)=min{C(n−1,m)+1,C(n,m−1)+1,C(n−1,m−1)+c(n,m)(置換またはマッチング)}
初期条件C(i,0)=I;C(0,j)=j
実装:

int min(int num1, int num2, int num3)
{
    int less = (num1 < num2) ? num1 : num2;
    return (less < num3) ? less : num3;
}

int **arralloc(int row,int column)
{
	if(row < 0 || column < 0)
		return 0;
	
	int **ptr = new int*[row]; //  m int*    
	for(int i = 0; i < row; ++i)
	{
		ptr[i] = new int[column];//  column int    
		memset(ptr[i],0,sizeof(int)*column);
	}
	return ptr;
}

int minimumchanges(const char *str1,const char *str2,int s1len, int s2len)
{
	if(str1 == NULL || str1 == NULL)
		return -1;

	int row = strlen(str1);
	int column = strlen(str2);
	int **arr = arralloc(row,column);

	for(int i = 0; i < column; ++i)
		arr[0][i] = i;
	//    1  ，  arr[0][0]      
	for(int i = 1; i < row; ++i)
		arr[i][0] = i;

	for(int i = 1; i<row; ++i)
	{
		for(int j = 1; j < column; ++j)
		{
			int deletion = arr[i-1][j]+1;
			int insertion = arr[i][j-1]+1;
			int substitution;
			if(str1[i]==str2[j])
				substitution = arr[i-1][j-1];
			else
				substitution = arr[i-1][j-1]+1;
			arr[i][j] = min(deletion,insertion,substitution);
		}
	}

	int minchanges = arr[row-1][column-1];

	for(int i = 0; i<row; ++i)
		delete []arr[i];
	delete []arr;

	return minchanges;
}

int _tmain(int argc, _TCHAR* argv[])
{
	minimumchanges("Saturday","Sunday",8,6);
	return 0;
}

まとめ:2 D配列を動的に生成するにはどうすればいいですか.この2 D配列はどのようにアドレスしますか.2 D配列にメモリを割り当てる方法はいくつありますか?