Apa Itu Algoritma Knuth Morris Pratt

Posted on by Anisa Rahma Nasution
0

Sejarah Algoritma KMP (Knuth-Morris-Pratt)

Algoritma Knuth-Morris-Pratt (KMP) diciptakan sebagai solusi terhadap permasalahan pencarian string yang efisien—terutama dalam kasus di mana pencocokan karakter yang berulang-ulang bisa menyebabkan pemborosan waktu.

Tokoh di Balik Algoritma KMP

Algoritma ini dinamai dari nama tiga ilmuwan komputer yang mengembangkannya:

  1. Donald E. Knuth

    • Salah satu tokoh paling berpengaruh dalam ilmu komputer teoritis.

    • Penulis buku legendaris The Art of Computer Programming.

  2. James H. Morris

    • Seorang peneliti dalam bidang sistem dan teori komputasi.

  3. Vaughan R. Pratt

    • Kontributor dalam banyak aspek teori komputasi, termasuk teori otomata dan logika formal.

Latar Belakang Pembuatan

Pada tahun 1970, James H. Morris sedang meneliti teknik pencocokan string sebagai bagian dari tesis Ph.D.-nya di Stanford University. Ia menemukan bahwa proses pencarian string dapat dioptimalkan dengan menghindari pencocokan ulang karakter yang sudah diperiksa sebelumnya.

Kemudian, Donald Knuth dan Vaughan Pratt ikut bekerja bersama Morris untuk merapikan, menyempurnakan, dan memformalkan ide tersebut. Hasil kerja mereka akhirnya diterbitkan pada tahun 1977 dalam makalah ilmiah berjudul:

“Fast Pattern Matching in Strings”, oleh D.E. Knuth, J.H. Morris Jr., dan V.R. Pratt.

Dampak dan Pengaruh

Algoritma ini merupakan salah satu algoritma pencocokan string pertama yang menawarkan kompleksitas waktu linear (O(n + m)), menjadikannya sangat efisien dibanding metode brute force yang memiliki kompleksitas O(n × m).

Sejak itu, KMP menjadi algoritma dasar dalam bidang:

  • Pemrosesan teks

  • Compiler (parsing token)

  • Bioinformatika (penyesuaian urutan DNA)

  • Pencarian dalam editor teks atau IDE

Inovasi Utama: LPS (Longest Prefix Suffix)

Intuisi inovatif utama dari KMP adalah penggunaan prefix table (LPS array), yang memungkinkan pattern “melompat” saat terjadi mismatch, tanpa perlu mencocokkan karakter yang sudah cocok sebelumnya. Ini menghemat waktu dan menghindari pemeriksaan ulang yang tidak perlu.

Pengertian Algoritma Knuth-Morris-Pratt (KMP)

Algoritma Knuth-Morris-Pratt (KMP) adalah algoritma pencocokan string (string matching) yang digunakan untuk mencari kemunculan suatu pola (pattern) di dalam sebuah teks (text). Algoritma ini dirancang untuk meningkatkan efisiensi pencarian dengan menghindari pemeriksaan ulang terhadap karakter-karakter dalam teks yang sebelumnya telah dibandingkan.

Saat membandingkan pattern dengan text, jika terjadi ketidakcocokan, KMP tidak langsung kembali ke awal pattern seperti metode brute-force. Sebaliknya, KMP menggunakan informasi dari bagian awal pola yang sudah cocok untuk menentukan sejauh mana pola dapat digeser tanpa kehilangan kecocokan yang mungkin. Informasi ini disimpan dalam sebuah array yang disebut LPS (Longest Prefix which is also Suffix).

Dua Tahap Utama Algoritma KMP:

1. Membangun Prefix Table (Failure Function / LPS – Longest Prefix Suffix)

Prefix table berisi panjang dari prefix terpanjang yang juga merupakan suffix untuk setiap posisi dalam pattern. Tabel ini digunakan untuk mengetahui berapa banyak pattern yang bisa digeser ketika terjadi ketidakcocokan.

Contoh:
Misalkan pattern = "ababaca"

Prefix table (LPS):

Index : 0 1 2 3 4 5 6
Pattern: a b a b a c a
LPS : 0 0 1 2 3 0 1

Penjelasan:

  • Untuk indeks ke-4 (karakter 'a'), substring "abab" memiliki prefix "ab" dan suffix "ab", maka LPS = 2.

2. Pencocokan Pola dengan Teks

Dengan menggunakan prefix table:

  • Jika terjadi kecocokan, lanjutkan ke karakter berikutnya.

  • Jika terjadi ketidakcocokan:

      • Pembuatan prefix table: O(m), di mana m = panjang pattern.

      • Pencocokan string: O(n), di mana n = panjang text.

Total waktu: O(n + m) → sangat efisien dibanding brute force O(nm).

Jangan kembali ke awal pattern, melainkan geser sesuai nilai pada prefix table.

Kompleksitas Waktu

Contoh Sederhana

1. Buat LPS:

Pattern : a b c a b y
Index : 0 1 2 3 4 5
LPS : 0 0 0 1 2 0

2. Cocokkan pola dalam teks:

  • Mencocokkan karakter demi karakter.

  • Jika cocok, teruskan.

  • Jika tidak cocok, gunakan LPS untuk mengetahui ke mana lompat, bukan ke awal lagi.

Hasilnya: "abcaby" cocok di posisi 6 dalam teks.

Kelebihan KMP

  • Tidak ada pemeriksaan ulang karakter.

  • Kompleksitas waktu linear.

  • Cocok untuk aplikasi seperti text editor, bioinformatika, dan search engine.

Tujuan Utama

  • Menemukan semua posisi dalam teks di mana pola muncul.

  • Melakukan pencocokan secara efisien dalam waktu linear.

Ciri Khas

  • Kompleksitas waktu: O(n + m)
    (n = panjang teks, m = panjang pola)

  • Tidak membandingkan ulang karakter yang sudah dicek.

  • Menggunakan tabel LPS untuk optimasi proses pencarian.

Contoh Kasus

Mencari pola "abc" dalam teks "abcabcabc":

  • KMP akan mencocokkan karakter satu per satu.

  • Saat terjadi ketidakcocokan, ia akan menggunakan tabel LPS untuk memutuskan seberapa jauh pattern bisa digeser — tanpa perlu memulai dari awal lagi.

Algoritma Knuth-Morris-Pratt (KMP) merupakan tonggak penting dalam bidang algoritma pencocokan string. Dengan mengusung pendekatan cerdas melalui prefix table (LPS), KMP menawarkan efisiensi tinggi dan kompleksitas waktu linear, menjadikannya solusi yang optimal dalam berbagai aplikasi dunia nyata — mulai dari editor teks hingga bioinformatika.

Diciptakan oleh tiga tokoh besar dalam ilmu komputer, KMP tidak hanya menyelesaikan masalah pencocokan string dengan cara yang elegan, tetapi juga membuka jalan bagi pengembangan algoritma string lainnya yang lebih kompleks dan efisien.

Memahami KMP berarti memahami prinsip dasar dari bagaimana komputasi efisien seharusnya bekerja: hindari pengulangan yang tidak perlu, dan manfaatkan informasi yang sudah tersedia secara optimal.

Post Views: 657