Longest Common Subsequences

Morning guys... Ini postingan tentang algoritma pertamaku. Setelah kemarin dapet tugas dari dosen tentang problem ini, aku putuskan untuk mempublish aja algoritma ini. Semoga bermanfaat buat kita bersama, amin...

A. Longest Common Subsequences???

Longest Common Subsequences adalah masalah pencarian subsequence (subrangkaian) bersama terpanjang dari beberapa buah rangkaian (biasanya 2 rangkaian).

B. Subsequence???

Sebelum membahas LCS lebih lanjut, sebaiknya kita kenalan dulu sama subsequence. Sebuah subsequence adalah sebuah rangkaian yang terbentuk dari rangkaian lain dengan menghapus beberapa elemen tanpa menghapus urutan dari elemen sisanya.

Contoh:
Rangkaian (A,B,C,D,E,F) memiliki subsequence (A,B,D).
Rangkaian (A,C,B,D,E,G,C,E,D,B,G) memiliki subsequence (B,C,D,G) dengan index (3,7,9,11).

C. Common Subsequence???

Diberikan dua buah subsequence X dan Y, maka sebuah sequence G dikatakan menjadi common subsequence (subsequence bersama) dari X dan Y jika G adalah sebuah subsequence dari X dan Y.

Contoh:
X = < A,C,B,D,E,G,C,E,D,B,G >
Y = < B,E,G,C,F,E,U,B,K >
maka sebuah common subsequence dari X dan Y adalah: G = < B,E,E >

G = < B,E,E > bukanlah common subsequence terpanjang, dimana G mempunyai panjang 3, karena ada common subsequence lain, salah satunya < B,E,E,B >, yang mempunyai panjang 4.

Common subsequence terpanjangnya adl < B,E,G,C,E,B >
Lihat:
X = < A,C,B,D,E,G,C,E,D,B,G >
Y = < B,E,G,C,F,E,U,B,K > 

Aplikasi Subsequence

Subsequence diaplikasikan dalam computer science khususnya di bidang bioinformatics. Computer digunakan untuk membandingkan dan menganalisis DNA.

Dua buah DNA:
ORG1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA
Subsequence digunakan untuk menentukan seberapa mirip kedua DNA tersebut.

D. Subsequence Tidak Sama Dengan Substring

Sebuah String bisa dikatakan sebagai sequence, tapi sebuah substring tidak dapat dikatakan sebagai subsequence. Karena setiap substring adalah bagian yang berurutan dari sebuah string. Hal ini berbeda dengan subsequence yang merupakan bagian yang tidak selalu berurutan dari sequence aslinya. Substring adalah bagian yang berurutan dari string, tapi subsequence belum tentu.

E. Algoritma Pencarian LCS

Setelah kita kenal dengan subsequence, sekarang kita masuk pada algoritma pencarian LCS. Untuk mencari LCS dari sequence X dengan panjang m dan Y dengan panjang n dapat menggunakan matrix dua dimensi dengan ukuran (m+1) x (n+1) dengan ketentuan:

0<=i<=m dan 0<=j<=n  

T[i,j] =

• 0 --->> jika i=0, j=0; 
• T[i-1,j-1]+1 --->> jika xi = yj;  
• max (T[i-1,j],T[i,j-1]); --->> yang lain

Panjang dari LCS dari X dan Y adalah T[m,n]

F. Source Code

Uuntuk mencari LCS, digunakan dua buah aray dua dimensi lcs[][] dan direction[][]. lcs[][] akan menampung nilai-nilai yang diinisiasi berdasarkan algoritma pencarian lcs di atas dan direction[][] akan menampung karakter:

• "\" (diagonal)
• "^" (up)
• "<" (left) 

yang digunakan untuk mencari subsequence terpanjang dengan cara back tracking.

Gambar 1. Pencarian LCS dengan input "A-G-C-G-A" dan "C-A-G-A-T-A-G-A-G"

Class LongestCommonSubsequence

/**
 * Longest Common Subsequence.
 *            | 0                             if i=0 || j=0
 * lcs(i,j) = | lcs(i-1,j-1) + 1,             if one[i]=two[j]
 *            | max(lcs(i-1,j), lcs(i,j-1)),  else(if lcs(i-1,j)==lcs(i,j-1),
 *                                                 then lcs(i,j)=lcs(i-1,j))
 * Boundary conditions:
 * so we think that index start at 1
 */

package lcs;

/**
 *
 * @author Nur Dian Wahyu S
 */

public class LongestCommonSubsequence {

    private String one;
    private String two;
    private int lcs[][];
    private Direction direction[][];

    public LongestCommonSubsequence(String a, String b)
    {
        this.one = a;
        this.two = b;

        init();
    }

    public void init()
    {

        lcs = new int[one.length()+1][two.length()+1];
        direction = new Direction[one.length()+1][two.length()+1];

        for(int a=0; a<(one.length()+1); a++)
        {
            lcs[a][0] = 0;
            direction[a][0] = Direction.WALL;
        }
        
        for(int b=0; b<(two.length()+1); b++)
        {
            lcs[0][b] = 0;
            direction[0][b] = Direction.WALL;
        }

        for(int i=1; i<(one.length()+1); i++)
            for(int j=1; j<(two.length()+1); j++)
            {
                if(one.charAt(i-1) == two.charAt(j-1))
                {
                    lcs[i][j] = lcs[i-1][j-1]+1;
                    direction[i][j] = Direction.DIAG;
                }
                else if(lcs[i-1][j] >= lcs[i][j-1])
                {
                    lcs[i][j] = lcs[i-1][j];
                    direction[i][j] = Direction.UP;
                }
                else
                {
                    lcs[i][j] = lcs[i][j-1];
                    direction[i][j] = Direction.LEFT;
                }
            }
    }

    public String getLCS()
    {
        String temp = "";
        int lengthOne = one.length();
        int lengthTwo = two.length();

        while(lengthOne>0 && lengthTwo>0)
        {
            if(direction[lengthOne][lengthTwo] == Direction.DIAG)
            {
                temp += one.charAt(lengthOne-1);
                lengthOne--;
                lengthTwo--;
            }
            if(direction[lengthOne][lengthTwo] == Direction.UP)
            {
                lengthOne--;
            }
            else if(direction[lengthOne][lengthTwo] == Direction.LEFT)
            {
                lengthTwo--;
            }
        }

        String result = "";
        for(int i=temp.length()-1; i>=0; i--)
            result += temp.charAt(i);

        return result;
    }

    public void printLCS()
    {
        System.out.print("    ");
        for(int a=0; a<(two.length()); a++)
            System.out.print(two.charAt(a)+" ");
        System.out.println();

        for(int i=0; i<(one.length()+1); i++)
        {
            if(i==0)
                System.out.print("  ");
            else
                System.out.print(one.charAt(i-1)+" ");
            
            for(int j=0; j<(two.length()+1); j++)
            {
                System.out.print(lcs[i][j] + " ");
            }
        System.out.println();
        }
    }

    public void printDirection()
    {
        System.out.print("    ");
        for(int a=0; a<(two.length()); a++)
            System.out.print(two.charAt(a)+" ");
        System.out.println();

        for(int i=0; i<(one.length()+1); i++)
        {
            if(i==0)
                System.out.print("  ");
            else
                System.out.print(one.charAt(i-1)+" ");

            for(int j=0; j<(two.length()+1); j++)
            {
                System.out.print(direction[i][j] + " ");
            }
        System.out.println();
        }
    }

    private enum Direction
    {
        LEFT, UP, DIAG, WALL;

        @Override
        public String toString()
        {
            switch (this)
            {
                case LEFT:
                    return "<";
                case UP:
                    return "^";
                case DIAG:
                    return "\\";
                case WALL:
                    return "#";
            }
            throw new IllegalStateException("Wrong Direction");
        }
    }
}

Class Main

package lcs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;

/**
 *
 * @author Nur Dian Wahyu S
 */
public class Main {

    public static void main(String[] args) throws IOException {
        LongestCommonSubsequence LCS = new LongestCommonSubsequence("australia","amerika");
        LCS.printLCS();
        System.out.println();
        LCS.printDirection();
        System.out.println();
        System.out.println("LCS : " + LCS.getLCS() + " - Length : " + LCS.getLCS().length());

    }

}

Output