Algoritma Rabin Karp – Metode Pencarian String

Puji syukur penyusun panjatkan kehadirat Tuhan Yang Maha Esa atas karunia-Nya penyusun dapat menyelesaikan penyusunan makalah berjudul ‘Metode Pencarian String – Rabin Karp’ ini dengan baik. Penyusun juga mengucapkan terima kasih kepada semua pihak yang telah mendukung penyelesaian tugas ini.

Penyelesaian penyusunan makalah “Metode Pencarian String – Rabin Karp” ini secara khusus ditujukan memenuhi tugas ke-3 mata kuliah Pemrograman Berorientasi Objek I Prodi Teknik Informatika FMIPA Unpad 2018.

Penyusun berharap makalah ini dapat menambah pengetahuan dan wawasan mengenai salah satu metode yang dapat digunakan dalam proses pencarian string dalam bahasa pemrograman java. Penyusun pun menyadari bahwa dalam penyusunannya, makalah ini masih memiliki kekurangan, oleh sebab itu penyusun mengharapkan adanya kritik, saran dan tanggapan yang bersifat membangun demi perbaikan makalah ini di kemudian hari.

Semoga makalah ini dapat berguna dan dapat dipahami oleh seluruh kalangan yang membacanya. Mohon maaf apabila terdapat kesalahan kata-kata yang kurang berkenan.

Atas perhatian Saudara/Saudari, penyusun mengucapkan terima kasih.

Jatinangor, 2 Oktober 2018

Penyusun

Disusun oleh:

Nama:

Muhammad Fadillah Arsa (140810170005)
Dimas Satria Prakoso (140810170007)
Muhammad Afif (140810170045)
Muhammad Ariq Farhansyah Mutyara (140810170053)

Kelas : A – Teknik Informatika 2017

MAKALAH
METODE PENCARIAN STRING – RABIN KARP
MATA KULIAH PEMROGRAMAN BERORIENTASI OBJEK I
ALGORITMA RABIN KARP

*Catatan tentang istilah yang nanti kita akan pakai:
String keseluruhan = Text String
Substring yang dicari = Pattern String

Algoritma Rabin-Karp dalam pencarian string, secara garis besar ialah mencari Pattern String pada Text String dengan menggunakan Hahsing. Proses perncarian akan di-looping sehingga Pattern akan dibandingkan/ di-compare dengan tiap substring pada Text string. Yang membedakan metode ini dengan metode pencarian string lainnya ialah pembandingnya, dimana yang dibandingkan disini bukanlah character melainkan Hash Value yang didapat dengan proses Hashing.

Hash Value adalah suatu nilai yang merepresentasikan substring tersebut melalui perhitungan matematika. Proses untuk mencari Hash Value dari suatu substring dinamakan Hashing. Hash Value ini yang nanti mempermudah kita untuk meng-compare dan membuat teknik Rabin-Karp ini akan lebih cepat dibandingkan dengan linear search yang pembandingnya hanya nilai individual character (nilai numerik character ASCII).

Yang pertama kita butuhkan dalam teknik Rabin-Karp ini selain Text dan Pattern nya adalah panjang dari pattern dan text nya itu sendiri. Kemudian kita mencari Hash Value dari pattern dan Hash Value dari subtring pertama text.

*Catatan: pattern akan dibandingkan dengan kesuluruhan substring pada Text yang panjangnya sama dengan panjang pattern.

Kemudian kita akan membuat suatu looping yang jumlah iterasinya merupakan jumlah substring seluruhnya dari Text. Dalam looping ini kita membuat 2 kondisi. Kondisi pertama ialah ketika hash value pada substring bernilai sama dengan hash value pada pattern. Jika demikian, baru kira bandingan character pattern dengan character substring satu per satu untuk memastikan jika pattern sesuai dengan substring. Jika iya, maka kondisi 1 berakhir dan menge-print nilai dari indeks dari substring terhadap Text. Kondisi kedua ialah ketika hash value substring sebelumnya tidak sama dengan hash value pattern maka langkah yang kita lakukan selanjutnya ialah mencari hash value untuk substring selanjutnya. Hash Value ini yang nanti kita akan bandingkan kembali dengan hash Value pattern. Begitu seterunya hingga looping selesai.

Output yang ingin dicapai nanti ialah program dapat memberi tahu posisi-posisi indeks pada keseluruhan substring text yang bersesuaian dengan pattern. Tentunya dengan proses pencarian yang lebih cepat dan efisien.

Pencarian String metode Rabin-Karp ini dikenal juga dengan Fingerprint Search karena menggunakan jumlah informasil yang minim untuk merepresentasikan suatu pola (memiliki potensi jumlah informasi yang bersar). Algoritma ini cukup baik sebab fingerprint (hash value pattern) dapat dikomputasikan dan dibandingkan dengan lebih mudah dan efisien.

SEJARAH ALGORITMA RABIN KARP

Algoritma Rabin Karp adalah algoritma pencarian string yang diciptakan oleh Miachel O. Rabin dan Richard M. Karp pada tahun 1987 yang penggunaannya menggunakan metode hashing untuk mencari set pattern string pada suatu teks.

FLOWCHART

$C:\Users\M Fadillah Arsa\Downloads\Untitled Diagram(1).png$

SOURCE CODE PROGRAM



//PSEUDO CODE
function RabinKarpSet(string s[1..n], set of string subs, m):
set hsubs := emptySet
foreach sub in subs
insert hash(sub[1..m]) into hsubs
hs := hash(s[1..m])
for i from 1 to n-m+1
if hs ∈ hsubs and s[i..i+m-1] ∈ subs
return i
hs := hash(s[i+1..i+m])
return not found

SCREENSHOT EKSEKUSI PROGRAM

KOMPLEKSITAS WAKTU ALGORITMA PENCOCOKAN RABIN KARP

Seperti yang ditunjukkan oleh vzn di atas, artikel wiki memiliki semua detail yang Anda cari.

Pertama, apa yang pra-pemrosesan dan apa runtime online, tergantung pada apa yang tetap konstan dan apa yang bervariasi. Sebagai contoh, jika kita diberi beberapa teks tetap dan diminta untuk mencocokkan berbagai string kecil dengan teks itu, pra-pemrosesan akan mengacak teks.

Dalam hal ini, mari kita katakan kita hanya memiliki satu string untuk dibandingkan dengan satu teks, untuk menghindari kebingungan tentang pra-pemrosesan. Operasi yang perlu kami lakukan adalah

Hash untuk string yang akan dicari (p) = O (m)

Hash untuk setiap substring berukuran m dalam teks (T) (dengan asumsi hash bergulir) = O (n − m + 1)

Jumlah perbandingan hash (satu per setiap substring berukuran m dalam T) = O (n − m + 1)

Jika ada r cocok dalam hash, maka kita membandingkan masing-masing substring T dengan p (setiap perbandingan menjadi O (m)) = O (rm)

Namun dalam kasus terburuk, jumlah kecocokan dalam hash dapat sebesar n − m + 1. Jadi kompleksitas kasus terburuk adalah O (m (n − m + 1)).

REFERENSI

Addanki, Rajesh. (2011). Karp-Rabin. USA: Indiana State University. Diakses dari http://cs.indstate.edu/~raddanki/abstract.pdf

Sedgewick, Robert. (2011). Algorithms – Fourth Edition. USA: Princeton University.

Noprisson, Handrie. (2013). Implementasi Algoritma Rabin-Karp untuk Menentukan Keterkaitan Antara Publikasi Penelitian Dosen Tahun 2013. Indonesia: Universitas Bengkulu. Diakses dari https://www.academia.edu/5977583/Implementasi_Algoritma_Rabin-Karp_-_Paper_-_UNIB_Rev_1

Stack Excange – Computer Science. Time Complexity of Rabin-Karp matching algorithm. Diakses pada 2 Oktober 2018 dari https://cs.stackexchange.com/questions/10258/time-complexity-of-rabin-karp-matching-algorithm