String
searching merupakan suatu proses yang umum dilakukan dalam proses-proses
yang dilakukan komputer karena teks merupakan bentuk utama penyimpanan data.
Terdapat beberapa macam cara yang dapat dilakukan untuk mencari sebuah string
pada kumpulan string lain yang lebih besar. Beberapa diantaranya
adalah algoritma Boyer- Moore, Turbo Boyer-Moore dan Tuned Boyer-Moore. Guna
mengetahui bagaimana performa algoritma-algoritma tersebut, terutama di bidang
waktu yang diperlukan, maka dibuatlah aplikasi yang dapat digunakan untuk
mengetahui waktu yang diperlukan untuk mencari suatu pattern dalam text.
Permasalahan string
searching adalah untuk mencari beberapa karakter (pattern) dalam
sejumlah besar teks (Hartoyo, Vembrina, & Meilana, 2011). Dengan demikian
dapat disimpulkan bahwa pencarian string atau string searching adalah
pencarian sebuah pattern dari teks. Algoritma
yang digunakan untuk pencarian string semakin berkembang dari hari ke
hari. Tujuan utamanya tentu saja untuk mencari string seakurat dan
secepat mungkin. Hingga saat ini algoritma pencarian string terbagi atas
3 kategori berdasarkan arah pencocokan string yaitu dari kiri ke kanan,
kanan ke kiri, dan dari arah yang ditentukan secara spesifik. Metode pencocokan
dari kiri ke kanan merupakan metode yang paling natural karena sesuai dengan
arah membaca, pencocokan string dari kanan ke kiri merupakan metode yang
dianggap paling efisien dalam praktiknya, dan pencocokan string dari
arah yang ditentukan secara spesifik merupakan algoritma yang memiliki hasil
yang paling baik secara teoritis (Kumara, 2009).
Algoritma Boyer Moore merupakan
metode yang praktis dalam pencocokan string,
terutama dalam 2 kategori :
-
Alphabet yang luas (large)
-
Alphabet yang panjang
Algoritma yang dianggap memiliki hasil yang paling baik
dalam praktiknya merupakan algoritma yang bergerak mencocokan string dari
arah kanan ke kiri. Algoritma Boyer-Moore adalah salah satu contoh algoritma
yang menggunakan arah dari kanan ke kiri. Algoritma ini telah banyak dikenal
oleh masyarakat dan dianggap paling efisien untuk pencarian string. Ide
dibalik algoritma ini adalah bahwa dengan memulai pencocokkan karakter dari
kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat
(Fauzy, 2011). Algoritma ini kemudian dikembangkan sehingga tercipta algoritma
Turbo Boyer-Moore dan Tuned Boyer-Moore.
Algoritma pencarian string atau
sering disebut juga pencocokan string adalah algoritma untuk melakukan
pencarian semua kemunculan string pendek pattern[0..n − 1] yang
disebut pattern di string yang lebih panjang teks[0..m − 1] yang
disebut teks (Wiramuda, 2008).