Algoritma Pencarian Substring dalam String Horspool : Pengertian, Konsep Dasar, Soal, dan Cara Kerja

Saat ini hampir segala aplikasi atau perangkat lunak populer yang digunakan oleh umat manusia memiliki fitur pencarian. Fitur pencarian menjadi salah satu fitur yang sangat penting untuk diterapkan dalam aplikasi. Pasalnya, fitur pencarian ini memiliki utilitas atau manfaat yang sangat besar dalam mempermudah user atau pengguna aplikasi dalam mencari data yang dibutuhkan.

Adapun hadirnya fitur pencarian bertujuan untuk mempermudah user atau pengguna aplikasi dalam mencari data tanpa harus melakukan pengecekan semua data satu - persatu, melainkan hanya dengan mengetikkan beberapa huruf atau dalam bahasan ini disebut dengan pattern atau substring, data yang dicari pun akan ditampilkan dengan segara pada aplikasi. Pada saat pengguna menggunakan fitur pencarian ini, maka sebenarnya dibelakang aplikasi tersebut berjalan bagian baris kode sebuah algoritma pencarian substring dalam string.

Algoritma Boyer-Moore-Horspool atau dapat disebut juga sebagai algoritma Horspool merupakan salah satu algoritma yang masuk dalam kategori algoritma pencarian substring dalam string yang dapat digunakan oleh seorang pemrogram untuk membuat aplikasi atau program yang dapat mencari atau menemukan data dengan menggunakan suatu pattern atau substring.

Algoritma ini diterbitkan oleh Nigel Horspool pada tahun 1980. Algoritma Horspool sendiri juga umum dikenal sebagai algoritma Boyer-Moore-Horspool, sebab algoritma Horspool sendiri merupakan versi pengembangan dan penyederhanaan dari algoritma pencarian substring lainnya yang telah diterbitkan lebih dulu tiga tahun sebelumnya, yaitu algortima Boyer-Moore yang diciptakan oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977.

Tahapan dalam Algoritma Horspool

Pencocokan dimulai dari char yang berada pada index terakhir pada pattern
Jika char pada string dan char pada pattern sama, maka perbandingan dilanjutkan kembali pada char index ke (n-1) pada pattern
Jika char pada string berbeda dengan char pada pattern, maka lakukan pergeseran sebanyak value Bad Match Table dari char pada pattern tersebut.

Adapun penulis ingin mengingatkan bahwa tahapan pada algoritma Horspool ini akan lebih mudah dipahami apabila diterapkan pada soal yang akan penulis jabarkan pada bagian selanjutnya.

Soal dan Cara Kerja Algoritma Horspool

Penulis akan menggunakan contoh sebagai berikut:

Pattern : ikako
String : informatikakoding

Bagaimanakah cara atau proses algoritma Horspool untuk menemukan substring atau pattern ikako diatas pada string informatikakoding? Pertama-tama tentukan terlebih dahulu value dan index untuk tiap-tiap huruf atau char pada pattern, untuk mendapatkan value pada tiap-tiap char didapatkan dari rumus sebagai berikut :

value = panjang pattern - index - 1

Panjang pattern adalah jumlah char yang terdapat pada pattern, sedangkan index merupakan urutan char di dalam pattern yang dimulai dari nol, berikut adalah index yang dimiliki oleh tiap-tiap char dalam pattern:

Selanjutnya, dengan index dan rumus untuk mencari value yang telah diketahui diatas maka didapatkan value untuk tiap-tiap char dalam pattern i k a k o sebagai berikut:

value
i : 5 - 0 - 1 = 4
k : 5 - 1 - 1 = 3
a : 5 - 2 - 1 = 2
k : 5 - 3 - 1 = 1
o : 5 - 4 - 1 = 0

Setelah mendapatkan value untuk tiap-tiap char dalam pattern, maka selanjutnya adalah menentukan nilai Bad Match Table untuk setiap char. Bad Match Table sendiri merupakan jumlah lompatan atau pergeseran posisi yang akan dilakukan saat proses perbandingan antara pattern dan string yang akan dilakukan selanjutnya.

Adapun nilai Bad Match Table untuk setiap char adalah value yang telah didapatkan sebelumnya. Sangat penting untuk diingat bahwa berlaku pengecualian untuk char terakhir pada pattern yaitu char o. Pada char terakhir ini, nilai Bad Match Tablenya tidak diambil dari value diatas, melainkan berasal dari panjang pattern atau jumlah char yang ada pada pattern tersebut.

Perlu diingat pula bahwa bila terdapat dua buah char yang sama dalam pattern seperti char k pada pattern i k a k o, maka char yang diambil untuk dimasukkan kedalam Bad Match Table adalah char dengan value terkecil. Berikut adalah Bad Match Table untuk pattern i k a k o :

Sebelum melanjutkan ke tahap selanjutnya, penulis ingin mengingatkan kepada para pembaca bahwa mulai pada bagian ini dan seterusnya, istilah Bad Match Table akan penulis ganti dengan singkatan BMT.

Selanjutnya dapat dilihat pada BMT diatas bahwa terdapat tanda * (bintang) yang tidak terdapat pada pattern. Adapun tanda bintang tersebut merupakan nilai untuk else, yaitu apabila saat proses perbandingan atau pencarian substring dalam string dijalankan terdapat char pada string yang tidak ditemukan pada pattern. Adapun BMT ini akan lebih mudah untuk dipahami setelah dan selama menjalankan proses pencarian yang akan dilakukan pada tahap berikutnya.

Setelah semua nilai yang diperlukan telah diketahui, barulah selanjutnya proses perbandingan atau pencarian substring dalam string dilakukan seperti yang terlihat pada tabel pencocokan sebagai berikut:

Untuk mencari substring dalam string, maka dilakukanlah perbandingan antara char yang ada dalam pattern dan juga char yang ada dalam string. Perbandingan dimulai dari char dengan urutan terakhir pada pattern sehingga didapatkanlah perbandingan pertama, yaitu antara char r pada string dan char o pada pattern.

Dapat dilihat pada perbandingan char pertama bahwa char r dan char o adalah dua buah char yang berbeda. Oleh karena itu, pattern akan digeser sebanyak nilai dari BMT dari char yang ada pada string yang dibandingkan saat ini, yaitu char r. Pada tabel BMT terlihat bahwa nilai BMT untuk char r tidak tersedia. Oleh karena itu, maka nilai yang digunakan adalah nilai else yang disimbolkan dengan tanda * yang bernilai sama dengan jumlah char dalam pattern yaitu lima sehingga dilakukanlah pergeseran ke arah kanan sebanyak lima kali. Tabel BMT pun sekarang telah berubah menjadi sebagai berikut karena pergeseran posisi yang dilakukan:

Selanjutnya dilakukan kembali proses yang sama seperti sebelumnya, yaitu melakukan perbandingan char urutan terakhir pada string dan pada pattern. Dapat dilihat pada tabel perbandingan diatas bahwa char k tidak sama dengan char o. Oleh karena itu, dilakukan pergeseran ke arah kanan sebanyak nilai BMT dari char k yang bernilai satu sehingga tabel perbandingan akan menjadi sebagai berikut:

Dapat dilihat pada tabel perbandingan bahwa kumpulan char yang terdapat pada pattern masih belum sesuai dengan kumpulan char pada string yang berada diatas kumpulan char pada pattern tersebut, maka proses perbandingan ini akan terus berjalan hingga akhirnya semua char pada pattern sesuai dengan char yang ada di atasnya yaitu char pada string.

Oleh sebab itu, Selanjutnya dilakukan kembali proses yang sama seperti sebelumnya, yaitu melakukan perbandingan char urutan terakhir pada string dan pada pattern. Dapat dilihat pada tabel perbandingan diatas bahwa char a tidak sama dengan char o. Oleh karena itu, dilakukan pergeseran ke arah kanan sebanyak nilai BMT dari char a yang bernilai dua sehingga tabel perbandingan akan menjadi sebagai berikut:

Dapat dilihat pada tabel perbandingan diatas bahwa semua char pada string setelah dibandingkan dari kanan ke kiri cocok atau sama dengan semua char pada pattern, maka proses pencarian substring atau pattern telah berhasil dilakukan dengan algortima Horspool.

Tambahan

Pada contoh dengan string dan pattern lainnya saat proses perbandingan, seringkali ditemukan bahwa hanya beberapa char saja yang sama seperti pada contoh berikut:

Pada tabel perbandingan diatas, dapat dilihat bahwa char terakhir pada pattern t o o t h sama atau sesuai dengan char pada string yang berada diatasnya h pada pattern dan h pada string. Pada kasus seperti ini, apabila terjadi kesamaan dalam perbandingan, proses perbandingan tidak serta merta berhenti begitu saja, melainkan dilakukan kembali perbandingan pada char sebelumnya pada pattern dengan char pada string yang berada diatasnya.

Dalam kasus diatas, selanjutnya yang dibandingkan adalah t pada pattern dengan t pada string. Dapat dilihat bahwa perbandingannya sama kembali seperti sebelumnya, maka lakukan perbandingan pada char yang berada sebelum char t pada pattern yaitu char o. Didapatkanlah perbandingan char s pada string dengan char o pada pattern maka ditemukan setelah dibandingan dua char ini merupakan char yang berbeda, maka proses pergeseran posisi pattern pun berjalan kembali untuk menyesuaikan posisi-posisi charnya.

Proses perbandingan pada algoritma horspool ini akan berhenti ketika semua char pada pattern saat dibandingkan dari char urutan terakhir sampai dengan char urutan paling awal semuanya sama yang berarti pula bahwa proses pencarian substring atau pattern di dalam string pun telah berhasil.

Para pembaca bisa menggunakan string dan pattern lainnya untuk melatih kemampuan dan pemahaman terkait algoritma Horspool, terutama dengan contoh yang cukup populer dengan string dan pattern sebagai berikut:

string : trusthardtoothbrushes
pattern : tooth