【シリアルおよびシーケンス処理6】LCS最長共通サブシーケンス

LCS:最長共通サブシーケンスとも呼ばれます.その中性子配列(subsequence)の概念は列のサブ列とは異なる.連続するとは限らないが、文字列Xから順番に取り出される文字列です.例えば、シリアル「AAAG」は、シリアル「CGATAATTGAGA」のサブシーケンスである.
 
 
文字列の類似性問題は2つの列間の最長共通サブシーケンス(LCS)を解くことによって得ることができる.もちろん,ノックアウトアルゴリズムを用いて列のすべてのサブシーケンスをリストすると,合計2^n種であり,各サブシーケンスが別の列のサブシーケンスであるかどうかはO(m)の時間的複雑度を必要とするため,このノックアウト法の時間的複雑度はO(m*(2^n))指数レベルであり,効率はかなり恐ろしい.この問題を解決するために動的計画アルゴリズムを採用した.
 
 
ダイナミックプランニングアルゴリズムによる最長共通サブシーケンスの解決
 
X=[0,1,2....n]Y=[0,1,2...m]の2つの文字列がある場合.L(i,j)をX[0...i]とY[0...j]の間の最長共通サブシーケンスの長さとして定義する.動的計画思想(複雑な問題の最適解はサブ問題の最適解とサブ問題の重なり合う性質によって決定される)によって.私たちはこの2つの状況を考えています.
 
(1)X[i]=Y[j]の場合、L(i,j)=L(i-1,j-1)+1となる.証明は簡単です.
(2)X[i]!=Y[j]の場合、このことを説明するX[0...i]とY[0...j]の最長共通サブシーケンスにX[i]とY[j]を同時に含むことは絶対に不可能である.共通のサブシーケンスはX[i]で終わる可能性があり、Y[j]で終わる可能性があり、X[i]またはY[j]を含まない可能性がある.したがって
                               L(i, j)= MAX{L(i-1 , j), L(i, j-1)}
 
LCSダイナミックプランニングJavaソース

package net.hr.algorithm.string;

/**
 *       LCS
 * @author heartraid
 */
public class LCS {

	/**   X     */
	private char[] charArrayX=null;
	/**   Y     */
	private char[] charArrayY=null;

	public LCS(String sa,String sb){
		charArrayX=new char[sa.length()+1];
		System.arraycopy(sa.toCharArray(),0,charArrayX,1,sa.length());
		charArrayY=new char[sb.length()+1];
		System.arraycopy(sb.toCharArray(),0,charArrayY,1,sb.length());
	}
	
	/**
	 *             
	 */
	public void getLCS(){
		
		int[][] length=new int[charArrayX.length+1][charArrayY.length+1];
		
		for(int m=1;m<charArrayX.length;m++)
			for(int n=1;n<charArrayY.length;n++){
				if(charArrayX[m]==charArrayY[n]){
					length[m][n]=length[m-1][n-1]+1;
				}
				else
					length[m][n]=max(length[m-1][n],length[m][n-1]);
					
			}
		//         
		String lcstr="";
		int x=charArrayX.length-1;
		int y=charArrayY.length-1;
		while(x>=1&&y>=1){
			if(charArrayX[x]==charArrayY[y]){
				lcstr=charArrayX[x]+lcstr;
				x--;
				y--;
			}else{
				if(length[x-1][y]<=length[x][y-1])
					y--;
				else
					x--;	
			}
		}
		System.out.println("        ："+lcstr+" [length="+lcstr.length()+"]");
	}
	/**
	 *     
	 */
	private int max(int m,int n){
		return m>n?m:n;
	}	
	
	/**
	 *   
	 */
	public static void main(String[] args) {
		LCS lcs=new LCS("GTTCCTAATA","CGATAATTGAGA");
		lcs.getLCS();
	}

}

     
ここで、getLength()の役割は、最も長い共通サブストリングの長さを再帰的に取得し、再帰中に各サブストリング間で最も長い共通サブストリングの長さを取得するステータステーブルlcs[][]を得ることであり、このテーブルの実行結果は以下の通りである.
 
      C G A T A A T T G A G A
   0 0 0 0 0 0 0 0 0 0 0 0 0 G 0 0 1 1 1 1 1 1 1 1 1 1 1 T 0 0 1 1 2 2 2 2 2 2 2 2 2 T 0 0 1 1 2 2 2 3 3 3 3 3 3 C 0 1 1 1 2 2 2 3 3 3 3 3 3 C 0 1 1 1 2 2 2 3 3 3 3 3 3 T 0 1 1 1 2 2 2 3 4 4 4 4 4 A 0 1 1 2 2 3 3 3 4 4 5 5 5 A 0 1 1 2 2 3 4 4 4 4 5 5 6 T 0 1 1 2 3 3 4 5 5 5 5 5 6 A 0 1 1 2 3 4 4 5 5 5 6 6 6
 
 
 
赤い数字の位置は最長の共通サブシーケンス:CTATTAを明らかにした.すなわち,このテーブルを解析すると最長の共通サブシーケンス文字列が得られる.
 
どうしてですか.テーブルの遡及プロセスにより,最も長い共通サブシーケンスが後方から前方に再構成されるためである.任意の位置lcs[i][j]について、X[i]=Y[j]かどうかを決定する.もしそうであれば、X[i]は最も長い共通のサブシーケンスの文字である必要があります.そうでない場合、lcs[i,j−1]とlcs[i−1,j]の間の大きい方に移動します.
 
 
動的計画方法LCS効率:
 
動的プランニング手法による最長共通サブシーケンスの構築にはO(m*n)の代価が必要であり,また,最長共通サブシーケンスを得るにはO(m+n)の時間が必要でcsl[][]配列を読み出す.それでも、その時間の複雑さは、力の乏しい指数レベルよりもずっと強い.
 
 
 
質問拡張:A,B,Cは、同じ定数サイズのアルファベットから取られた3つの長さnの文字列とします.3つの列の最長共通サブ列を探し出すO(n^3)の時間アルゴリズムを設計した.(「Algorithm Design」(中国語版:アルゴリズム分析と設計)-Chapter 9-テキスト処理-革新問題C-9.18)
 
分析:「LCS最長共通サブシーケンス」の動的計画アルゴリズムにより、Javaソースコードを以下のように設計することができる.

public class TriLCS{
	
	char[] charA=null;
	char[] charB=null;
	char[] charC=null;
	
	
	public TriLCS(String sa,String sb,String sc){
		charA=new char[sa.length()+1];
		System.arraycopy(sa.toCharArray(),0,charA,1,sa.length());
		charB=new char[sb.length()+1];
		System.arraycopy(sb.toCharArray(),0,charB,1,sb.length());
		charC=new char[sc.length()+1];
		System.arraycopy(sc.toCharArray(),0,charC,1,sc.length());
	}
	
	public void getTriLCS(){
		
		int[][][] length=new int[charA.length][charB.length][charC.length];
		
		for(int a=1;a<charA.length;a++)
			for(int b=1;b<charB.length;b++)
				for(int c=1;c<charC.length;c++){
					
					if(charA[a]==charB[b]&&charA[a]==charC[c]){
						length[a][b][c]=length[a-1][b-1][c-1]+1;
					}
					else if(charA[a]==charB[b]&&charA[a]!=charC[c]){
						length[a][b][c]=max(length[a-1][b-1][c],length[a][b][c-1]);
					}
					else if(charA[a]==charC[c]&&charA[a]!=charB[b]){
						length[a][b][c]=max(length[a-1][b][c-1],length[a][b-1][c]);
					}
					else if(charB[b]==charC[c]&&charA[a]!=charB[b]){
						length[a][b][c]=max(length[a][b-1][c-1],length[a-1][b][c]);
					}
					else{
						length[a][b][c]=max(length[a-1][b][c],length[a][b-1][c],length[a][b][c-1],length[a-1][b-1][c],length[a-1][b][c-1],length[a][b-1][c-1]);
					}					
				}
		
		
		
		//         
		String lcstr="";	
		int a=charA.length-1;
		int b=charB.length-1;
		int c=charC.length-1;
		while(a>=1&&b>=1&&c>=1){
			if(charA[a]==charB[b]&&charA[a]==charC[c]){
				lcstr=charA[a]+lcstr;
				a--;
				b--;
				c--;
			}
			else if(charA[a]==charB[b]&&charA[a]!=charC[c]){
				if(length[a-1][b-1][c]<=length[a][b][c-1])
					c--;
				else{
					a--;
					b--;
				}
			}
			else if(charA[a]==charC[c]&&charA[a]!=charB[b]){
				if(length[a-1][b][c-1]<=length[a][b-1][c])
					b--;
				else{
					a--;
					c--;
				}
			}
			else if(charB[b]==charC[c]&&charA[a]!=charB[b]){
				if(length[a][b-1][c-1]<=length[a-1][b][c])
					a--;
				else{
					b--;
					c--;
				}
			}
			else{
				int maxize=max(length[a-1][b][c],length[a][b-1][c],length[a][b][c-1],length[a-1][b-1][c],length[a-1][b][c-1],length[a][b-1][c-1]);
				if(maxize==length[a-1][b][c])
					a--;
				if(maxize==length[a][b-1][c])
					b--;
				if(maxize==length[a][b][c-1])
					c--;
				if(maxize==length[a-1][b-1][c]){
					a--;
					b--;
				}
				if(maxize==length[a-1][b][c-1]){
					a--;
					c--;
				}
				if(maxize==length[a][b-1][c-1]){
					b--;
					c--;
				}	
			}
		}
		
		System.out.println("     ："+lcstr+"(length="+length[charA.length-1][charB.length-1][charC.length-1]+")");
	}
	
	/**
	 *     
	 */
	private int max(int m,int n){
		return m>n?m:n;
	}
	/**
	 *     
	 */
	private int max(int x,int y,int z,int k,int m,int n){
		int maxizen=0;
		if(maxizen<x) maxizen=x;
		if(maxizen<y) maxizen=y;
		if(maxizen<z) maxizen=z;
		if(maxizen<k) maxizen=k;
		if(maxizen<m) maxizen=m;
		if(maxizen<n) maxizen=n;
		return maxizen;
	}
	
	public static void main(String[] args){
		TriLCS tri=new TriLCS("aadsbbbcs","adsabcs","adbsbsdcs");
		tri.getTriLCS();
	}	
}