• Beranda
  • Kelas
  • Blog
  • Lainnya
    • Event
    • Webinar
      • DaftarLogin
    InformatikawanInformatikawan
    • Beranda
    • Kelas
    • Blog
    • Lainnya
      • Event
      • Webinar
      • DaftarLogin

      Algoritma dan Pemrograman

      • Beranda
      • Blog
      • Algoritma dan Pemrograman
      • Algoritma Rabin Karp – Metode Pencarian String

      Algoritma Rabin Karp – Metode Pencarian String

      • Ditulis oleh Informatikawan
      • Kategori Algoritma dan Pemrograman
      • Tanggal 15/10/2020
      • Komentar 0 komentar

      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

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

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

      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

      • Bagikan:
      Informatikawan
      Informatikawan adalah platform pembelajaran bidang informatika. Menyediakan materi yang lengkap, terarah, dan dibimbing oleh pengajar berpengalaman di bidangnya.

      Pos sebelumnya

      Tutorial Mongoose #6: Relationship Data
      15/10/2020

      Pos selanjutnya

      Webinar UI/UX Designer with Yunilucki Siswantari
      05/11/2020

      Mungkin kamu juga suka

      ilustrasi-mergesort
      #SourceCode Merge Sort C++
      18 Juni, 2019
      belajar python informatikawan
      Belajar Python #5: Penggunaan Variabel dalam Python
      18 Juni, 2019
      belajar python informatikawan
      Belajar Python #4: Antara Python 2 atau Python 3 dan Cara Mengonversinya
      18 Juni, 2019

      Cari

      Pos-pos Terbaru

      • Webinar Flutter for Startup with Ilzam Mulkhaq 05/11/2020
      • Webinar UI/UX Designer with Yunilucki Siswantari 05/11/2020
      • Algoritma Rabin Karp – Metode Pencarian String 15/10/2020

      Kelas Populer

      Ethical Hacking Practical

      Ethical Hacking Practical

      Kelas Terbaru

      UI/UX Design

      UI/UX Design

      Aplikasi Web dengan Python Django

      Aplikasi Web dengan Python Django

      WHATSAPP 3 ADMIN
      BANDUNG INDONESIA
      INFORMATIKAWAN @GMAIL.COM
      BUKA SENIN - SABTU MINGGU: SLOWRESPON

      Informatikawan adalah platform pembelajaran bidang informatika. Menyediakan materi yang lengkap, terarah, dan dibimbing oleh pengajar berpengalaman di bidangnya.

      Fitur

      • Cara Belajar
      • Cara Membeli Kelas

      Lainnya

      • Aturan Penggunaan
      • Kebijakan Privasi
      • Refund Policy
      • Kontak Kami

      Menerima Berbagai Metode Pembayaran

      • ATM Bersama - Pembayaran Informatikawan
      • Prima - Pembayaran Informatikawan
      • Alto - Pembayaran Informatikawan
      • Bank BNI - Pembayaran Informatikawan
      • Bank Mandiri - Pembayaran Informatikawan
      • QRIS - Pembayaran Informatikawan
      • GOPAY GOJEK - Pembayaran Informatikawan
      • LinkAja - Pembayaran Informatikawan
      • OVO - Pembayaran Informatikawan
      • DANA - Pembayaran Informatikawan

      Informatikawan © 2020

      Login with your site account

      Masuk dengan Facebook Masuk dengan Google


      Lost your password?

      Not a member yet? Register now

      Register a new account

      Are you a member? Login now

      Tanya Kelas Berbayar
      Chat Whatsapp kami untuk bertanya perihal kelas online berbayar.
      * Hanya untuk bertanya perihal kelas online berbayar.
      Muhammad Fadillah Arsa
      Admin
      I will be back soon
      Muhammad Hafidz Alfarizi
      Admin
      Naufal Ariful Amri
      Admin