Analisis Algoritma Boyer Moore

Algoritma Boyer Moore adalah algoritma pencocokan string.  Dalam kasus lain algoritma ini digunakan sebagai pencarian string, dipublikasikan oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977.

Algoritme ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum. Tidak seperti algoritma pencarian string yang ditemukan sebelumnya, algoritme Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritma ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat.

Pattern merupakan variabel yang akan di cari pada suatu data. Dari data tersebut maka akan di analisis mulai dari dihitung jumlah, cari, dan di cocokan sesuai dengan pattern yang dimasukkan.

Cara Kerja Algoritma Boyer Moore

Dari sebuah pencarian dan pencocokan kata pada sebuah teks maka akan di mulai dengan langkah-langkah boyer moore sebagai berikut:

  1. Algoritma Boyer-Moore mulai mencocokkan pattern pada awal teks
  2. Dari kanan ke kiri, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut, yaitu:pertama karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch). Kedua semua karakter di pattern cocok. Kemudian algoritme akan memberitahukan penemuan di posisi ini.
  3. Algoritme kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix dan penggeseran bad-character, lalu mengulangi langkah 2 sampai pattern berada di ujung teks

Beberapa implementasi algoritma boyer moore

  1. Pencarian dokumen
  2. Aplikasi mesin pencari atau search engine
  3. Aplikasi pencarian nama
  4. Filtering kata pada sebuah form

Kelebihan dan Kelemahan algoritma boyer moore

#Kelebihan

Tidak seperti pencarian string lainnya Brute Force, Knuth-Morris-Pratt yang mempunyai cara kerja membandingkan satu – persatu karakter dari kiri ke kanan. Boyer-Moore membandingkan karakter dari kanan ke kiri dan memiliki loncatan karakter yang besarsehingga mempercepat pencarian string karena dengan hanya memeriksa sedikit karakter, dapat langsung diketahui bahwa string yang dicari tidak ditemukan dan dapat digeser ke posisi berikutnya.

#Kelemahan

Algoritma Boyer-Moore mencocokan Pattern dari kanan ke kiri oleh sebab itu
kelemahan dari algoritma ini adalah ketika semua karakter memiliki kesamaan atau cocok dan hanya karakter terakhir atau karakter paling kiri yang berbeda maka pencarian ini akan memerlukan waktu yang sedikit lama (Utomo, 2008).

Sumber jurnal dan penelitian tentang algoritma boyer moore

  1. nero.trunojoyo.ac.id/index.php/nero/article/download/18/16
  2. research.pps.dinus.ac.id/lib/jurnal/Vol%2008.1%20040-048.pdf
  3. jurnal.unikom.ac.id/jurnal/penerapan-string-matching.3v/09-miu-11-2-diana.pdf
  4. repository.usu.ac.id/bitstream/123456789/60560/3/Chapter%20II.pdf
  5. repository.usu.ac.id/xmlui/handle/123456789/60560
  6. https://ojs.uajy.ac.id/index.php/jbi/article/download/491/522
  7. nformatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2015…/MakalahStima-2016-061.pdf

 

Untuk aplikasi algoritma boyer moore

DISINI

 

 

 

 

Postingan berikutnya

  1. Algoritma boyer moore

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>