Quick Search Bad-Character Shift (qsBc)

Dua hari lalu, saya memandu salah seorang kawan saya untuk membuat suatu program sederhana. Program tersebut adalah program yang akan mencoba menemukan suatu pola atau substring tertentu dari suatu teks atau string. Program melakukan pencocokkan suatu pola atau substring dengan memanfaatkan suatu algoritma yang dikenal dengan nama algoritma Smith (Smith algorithm). Ternyata algoritma Smith memanfaatkan dua buah fungsi yang dia gunakan untuk melakukan pergeseran saat suatu karakter dalam pola yang coba dicari tidak cocok dengan karakter pada posisi tertentu dalam suatu string. Salah satu fungsi yang dipakai oleh algoritma tersebut berasal dari algoritma lain, yaitu algoritma Quick Search (Quick Search algorithm).

Algoritma Quick Search merupakan penyederhaan dari algoritma string matching yang lain, yaitu algoritma Boyer-Moore (Boyer-Moore algorithm). Algorithma Quick Search seperti halnya algoritma Boyer-Moore mendasarkan proses pencocokkan polanya terhadap string atau teks dengan menggunakan sistem window atau blok. Ukuran blok sesuai dengan panjang dari pattern atau pola yang coba dicari atau dicocokkan dengan string. Misalkan ukuran atau panjang dari pattern adalah m maka proses pencocokkan pattern akan dimulai dari posisi j sampai j+m pada string. Setiap kali ada suatu karakter dalam pattern yang tidak cocok dengan salah satu karakter pada string yang terletak antara posisi j sampai j+m, maka harus dilakukan penggeseran posisi pencocokkan berikutnya pada string. Penggeseran dilakukan dengan menggeser posisi pencocokkan awal pada string ( j ) untuk kemudian mulai melakukan pencocokkan lagi. Proses penggeseran j akan terus dilakukan sampai nilainya melebihi suatu posisi atau threshold (batas) tertentu.

Setelah posisi j melebihi posisi tertentu, maka proses pencocokkan akan berhenti. Proses pencocokkan dapat memberikan hasil yang memberitahu apakah proses pencocokkan yang telah dilakukan berhasil menemukan atau tidak pola yang dicari. Berikut adalah contoh baris kode dari fungsi Quick Search bad-character shift dalam bahasa C. Semoga bermanfaat dan jika Anda tertarik untuk mengembangkan suatu program atau software menggunakan algoritma Smith, Anda dapat menghubungi saya. Terima kasih.

void preQsBc(char *x, int m, int qsBc[])

{

int i;

for (i = 0; i < ASIZE; ++i)

qsBc[i] = m + 1;

for (i = 0; i < m; ++i)

qsBc[x[i]] = m - i;

}