Algoritma Boyer-Moore

Kali ini saya akan menjelaskan cara kerja dari sebuah algoritma pencarian string dalam dokumen teks, yaitu algoritma Boyer-Moore. Boyer-Moore secara rata-rata merupakan algoritma pencarian string yang paling baik jika dibandingkan dengan algoritma pencarian string lainnya seperti Brute-Force ataupun Knuth-Morris-Pratt. Jika kita menggunakan fasilitas Find/Search pada berbagai aplikasi pengolah teks, web browser, dan aplikasi lainnya mungkin saja kita telah memanfaatkan algoritma Boyer-Moore dalam pencarian tersebut, karena algoritma ini paling banyak diimplementasikan dalam berbagai aplikasi untuk fasilitas pencarian teksnya.

Algoritma Boyer-Moore adalah salah satu algoritma untuk mencari suatu string di dalam teks, dibuat oleh R.M Boyer dan J.S Moore. 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 :

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 :

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.

Langkah-langkah algoritma Boyer-Moore :

1. Buat tabel pergeseran string yang dicari (S) dengan pendekatan Match Heuristic (MH) dan Occurence Heuristic (OH), untuk menentukan jumlah pergeseran yang akan dilakukan jika mendapat karakter tidak cocok pada proses pencocokan dengan string (T).
2. Jika dalam proses pembandingan terjadi ketidakcocokan antara pasangan karakter pada S dan karakter pada T,  pergeseran dilakukan dengan memilih salah satu nilai pergeseran dari dua tabel analisa string, yang memiliki nilai pergeseran paling besar.
3. Dua kemungkinan penyelesaian dalam melakukan pergeseran S, jika sebelumnya belum ada karakter yang cocok adalah dengan melihat nilai pergeseran hanya pada tabel occurence heuristic : Jika karakter yang tidak cocok tidak ada pada S maka pegeseran adalah sebanyak jumlah karakter pada S. dan jika karakter yang tidak cocok ada pada S, maka banyaknya pergeseran bergantung dari nilai pada tabel.
4. Jika karakter pada teks yang sedang dibandingkan cocok dengan karakter pada S, maka posisi karakter pada S dan T diturunkan sebanyak 1 posisi, kemudian lanjutkan dengan pencocokan pada posisi tersebut dan seterusnya. Jika kemudian terjadi ketidakcocokan karakter S dan T, maka pilih nilai pergeseran terbesar dari dua tabel analisa pattern yaitu nilai dari tabel match heuristic dan nilai tabel occurence heuristic dikurangi dengan jumlah karakter yang telah cocok.
5. Jika semua karakter telah cocok, artinya S telah ditemukan di dalam T, selanjutnya geser pattern sebesar 1 karakter.
6. Lanjutkan sampai akhir string T.

Cara Menghitung Tabel Occurence Heuristic :
contoh string : manaman
Panjang : 7 karakter
Tabel Occurence Heuristic

1. Lakukan pencacahan mulai dari posisi terakhir string sampai ke posisi awal, dimulai dengan nilai 1, catat karakter yang sudah ditemukan (dalam contoh ini karakter “n”)
2. Mundur ke posisi sebelumnya, nilai pencacah ditambah 1, jika karakter pada posisi ini belum pernah ditemukan, maka nilai pergeserannya adalah sama dengan nilai pencacah. (dalam contoh ini, karakter “a” belum pernah ditemukan sehingga nilai pergeserannya adalah sebesar nilai pencacah yaitu 2)
3. Mundur ke posisi sebelumnya, karakter “m” nilai pergeserannya 3
4. Mundur lagi, karakter “a”. karakter “a” sudah pernah ditemukan sebelumnya sehingga nilai pergeserannya sama dengan nilai pergesean karakter “a” yang sudah ditemukan paling awal yaitu 2.
5. Begitu seterusnya sampai posisi awal string.

catatan : untuk karakter selain “m”,”a” dan “n” nilai pergeseran sebesar panjang string yaitu 7 karakter.

Cara Menghitung Tabel Match Heuristic :
contoh string : manaman
Panjang : 7 karakter
Tabel Match Heuristic

Langkah-langkah perhitungannya adalah sebagai berikut :

• jika karakter pada posisi 7 bukan “n” maka geser 1 posisi, berlaku untuk semua string yang dicari.

contoh :

• jika karakter “n” sudah cocok, tetapi karakter sebelum “n” bukan “a” maka geser sebanyak 7 posisi, sehingga posisi string melewati teks.karena sudah pasti “manambn” bukan “manaman”

contoh :

• jika karakter “an” sudah cocok, tetapi karakter sebelum “an” bukan “m” maka geser sebanyak 7 posisi, sehingga posisi string melewati teks.karena sudah pasti “manaban” bukan “manaman”

contoh :

• jika karakter “man” sudah cocok, tetapi karakter sebelum “man” bukan “a” maka geser sebanyak 4 posisi, sehingga posisi string berada / bersesuaian dengan akhiran “man” yang sudah ditemukan sebelumnya. karena bisa saja akhiran “man” yang sudah ditemukan sebelumnya merupakan awalan dari string “manaman” yang berikutnya.

contoh :

• jika karakter “aman” sudah cocok, tetapi karakter sebelum “aman” bukan “n” maka geser sebanyak 4 posisi, sehingga posisi string berada / bersesuaian dengan akhiran “man” yang sudah ditemukan sebelumnya, karena bisa saja akhiran “man” yang sudah ditemukan sebelumnya merupakan awalan dari string “manaman” yang berikutnya.

contoh :

• selanjutnya sama, pergseran paling mungkin dan aman dalam tabel Match Heuristic adalah pergeseran sebanyak 4 posisi.

Contoh Kasus

Dalam implementasinya, algoritma Boyer-Moore akan memilih nilai pergeseran terbesar dari 2 tabel pergeseran (Occurence Heuristic dan Match Heuristic). Saya akan menjelaskan implementasi algoritma Boyer-Moore dalam sebuah contoh kasus berikut ini :

teks : berikut ini anpamman bukan anpanman
pada tabel OH, –> selain karakter “a”,”n”,”p”,”m” nilai pergeseran sebesar panjang string yaitu 8

tahap 1

-spasi tidak cocok dengan “n”
-tabel OH : karakter spasi nilai pergeserannya = 8 belum ada karakter yang cocok
-tabel MH : ketidakcocokan pada posisi 8 (karakter “n”) nilai pergeserannya = 1
-sehingga geser string sebesar 8 posisi (nilai maksimal dari kedua tabel pergeseran)

tahap 2

-”a” tidak cocok dengan “n”
-tabel OH : karakter “a” nilai pergeserannya = 1 belum ada karakter yang cocok
-tabel MH : ketidakcocokan pada posisi 8 (karakter “n”) nilai pergeserannya = 1
-sehingga geser string sebesar 1 posisi (nilai maksimal dari kedua tabel pergeseran)

tahap 3

-”m” tidak cocok dengan “n”
-tabel OH : karakter “m” nilai pergeserannya = 2 belum ada karakter yang cocok
-tabel MH : ketidakcocokan pada posisi 8 (karakter “n”) nilai pergeserannya = 1
-sehingga geser string sebesar 2 posisi (nilai maksimal dari kedua tabel pergeseran)

tahap 4

-”a” tidak cocok dengan “n”
-tabel OH : karakter “a” nilai pergeserannya = 1 belum ada karakter yang cocok
-tabel MH : ketidakcocokan pada posisi 8 (karakter “n”) nilai pergeserannya = 1
-sehingga geser string sebesar 1 posisi (nilai maksimal dari kedua tabel pergeseran)

tahap 5

-”n” cocok dengan “n”
-”a” cocok dengan “a”
-”m” cocok dengan “m”
-”m” cocok dengan “n”
-tabel OH : karakter “m” nilai pergeserannya = 2, sudah ada 3 karakter cocok, nilai pergeseran = 2-3=-1 (pergeseran tidak mungkin dilakukan, hal ini merupakan kekurangan tabel occurence heuristic, ada kemungkinan nilai pergeseran menjadi negatif)
-tabel MH : ketidakcocokan pada posisi 5 (karakter “n”) nilai pergeserannya = 6
-sehingga geser string sebesar 6 posisi (nilai maksimal dari kedua tabel pergeseran)

tahap 6

-”n” cocok dengan “n”
-”a” cocok dengan “a”
-”k” tidak cocok dengan “m”
-tabel OH : karakter “k” tidak ada dalam string, sudah ada 2 karakter cocok, sehingga nilai pergeserannya = 8-2=6
-tabel MH : ketidakcocokan pada posisi 6 (karakter “m”) nilai pergeserannya = 3
-sehingga geser string sebesar 6 posisi (nilai maksimal dari kedua tabel pergeseran)

tahap 7

-”n” cocok dengan “n”
-”a” cocok dengan “a”
-”p” tidak cocok dengan “m”
-tabel OH : karakter “p” nilai pergeseran 5, sudah ada 2 karakter cocok, sehingga nilai pergeserannya = 5-2=3
-tabel MH : ketidakcocokan pada posisi 6 (karakter “m”) nilai pergeserannya = 3
-sehingga geser string sebesar 3 posisi (nilai maksimal dari kedua tabel pergeseran)

tahap 8

semua karakter cocok, string yang dicari telah ditemukan.

Catatan :
dalam sumber lain Occurence Heuristic disebut Bad-Character shift dan Match Heuristic disebut Good-Suffix shift, teapi pada dasarnya nilai pergeseran yang dihasilkan adalah sama.

karena banyak yang minta source codenya, saya sediakan source codenya yang dulu pernah saya buat pake VB.Net, semoga membantu . Silahkan download di sini

Referensi :
http://en.wikipedia.org/wiki/Boyer-Moore
http://www-sr.informatik.uni-tuebingen.de/~buehler/BM/BM.html
William B. Frakes dan Ricardo Baeza-Yates, Information Retrieval Data Structures & Algorithms (New Jersey : Prentice-Hall, Inc. 1992), hal. 224.