Problem Longest Common Subsequence dengan Tiga Sekuen

Posted: December 1, 2009 in Algorithm, C#, Programming
Tags: , ,

Problem yang pertama adalah mengenai longest common subsequence dengan menggunakan tiga sekuen. Algoritma ini memiliki tujuan untuk mendapatkan subsekuen yang sama secara berurutan dan tentunya yang paling panjang dari ketiga subsekuen.

Contoh :

Sekuen Pertama : SURABAYA
Sekuen Kedua : SURAKARTA
Sekuen Ketiga : PASURUAN
Hasil : SURA

Algoritma

Algoritma solusi menggunakan solusi dynamic programming. Sebenarnya LCS dengan tiga sekuen sama saja dengan LCS menggunakan dua sekuen. Namun bedanya disini, dalam mengelesaikan LCS dengan tiga string, dibutuhkan array tiga dimensi yang volumenya adalah X.Y.Z dimana X, Y, dan Z adalah panjang dari ketiga sekuen.
Solusi optimal yang dihasilkan akan didapatkan di elemen array yang terakhir, yaitu array dengan indeks X-1, Y-1, dan Z-1
Petbedaan lainnya dalam LCS menggunakan tiga sekuen, arah/direction yang perlu di-cek adalah sebanyak tujuh arah. Tujuh arah tersebut yang direpresentasikan dengan angka adalah sebagai berikut :

0 menuju ke c[i – 1, j – 1, k – 1]
1 menuju ke c[i – 1, j – 1, k]
2 menuju ke c[i – 1, j, k – 1]
3 menuju ke c[i, j – 1, k – 1]
4 menuju ke c[i, j, k – 1]
5 menuju ke c[i, j – 1, k]
6 menuju ke c[i – 1, j, k]

Algoritma LCS-Length

LCS-LENGTHX, Y, Z, c then

// menginisiasi array c

for i ß 0 to X.Length-1 do

for j ß 0 to Y.Length-1 do

for k ß 0 to Z.Length-1 do

c[i, j, k].Value ß 0   // tidak memiliki nilai

c[i, j, k].Direction ß -1    // tidak memiliki arah

// looping sebanyak X.Y.Z dimana masing-masing

// adalah panjang dari subsequence then

for i ß 0 to X.Length-1 do

for j ß 0 to Y.Length-1 do

for k ß 0 to Z.Length-1 do

max ß 1 // variabel nilai temporari

dir ß -1 // variabel arah temporari

if Xi = Yj = Zk then

// mendapatkan karakter

max ß c[i – 1, j – 1, k – 1].Value + 1

// yang cocok

dir ß 0

else

// tidak mendapatkan karakter yang cocok,

// maka mencari nilai maksimal

if c[i – 1, j – 1, k].Value > max then

max ß c[i – 1, j – 1, k].Value

dir ß 1

if c[i – 1, j, k – 1].Value > max then

max ß c[i – 1, j, k – 1].Value

dir ß 2

if c[i, j – 1, k – 1].Value > max then

max ß c[i, j – 1, k – 1].Value

dir ß 3

if c[i, j, k – 1].Value > max then

max ß c[i, j, k – 1].Value

dir ß 4

if c[i, j – 1, k].Value > max then

max ß c[i, j – 1, k].Value

dir ß 5

if c[i – 1, j, k].Value > max then

max ß c[i – 1, j, k].Value

dir ß 6

// inputkan nilai maksimal

c[i, j, k].Value ß max

c[i, j, k].Direction ß dir

LCS-LENGTHX, Y, Z, c then
    // menginisiasi array c
    for i <-- 0 to X.Length-1 do
        for j <-- 0 to Y.Length-1 do
            for k <-- 0 to Z.Length-1 do
                c[i, j, k].Value <-- 0   // tidak memiliki nilai
                c[i, j, k].Direction <-- -1    // tidak memiliki arah

     // looping sebanyak X.Y.Z dimana masing-masing
     // adalah panjang dari subsequence then
     for i <-- 0 to X.Length-1 do
        for j <-- 0 to Y.Length-1 do
            for k <-- 0 to Z.Length-1 do

                max <-- 1 // variabel nilai temporari
                dir <-- -1 // variabel arah temporari

                if Xi = Yj = Zk then
                    // mendapatkan karakter
                    max <-- c[i - 1, j - 1, k - 1].Value + 1
                    // yang cocok
                    dir <-- 0
                else
                    // tidak mendapatkan karakter yang cocok,
                    // maka mencari nilai maksimal

                    if c[i - 1, j - 1, k].Value > max then
                        max <-- c[i - 1, j - 1, k].Value
                        dir <-- 1

                    if c[i - 1, j, k - 1].Value > max then
                        max <-- c[i - 1, j, k - 1].Value
                        dir <-- 2

                    if c[i, j - 1, k - 1].Value > max then
                        max <-- c[i, j - 1, k - 1].Value
                        dir <-- 3

                    if c[i, j, k - 1].Value > max then
                        max <-- c[i, j, k - 1].Value
                        dir <-- 4

                    if c[i, j - 1, k].Value > max then
                        max <-- c[i, j - 1, k].Value
                        dir <-- 5

                    if c[i - 1, j, k].Value > max then
                        max <-- c[i - 1, j, k].Value
                        dir <-- 6

                // inputkan nilai maksimal
                c[i, j, k].Value <-- max
                c[i, j, k].Direction <-- dir

Algoritma Print-LCS

PRINT-LCS(c, X, i, j, k)
    // sudah sampai sisi dari array tiga dimensi
    // maka stop
    if i = 0 or j = 0 or k = 0 then
        return

    // mengecek arah pada tabel c
    if c[i, j, k].Direction = 0 then
        PRINT-LCS(c, X, i - 1, j - 1, k - 1)
        print(Xi)
    else if c[i, j, k].Direction = 1 then
        PRINT-LCS(c, X, i - 1, j - 1, k)
    else if c[i, j, k].Direction = 2 then
        PRINT-LCS(c, X, i - 1, j, k - 1)
    else if c[i, j, k].Direction = 3 then
        PRINT-LCS(c, X, i, j - 1, k - 1)
    else if c[i, j, k].Direction = 4 then
        PRINT-LCS(c, X, i, j, k - 1)
    else if c[i, j, k].Direction = 5 then
        PRINT-LCS(c, X, i, j - 1, k)
    else if c[i, j, k].Direction = 6 then
        PRINT-LCS(c, X, i - 1, j, k)

Implementasi menggunakan C#

Fungsi LCS-Length

        /// Fungsi ini akan mengisi tabel c yang berupa instansiasi dari
        /// Entity yang memiliki dua informasi, yaitu nilai dan arah
        /// Dari tabel c ini, kita akan dapat mengetahui solusi optimal dari lcs
        /// </summary>
        /// <param name="X"></param>
        /// <param name="Y"></param>
        /// <param name="Z"></param>
        /// <param name="c"></param>
        private void LCSLength(string X, string Y, string Z, Data[, , ] c)
        {
            // menginisiasi array c
            for (int i = 0; i < X.Length; i++)
                for (int j = 0; j < Y.Length; j++)
                    for (int k = 0; k < Z.Length; k++)
                    {
                        c[i, j, k].Value = 0;           // tidak memiliki nilai
                        c[i, j, k].Direction = -1;      // tidak memiliki arah
                    }

            // looping sebanyak X.Y.Z (dimana masing-masing adalah panjang
            // dari subsequence)
            for (int i = 1; i < X.Length; i++)
                for (int j = 1; j < Y.Length; j++)
                    for (int k = 1; k < Z.Length; k++)
                    {

                        numOfIteration++;

                        int max = -1; // variabel nilai temporari
                        int dir = -1; // variabel arah temporari

                        if (X[i] == Y[j] && Y[j] == Z[k])
                        {
                            max = c[i - 1, j - 1, k - 1].Value + 1; // mendapatkan
                                                                    // karakter
                            dir = 0;                                // yang cocok
                        }
                        else
                        {   // tidak mendapatkan karakter yang cocok,
                            // maka mencari nilai maksimal

                            if (c[i - 1, j - 1, k].Value > max)
                            {
                                max = c[i - 1, j - 1, k].Value;
                                dir = 1;
                            }

                            if (c[i - 1, j, k - 1].Value > max)
                            {
                                max = c[i - 1, j, k - 1].Value;
                                dir = 2;
                            }

                            if (c[i, j - 1, k - 1].Value > max)
                            {
                                max = c[i, j - 1, k - 1].Value;
                                dir = 3;
                            }

                            if (c[i, j, k - 1].Value > max)
                            {
                                max = c[i, j, k - 1].Value;
                                dir = 4;
                            }

                            if (c[i, j - 1, k].Value > max)
                            {
                                max = c[i, j - 1, k].Value;
                                dir = 5;
                            }

                            if (c[i - 1, j, k].Value > max)
                            {
                                max = c[i - 1, j, k].Value;
                                dir = 6;
                            }
                        }

                        // inputkan nilai maksimal
                        c[i, j, k].Value = max;
                        c[i, j, k].Direction = dir;

                    }

        }

Fungsi Print-LCS

        /// <summary>
        /// Fungsi ini akan mencetak solusi dari lcs dengan
        /// melakukan pembacaan secara rekursif terhadap tabel c
        /// </summary>
        /// <param name="c">tabel c yang berupa array tiga dimensi</param>
        /// <param name="X">Sekuen pertama</param>
        /// <param name="i">indeks array i</param>
        /// <param name="j">indeks array j</param>
        /// <param name="k">indeks array k</param>
        private void PrintLCS(Data[, , ] c, string X, int i, int j, int k)
        {
            // sudah sampai sisi dari array tiga dimensi
            // maka stop
            if (i == 0 || j == 0 || k == 0)
                return;

            // mengecek arah pada tabel c
            switch (c[i, j, k].Direction)
            {
                case 0:
                    PrintLCS(c, X, i - 1, j - 1, k - 1);
                    solution.Add(X[i]); // print solusi optimal
                    break;

                case 1:
                    PrintLCS(c, X, i - 1, j - 1, k);
                    break;

                case 2:
                    PrintLCS(c, X, i - 1, j, k - 1);
                    break;

                case 3:
                    PrintLCS(c, X, i, j - 1, k - 1);
                    break;

                case 4:
                    PrintLCS(c, X, i, j, k - 1);
                    break;

                case 5:
                    PrintLCS(c, X, i, j - 1, k);
                    break;

                case 6:
                    PrintLCS(c, X, i - 1, j, k);
                    break;
            }
        }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s