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 :
-
- Memindai teks dengan bantuan sebuah window yang ukurannya sama dengan panjang pattern.
- Menempatkan window pada awal teks.
- 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 :
-
- Pattern, yaitu deretan karakter yang akan dicocokkan dengan teks, dinyatakan dengan x[0..m-1], panjang pattern dinyatakan dengan m.
- Teks, yaitu tempat pencocokan pattern dilakukan, dinyatakan dengan y[0..n-1], panjang teks dinyatakan dengan n.
- Alfabet, yang berisi semua simbol yang digunakan oleh bahasa pada teks dan pattern, dinyatakan dengan ∑ dengan ukuran dinyatakan dengan ASIZE.
Pembahasan lainnya :
-
- Konsep Dasar Stack
- Jenis-Jenis Binary Tree
- Strategi Algoritma Greedy
- Pengertian Knapsack Problem
- Contoh Soal Knapsack Problem
- Algoritma Dynamic Programming
- Elemen Elemen Algoritma Greedy
- Karakteristik Algoritma Brute Force
- Keunggulan Bahasa Pemrograman Java
- Pengertian Logaritma dan Sifat-Sifatnya
- Efisiensi Algoritma Ditinjau dari 2 Dua Hal
- Penyelesaian Knapsack Problem dengan Kriteria Greedy
Originally posted 2022-10-20 22:51:54.