Creator Media

Algoritma Boyer Moore untuk String Matching

Algoritma Boyer-Moore termasuk algoritma string matching yang paling efisien dibandingkan algoritma-algoritma string matching lainnya. Karena sifatnya yang efisien, banyak dikembangkan algoritma string matching dengan bertumpu pada konsep algoritma Boyer-Moore, beberapa di antaranya adalah algoritma Turbo BM dan algoritma Quick Search.

Algoritma Boyer-Moore termasuk algoritma string matching yang paling efisien dibandingkan algoritma-algoritma string matching lainnya. Karena sifatnya yang efisien, banyak dikembangkan algoritma string matching dengan bertumpu pada konsep algoritma Boyer-Moore, beberapa di antaranya adalah algoritma Turbo BM dan algoritma Quick Search. String matching adalah pencarian sebuah pattern pada sebuah teks. Prinsip kerja algoritma string matching adalah sebagai berikut :

1. 1. Memindai teks dengan bantuan sebuah window yang ukurannya sama dengan panjang pattern.
   2. Menempatkan window pada awal teks.
   3. Membandingkan karakter pada window dengan karakter dari pattern. Setelah pencocokan (baik hasilnya cocok atau tidak cocok), dilakukan shft ke kanan pada window. Prosedur ini dilakukan berulang-ulang sampai window berada pada akhir teks. Mekanisme ini disebut mekanisme sliding-window.

Algoritma string matching mempunyai tiga komponen utama, yaitu :

1. 1. Pattern, yaitu deretan karakter yang akan dicocokkan dengan teks, dinyatakan dengan x[0..m-1], panjang pattern dinyatakan dengan m.
   2. Teks, yaitu tempat pencocokan pattern dilakukan, dinyatakan dengan y[0..n-1], panjang teks dinyatakan dengan n.
   3. Alfabet, yang berisi semua simbol yang digunakan oleh bahasa pada teks dan pattern, dinyatakan dengan ∑ dengan ukuran dinyatakan dengan ASIZE.

Pembahasan lainnya :

• 1. Konsep Dasar Stack
  2. Jenis-Jenis Binary Tree
  3. Strategi Algoritma Greedy
  4. Pengertian Knapsack Problem
  5. Contoh Soal Knapsack Problem
  6. Algoritma Dynamic Programming
  7. Elemen Elemen Algoritma Greedy
  8. Karakteristik Algoritma Brute Force
  9. Keunggulan Bahasa Pemrograman Java
  10. Pengertian Logaritma dan Sifat-Sifatnya
  11. Efisiensi Algoritma Ditinjau dari 2 Dua Hal
  12. Penyelesaian Knapsack Problem dengan Kriteria Greedy