Mengenal Algoritma Pencocokan String Rabin-Karp

Posted on by Anisa Rahma Nasution
0

Pengertian Algoritma Rabin-Karp

Algoritma Rabin-Karp adalah algoritma pencocokan string (string matching) yang menggunakan teknik hashing untuk mencari satu atau lebih pola (pattern) dalam sebuah teks. Algoritma ini diperkenalkan oleh Michael O. Rabin dan Richard M. Karp pada tahun 1987.

Inti dari algoritma ini:

Alih-alih membandingkan string karakter demi karakter secara langsung, algoritma ini:

  • Mengubah pola dan bagian dari teks menjadi nilai hash (angka).

  • Membandingkan nilai hash tersebut untuk menentukan kemungkinan kecocokan.

  • Jika nilai hash cocok, maka dilakukan pembandingan langsung untuk memastikan tidak terjadi hash collision.

Langkah-langkah Kerja Algoritma Rabin-Karp:

1. Konversi ke Hash

  • Hitung nilai hash dari pola yang ingin dicari (pattern).

  • Hitung nilai hash untuk substring dalam teks dengan panjang yang sama seperti pattern.

Hash digunakan agar pencocokan bisa dilakukan lebih cepat dibanding memeriksa karakter satu per satu.

2. Sliding Window

  • Gunakan jendela (window) sepanjang m karakter (panjang pattern), dan geser dari kiri ke kanan dalam teks.

  • Setiap kali jendela bergeser, hitung ulang hash dari substring teks secara efisien (menggunakan rolling hash).

3. Bandingkan Hash

  • Jika hash dari pattern = hash dari substring teks, maka lakukan verifikasi karakter demi karakter.

    • Ini untuk memastikan bahwa kecocokan benar-benar terjadi (karena bisa terjadi hash collision).

4. Geser Window

  • Geser window ke kanan satu karakter dan ulangi proses sampai semua bagian teks yang mungkin sudah diperiksa.

Rolling Hash (Optimasi Hash)

Agar efisien, nilai hash tidak dihitung ulang dari nol setiap kali window bergeser. Sebagai gantinya:

  • Hitung hash baru berdasarkan hash sebelumnya.

  • Tambah karakter baru di akhir dan hapus karakter lama di awal.

Contoh rumus rolling hash (basis 10 atau 256, dan modulus prime q):

hash = (d * (hash – old_char * h) + new_char) % q

  • d: jumlah karakter dalam alfabet (misalnya 256 untuk ASCII)

  • h: nilai tertinggi (d^(m-1) mod q)

  • q: bilangan prima besar untuk menghindari collision

Contoh Singkat

Misal:

  • Text: "abcdabc"

  • Pattern: "abc"

Langkah:

  1. Hitung hash dari "abc".

  2. Sliding window 3 karakter:

    • "abc" β†’ hash cocok β†’ verifikasi β†’ cocok β†’ simpan indeks.

    • "bcd" β†’ hash beda β†’ lewati.

    • "cda" β†’ hash beda β†’ lewati.

    • "dab" β†’ hash beda β†’ lewati.

    • "abc" β†’ hash cocok β†’ verifikasi β†’ cocok β†’ simpan indeks.

Kompleksitas Waktu

Kasus Waktu
Terbaik O(n + m)
Rata-rata O(n + m)
Terburuk O(nm) (jika banyak collision)

Kelebihan Algoritma Rabin-Karp

Efisien untuk Banyak Pola Sekaligus (Multiple Pattern Matching)

  • Algoritma Rabin-Karp sangat efektif untuk mencari beberapa pola dalam satu teks sekaligus.

  • Cukup hitung hash semua pola terlebih dahulu, lalu bandingkan dengan hash teks β€” ini jauh lebih cepat daripada pencocokan karakter demi karakter.

Menggunakan Hashing untuk Mempercepat Pencocokan

  • Hash digunakan untuk membandingkan string secara cepat tanpa harus membandingkan tiap karakter satu per satu.

  • Jika hash berbeda, bisa langsung lanjut ke posisi berikutnya tanpa pemeriksaan lebih lanjut.

Rolling Hash yang Efisien

  • Teknik rolling hash memungkinkan penghitungan hash untuk substring baru dari hash sebelumnya dalam O(1) waktu.

  • Hal ini membuat Rabin-Karp lebih cepat dibandingkan algoritma lain dalam banyak kasus.

Sederhana dan Mudah Diimplementasikan

  • Meskipun menggunakan hash, algoritma ini cukup sederhana dan dapat diimplementasikan dengan mudah dalam berbagai bahasa pemrograman.

Sangat Cocok untuk Aplikasi Teks Besar

  • Dalam aplikasi seperti deteksi plagiarisme, pemindaian log, atau pencarian di dokumen besar, Rabin-Karp dapat melakukan pencocokan dengan cepat dan akurat.

Rata-rata Kompleksitas Waktu Efisien

  • Kompleksitas waktu rata-rata adalah O(n + m), di mana n panjang teks dan m panjang pola.

  • Jika collision bisa diminimalkan, performa sangat optimal.

Kekurangan Algoritma Rabin-Karp

Rawan Terhadap Hash Collision

  • Dua string yang berbeda bisa memiliki nilai hash yang sama (collision).

  • Saat terjadi collision, Rabin-Karp harus melakukan pembandingan karakter demi karakter (verifikasi manual), yang bisa memperlambat proses.

Performa Buruk pada Kasus Terburuk

  • Jika banyak collision terjadi, algoritma harus membandingkan banyak substring secara langsung.

  • Dalam kasus terburuk, kompleksitasnya bisa menjadi O(n * m) β€” sama dengan pencocokan naif.

Butuh Perhitungan Hash yang Teliti

  • Fungsi hash harus dirancang dengan hati-hati agar:

    • Tidak terlalu banyak collision.

    • Tidak menyebabkan overflow (terutama jika basis hash besar).

  • Pemilihan nilai basis dan modulus yang salah bisa merusak efisiensi algoritma.

Rolling Hash Sedikit Rumit untuk Dipahami

  • Walaupun efisien, rolling hash memiliki logika matematika yang tidak sesederhana pencocokan biasa.

  • Bisa menjadi lebih rumit saat mengimplementasikan untuk karakter non-ASCII atau string Unicode.

Kurang Efisien untuk Pencocokan Satu Pola

  • Jika hanya mencari satu pola pendek, algoritma lain seperti Knuth-Morris-Pratt (KMP) atau Boyer-Moore biasanya lebih cepat dan lebih konsisten.

Penggunaan Memori Tambahan

  • Untuk pencocokan banyak pola, perlu menyimpan hash untuk setiap pola.

  • Ini bisa meningkatkan penggunaan memori dibanding algoritma yang bekerja langsung tanpa pre-processing.

Algoritma Rabin-Karp adalah salah satu algoritma pencocokan string yang efisien dan cerdas karena memanfaatkan teknik hashing untuk mempercepat pencarian pola dalam teks. Dengan kekuatan rolling hash, algoritma ini sangat cocok untuk pencocokan banyak pola dalam teks besar, seperti dalam aplikasi deteksi plagiarisme atau sistem pencarian dokumen.

Namun, seperti algoritma lainnya, Rabin-Karp juga memiliki keterbatasan, terutama ketika terjadi banyak hash collision atau saat digunakan untuk pencarian satu pola pendek β€” di mana algoritma lain seperti KMP atau Boyer-Moore bisa lebih unggul.

πŸ” Kesimpulannya:

  • Gunakan Rabin-Karp saat efisiensi pencocokan banyak pola menjadi prioritas.

  • Pertimbangkan algoritma lain jika hanya satu pola yang dicari atau jika stabilitas waktu eksekusi sangat penting.

Post Views: 295