Algoritma Horspool
Dekskripsi Algoritma Horspool
Algoritma
Horspool merupakan penyederhanaan dari algoritma Boyer-Moore. Perbedaan antara
keduanya adalah pada metode penggeseren patternnya. Jika Boyer-Moore
menggunakan dua metode praproses bad character shift dan good shufix
shift, akan tetapi Horspool hanya menggunakan satu metode praproses yaitu bad
character shift. Kompleksitas
rata-rata algoritma ini sama dengan Boyer-Moore O(n), seangkan untuk metode
praproses nya adalah O(m+σ).
Cara Kerja Algoritma
Algoritma Horspool hampir mirip dengan algoritma
Boyer-Moore, pergeseran pada Algoritma Horspool adalah :
·
Menggunakan pencocokan
pattern indeks terakhir dengan text.
·
jika pattern indek terakhir
terjadi kesaaaman dengan text maka akan dilakukan pengecekan unutk indek
pattern sebelumnya.
·
Hal itu dilakukan secara
terus menerus sampai ditemukanya pattern pada teks.
Analisis Hasil :
Pada running time text yang diinputkan adalah “program studi
informatika fmipa uns”. Dengan pattern sebagai berikut :
·
Untuk best case = “program”
·
Untuk average case =
“informatika”
·
Untuk worst case = “uns”
Setiap case akan dirunning
sebanyak 10 kali, sehingga didapatkan 10 data running time. Pada akhir data
akan disediakan rata-rata dari 10 running time, berikut penjelasan dari setiap
case :
1.
Penjelasan Base Case :
“program”
Match
Pada kasus ini tidak ada
pergeseran
2.
Penjelasan average case :
“informatika”
Terjadi 3 kali pergeseran pattern pada
kasus di atas.
3.
Penjelasan W
orst case:
”uns”
Pada kasus ini terjadi 12 pergeseran pattern,
yang mana apabila tidak ada kecocokan pada pattern indeks terakhir maka
langsung di lanjutkan pencocokan ke indeks teks selanjutnya sampai terjadi
matching.
Mungkin Cukup Sekian, apabila ada Komplain atau saran yang memabangun bisa komen di bawah :
Wassalamualaikum wr.wb
0 Comments