Kita sering mendengar tentang Algoritma,terus algoritma sendiri itu apa?Algoritma menurut saya pribadi dan kebanyakan definisi yang saya temukan di internet mengacu pada suatu hal/ definisi yang sama, yaitu suatu cara/ langkah yang digunakan untuk menyelesaikan suatu kasus/ permasalahan/ pekerjaan tertentu. Algoritma tidak hanya berlaku di dalam dunia pemrograman, namun lingkupnya luas mencakup ke seluruh aspek kehidupan manusia. Namun memang Algoritma lebih sering dikaitkan dengan pemrograman komputer itu sendiri. Dalam Algoritma, pasti terdapat alur proses penyelesaian masalah, dimana biasanya mencakup Input, lalu Proses, hingga berakhir pada suatu Output yang diinginkan. Mengapa saya katakan biasanya? Karena terkadang ada ada program komputer yang dibuat tanpa ada Input, namun langsung menghasilkan suatu Output tertentu. Mungkin program – program iseng, atau bagi mereka yang termasuk baru belajar pemrogramman. Nah, dalam menyelesaikan suatu permasalahan, suatu Algoritma yang dibuat hendaknya memenuhi beberapa kriteria berikut :
- Finite (Terbatas)
Disini maksudnya adalah suatu Algoritma harus berhenti setelah beberapa langkah yang dilaksanakan. Tidak mungkin suatu Algoritma akan terus berjalan jika hasil yang diharapkan sudah didapat. Itu == buang waktu == tidak efisien.
- Presisi (Tepat, pas)
Algoritma yang dibuat harus tepat sesuai apa yang diinginkan. Jika permasalahan yang dihadapi adalah cara mencari luas suatu segitiga, maka Algoritma yang digunakan harus berakhir/ menghasilkan luas segitiga yang diinginkan sesuai input yang diberikan, seperti panjang alas dan tinggi segitiga tersebut.
- Complete (Lengkap)
Lengkap di sini maksudnya adalah Algoritma yang dibuat harus lengkap, dalam menyelesaikan suatu permasalahan. Tidak ada Algoritma yang berhenti di tengah jalan namun hasil yang diharapkan tidak didapatkan. Jika kita dihadapkan pada suatu kasus, misalkan saja mencari luas segitiga, maka keseluruhan alur harus lengkap, baik dari Input, Proses, hingga Output.
Tentunya masih ada kriteria – kriteria lain yang menurut orang lain dianggap harus dipenuhi, namun bagi saya sendiri kriteria – kriteria di atas sudah cukup.
Untuk Postingan edisi kali ini saya akan menjelaskan cara kerja dari sebuah algoritma pencarian string dalam dokumen teks, yaitu algoritma Boyer-Moore. Boyer-Moore secara rata-rata merupakan algoritma pencarian string yang paling baik jika dibandingkan dengan algoritma pencarian string lainnya seperti Brute-Force ataupun Knuth-Morris-Pratt. Jika kita menggunakan fasilitas Find/Search pada berbagai aplikasi pengolah teks, web browser, dan aplikasi lainnya mungkin saja kita telah memanfaatkan algoritma Boyer-Moore dalam pencarian tersebut, karena algoritma ini paling banyak diimplementasikan dalam berbagai aplikasi untuk fasilitas pencarian teksnya.
Algoritma Boyer-Moore adalah salah satu algoritma untuk mencari suatu string di dalam teks, dibuat oleh R.M Boyer dan J.S Moore. Ide utama algoritma ini adalah mencari string dengan melakukan pembandingan karakter mulai dari karakter paling kanan dari string yang dicari. Dengan mengunakan algoritma ini, secara rata-rata proses pencarian akan menjadi lebih cepat jika dibandingakan dengan algoritma lainnya. alasan melakukan pencocokan dari kanan (posisi terakhir string yang dicari) ditunjukan dalam contoh berikut:
Pada contoh diatas, dengan melakukan pembandingan dari posisi paling akhir string dapat dilihat bahwa karakter “n” pada string “kanan” tidak cocok dengan karakter “o” pada string “radio” yang dicari, dan karakter “n” tidak pernah ada dalam string “radio” yang dicari sehingga string “radio” dapat digeser melewati string “kanan” sehingga posisinya menjadi :
Dalam contoh terlihat bahwa algoritma Boyer-Moore memiliki loncatan karakter yang besar sehingga mempercepat pencarian string karena dengan hanya memeriksa sedikit karakter, dapat langsung diketahui bahwa string yang dicari tidak ditemukan dan dapat digeser ke posisi berikutnya.
Langkah-langkah algoritma Boyer-Moore :
- Buat tabel pergeseran string yang dicari (S) dengan pendekatan Match Heuristic (MH) dan Occurence Heuristic (OH), untuk menentukan jumlah pergeseran yang akan dilakukan jika mendapat karakter tidak cocok pada proses pencocokan dengan string (T).
- Jika dalam proses pembandingan terjadi ketidakcocokan antara pasangan karakter pada S dan karakter pada T, pergeseran dilakukan dengan memilih salah satu nilai pergeseran dari dua tabel analisa string, yang memiliki nilai pergeseran paling besar.
- Dua kemungkinan penyelesaian dalam melakukan pergeseran S, jika sebelumnya belum ada karakter yang cocok adalah dengan melihat nilai pergeseran hanya pada tabel occurence heuristic : Jika karakter yang tidak cocok tidak ada pada S maka pegeseran adalah sebanyak jumlah karakter pada S. dan jika karakter yang tidak cocok ada pada S, maka banyaknya pergeseran bergantung dari nilai pada tabel.
- Jika karakter pada teks yang sedang dibandingkan cocok dengan karakter pada S, maka posisi karakter pada S dan T diturunkan sebanyak 1 posisi, kemudian lanjutkan dengan pencocokan pada posisi tersebut dan seterusnya. Jika kemudian terjadi ketidakcocokan karakter S dan T, maka pilih nilai pergeseran terbesar dari dua tabel analisa pattern yaitu nilai dari tabel match heuristic dan nilai tabel occurence heuristic dikurangi dengan jumlah karakter yang telah cocok.
- Jika semua karakter telah cocok, artinya S telah ditemukan di dalam T, selanjutnya geser pattern sebesar 1 karakter.
- Lanjutkan sampai akhir string T.
Cara Menghitung Tabel Occurence Heuristic :
contoh string : "manaman"
Panjang : 7 karakter
Tabel Occurence Heuristic
- Lakukan pencacahan mulai dari posisi terakhir string sampai ke posisi awal, dimulai dengan nilai 1, catat karakter yang sudah ditemukan (dalam contoh ini karakter “n”)
- Mundur ke posisi sebelumnya, nilai pencacah ditambah 1, jika karakter pada posisi ini belum pernah ditemukan, maka nilai pergeserannya adalah sama dengan nilai pencacah. (dalam contoh ini, karakter “a” belum pernah ditemukan sehingga nilai pergeserannya adalah sebesar nilai pencacah yaitu 2)
- Mundur ke posisi sebelumnya, karakter “m” nilai pergeserannya 3
- Mundur lagi, karakter “a”. karakter “a” sudah pernah ditemukan sebelumnya sehingga nilai pergeserannya sama dengan nilai pergesean karakter “a” yang sudah ditemukan paling awal yaitu 2.
- Begitu seterusnya sampai posisi awal string.
catatan : untuk karakter selain “m”,”a” dan “n” nilai pergeseran sebesar panjang string yaitu 7 karakter.
Cara Menghitung Tabel Match Heuristic :
contoh string : manaman
Panjang : 7 karakter
Tabel Match Heuristic
Langkah-langkah perhitungannya adalah sebagai berikut :
jika karakter pada posisi 7 bukan “n” maka geser 1 posisi, berlaku untuk semua string yang dicari.
jika karakter “n” sudah cocok, tetapi karakter sebelum “n” bukan “a” maka geser sebanyak 7 posisi, sehingga posisi string melewati teks.karena sudah pasti “manambn” bukan “manaman”
jika karakter “man” sudah cocok, tetapi karakter sebelum “man” bukan “a” maka geser sebanyak 4 posisi, sehingga posisi string berada / bersesuaian dengan akhiran “man” yang sudah ditemukan sebelumnya. karena bisa saja akhiran “man” yang sudah ditemukan sebelumnya merupakan awalan dari string “manaman” yang berikutnya.
jika karakter “aman” sudah cocok, tetapi karakter sebelum “aman” bukan “n” maka geser sebanyak 4 posisi, sehingga posisi string berada / bersesuaian dengan akhiran “man” yang sudah ditemukan sebelumnya, karena bisa saja akhiran “man” yang sudah ditemukan sebelumnya merupakan awalan dari string “manaman” yang berikutnya
selanjutnya sama, pergseran paling mungkin dan aman dalam tabel Match Heuristic adalah pergeseran sebanyak 4 posisi.
Contoh Kasus
Dalam implementasinya, algoritma Boyer-Moore akan memilih nilai pergeseran terbesar dari 2 tabel pergeseran (Occurence Heuristic dan Match Heuristic). Saya akan menjelaskan implementasi algoritma Boyer-Moore dalam sebuah contoh kasus berikut ini :
teks : berikut ini anpamman bukan anpanman
pada tabel OH, –> selain karakter “a”,”n”,”p”,”m” nilai pergeseran sebesar panjang string yaitu 8
tahap 1
spasi tidak cocok dengan “n”
-tabel OH : karakter spasi 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)
tahap 2
-”a” tidak cocok dengan “n”
-tabel OH : karakter “a” nilai pergeserannya = 1 belum ada karakter yang cocok
-tabel MH : ketidakcocokan pada posisi 8 (karakter “n”) nilai pergeserannya = 1
-sehingga geser string sebesar 1 posisi (nilai maksimal dari kedua tabel pergeseran)
tahap 3
m” tidak cocok dengan “n”
-tabel OH : karakter “m” nilai pergeserannya = 2 belum ada karakter yang cocok
-tabel MH : ketidakcocokan pada posisi 8 (karakter “n”) nilai pergeserannya = 1
-sehingga geser string sebesar 2 posisi (nilai maksimal dari kedua tabel pergeseran)
tahap 4
-”a” tidak cocok dengan “n”
-tabel OH : karakter “a” nilai pergeserannya = 1 belum ada karakter yang cocok
-tabel MH : ketidakcocokan pada posisi 8 (karakter “n”) nilai pergeserannya = 1
-sehingga geser string sebesar 1 posisi (nilai maksimal dari kedua tabel pergeseran)
tahap 5
”n” cocok dengan “n”
-”a” cocok dengan “a”
-”m” cocok dengan “m”
-”m” cocok dengan “n”
-tabel OH : karakter “m” nilai pergeserannya = 2, sudah ada 3 karakter cocok, nilai pergeseran = 2-3=-1 (pergeseran tidak mungkin dilakukan, hal ini merupakan kekurangan tabel occurence heuristic, ada kemungkinan nilai pergeseran menjadi negatif)
-tabel MH : ketidakcocokan pada posisi 5 (karakter “n”) nilai pergeserannya = 6
-sehingga geser string sebesar 6 posisi (nilai maksimal dari kedua tabel pergeseran)
tahap 6
-”n” cocok dengan “n”
-”a” cocok dengan “a”
-”k” tidak cocok dengan “m”
-tabel OH : karakter “k” tidak ada dalam string, sudah ada 2 karakter cocok, sehingga nilai pergeserannya = 8-2=6
-tabel MH : ketidakcocokan pada posisi 6 (karakter “m”) nilai pergeserannya = 3
-sehingga geser string sebesar 6 posisi (nilai maksimal dari kedua tabel pergeseran)
tahap 7
-”n” cocok dengan “n”
-”a” cocok dengan “a”
-”p” tidak cocok dengan “m”
-tabel OH : karakter “p” nilai pergeseran 5, sudah ada 2 karakter cocok, sehingga nilai pergeserannya = 5-2=3
-tabel MH : ketidakcocokan pada posisi 6 (karakter “m”) nilai pergeserannya = 3
-sehingga geser string sebesar 3 posisi (nilai maksimal dari kedua tabel pergeseran)
tahap 8
semua karakter cocok, string yang dicari telah ditemukan.
Catatan :
dalam sumber lain Occurence Heuristic disebut Bad-Character shift dan Match Heuristic disebut Good-Suffix shift, teapi pada dasarnya nilai pergeseran yang dihasilkan adalah sama.
Untuk implementation mari perhatikan listing berikut dibawah ini:
# include <limits.h>
# include <string.h>
# define ALPHABET_SIZE (1 << CHAR_BIT)
static void compute_prefix(const char* str, size_t size, int result[size]) {
size_t q;
int k;
result[0] = 0;
k = 0;
for (q = 1; q < size; q++) {
while (k > 0 && str[k] != str[q])
k = result[k-1];
if (str[k] == str[q])
k++;
result[q] = k;
}
}
static void prepare_badcharacter_heuristic(const char *str, size_t size,
int result[ALPHABET_SIZE]) {
size_t i;
for (i = 0; i < ALPHABET_SIZE; i++)
result[i] = -1;
for (i = 0; i < size; i++)
result[(size_t) str[i]] = i;
}
void prepare_goodsuffix_heuristic(const char *normal, size_t size,
int result[size + 1]) {
char *left = (char *) normal;
char *right = left + size;
char reversed[size+1];
char *tmp = reversed + size;
size_t i;
/* reverse string */
*tmp = 0;
while (left < right)
*(--tmp) = *(left++);
int prefix_normal[size];
int prefix_reversed[size];
compute_prefix(normal, size, prefix_normal);
compute_prefix(reversed, size, prefix_reversed);
for (i = 0; i <= size; i++) {
result[i] = size - prefix_normal[size-1];
}
for (i = 0; i < size; i++) {
const int j = size - prefix_reversed[i];
const int k = i - prefix_reversed[i]+1;
if (result[j] > k)
result[j] = k;
}
}
/*
* Boyer-Moore search algorithm
*/
const char *boyermoore_search(const char *haystack, const char *needle) {
/*
* Calc string sizes
*/
size_t needle_len, haystack_len;
needle_len = strlen(needle);
haystack_len = strlen(haystack);
/*
* Simple checks
*/
if(haystack_len == 0)
return NULL;
if(needle_len == 0)
return NULL;
if(needle_len > haystack_len)
return NULL;
/*
* Initialize heuristics
*/
int badcharacter[ALPHABET_SIZE];
int goodsuffix[needle_len+1];
prepare_badcharacter_heuristic(needle, needle_len, badcharacter);
prepare_goodsuffix_heuristic(needle, needle_len, goodsuffix);
/*
* Boyer-Moore search
*/
size_t s = 0;
while(s <= (haystack_len - needle_len))
{
size_t j = needle_len;
while(j > 0 && needle[j-1] == haystack[s+j-1])
j--;
if(j > 0)
{
int k = badcharacter[(size_t) haystack[s+j-1]];
int m;
if(k < (int)j && (m = j-k-1) > goodsuffix[j])
s+= m;
else
s+= goodsuffix[j];
}
else
{
return haystack + s;
}
}
/* not found */
return NULL;
}sekian dulu postingan dari saya,semoga artikel ini bisa membantu
teman-teman semua untuk lebih mengetahui apa itu Boyer-moore
dan bagaimana pula algoritmanya
Referensi:
http://en.wikipedia.org/wiki/Boyer-Moore
http://en.wikipedia.org/w/index.php?title=Boyer%E2%80%93Moore_string_search_algorithm&action=edit§ion=6
