I.     ALGORITMA BOYER MOORE

1.1  Dekripsi Algoritma Boyer Moore

Algoritma pencarian string Boyer Moore merupakan algoritma pencarian string yang paling efisien dalam aplikasi sehari hari. Algoritma tersebut dikembangkan oleh Bob Boyer dan J Strother Moore pada tahun 1977. Pada proses pencarian string, algoritma Boyer Moore  membaca karakter-karakter dari pattern dari kanan ke kiri. Dalam kasus dimana jumlah karakter pada pattern lebih sedikit daripada jumlah karakter pada teks maka algoritma tersebut menggunakan 2 buah fungsi precomputed. 2 buah fungsi pengubah ini disebut good-suffix shift. Aturan pada good-suffix shift bertujuan untuk menangani kasus dimana terdapat pengulangan karakter pada pattern.

Ide utama algoritma ini adalah mencari string dengan melakukan pembandingan karakter mulai dari karakter paling kanan dari string yang dicari. Dengan mengunakan algoritma ini, secara rata-rata proses pencarian akan menjadi lebih cepat jika dibandingakan dengan algoritma lainnya. alasan melakukan pencocokan dari kanan (posisi terakhir string yang dicari) ditunjukan dalam contoh berikut :

K

A

N

A

N

K

I

R

I

O

K

E

R

A

D

I

O

R

A

D

I

O

pada contoh diatas, dengan melakukan pembandingan dari posisi paling akhir string dapat dilihat bahwa karakter “n” pada string “kanan” tidak cocok dengan karakter “o” pada string “radio” yang dicari, dan karakter “n” tidak pernah ada dalam string “radio” yang dicari sehingga string “radio” dapat digeser melewati string “kanan” sehingga posisinya menjadi :

K

A

N

A

N

K

I

R

I

O

K

E

R

A

D

I

O

R

A

D

I

O

Dalam contoh terlihat bahwa algoritma Boyer-Moore memiliki loncatan karakter yang besar sehingga mempercepat pencarian string karena dengan hanya memeriksa sedikit karakter, dapat langsung diketahui bahwa string yang dicari tidak ditemukan dan dapat digeser ke posisi berikutnya.

1.2 Prinsip Dasar

Algoritma Boyer Moore mempunyai empat konsep dasar di dalam proses pencarian string, yaitu :

1. Preprocessing

2. Right-to-left-scan

3. Bad-character-rule

4. Good-suffix-rule

Precomputation dari algoritma Boyer Moore terdiri dari bad-character preprocessing dan good-suffix preprocessing. Prinsip dasar yang pertama dari algoritma Boyer-Moore adalah melakukan perbandingan antara pattern yang dicari dengan teks. Perbandingan pattern dengan teks dilakukan dari arah kanan ke kiri. Perbandingan dimulai dengan membandingkan antara karakter paling kanan dari pattern dengan teks. Jika terjadi kecocokkan, maka perbandingan akan dilanjutkan dengan karakter yang di sebelah kiri dari yang dibandingkan sampai ke karakter pertama dari pattern. Jika terjadi ketidakcocokkan maka akan dilakukan pergeseran yang ditentukan oleh 2 fungsi pergeseran yaitu bad character shift (OH) dan good suffix shift(MH). Aturan dari bad character shift dibutuhkan untuk menghindari pengulangan perbandingan yang gagal dari suatu karakter dalam teks dengan pattern. Aturan dari good suffix shift dibutuhkan untuk menangani kasus yang di dalamnya terdapat pengulangan karakter pada pattern.