String Matching Algoritma Rabin Karp

Asslaamualaikum wr.wb.

pada kesempatan kali ini kita akan memabahas apa itu Algoritma String Matching Rabin Karp, yang biasanya kita hanya menemukan Algoritma String MAthcing , antara lain : Brute Force, KMP, dan Boyer Moore. Akan tetapi masih banyak lagi Alagoritma-algoritma lain yang dapat digunakan untuk menyelesaikan permasalahan String Matching contohnya ALgoritma Rabin Karp, Berikut adalah penjelasanya :

Algoritma Rabin Karp

Dekskripsi Algoritma

Algoritma Rabin karp adalah algoritma yang menggunakan pola untuk mencocokan teks dengan patternnya. Kelebihan penggunaan algoritma iniadalah tidak langsung mencocokan String antara pattern dan teks, akan tetapi mencari kemiripan teks dan pattern terlebih dahulu menggunakan perhitungan fungsi hash lalu mencocokannya secara Brute Force. Kompleksitas dari algoritma Rabin Karp adalah : O(m) untuk fase preprocessing, O(mn) untuk fase pencarian, dan O(m+n) untuk kesuluruhan waktu yang diperlukan.

Cara Kerja Algoritma Rabin karp :

Pola yang digunakan adalah misal panjang pattern(P) adalah n. maka pola yang terbentuk adalah pencocokan kemiripan pattern dengan substring pada teks sepanjang n kita misalkan (Sn). Lalu step matchingnya adalah :

·         Hitung nilai fungsi hash pada pattern.

·         Hitung nilai masing-masing Sn.

·         Lakukan pencarian terhadap Sn, jika nilai h(Sn) = h(P), maka dilakukan pencocokan String dengan cara Brute Force.

·         Jika nilai h(Sn) ≠ h(P), maka dilakukan pergeseran dan pencocokan nilai hash pada Sn selanjutnya.

Analisis Hasil :

Pada running time text yang diinputkan adalah “program studi informatika fmipa uns”. Dengan pattern sebagai berikut :

·         Untuk best case = “program”

·         Untuk average case = “informatika”

·         Untuk worst case = “uns”

Setiap case akan dirunning sebanyak 10 kali, sehingga didapatkan 10 data running time. Pada akhir data akan disediakan rata-rata dari 10 running time, berikut penjelasan dari setiap case :

1.       Penjelasan Base Case : “program”

Panjang pattern = 7

Program memiliki nilai ASCII 760

h(S0...S6) =

                h(program) = h(S0..S6), lalu setelah itu di cek dengan Brute Force.

                760 = 760, karena sama lannjut algoritma Brute Force dan hasilnya Match.

2.       Penjelasan Average Case : “informatika”.

Panjang pattern = 10

“infotmaika” memilii nilai ASCII = 1173

a.       h(S0..S10) =  Nilai ASCII = 1134

h(informatika) ≠  h(S0...S10) , karena dissmatch dilakukan pergeseran ke substring selanjutnya

b.      h(S1..S11) =   Nilai ASCII = 1049

h(informatika) ≠ h(S0...S10), karena dissmatch dilakukan pergeseran ke substring selanjutnya

c.       pada akhirnya String akan Match pada

h(19..29) = Nilai ASCII = 1173              

h(informatika) = h(19..29)

karena fungsi hash sama dilakukan algoritma Brute Force dan hasilnya adalah match.

3.       Penjelasan Worst Case : “UNS”

Panjang pattern = 3.

“UNS” memiliki nilai ASCII 342

Sama dengan sebelumnya maka akan ditemukan UNS match dengan (S38...S40)

h(S38...S40) =

h(UNS) = h(S38...S40)

342 = 342, maka lanjutkan Brute Force danhasilnya Match.