Mudah dan Cepat Belajar Algoritma Rabin Karp

Buku adalah panduan yang paling sering saya pakai saat belajar algoritma. “Introduction to Algorithm”, buku ini dibuat oleh Ronald L Rivest dan satu-satunya buku yang saya punya waktu baru mulai belajar.

Salah satu algoritma yang paling berkesan waktu kuliah dulu adalah algoritma Rabin Karp, kategori algoritma String Matching. Ini algoritma yang akan kita bahas. Algoritma untuk pencarian teks di dalam teks lain.

Kali ini yang kita bahas adalah langkah-langkah dalam proses algoritma ini, plus contoh kode program yang bisa kamu coba. Contoh source code algoritma Rabin Karp ini menggunakan bahasa Python. Jadi silahkan install dulu Python-nya di komputer kamu.

Apa itu Algoritma Rabin Karp?

Algoritma ini menghitung nilai numerik suatu fungsi hash untuk suatu pola serta setiap substring dari teks. Setelah itu, algoritma ini membandingkan nilai numerik antara pola tersebut dengan teksnya. Ia akan mencari apakah ada teks yang cocok dengan pola.

Apa saja contoh Implementasi Algoritma Rabin Karp?

Algoritma ini sudah berkali-kali digunakan dalam penelitian plagiarism, alias memerika apakah sebuah dokumen berisi tulisan yang mencontek tulisan orang lain. Kamu bisa menggunakan algoritma ini untuk membuat skripsi dengan topik yang serupa.

Langkah-Langkah Algoritma Rabin Karp

Algoritma ini menemukan teks dengan menghitung nilai hash di setiap teks. Langkah-langkahnya adalah sebagai berikut:

  1. Hitung nilai hash pada pola (teks yang dicari) dan teks di posisi paling kiri. Panjang karakter teks harus sama dengan pola. Karakter teks pertama ini disebut dengan jendela teks pertama.
  2. Periksa nilai hash, kalau nilai hash pola dan teks cocok, periksa apakah karakter mereka juga cocok.
  3. Jika cocok, tampilkan indeks karakter paling kiri dari teks yang cocok tersebut.
  4. Jika tidak ada karakter yang cocok, hitung nilai hash untuk jendela teks berikutnya.
  5. Ulangi lagi dari langkah ke-2 hingga pola dan teks yang cocok ditemukan.

Bagaimana Caranya Menghitung Nilai Hash?

Nilai hash dihitung dengan rumus berikut:

Jumlah karakter di alfabet dikali dengan nilai hash pola ( atau teks sebelumnya) (jika belum, nilainya nol) kemudian dijumlahkan dengan Unicode dari seluruh karakter di pola/teks yang sedang dihitung. Lalu hasilnya di modulus dengan bilangan prima.

Source Code Algoritma Rabin Karp

Anyway, Algoritma Rabin Karp punya Average Running Time sebesar O(n+m) dan Worst Case Time dari algoritma ini sebesar O(nm). Kasus terburuknya muncul saat semua karakter dari pola dan teks punya nilai hash yang sama. Misalnya tulisan yang dicari dan tulisan sumber punya huruf yang sama semua.

Semoga bermanfaat!