Contoh kasus sederhana penerapan algoritma Boyer-Moore

berikut ini contoh kasus sederhana penerapan algoritma boyer-moore.
pattern : RESTORAN
string    : SAYA MAU MAKAN BAKSO SAPI DI RESTORAN PASTISEDAP
Sebelum mulai pencarian, algoritma BM ini perlu menghitung nilai pergeseran dari pattern yg akan dicari. jadi pasti akan ada 2 tabel pergeseran(OH dan MH). Nanti pada saat mulai mencari, jika terjadi ketidakcocokan karakter, algoritma akan memilih salah satu nilai pergeseran yang akan dilakukan. nilai pergeseran yang dipilih adalah yang
paling maksimal, supaya pencarian menjadi lebih cepat.

tabel Occurence Heuristic

untuk OH kelihatannya tidak perlu dijelaskan lagi. Sudah sangat jelas disini. hehehe
tabel Match Heuristic

untuk setiap langkah, baris pertama adalah potongan string, dan baris kedua adalah pattern yg dicari. Jadi untuk MH, point utamanya adalah “pergeseran dilakukan berdasarkan posisi ketidakcocokan karakter yang terjadi”, maksudnya untuk menghitung MH, kita perlu tahu pada posisi ke berapa terjadi ketidakcocokan. posisi ketidakcocokan itulah yang akan menentukan besar pergeseran. berbeda dengan OH yang menentukan nilai pergeseran berdasarkan karakter apa yang menyebabkan tidak cocok.


Cara perhitungannya adalah sebagai berikut.
langkah-1
untuk ketidakcocokan karakter pada posisi 8, karakter “N” maka nilai pergeserannya selalu 1
langkah-2
jika karakter “N” sudah cocok, tetapi karakter pada posisi 7 (sebelum “N”) bukan “A” maka geser sebanyak 8 posisi, sehingga posisi string melewati teks.karena sudah pasti “RESTORZN” bukan “RESTORAN”
langkah-3
jika karakter “AN” sudah cocok, tetapi karakter pada posisi 6 (sebelum “AN”) bukan “R” maka geser sebanyak 8 posisi, sehingga posisi string melewati teks.karena sudah pasti “RESTOZAN” bukan “RESTORAN”
langkah-4
jika karakter “RAN” sudah cocok, tetapi karakter pada posisi 5 (sebelum “RAN”) bukan “O” maka geser sebanyak 8 posisi, sehingga posisi string melewati teks.karena sudah pasti “RESTZORAN” bukan “RESTORAN”
langkah-5
jika karakter “ORAN” sudah cocok, tetapi karakter pada posisi 4 (sebelum “ORAN”) bukan “T” maka geser sebanyak 8 posisi, sehingga posisi string melewati teks.karena sudah pasti “RESZORAN” bukan “RESTORAN”
langkah-6
jika karakter “TORAN” sudah cocok, tetapi karakter pada posisi 3 (sebelum “TORAN”) bukan “S” maka geser sebanyak 8 posisi, sehingga posisi string melewati teks.karena sudah pasti “REZTORAN” bukan “RESTORAN”
langkah-7
jika karakter “STORAN” sudah cocok, tetapi karakter pada posisi 2 (sebelum “STORAN”) bukan “E” maka geser sebanyak 8 posisi, sehingga posisi string melewati teks.karena sudah pasti “RZSTORAN” bukan “RESTORAN”
langkah-8
jika karakter “ESTORAN” sudah cocok, tetapi karakter pada posisi 1 (sebelum “ESTORAN”) bukan “R” maka geser sebanyak 8 posisi, sehingga posisi string melewati teks.karena sudah pasti “ZESTORAN” bukan “RESTORAN”
Selanjutnya proses pencarian pattern “RESTORAN” di dalam string
langkah-1

-”U” tidak cocok dengan “N”
selanjutnya algo membandingkan nilai pergeseran dari 2 tabel.
-tabel OH : karakter “U” 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)
dapat dilihat perbedaan karakter dari 2 tabel, tabel OH melihat “karakter APA yang menyebabkan ketidakcocokan” sedangkan tabel MH melihat “karakter PADA POSISI KEBERAPA yang menyebabkan ketidakcocokan”
tabel OH : karakter yang menyebabkan ketidakcocokan adalah “U” nilai pergeseran untuk karakter “U” adalah 8.
tabel MH : karakter yang menyebabkan ketidakcocokan adalah karakter pada posisi 8, dan nilai pergeseran apabila terjadi ketidakcocokan pada posisi 8 adalah sebesar 1.
seanjutnya 8>1 kan? maka daripada cuma menggeser pattern sebanyak 1 karakter, lebih baik jika melakukan pergeseran sebesar 8 karakter.
langkah-2

-”B” tidak cocok dengan “N”
-tabel OH : karakter “B” 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)
langkah-3

-”P” tidak cocok dengan “N”
-tabel OH : karakter “P” 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)
langkah-4

-”S” tidak cocok dengan “N”
-tabel OH : karakter “S” nilai pergeserannya = 5 belum ada karakter yang cocok
-tabel MH : ketidakcocokan pada posisi 8 (karakter “N”) nilai pergeserannya = 1
-sehingga geser string sebesar 5 posisi (nilai maksimal dari kedua tabel pergeseran)
setelah digeser 5 karakter, pattern ditemukan.