Longest Common Subsequence ( LCS )

Pada project kali ini algoritma yang kedua,kami menggunakan algoritma LCS..
Jadi gini,ceritanya aplikasi kami ini bisa meramalkan kecocokan dua orang karakter yang berbeda..
Jadi,nanti kita bisa tahu,seberapa cocok karakter kita dengan teman atau pasangan kita,..

Mengapa?

Sebenarnya cara ini bisa dijelaskan secara logis melalui algoritma LCS..
Berbicara tentang konsep itu sendiri,Longest Common Subsequence menurut WIKIPEDIA adalah :
The longest common subsequence problem (LCS) is finding the longest subsequence common to all sequences in a set of sequences (often just two).
Yaitu masalah mencari uparangkaian bersama (common subsequence) terpanjang dari beberapa (biasanya hanya 2) buah rangkaian.

Dalam buku Cormen,dijelaskan teorema tentang algoitma LCS, yaitu :
Misal X = < x1, x2, .. , xm > dan Y = < y1, y2, .. , yn > adalah rangkaian dan
Z = < z1, z2, .. , zk> adalah suatu LCS dari X dan Y.

1. Jika xm = yn, maka zk = xm = yn dan Zk-1 adalah suatu LCS dari Xm-1 dan Yn-1.
2. Jika xm ≠ yn maka zk ≠ xm mengimplikasikan bahwa Z adalah suatu LCS dari Xm-1 & Y
3. Jika xm ≠ yn maka zk ≠ yn mengimplikasikan bahwa Z adalah suatu LCS dari X dan Yn-1

Didalam bukunya cormen,juga menjelaskan tentang teorema tersebut :
Jika zk ≠ xm maka kita bisa meng-append xm = yn pada Z untuk mendapatkan common subsequence dari X dan Y untuk panjang k + 1, yang kontradiksi dengan dugaan bahwa Z adalah LCS dari X dan Y. Untuk menunjukkan bahwa itu adalah LCS :

Misal, kita mempunyai zk = xm = yn. Sekarang prefiks dari Zk-1 adalah common subsequence dari Xm-1 dan Yn-1 yang panjangnya adalah k-1.Lalu ada sebuah common subsequence W dari Xm-1 & Yn-1 dengan panjang lebih besar daripada k-1.

Melakukan append xm = yn pada W menghasilkan common subsequence dari X dan Y dengan panjang lebih dari k.Yang adalah kontradiksi dengan pernyataan di atas.

Jika zk ≠ xm maka Z adalah common subsequence dari Xm-1 dan Y. Jika terdapat sebuah common subsequenceW dari Xm-1 dan Y yang panjangnya lebih dari k, maka hal ini berkontradiksi dengan asumsi bahwa Z adalah LCS dari X dan Y.
Pembuktian simetris dengan kasus 2.

Gampangannya,Semacam mencari kesamaan 2 kata yang berbeda.
Contoh : ada dua kata yang terdiri dari ARDIAZ dan ARYANDIKA.
misal X = A R Y A N D I K A dan Y = A R D I A Z ,
maka langkah pemecahan problem yang didapat adalah dengan membuat tabel dengan dimensi C[6][9].Kita menggunakan tabel dengan urutan jalan adalah dari C[1][1] hingga C[6][9].Tabel ini jika ditransformasikan kedalam tabel,maka kita menggunakan array untuk membuat tabel tersebut.

Penyelesaian dengan LCS :
tes2

Dari implementasi algoritma diatas,bisa didapat jawaban LCS dari dua kata tersebut yaitu A R D I A dengan jumlah LCS 5

Untuk menangani dirimu, gunakan kepalamu.
Tetapi untuk menangani orang lain, gunakan hatimu.
— No Name —

3 thoughts on “Longest Common Subsequence ( LCS )

  1. Mas…Minta psedeucode-nya dunk mas….
    saya buat algoritma itu tapi masih kejebak di kata yang sama tetapi dibelakang kata yang sama tersebut masih ada kata yang sama lainnya di depannya….

    Makasih…

    Regard,

    Ali Marjan

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