IF Notes

Algoritma Knuth-Morris-Pratt (KMP)

6 min read

Back to IF2211 Strategi Algoritma

Algoritma Knuth-Morris-Pratt (KMP)

Questions/Cues

  • Definisi KMP
  • Tokoh Pengembang KMP
  • Ide Cerdas KMP (Pergeseran)
  • Fungsi Pinggiran KMP / Failure Function
  • Definisi Fungsi Pinggiran b(k)
  • Contoh Perhitungan Fungsi Pinggiran
  • Cara Menggunakan Fungsi Pinggiran
  • Implementasi KMP (Java)
  • kmpMatch (Logika Cocok)
  • kmpMatch (Logika Mismatch)
  • computeBorder (Logika)
  • Kompleksitas Waktu KMP
  • Keunggulan KMP
  • Kelemahan KMP
  • Ekstensi KMP

Algoritma Knuth-Morris-Pratt (KMP)

Algoritma KMP adalah salah satu algoritma pencocokan string yang lebih efisien dibandingkan Brute Force.

  • Definisi: Algoritma KMP mencari pattern di dalam teks secara kiri-ke-kanan (mirip dengan Brute Force dalam arah perbandingan), tetapi ia menggeser pattern dengan lebih cerdas daripada Brute Force. KMP menghindari perbandingan yang tidak perlu dengan memanfaatkan informasi tentang pattern itu sendiri.
  • Tokoh: Algoritma ini dikembangkan oleh tiga ilmuwan komputer terkemuka: Donald E. Knuth, James H. Morris, dan Vaughan R. Pratt. Donald E. Knuth dikenal luas sebagai “bapak” analisis algoritma modern.

Ide Cerdas Pergeseran KMP

Kunci efisiensi KMP terletak pada bagaimana ia menangani ketidakcocokan (mismatch).

  • Pertanyaan Kunci: Jika terjadi ketidakcocokan antara teks T dan pattern P pada posisi P[j] (yaitu, T[i]=P[j]), seberapa jauh pattern dapat digeser ke kanan untuk menghindari perbandingan yang tidak perlu?
  • Jawabannya: Geser pattern sejauh mungkin sehingga bagian pattern yang sudah cocok sebelumnya (yaitu, prefix dari pattern hingga sebelum mismatch) masih bisa selaras dengan teks yang sudah cocok, tanpa harus “mundur” di teks T. Ini dilakukan dengan mencari prefix terbesar dari pattern P[0…j−1] yang juga merupakan suffix dari pattern P[1…j−1]. Posisi pattern yang baru untuk memulai perbandingan setelah pergeseran adalah panjang dari prefix/suffix terbesar ini.

Fungsi Pinggiran KMP (KMP Border Function) / Fungsi Kegagalan (Failure Function)

Untuk mengimplementasikan ide pergeseran cerdas ini, KMP melakukan preprocessing pada pattern itu sendiri.

  • Proses Preprocessing: KMP melakukan preprocessing pada pattern untuk mencari kecocokan prefix dari pattern dengan pattern itu sendiri. Hasil preprocessing ini disimpan dalam sebuah tabel atau array yang disebut fungsi pinggiran atau fungsi kegagalan.

  • Definisi b(k): Misalkan j adalah posisi mismatch di pattern P[], dan k adalah posisi sebelum mismatch (jadi k=j–1). Fungsi pinggiran b(k) (atau sering disebut fail[k]) didefinisikan sebagai ukuran (size) prefix terbesar dari P[0…k] yang juga merupakan suffix dari P[1…k]. b(k) ini adalah ukuran dari border terbesar.

  • Dalam kode, b() direpresentasikan oleh sebuah array, di mana b[k] menyimpan panjang border untuk prefix pattern hingga indeks k.

  • Contoh Fungsi Pinggiran (Border Function) Mari kita ambil pattern P="abaaba".

j (Indeks Pola)P[j]k (Indeks Akhir Sufiks)Prefiks P[0..k]Sufiks P[1..k]Prefiks Terpanjang dari P[0..k] yang Juga Sufiks dari P[1..k]b[k] (Panjang)
0a0”a"""""0
1b1”ab""b"""0
2a2”aba""ba""a”1
3a3”abaa""baa""a”1
4b4”abaab""baab""ab”2
5a5”abaaba""baaba""aba”3

Sehingga tabel b (atau fail) untuk “abaaba” adalah:

  • j (Indeks Pola): 0 1 2 3 4 5

  • P[j]: a b a a b a

  • b[k]: 0 0 1 1 2 1

  • (Catatan: b[k] adalah nilai fungsi prefiks untuk P[0..k]. Dalam implementasi algoritma KMP, seringkali nilai b[j-1] yang digunakan untuk menentukan pergeseran saat terjadi ketidakcocatan pada P[j].)

  • Menggunakan Fungsi Pinggiran: Jika terjadi mismatch pada P[j] (yaitu P[j]=T[i]), maka:

    • Kita memiliki informasi tentang seberapa banyak karakter dari pattern yang sudah cocok sebelum mismatch tersebut.
    • Jika j>0 (artinya mismatch bukan pada karakter pertama pattern), pattern digeser berdasarkan nilai dari fungsi pinggiran: j = b[j-1]. Ini berarti kita melanjutkan perbandingan dari posisi b[j−1] di pattern, tanpa harus memundurkan indeks teks i.
    • Jika j == 0 (artinya karakter pertama pattern tidak cocok), maka kita harus menggeser teks satu posisi ke kanan (i++), dan indeks pattern j tetap 0.

Implementasi Algoritma KMP (dalam Java)

Algoritma KMP biasanya melibatkan dua bagian utama: membangun fungsi pinggiran dan melakukan pencocokan.

public class KMP {
    // Metode utama untuk pencocokan KMP
    public int kmpMatch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] b = computeBorder(pattern); // Membangun fungsi pinggiran
 
        int i = 0; // Indeks untuk teks (T)
        int j = 0; // Indeks untuk pattern (P)
 
        while (i < n) { // Loop berlanjut hingga teks habis
            if (pattern.charAt(j) == text.charAt(i)) { // Karakter cocok
                if (j == m - 1) { // Seluruh pattern cocok
                    return i - m + 1; // Kembalikan posisi awal pattern di teks
                }
                i++; // Maju di teks
                j++; // Maju di pattern
            } else { // Karakter tidak cocok (mismatch)
                if (j > 0) { // Jika mismatch bukan pada karakter pertama pattern
                    j = b[j - 1]; // Geser pattern berdasarkan fungsi pinggiran
                                // (tidak memajukan indeks teks i)
                } else { // Mismatch pada karakter pertama pattern
                    i++; // Maju di teks
                         // j tetap 0
                }
            }
        }
        return -1; // Pattern tidak ditemukan
    }
 
    // Metode untuk menghitung array fungsi pinggiran b[]
    private int[] computeBorder(String pattern) {
        int m = pattern.length();
        int[] b = new int[m];
        b[0] = 0; // Fungsi pinggiran untuk karakter pertama selalu 0
 
        int j = 0; // Panjang border sebelumnya
        for (int i = 1; i < m; i++) { // Iterasi melalui pattern untuk mengisi b[]
            while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = b[j - 1]; // Mundur ke border yang lebih kecil
            }
            if (pattern.charAt(j) == pattern.charAt(i)) {
                j++; // Perpanjang border
            }
            b[i] = j; // Simpan panjang border untuk prefix P[0..i]
        }
        return b;
    }
}
  • Penggunaan: Mirip dengan Brute Force, Anda akan memanggil kmpMatch dan mencetak hasilnya.

Analisis Kompleksitas KMP

  • Menghitung fungsi pinggiran (computeBorder): Kompleksitas waktu O(m). Ini karena setiap karakter pattern diiterasi paling banyak dua kali (sekali dengan i++ dan mungkin beberapa kali dengan j = b[j-1]).
  • Pencarian string (kmpMatch): Kompleksitas waktu O(n). Mirip dengan computeBorder, setiap karakter teks T diiterasi paling banyak dua kali.
  • Kompleksitas waktu total algoritma KMP adalah O(m+n). Ini jauh lebih cepat dan efisien dibandingkan Brute Force, terutama untuk teks yang sangat panjang.

Keunggulan dan Kelemahan KMP

  • Keunggulan KMP (KMP Advantages):

    • Algoritma tidak pernah perlu bergerak mundur di dalam teks input T. Ini sangat penting untuk efisiensi.
    • Fitur ini membuat algoritma ini sangat baik untuk memproses berkas yang sangat besar yang dibaca dari perangkat eksternal (misalnya, hard drive) atau melalui network stream, karena kita tidak perlu menyimpan seluruh teks di memori atau membaca ulang bagian yang sudah diproses.

  • Kelemahan KMP (KMP Disadvantages):

    • KMP tidak bekerja sebaik ketika ukuran alfabet meningkat. Ketika alfabet sangat besar (misalnya, Unicode yang luas), peluang terjadinya mismatch meningkat, dan fungsi pinggiran mungkin tidak memberikan pergeseran yang optimal.
    • Lebih banyak peluang terjadinya mismatch di awal pattern.
    • KMP lebih cepat ketika mismatch terjadi belakangan dalam pattern, karena itu berarti ada prefix yang lebih panjang untuk dimanfaatkan oleh fungsi pinggiran.

  • Ekstensi KMP: Algoritma dasar KMP tidak mempertimbangkan karakter dalam teks yang menyebabkan mismatch (ia hanya melihat pattern). Beberapa varian KMP mungkin mempertimbangkan informasi ini untuk potensi optimasi lebih lanjut.

Summary

KMP adalah algoritma pencocokan string efisien yang menggeser pattern secara cerdas tanpa memundurkan teks. Ini dicapai melalui fungsi pinggiran (b(k)) yang dihitung saat preprocessing pattern (O(m)), mengidentifikasi prefix terpanjang yang juga suffix. Saat mismatch, pattern digeser berdasarkan b[j−1] (jika j>0) atau teks dimajukan (jika j=0), menghasilkan kompleksitas total O(m+n). KMP unggul untuk stream data besar karena tidak memundurkan teks, tetapi kurang optimal dengan alfabet besar.

Graph View

Backlinks