Longest Common Subsequence (LCS): Pengertian Dan Cara Kerja

by Jhon Lennon 60 views

Hey guys! Pernah denger istilah Longest Common Subsequence atau LCS? Nah, buat kalian yang lagi belajar algoritma dan struktur data, konsep ini penting banget, lho. Di artikel ini, kita bakal bahas tuntas tentang apa itu LCS, kenapa penting, dan gimana cara kerjanya. Yuk, langsung aja kita mulai!

Apa Itu Longest Common Subsequence (LCS)?

Longest Common Subsequence (LCS) adalah urutan karakter terpanjang yang dimiliki oleh dua atau lebih string, tetapi karakter-karakter ini tidak harus berurutan secara berdekatan dalam string aslinya. Bingung? Oke, gini deh, kita ambil contoh biar lebih jelas. Misalkan kita punya dua string:

  • String 1: "ABCDGH"
  • String 2: "AEDFHR"

LCS dari kedua string ini adalah "ADH". Kenapa? Karena "ADH" adalah urutan karakter terpanjang yang muncul di kedua string tersebut, meskipun posisi 'A', 'D', dan 'H' tidak berdekatan.

Perbedaan LCS dan Longest Common Substring: Penting untuk dicatat bahwa LCS berbeda dengan Longest Common Substring. Kalau substring, urutannya harus berdekatan. Misalnya, pada contoh di atas, tidak ada substring yang sama antara kedua string tersebut.

Kenapa LCS Penting?

LCS punya banyak aplikasi penting di berbagai bidang, di antaranya:

  1. Bioinformatika: Dalam bioinformatika, LCS sering digunakan untuk membandingkan urutan DNA. Dengan menemukan LCS dari dua urutan DNA, para ilmuwan dapat mengidentifikasi bagian-bagian yang mirip dan mungkin memiliki fungsi yang sama. Ini sangat membantu dalam memahami evolusi dan hubungan genetik antara spesies yang berbeda.
  2. Perbandingan File (Diff): Program diff yang digunakan untuk membandingkan file teks menggunakan konsep LCS untuk menemukan perbedaan antara dua versi file. Dengan mengidentifikasi LCS, program diff dapat menunjukkan baris-baris mana yang telah ditambahkan, dihapus, atau diubah. Ini sangat berguna bagi para pengembang perangkat lunak untuk melacak perubahan dalam kode mereka.
  3. Pengenalan Ucapan: Dalam pengenalan ucapan, LCS dapat digunakan untuk membandingkan urutan fonem yang diucapkan dengan urutan fonem yang diharapkan. Ini membantu dalam mengidentifikasi kata-kata yang diucapkan dengan benar, bahkan jika ada beberapa kesalahan pengucapan. Misalnya, jika seseorang mengucapkan kata "apel" dengan sedikit berbeda, sistem pengenalan ucapan masih dapat mengenalinya berdasarkan LCS antara ucapan yang diucapkan dan ucapan yang diharapkan.
  4. Koreksi Ejaan: LCS juga dapat digunakan dalam koreksi ejaan untuk menemukan kata yang paling mirip dengan kata yang salah dieja. Dengan membandingkan kata yang salah dieja dengan daftar kata yang benar, sistem koreksi ejaan dapat menyarankan kata yang paling mungkin dimaksud oleh pengguna. Misalnya, jika seseorang salah mengetik "aple", sistem koreksi ejaan dapat menyarankan "apel" sebagai koreksi yang paling mungkin.

Cara Mencari LCS

Ada beberapa cara untuk mencari LCS dari dua string, tapi yang paling umum dan efisien adalah dengan menggunakan dynamic programming. Metode ini melibatkan pembuatan tabel yang menyimpan panjang LCS dari awalan string. Berikut adalah langkah-langkahnya:

  1. Inisialisasi Tabel: Buat tabel (biasanya berupa array 2D) dengan ukuran (m+1) x (n+1), di mana m adalah panjang string pertama dan n adalah panjang string kedua. Inisialisasi semua sel di baris pertama dan kolom pertama dengan 0. Tabel ini akan kita isi dengan panjang LCS dari awalan string.
  2. Isi Tabel: Iterasi melalui tabel mulai dari baris 1 dan kolom 1. Untuk setiap sel (i, j), bandingkan karakter ke-i dari string pertama dengan karakter ke-j dari string kedua.
    • Jika karakter sama: Jika karakter sama, maka nilai sel (i, j) adalah nilai sel diagonal sebelumnya (i-1, j-1) ditambah 1. Ini karena kita telah menemukan karakter yang sama di kedua string, sehingga panjang LCS meningkat.
    • Jika karakter berbeda: Jika karakter berbeda, maka nilai sel (i, j) adalah nilai maksimum antara sel di atasnya (i-1, j) dan sel di sebelah kirinya (i, j-1). Ini karena kita harus memilih awalan string mana yang memberikan LCS terpanjang.
  3. Nilai LCS: Setelah tabel terisi penuh, nilai LCS dari kedua string adalah nilai di sel (m, n), yaitu sel di sudut kanan bawah tabel.
  4. Rekonstruksi LCS (Opsional): Jika kita ingin mengetahui urutan karakter LCS-nya (bukan hanya panjangnya), kita dapat melakukan backtracking dari sel (m, n) ke sel (0, 0). Mulai dari sel (m, n), kita bergerak ke sel sebelumnya yang memberikan nilai maksimum. Jika kita bergerak secara diagonal, berarti karakter yang sesuai adalah bagian dari LCS. Dengan mengikuti jalur ini, kita dapat merekonstruksi urutan karakter LCS.

Contoh Implementasi Dynamic Programming dalam Kode

Biar makin paham, kita lihat contoh implementasi dynamic programming untuk mencari LCS dalam bahasa Python:

def longest_common_subsequence(string1, string2):
    m = len(string1)
    n = len(string2)

    # Inisialisasi tabel
    dp = [([0] * (n + 1)) for _ in range(m + 1)]

    # Isi tabel
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if string1[i - 1] == string2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Nilai LCS
    lcs_length = dp[m][n]

    # Rekonstruksi LCS (Opsional)
    i = m
    j = n
    lcs = ""
    while i > 0 and j > 0:
        if string1[i - 1] == string2[j - 1]:
            lcs = string1[i - 1] + lcs
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return lcs_length, lcs

# Contoh penggunaan
string1 = "ABCDGH"
string2 = "AEDFHR"
length, sequence = longest_common_subsequence(string1, string2)
print(f"Panjang LCS: {length}")
print(f"LCS: {sequence}")

Kode di atas akan menghasilkan output:

Panjang LCS: 3
LCS: ADH

Optimasi dan Kompleksitas Waktu

Kompleksitas Waktu: Algoritma dynamic programming untuk mencari LCS memiliki kompleksitas waktu O(m*n), di mana m dan n adalah panjang string. Ini karena kita harus mengisi tabel dengan ukuran (m+1) x (n+1).

Optimasi: Meskipun kompleksitas waktu O(m*n) sudah cukup efisien, ada beberapa optimasi yang bisa dilakukan untuk mengurangi penggunaan memori. Misalnya, kita tidak perlu menyimpan seluruh tabel, tetapi hanya dua baris terakhir saja. Ini karena untuk menghitung nilai sel (i, j), kita hanya membutuhkan nilai dari baris sebelumnya (i-1) dan kolom sebelumnya (j-1). Dengan hanya menyimpan dua baris terakhir, kita dapat mengurangi penggunaan memori menjadi O(min(m, n)).

Variasi Permasalahan LCS

Selain mencari LCS dari dua string, ada juga beberapa variasi permasalahan LCS yang menarik, di antaranya:

  1. Longest Common Subsequence dari Tiga String atau Lebih: Algoritma dynamic programming dapat diperluas untuk mencari LCS dari tiga string atau lebih. Dalam kasus ini, kita perlu membuat tabel dengan dimensi yang sesuai dengan jumlah string. Misalnya, untuk tiga string, kita akan membuat tabel 3D.
  2. Weighted Longest Common Subsequence: Dalam variasi ini, setiap karakter memiliki bobot tertentu. Tujuan kita adalah mencari LCS dengan total bobot maksimum. Algoritma dynamic programming dapat dimodifikasi untuk mempertimbangkan bobot karakter.
  3. Constrained Longest Common Subsequence: Dalam variasi ini, kita memiliki batasan tambahan pada LCS yang harus dipenuhi. Misalnya, kita mungkin ingin mencari LCS yang mengandung karakter tertentu atau yang memiliki panjang minimal tertentu.

Kesimpulan

Longest Common Subsequence (LCS) adalah konsep penting dalam ilmu komputer dengan banyak aplikasi praktis. Dengan memahami apa itu LCS dan bagaimana cara kerjanya, kita dapat memecahkan berbagai masalah yang terkait dengan perbandingan urutan. Algoritma dynamic programming adalah cara yang efisien untuk mencari LCS, dan ada beberapa optimasi dan variasi yang dapat kita gunakan untuk meningkatkan kinerja dan fleksibilitasnya.

Jadi, gimana guys? Udah pada paham kan sekarang tentang LCS? Jangan ragu untuk mencoba implementasi kode di atas dan bereksperimen dengan string yang berbeda. Selamat belajar dan semoga sukses!