studi perbandingan implementasi algoritma naive method

Studi Perbandingan Implementasi

Algoritma Naive Method, Knuth-Morris-Pratt,

dan Boyer-Moore-Hoorspool

pada Multi Record Database

Artikel Ilmiah

Diajukan kepada

Fakultas Teknologi Informasi

untuk memperoleh Gelar Sarjana Komputer

Oleh :

Yoseph Kurniawan Sunarto

NIM : 672013720

Program Studi Teknik Informatika


Universitas Kristen Satya Wacana

Salatiga

Juni 2015





1)

Yoseph Kurniawan Sunarto, 2)

Sri Yulianto J.P




Jl. Diponegoro 52-60 Salatiga

Email : 1)

[email protected] , 2)

[email protected]

ABSTRAK

Pencocokan string adalah sebuah hal yang kita lakukan setiap hari. Sebagai

contohnya, kita melakukan pencocokan string saat kita mencari sebuah data atau artikel di

internet. Kita memasukkan kata kunci, kemudian browser mengirimkan kata kunci tersebut

ke sebuah server. Server tersebut melakukan algoritma pencarian. Setelah beberapa saat,

artikel yang kita cari berdasarkan kata kunci kita telah ditemukan.

Banyak sekali algoritma yang sampai hari ini terus dikembangkan. Salah satunya

adalah "Boyer-Moore-Hoorspool". Algoritma ini adalah pengembangan dari algoritma

sebelumnya, yaitu algoritma "Boyer-Moore".

Secara umum, algoritma "Boyer-Moore-Hoorspool" adalah salah satu dari algoritma

- algoritma pencocokan string yang efektif. Dengan kita menerapkan algoritma tersebut ke

dalam sebuah aplikasi search engine, maka kita akan membuat pencarian kita lebih cepat, dan

efisien dalam penggunaan waktu. Setelah dilakukan percobaan dan pengamatan pada seribu

data pada empat buah basisdata, sebuah kesimpulan dapat ditarik. Algoritma Boyer-Moore-

Hoorspool dapat melakukan optimasi pencarian yang sangat baik. Di saat metode tradisional

atau NaiveMethod sangat lambat dalam melakukan pencarian kata kunci, algoritma Boyer-

Moore-Hoorspool dapat melakukan optimasi mencapai 76.9%. Ini adalah hasil yang sangat

baik, dibandingkan dengan hasil sebesar 27.2% yang dicapai oleh algoritma pencarian string

modern lainnya, algoritma Knuth-Morris-Pratt.

Kata kunci: String matching algorithm, Boyer-Moore-Hoorspool, Searching Engine





1)

Yoseph Kurniawan Sunarto, 2)

Sri Yulianto J.P




Jl. Diponegoro 52-60 Salatiga

Email : 1)

[email protected] , 2)

[email protected]

ABSTRACT

String matching is a common thing that we do every day. For example, we are

doing a string matching when we are looking for a data or an article on internet. We type the

keyword, then the browser send our keyword to a server. The server will do a searching

algorithm. After a few seconds, articles we are looking forbased on the keywordhas been

found.

There are many algorithmswhich have been developed these days. One of those

strings searching algorithm is the “Boyer-Moore-Hoorspool” algorithm. This algorithm is a

development from its former, the “Boyer-Moore” algorithm.

Generally, “Boyer-Moore-Hoorspool” algorithm is one of the most effective string

searching algorithms. By applying the algorithm into a search engine application, we will

perform a faster and more efficient searching. After a research and observation over a

thousand data on four databases, a conclusion can be drawn. The Boyer-Moore-Hoorspool

can do a very good improvement in string matching. While the traditional method or the

Naïve Method is very slow in string matching, the Boyer-Moore-Hoorspool can improve the

rate of string matching by 79.6%. This is a very good result compared to the result of 27.2%

performed by another modern string matching algorithm, the Knuth-Morris-Pratt.

Keyword : String matching algorithm, Boyer-Moore-Hoorspool, Searching Engine

1. Pendahuluan

Mesin pencari atau search engine bukanlah barang baru di Indonesia. Dengan

sangat cepat Google, Yahoo, dan banyak penyedia layanan ini berkembang. Hal ini

tentu tidak dicapai dengan instan, ada waktu dan pengembangan yang terus menerus

dari pihak penyedia layanan pencarian ini. Metode pencarian data adalah metode yang

selalu dipakai oleh masyarakat. Masyarakat selalu ingin mendapatkan atau mencari

sesuatu dengan efektif (Desi, 2005). Jika semua ruang pencarian dan objek pencarian

dicampur dalam sebuah ruang yang tidak terpisah, maka akan menghabiskan waktu.

Jadi yang dicari oleh masyarakat adalah kecepatan dan akurasi pencarian..

Berdasarkan survey terdahulu yang dilakukan terhadap 100 orang responden

di daerah kota Ungaran pada bulan Maret 2015, pembatalan pencarian sebuah

informasi dalam sebuah artikel di internet akan dilakukan jika halaman websitetidak

memberikan respon dalam waktu 10 - 15 detik.

Sebuah mesin pencari menjadi lambat dalam menanggapipermintaan

penggunatidak hanya semata-mata karena tidak akuratnya algoritma yang digunakan

dalam mesin pencari tersebut, tapi bisa juga karena faktor mungkin terlalu banyak

obyek yang harus di-muatdi dalam sebuah halaman situs web, lalu lintas data

elektronikyang padat, dan bisa juga pengaruh bandwidth yang tidak besar. Meski kita

tidak bisa mengubah faktor bandwidth yang tidak besar, jika kita bisa

mengoptimalkan akurasi dan kecepatan algoritma pencarian dalam sebuah mesin

pencari maka kita bisa meminimalkan pembatalan pencarian oleh pengguna (Priyanto,

2014).

Dalam perkembangannya, string searching algorithm atau algoritma pencarian

string tidak hanya ada algoritma Boyer-Moore-Hoorspool saja, masih ada banyak

metode yang lain, seperti Algoritma Knuth-Morris-Pratt yang mulai dikembangkan

pada tahun 1977. Kedua algoritma Knuth-Morris-Pratt (KMP) dan Boyer-Moore-

Hoorspool (BMH) memiliki kemiripan dalam jalannya proses penghitungan dan

logika, tapi memiliki perbedaan yang cukup signifikan di dalam metode penentuan

awal pencocokan string. Algoritma Knuth-Morris-Pratt memulai penghitungan dari

indeks pertamakata kunci. Sedangkan pada algoritma Boyer-Moore-Hoorspool,

pencocokan dimulai dari indeks terakhir kata kunci, dengan tujuan untuk memberikan

hasil pencarian yang lebih cepat (Aulia, 2008).

Meski pun secara umum algoritma Boyer-Moore-Hoorspool terbukti lebih

efisien dalam melakukan pergeseran, percobaan, pengujian dan analisa algoritma

pencarian stringakan membantu melihat atau menentukan algoritma mana yang paling

cocok dan efektif untuk dipakai di dalam sebuah sistem pencarian string. Dalam

penulisan karya ilmiah ini, penulis membandingkan dan menganalisa tiga buah

algoritma pencarian string, yaitu Naive Method, Knuth-Morris-Pratt, dan Boyer-

Moore-Hoorspool. Ketiga algoritma ini akan dibandingkan, dan di analisa, untuk

mengetahui algoritma manakah yan paling efektif dalam pencarian kata kunci di

dalam basisdata multirecord.

2. Kajian Pustaka

Mesin pencari web (web searching engine) adalah program komputer yang

dirancang untuk melakukan pencarian atas berkas-berkas yang tersimpan dalam

layanan www, atau FTP (File Transfer Protocol), dalam sebuah ataupun sejumlah

komputer peladen (server) dalam suatu jaringan. Hasil pencarian umumnya

ditampilkan dalam bentuk daftar yang seringkali diurutkan menurut tingkat akurasi

ataupun rasio pengunjung atas suatu berkas. Informasi yang menjadi target pencarian

http://id.wikipedia.org/wiki/Program_komputer

http://id.wikipedia.org/wiki/Peladen

http://id.wikipedia.org/wiki/Jaringan_komputer

bisa terdapat dalam berbagai macam jenis berkas seperti halaman situs web, gambar,

ataupun jenis-jenis berkas lainnya. Beberapa mesin pencari juga diketahui melakukan

pengumpulan informasi atas data yang tersimpan dalam

suatu basisdata ataupun direktori web.

Untuk mendapatkan informasi-informasi yang dibutuhkan, pengunjung

internet masuk ke situs tersebut dan melakukan pencarian. Mesin pencari yang

terkenal adalah Google dan Yahoo. Gambar cara kerja mesin pencari secara umum :

Gambar 1 Cara kerja mesin pencari (sumber gambar)

Cara kerja mesin pencari pertama-tama menyalin semua halaman situs web

yang ada di dunia. Hal ini dilakukan oleh sebuah mesin atau sebuah program yang

biasa disebut dengan crawler, harvester, atau importer. Setelah data disalin dan

terdaftar dengan baik di dalam basisdata, maka saat pengguna mencari data yang

dibutuhkan, mesin pencari akan menampilkan data sesuai dengan kata kunci yang

dimasukkan pengguna.Mesin pencari akan berusaha sebisa mungkin menampilkan

data yang paling relevan dengan kata kunci yang dimasukkan olehpengguna.

Di dalam jurnal penelitian Satya Fajar Pratama yang berjudul “Pencocokan

DNA Pattern dengan Algoritma Boyer-Moore-Hoorspool” (2006), telah didapatkan

kesimpulan bahwa algoritma Boyer-Moore-Hoorspool adalah algoritma yang efektif

di gunakan untuk pencarian string di dalam sebuah pola kalimat karena telah

dibuktikan oleh penulis jurnal bahwa kecepatan algoritma ini sangat baik untuk

rangkaian string yang panjang sekalipun. Memang di dalam penelitian ini hanya

dipakai satu rangkaian string atau pola kalimat yang di cocokkan terhadap sebuah

kata kunci. Dengan dasar inilah maka penelitian ini dilakukan untuk membuktikan

kecepatan algoritma ini jika diaplikasikan ke dalam sebuah basisdata yang tentunya

tidak hanya memiliki satu data untuk dibandingkan.

Algoritma yang nantinya menjadi pembanding adalah algoritma tradisional,

yaitu Naïve Method, dan sebuah algoritma yang lebih modern, yaitu algoritma Knuth-

Morris-Pratt. Kedua metode ini dipilih untuk menjadi pembanding, dan diaplikasikan

ke dalam basisdata yang sama.

Metode Naive melakukan pencarian string dari indeks pertama kata kunci

yang dibandingkan dengan indeks pertama dari pola kalimat. Masing masing indeks

di cocokkan sampai terjadi kecocokan. Berbeda dengan algoritma tradisional,

sebelum melakukan pencocokan dan pencarian, algoritma Knuth-Morris-Pratt dan

Boyer-Moore-Hoorspool akan membangun sebuah tabel yang berisi nilai-nilai

pergeseran untuk setiap karakter yang terdapat di dalam kata kunci. Tabel ini akan di

http://id.wikipedia.org/wiki/Situs_web

http://id.wikipedia.org/wiki/Basisdata

http://id.wikipedia.org/wiki/Direktori_web

gunakan saat proses pencarian menemui ketidakcocokan atau mismatch. Tabel ini

akan menunjukkan berapa besar pergeseran yang dilakukan oleh algoritma tersebut.

Seberapa besar efisiensi pencarian string ini akan sangat bergantung dari seberapa

besarnya pergeseran yang bisa dilakukan oleh sebuah algoritma saat menemukan

ketidakcocokan karakter yang sedang dibandingkan.

2.1 Metode Naive

Metode ini adalah metode pencarian string yang paling sederhana. Setiap

karakter dalam kata kunci akan dibandingkan mulai dari indeks pertama dari pola

kalimat. Berikut adalah sebuah contoh bagaimana metode ini mencocokan sebuah

kata kunci.

Pola kalimat : SAYA MAU MAKAN BAKSO SAPI

Kata kunci : BAKSO

Dengan kasus ini, metode Naive akan melakukan pencarian seperti ini :

S A Y A M A U M A K A N B A K S O S A P I

B A K S O

Di indeks pertama kata kunci, ditemukan ketidakcocokan dengan pola kalimat

(mismatch), maka dilakukan pergeseran sebanyak satu karakter, sehingga terjadi

kondisi seperti ini :


B A K S O

Setelah pergeseran, indeks pertama kata kunci tidak cocok dengan pola kalimat,

sehingga dilakukan pergeseran lagi.


B A K S O

Terjadi ketidakcocokan lagi, sehingga harus dilakukan pergeseran lagi, sehingga

terjadi kondisi seperti ini :


B A K S O

Pada indeks pertama kata kunci tidak cocok dengan karakter pada pola kalimat,

sehingga akan terus dilakukan pergeseran dan pencocokan, sampai terjadi kondisi

seperti ini :


B A K S O

Setelah mengerjakan banyak pergeseran dan pencocokan, akhirnya algoritma

ini berhasil menemukan bahwa kata kunci ada di dalam pola kalimat.

Dalam pencocokan string, meskipun metode ini bisa menemukan hasil yang

dimaksud, tapi permasalahan nya adalah kecepatan. Jika pergeseran karakter yang

dilakukan seperti ini, maka algoritma ini akan memakan waktu yang cukup

lama.Berikut diagram alir jalannya algoritma ini :

Gambar 2Alur pencarian pada Metode Naive

Langkah pertama yang dilakukan adalah pengecekan awal, apakah karakter

pada indeks pertama kata kunci sama dengan indeks pertama dari pola kalimat. Jika

ditemukan sama, maka nilai kedua indeks akan di tambah masing masing satu, tapi

jika tidak, maka hanya nilai indeks pola kalimat yang ditambah satu. Ini artinya

dilakukan pergeseran sebanyak satu karakter pada pola kalimat.Pengecekan ini

dilakukan selama indeks terakhir kata kunci tidak melebihi indeks terakhir pada pola

kalimat tersebut. Hal ini mencegah adanya pengecekan setelah karakter terakhir dari

pola kalimat. Berikut pseudocode untuk mempermudah pengkodean metode Naive.

Kode Program 1 Pseudocode algoritma Naive

1. Baris 1 – 7 adalah definisi variabel yang akan dipakai dalam metode ini. Di

dalam metode ini, kata kunci dan pola kalimat akan diubah menjadi array satu

dimensi, agar pencocokan bisa dilakukan.

2. Baris 8 – 13 adalah bagian dimana sistem meminta masukan kata kunci dan

pola kalimat dari pengguna. Dan pada bagian ini, setiap masukan dari

pengguna, baik kata kunci maupun pola kalimat dimasukkan ke dalam array

yang sudah disediakan.

3. Baris 14 – 24 adalah baris dimana proses pencocokan setiap karakter pada kata

kunci dengan setiap karakter pada pola kalimat.

4. Baris 25 – 29 adalah bagian dimana jika kata kunci ditemukan atau tidak

ditemukan pada pola kalimat, sistem akan memberikan sebuah keluaran, atau

pemberitahuan kepada pengguna.

2.2 Algoritma Knuth-Morris-Pratt

Algoritma Knuth-Morris-Pratt (KMP) adalah sebuah algoritma pencarian

string yang melakukan pergeseran berdasarkan sebuah tabel yang sudah dihitung

sebelumnya. Dengan tabel ini, maka penentuan pergeseran kata kunciakan menjadi

lebih efektif. Tabel nilai pergeseran ini akan menjadi faktor penentu seberapa cepat

algoritma ini mampu menemukan kata kunci di dalam sebuah pola kalimat.

Berikut adalah sebuah contoh penghitungan untuk sebuah kata kunci dengan

panjang 10 karakter.

Posisi (k) 1 2 3 4 5 6 7 8 9 10

Kata kunci(P) A B C C B A B C B B

KAMUS

1. i, j, pjg_katakunci, pjg_kalimat : integer

2. kecocokan : boolean

3. ar_kalimat : array[0..pjg_kalimat-1] of char

4. ar_katakunci : array [0.. pjg_katakunci-1] of char

5. i 0

6. j 0

7. kecocokan false

ALGORITMA

8. input (kalimat)

9. input (katakunci)

10. pjg_kalimat count(kalimat)

11. pjg_katakunci count(katakunci)

12. ar_kalimat ..

13. ar_katakunci ..

14. while (i<=pjg_kalimat-1) and (j<=pjg_katakunci-1) 15. if ar_kalimat[i] = ar_katakunci[j] then

16. i i+1

17. j j+1

18. kecocokan true 19. else

20. i i+1

21. j 0

22. kecocokan false 23. end if 24. end while 25. if kecocokan = truethen 26. output (true) 27. else 28. output (false) 29. end if

Pergeseran (s) 0 0 0 0 0 1 2 3 0 0

1. Nilai s pada posisi k pertama sebesar 0 (nol) karena karakter “a” tidak dapat

dibandingkan dengan karakter manapun.

2. Berikutnya karakter “a” akan dicocokkan dengan karakter pada posisi kedua,

yaitu “b”. Dan sekali lagi terjadi ketidakcocokan, oleh sebab itu nilai

pergeserannya 0.

3. Berikutnya, karakter “a” pada posisi pertama, dan “c” pada posisi ke tiga.

Tidak cocok, maka diberikan nilai 0.

4. Berikutnya, karakter “a” pada posisi pertama dan “c” pada posisi keempat.

Tidak cocok, maka nilai pergeserannya adalah 0.

5. Karakter “a” pada posisi pertama dibandingkan dengan karakter “b” pada

posisi ke lima, tidak cocok. Maka nilai pergeserannya adalah 0 untuk karakter

ini.

6. Di posisi keenam, ada karakter “a”, yang adalah sebuah kecocokan. Oleh

karena itu nilai pergeserannya adalah 1 untuk karakter ini.

7. Untuk langkah berikutnya, tidak langsung dibandingkan karakter pada posisi

kedua dengan karakter di posisi ketujuh, tapi kita akan mulai mengecek

apakah ada pola yang sama, di posisi pertama dengan posisi ke enam. Karakter

pada posisi kedua, adalah “b”, dan di posisi ketujuhjuga adalah karakter “b”.

Kita akan menambahkan nilai sebelumnya dengan 1, untuk karakter di posisi

ketujuh, sehingga nilainya 2.

8. Karakter di posisi ketiga dan karakter pada posisi kedelapan cocok, yaitu “c”.

Maka kita bisa menambahkan nilai sebelumnya dengan 1. Sehingga nilainya 3.

9. Berikutnya, pengecekan karakter di posisi keempat yaitu “c” dan karakter pada

posisi kesembilan yaitu “b”. Tidak cocok. Sebelum mengisi nilai pergeseran

karakter pada posisi kesembilan dengan 0, harus dibandingkan sekali lagi

dengan karakter pada posisi pertama, yaitu “a”. Ternyata didapati tidak cocok.

Oleh sebab itu nilai pergeseran nya adalah 0.

10. Dan terakhir, kita akan melakukan pengecekan untuk karakter pada posisi

pertama dan karakter pada posisi kesepuluh. Dan ternyata tidak cocok. Maka

nilai pergeserannya adalah 0.

Untuk membantu memahami langkah langkah pemberian nilai setiap karakter

dalam kata kunci, berikut sebuah diagram :

Gambar 3 Diagram alur pembuatan tabel pergeseran

pada algoritma Knuth-Morris-Pratt

Berikut adalah sebuah contoh kasus bagaimana metode ini mencocokan

sebuah kata kunci. Kata kunci dan pola kalimat disamakan dengan contoh pada

metode Naive agar bisa terlihat perbedaan dan efisiensinya.

Pola kalimat : SAYA MAU MAKAN BAKSO SAPI

Kata kunci : BAKSO

Berikut perhitungan untuk tabel pergeserannya : Posisi (k) 1 2 3 4 5

Kata kunci(P) B A K S O

Pergeseran (s) 0 0 0 0 0

1. Nilai s pada posisi pertama adalah 0, dan karena karakter “b” pada posisi

pertama dan karakter “a” pada posisi kedua tidak cocok, maka nilai

pergeseran untuk karakter “a” pada posisi kedua juga bernilai 0.

2. Berikutnya karakter “b” pada posisi pertama akan dicocokkan dengan

karakter pada posisi ketiga, yaitu “k”. Dan sekali lagi terjadi ketidakcocokan,

oleh sebab itu nilai pergeserannya 0.


karakter pada posisi keempat, yaitu “s”. Tidak cocok, oleh sebab itu nilai

pergeserannya 0.


karakter pada posisi kelima, yaitu “o”. Dan sekali lagi terjadi

ketidakcocokan, oleh sebab itu nilai pergeserannya 0.

Berikut ini adalah langkah langkah pergeseran yang dilakukan oleh algoritma

Knuth-Morris-Pratt berdasarkan tabel pergeseran yang ada.


B A K S O

Di indeks pertama kata kunci, ditemukan ketidakcocokan dengan pola kalimat

(mismatch). Untuk melakukan pergeseran, dilakukan sebuah rumus untuk menentukan

pergeseran :

Besar pergeseran = i - n

i = posisi karakter yang terakhir cocok

n = nilai pergeseran karakter yang terakhir cocok)

Ketidakcocokan terjadi di posisi indeks pertama, maka pergeseran yang dilakukan

adalah sebesar 1 – 0. Yaitu 1 karakter. Pada karakter pertama yang di cocok kan, yaitu

“B” pada katakunci, terjadi mismatch. Posisi karakter “B” adalah 1, dan nilai

pergeserannya adalah 0, jadi besarnya pergeseran yang bisa dilakukan adalah 1

karakter. Dan posisi kata kunci berubah menjadi seperti ini :


B A K S O

Terjadi ketidakcocokan, dan dilakukan pergeseran sebanyak 1 – 0.


B A K S O



B A K S O


Setelah dilakukan beberapa kali pengulangan dan pergeseran, didapati bahwa

kecocokan terjadi di semua karakter. Maka dinyatakan algoritma ini berhasil

menemukan kata kunci yang diminta oleh pengguna.


B A K S O

Berikut adalah pseudocode untuk mempermudah pengkodean algoritma ini ke dalam

sebuah bahasa pemrograman. Kode Program 2 Pseudocode tabel pergeseran algoritma Knuth-Morris-Pratt

1. Baris 1 – 4 adalah definisi variabel yang akan dipakai dalam metode ini. Di

dalam metode ini, kata kunci akan diubah menjadi arraydua dimensi, yang

berisi karakter dan nilai pergeserannya.

2. Baris 7 – 8 adalah baris dimana pemberian nilai awal pada indeks pertama

kata kunci.

3. Baris 9 – 16 adalah perhitungan nilai pergeseran berdasarkan rumus yang

sudah dijelaskan.

Kode Program 3Pseudocode pergeseran algoritma Knuth-Morris-Pratt

KMP_Pergeseran

KAMUS

1. input m, n : integer,

2. input P : array[0..n-1] of char,

3. input T : array[0..m-1] of char,

4. output ketemu : array[0..m-1] of boolean

5. i, j,next: integer

6. kmpNext : array[0..n] of interger

ALGORITMA

7. preKMP(n, P, kmpNext)

8. i 0

9. while (i<= m-n) do

10. j 0 11. while (j < n and T[i+j] = P[j]) do

12. jj+1 13. endwhile 14. if(j >= n) then

15. ketemu[i] true; 16. endif

17. Next j - kmpNext[j]

18. I i+next 19. endwhile

KMP_TabelPergeseran

KAMUS

1. i,j: integer 2. input katakunci : array[0..n-1] of char, 3. input nilai_pergeseran : integer, 4. input/output TabelKMP : array[0..n] of

integer

ALGORITMA

5. i 0;

6. j TabelKMP [0] -1; 7. while (i < n) 8. while (j > -1 andnot(P[i] = P[j]))

9. j TabelKMP[j];

10. i i+1;

11. j j+1;

12. if (P[i] = P[j])

13. TabelKMP[i] TabelKMP[j];

14. else

15. TabelKMP[i] j;

16. end if

17. end while 18. end while

2.3 Algoritma Boyer-Moore-Hoorspool

Algoritma Boyer-Moore-Hoorspooladalah sebuah bentuk pengembangan dari

algoritma Boyer-Moore. Pada dasarnya, algoritma Boyer-Moore-Hoorspool

menggunakan dasar dasar dan hukum yang sama dengan algoritma pendahulunya,

yaitu Boyer-Moore. Ada tiga aturan dasar yang menjadi intisari dari algorima Boyer-

Moore dan pengembangan nya. Ketiga hukum atau aturan ini adalah :

2.3.1 Aturan “Right to Left Scanning”

Right to Left Scanning Rule adalah sebuah aturan dasar yang mengatur agar

pencarian atau pencocokan dalam algoritma ini selalu dimulai dari karakter paling

akhir dari kata kunci. Berikut ilustrasi nya.

Posisi 1 2 3 4 5 6 7 8 9 10 11 12 13

P X Y X Y Y Z X Y Z X Z Y X

K X Y Z

“P” adalah sebuah rangkaian pola kalimat, sedangkan “K” adalah kata kunci

yang sedang kita cari di dalam pola kalimat. Dengan aturan ini, pencarian kata kunci

akan dilakukan dari karakter paling kanan dari kata kunci, dan bergerak ke kiri,

berbeda dengan algoritma Naive, dan Knuth-Morris-Pratt yang melakukan

pengecekan dari kiri ke kanan. Dalam ilustrasi ini, berarti algoritma Boyer-Moore-

Hoorspool melakukan pengecekan pertama kali pada karakter Z, kemudian jika di

dapati cocok, maka dilanjutkan dengan karakter Y, dan jika di dapati cocok,

kemudian baru dilanjutkan pada karakter terakhir.

2.3.2 Aturan Bad Character

Bad Character Rule adalah sebuah keunggulan untuk melakukan pergeseran

lebih dari satu karakter setiap kali terjadi ketidakcocokan. Prinsip utama dari aturan

ini adalah menentukan besarnya pergeseran dengan cara melewati karakter karakter

dalam kata kunci yang tidak berpotensi cocok.Keadaan yang harus dicapai oleh aturan

ini adalah : kata kunci digeser sampai karakter yang tidak cocok menjadi cocok, atau

kata kunci tersebut digeser sepenuhnya, dan memulai iterasi pengecekan lagi. Berikut

ilustrasi nya dengan kasus yang sama.

Posisi 1 2 3 4 5 6 7 8 9 10 11 12 13


K X Y Z

Pengecekan pertama akan dilakukan dari karakter paling kanan dari kata

kunci. Karakter “Z” pada kata kunci akan di bandingkan dengan karakter “X” pada

pola kalimat. Dan ditemukan tidak cocok. Dengan aturan ini, algoritma akan

melakukan pengecekan apakah karakter X pada pola kalimat posisi 3 ada di dalam

kata kunci. Karena ditemukan ada karakter X pada pada kata kunci, maka berdasarkan

aturan ini, dilakukan pergeseran sebanyak 2 kali untuk mencapai kondisi cocok.

Posisi 1 2 3 4 5 6 7 8 9 10 11 12 13


K X Y Z

Sama dengan langkah sebelumnya, tetapi dilakukan pergeseran hanya sebesar 1

karakter.

Posisi 1 2 3 4 5 6 7 8 9 10 11 12 13


K X Y Z

Dengan posisi karakter seperti ini, maka ditemukan ketidak cocokan antar karakter Y

dan X. Maka dilakukan pergeseran sebanyak panjang kata kunci, karena sudah

mencapai ujung pencarian. sehingga posisi nya menjadi seperti ini.

Posisi 1 2 3 4 5 6 7 8 9 10 11 12 13


K X Y Z

Dilakukan pengecekan, dan didapati semua karakter cocok. Kata kunci ditemukan ada

di dalam pola kalimat.

2.3.3 Aturan Good Suffix

Aturan Good Suffix adalah satu aturan yang dipakai di dalam Algoritma Boyer-

Moore yang membuat algoritma ini menjadi semakin akurat. Tujuan dari aturan ini

adalah sama dengan aturan Bad Character, yaitu kata kunci digeser sampai karakter

yang tidak cocok menjadi cocok, atau kata kunci tersebut digeser sepenuhnya, dan

memulai iterasi pengecekan lagi. Saat terjadi mismatch, algoritma ini melihat karakter

yang sudah cocok sebagai acuan untuk melakukan perhitungan dan pergeseran

berikutnya. Untuk mempermudah, berikut ilustrasi nya.

Posi

si

1 2 3 4 5 6 7 8 9 1

0

1

1

1

2

1

3

1

4

1

5

1

6

1

7

1

8

1

9

2

0

2

1

2

2

2

3

P C G T G C C T A C T T A C T T A C T T A C T T

K C T T A C T T A C

Saat pencarian dimulai dari karakter paling kanan, kita mendapati bahwa

posisi 7,8 dan 9 adalah match, tetapi di posisi 6 di dapati mismatch. Dengan kondisi

seperti ini, maka awalan “TAC” pada posisi 7,8, dan 9 memenuhi aturan Good

Suffixdan kita akan sebut sebagai “t”. Oleh sebab itu kita akan melakukan pergeseran

kata kunci hingga menjadi matchdan pola awalan yang sudah ada (t) tidak menjadi

mismatch. Dari kata kunci, terdapat pola “TAC” pada posisi 3, 4, dan 5. Oleh sebab

itu, pergeseran akan dilakukan sampai TAC pada posisi 3,4,5 dari kata kunci sejajar

dengan TAC posisi 7,8, dan 9 pada pola kalimat.

Posi

si

1 2 3 4 5 6 7 8 9 1

0

1

1

1

2

1

3

1

4

1

5

1

6

1

7

1

8

1

9

2

0

2

1

2

2

2

3


K C T T A C T T A C

Setelah dilakukan pergeseran, maka dilakukan pengecekan lagi, dan di dapati

bahwa pada posisi 7, 8, 9, 10, 11, 12, dan 13 adalah cocok. Tetapi posisi 6 tidak

cocok. Dalam kondisi ini, ada kemungkinan pola “TTAC” posisi 10, 11, 12, 13 pada

kata pola kalimat match dengan “TTAC” posisi 6, 7, 8, 9 pada kata kunci, sehingga

dilakukan pergeseran sebanyak 4 karakter, agar memenuhi kondisi yang diharapkan. Posi

si

1 2 3 4 5 6 7 8 9 1

0

1

1

1

2

1

3

1

4

1

5

1

6

1

7

1

8

1

9

2

0

2

1

2

2

2

3


K C T T A C T T A C

Setelah dilakukan pergeseran, kata kunci telah ditemukan di dalam pola kalimat.

Algoritma Boyer-Moore-Hoorspool menggunakan aturan aturan yang ada di

dalam algoritma Boyer-Moore, tetapi dalam fase pre-komputasi, algortima ini

membangun sebuah tabel yang akan mempermudah dan menyederhanakan aturan Bad

Character dan Good Suffix. Berikut jalannya algoritma Boyer-Moore-

Hoorspooldengan mengambil sebuah contoh kasus.

Pola Kalimat : SAYA MAU MAKAN BAKSO SAPI

Kata kunci : BAKSO

Dengan algoritma Boyer-Moore-Hoorspool, sebelum kita lakukan pencocokan

karakter dan pergeseran, maka kita harus melakukan pencatatan karakter yang ada di

dalam kata kunci ke dalam sebuah tabel yang disebut dengan tabel pergeseran.

Berikut sebuah diagram yang menjelaskan proses memasukkan setiap karakter

kedalam tabel.

Apakah karakter itu

sudah ada di dalam tabel?

Masukkan kedalam

tabel, index kw + 1Skip, index kw + 1

Index kw <= kw.length-1?

Ya Tidak

Ya Tidak

MULAI

SELESAI, dan

Mulai penghitungan

Gambar 4 Proses memasukkan karakter unique kata kunci ke dalam tabel

Selanjutnya, setelah semua karakter masuk kedalam tabel, dan tidak ada yang

sama, atau sudah unique, maka nilai pergeseran pada tabel ini didapatkan dengan

rumus :

Nilai tertinggi( 1, Panjang kata kunci - 1 – indeks karakter tersebut)

Maka penghitungannya akan dilakukan seperti ini :

Indeks 0 1 2 3 4 5

Karakter B A K S O *

Pergeseran 4 3 2 1 1 5

Untuk karakter "B", indeksnya adalah 0. Penghitungannya adalah :

=>Nilai Tertinggi ( 1, panjang kata kunci - 1 - indeks )

=>Nilai Tertinggi ( 1, 5 - 1 - 0)

=>Nilai Tertinggi ( 1, 4 )

Nilai tertinggi antara 1 dan 4 adalah 4, maka nilai tersebut akan di pakai sebagai nilai

pergeseran karakter "B".

Untuk karakter "A", indeksnya adalah 1, maka penghitungannya:



=>Nilai Tertnggi ( 1, 3 )

Nilai tertinggi antara 1 dan 3 adalah 3.

Untuk karakter "K", indeksnya adalah 2, maka penghitungannya adalah :




Nilai tertinggi antara 1 dan 2 adalah 2, maka nilai pergeserannya adalah 2.

Untuk karakter "S", indeksnya adalah 3, maka penghitungannya adalah :





Untuk karakter "O", indeksnya adalah 4, maka penghitungannya adalah :





Dan ada satu lagi karakter bintang, atau asterisk ( * ) yang ada di tabel

tersebut. Karakter bintang ini mewakili semua karakter yang tidak ada pada kata

kunci. Dengan kata lain, karakter bintang mewakili semua huruf selain huruf B, A, K,

S, dan O. dan nilainya adalah panjang kata kunci. Misalnya ditemukan karakter lain

selain kata kunci, maka dipastikan karakter tersebut itu tidak akan dicocokkan dengan

karakter di dalam tabel, dan akan langsung di geser sebanyak panjang kata

kunci.Berikut diagramnya:

YaTidak

Lakukan Rumus

Tambahkan ke

dalam Tabel

Lakukan Rumus

Perbarui nilai

yang sudah ada

Indeks = panjang katakunci?

YaTidak

Lakukan Rumus

Beri nilai 1

MULAI

SELESAI

Karakter

sudah unique?

Tambahkan karakter bintang

Dengan nilai pergeseran =

panjang kata kunci

Gambar 5 Diagram proses pembuatan tabel

pergeseran pada algoritma Boyer-Moore-Hoorspool

Setelah semua karakter masuk ke dalam tabel, pencocokan dimulai dari indeks

atau karakter terakhir pada kata kunci. Algoritma Boyer-Moore-Horspool pertama

tama akan melakukan pencarian seperti ini :


B A K S O

Pencocokan pada karakter paling kanan (indeks terakhir) dari kata kunci tidak

cocok dengan pola kalimat. Maka selajutnya akan di cek apakah karakter "spasi" ada di dalam tabel yang sebelumnya dibuat. Dan didapati ternyata tidak ada, maka akan

dilakukan pergeseran secara penuh, sehingga keadaan nya menjadi seperti ini :


B A K S O

Setelah pergeseran, pengecekan karakter dilakukan lagi. Didapati bahwa karakter

pada indeks terakhir dari kata kunci tidak cocok dengan pola kalimat, dan karakter

“M” tidak ada di dalam tabel. Maka dilakukan pergeseran karakter secara penuh.


B A K S O

Setelah pergeseran, pengecekan karakter dilakukan lagi. Didapati bahwa karakter "O"

tidak cocok dengan pola kalimat (spasi), dan karakter spasi tidak ada di dalam tabel.

Maka dilakukan pergeseran karakter secara penuh.


B A K S O

Dengan keadaan seperti ini, maka algoritma ini sudah menemukan letak kata

kunci dalam pola kalimat. Dengan gambaran jalannya algoritma seperti yang sudah

dibahas pada bagian ini, maka sebuah pseudocodebisa di buat untuk mempermudah

penterjemahan logika ke dalam bahasa pemrograman.

Kode Program 4Pseudocode pembuatan tabel pergeseran algoritma Boyer-Moore-Hoorspool

Baris kode ini menjelaskan proses bagaimana tabel yang berisi perhitungan

pergeseran (rightmost table) dibuat.

1. Baris 1 - 3 adalah deklarasi variabel yang digunakan dalam program ini.

2. Pada baris ke 4 - 5, program ini akan memeriksa apakah karakter yang

sedang di tunjuk oleh pointer i adalah karakter yang sudah ada di dalam

tabel, atau belum.

3. Pada baris 7 – 8, jika karakter yag ditunjuk oleh pointer belum ada di dalam

tabel, maka karakter tersebut akan ditambahkan ke dalam tabel atau array

yang sudah di sediakan, dan dilakukan penghitungan rumus pergeseran.

4. Pada baris 10 – 14, jika karakter yang ditunjuk oleh pointer sudah terdapat

dalam tabel, maka karakter tersebut tidak ditambahkan ke dalam tabel,

namun nilai pergeseran nya akan dihitung dari indeks terakhir, dan nilai

yang lama akan di ganti dengan nilai hasil penghitungan yang baru.

BMH_TabelPergeseran

KAMUS

1. katakunci : array [0,..pjg_katakunci-1] of char

2. tabel : array [0,..pjg_katakunci-1] of char

3. i, nilai_pergeseran, pjg_katakunci : integer

ALGORITMA

4. While i <= pjg_katakunci

5. If katakunci[i] = exist in tabel[]

6. Then

7. i = i + 1

8. nilai_pergeseran = pjg_katakunci – 1 – index_katakunci

9. Else

10. If i < pjg_katakunci

11. Then

12. Insert katakunci[i,nilai] to tabel[posisi, nilai]

13. i = i + 1

14. nilai_pergeseran = pjg_katakunci – 1 –

index_katakunci

15. else if i = pjg_katakunci

16. nilai_pergeseran = pjg_katakunci

17. end if

18. end if

19. exit while

5. Pada baris 15 – 16, di jelaskan bahwa jika setelah pointer mencapai akhir

dari array katakunci, maka nilai pergeseran untuk semua karakter selain

karakter yang ada di dalam array katakunci (karakter asterisk atau bintang)

akan diberi nilai sebanyak panjang kata kunci.

Kode Program 5Pseudocode proses pergeseran pada algoritma Boyer-Moore-Hoorspool

Baris program ini menjelaskan alur jalannya perhitungan algoritma ini.

1. Baris 1 – 7 adalah deklarasi variabel yang digunakan dalam program ini

2. Pada baris 8, dijelaskan bahwa perhitungan dimulai dari karakter terakhir

katakunci, dan berjalan karakter per karakter sampai pointer ada di awal kata

kunci.

3. Pada baris 9 – 10, dijelaskan jika karakter terakhir dari katakunci sama dengan

karakter dari pola kalimat yang sedang di tunjuk oleh pointer i, maka

pencarian akan dilanjutkan dengan karakter berikutnya.

4. Pada baris 11 – 14, tapi jika karakter nya tidak sama, maka tabel perhitungan

akan di cek, dan nilai pergeseran akan diambil dari hasil perhitungan pada

tabel.

Dengan demikian pencarian akan menjadi lebih efektif, karena tidak perlu

mencocokan karakter satu demi satu. Tabel ini akan sangat membantu pergeseran.

3. Metode Perancangan Sistem

Dalam pembuatan aplikasi untuk melakukan pembandingan dan penghitungan

besarnya nilai pergeseran dari pencarian string ini, penulis tidak menggunakan

metode atau pendekatan tertentu, hanya menggunakan permodelan saja. Penulis

melakukan pengamatan kebutuhan sendiri, mengkodekan, dan melakukan pengujian

serta analisa sendiri.

Tahap perancangan ini adalah sebuah tahap dimana sebuah sistem akan

digambarkan, dan di jelaskan secara rinci sehingga setiap pemakai atau pengembang

bisa memahami seperti apa jalannya sistem dengan lebih mudah. Alat bantu yang

Algoritma_BMH() KAMUS

1. katakunci : Array[0,..pjg_katakunci-1] of char 2. pola : Array [0,..pjg_pola-1] of char 3. tabel : Array [] of char 4. i, pjg_katakunci : integer 5. Boolean ketemu

ALGORITMA

6. For i = pjg_katakunci ; i-- 7. If katakunci[i] = pola[i] then 8. ketemu true 9. Else 10. ketemu false 11. i pjg_katakunci 12. j j + tabel[i, nilai] 13. end for

digunakan dalam tahap ini adalah Unified Modeling Language, atau UML. UML

adalah bahasa standar yang di gunakan untuk menggambarkan dan memvisualisasi

sebuah proses bisnis, dan memudahkan dokumentasi.

Gambar 6 adalah gambar dari Use Case yang menggambarkan apa yang di

kerjakan oleh pengguna aplikasi ini. Pengguna tidak perlu login untuk menggunakan

aplikasi ini, tinggal mengetikkan kata kunci yang akan dicocokkan dengan data di

dalam basisdata, memilih metode atau algoritma yang akan di gunakan, dan tinggal

menekan tombol untuk memulai pencarian.

Gambar 6 Use Case Aplikasi

Gambar 7 adalah Activity Diagram dari aplikasi ini. Seperti mesin pencari

pada umumnya, tentu hal yang harus dimasukkan pertama kali adalah sebuah kata

kunci.Setelah aplikasi di buka, maka yang pertama harus di lakukan oleh pengguna

adalah memasukkan kata kunci di dalam textbox yang tersedia. Setelah itu pengguna

bisa memilih algoritma pencarian string. Setelah itu, saat di eksekusi, maka yang

dilakukan sistem adalah melakukan penghitungan, dan pencarian sehingga bisa di

lihat hasil penghitungan, dan pencarian yang dilakukan oleh algoritma pencarian

string.

Aplikasi pembandingan algoritma pencarian string

Pengguna SistemP

rose

s B

isn

is A

pli

kas

i

ya

START

Memasukan keyword

Ambil data di

basisdata

Jalankan algoritma

dan perhitungan pegeseran

Tampilkan hasil perhitungan

STOP

tidak

ya

tidak

ya tidak

Apakah katakunci sudah

dimasukkan?

Basisdata terisi?

Ulangi pencarian?

Gambar 7 Activity Diagram Aplikasi

Gambar 8 adalah gambar dari sequence diagram aplikasi ini. Kata kunci yang

di masukkan oleh pengguna ke dalam text box akan di teruskan melalui antarmuka,

dan akan di proses oleh basisdata. Setelah data dalam basisdata berhasil ditarik, maka

perhitungan akan segera dilakukan, dan hasil perhitungan nya akan diteruskan melalui

antarmuka, danpengguna bisa melihat hasil perhitungan dan pergeseran.

Pengguna Antarmuka

memasukkan kata kunci

BasisdataAlgoritma

mengirim kata kunci

menarik data dari basisdata

pengambilan data

mengirim datatable

perhitungan pergeseran

mengirim hasil perhitungan

menampilkan hasil

Gambar 8 Sequence Diagram Aplikasi

4. Hasil dan Pembahasan

Semua data yang di masukkan ke dalam basisdata sebagai pola kalimat

diambil dari 1000 judul skripsi yang terdapat pada koleksi digital perpustakaan

UKSW dan dari berbagai sumber. Dari data data ini, telah dilakukan 400 kali

pengujian dengan 100 kata kunci yang berbeda. Untuk satu kata kunci, dikerjakan

oleh 3 algoritma yang berbeda, dan setiap algoritma menghitung jumlah pergeseran

yang dilakukan oleh algoritma, dan menampilkannya dalam sebuah textbox.

Indikator yang dipakai dalam penelitian ini adalah besarnya angka pergeseran

yang dilakukan oleh setiap algoritma. Dengan menghitung angka pergeseran, kita

akan bisa melihat seberapa besar efisiensi yang dilakukan oleh sebuah algoritma

pencarian string.

Berikut ini adalah antarmuka yang digunakan di dalam aplikasi ini. Pengguna

hanya perlu memasukkankata kunci, dan memilih algoritma apa yang akan digunakan,

kemudian setelah itu pengguna hanya menekan tombol “execute”, maka algoritma

akan mulai mengerjakan penghitungan dan menampilkan hasil nya.

Gambar 9 Antarmuka Aplikasi

Angka efisiensi algoritma Knuth-Morris-Pratt dan Boyer-Moore-Hoorspool

yang di dapatkan dari tabel berikut ini adalah angka yang didapatkan dari

pembandingan besar pergeseran algoritma Knuth-Morris-PrattatauBoyer-Moore-

Hoorspool dibandingkan dengan Naive Method, dan dikalikan 100 persen untuk

mendapatkan angka persentase.

Dari formula ini, selisih pergeseran antara algoritma KMP atau BMH akan

menjadi faktor penentu besarnya efisiensi yang bisa dilakukan algoritma tersebut.

Sebagai ilustrasi, jika dengan metode Naive sebuah pencarian membutuhkan 100 kali

pergeseran, dan dengan metode KMP hanya membutuhkan 50 kali pergeseran, berarti

ada 50 pergeseran yang tidak perlu dilakukan oleh metode KMP dalam pencarian

tersebut. Itu berarti dalam pencarian tersebut, metode KMP dapat melakukan efisiensi

sebanyak (50 / 100) x 100% = 50%. Dengan angka yang didapat di sini, maka kita

bisa melihat bahwa Metode KMP lebih efisien dalam melakukan pencarian kata kunci

tersebut.

Dari 400 kali percobaan yang dilakukan dengan 1000 data di dalam basisdata,

bisa ditarik kesimpulan Algoritma Boyer-Moore-Hoorspool adalah algoritma yang

paling efektif untuk pencarian kata kuncidalam pola kalimat yang lebih dari 1 data.

Dengan pembuatan tabel pergeseran yang lebih baik dari algoritma Knuth-Morris-

Pratt, dan dengan metode pencarian dari indeks terakhir, dari karakter paling kanan

dari kata kunci (Right to LeftRule), maka algoritma ini bisa menemukan kesalahan

lebih cepat dari algoritma lainnya, dan bisa melakukan pergeseran lebih cepat dari

algoritma yang lain. Meski tidak secepat algoritma Boyer-Moore-Hoorspool,

algoritma Knuth-Morris-Pratt masih lebih cepat dari metode Naive, atau Naive

Method, karena sudah memiliki tabel pergeseran.

Tabel 1 Hasil perhitungan efisiensi bagian 1

Total Pergeseran dgn metode Naive 3108.9

Selisih Pergeseran (dibanding dgn Naive)

736.5 2300.1

Efisiensi umum (selisih / jml pergeseran) % 0 23.6 73.9

Selisih Pergeseran KMP / BMH – Pergeseran Naive

Pergeseran Naive x 100%

Dari tabel ini bisa dilihat bahwa efisiensi bisa dilakukan dengan algoritma

yang lebih modern dari pada dengan metode Naive atau tradisional. Efisiensi secara

umum pada algoritma Knuth-Morris-Pratt adalah 23,6%. Sedangkan untuk algoritma

Boyer-Moore-Hoorspool, angkanya lebih baik lagi, yaitu 73,9%. Tabel 2 Hasil perhitungan efisiensi bagian 2


Selisih Pergeseran (dibanding dgn Naive) 408.2 1176.6

Efisiensi umum (selisih / jml pergeseran) % 0 25.10% 72.50%

Dari tabel bagian kedua ini bisa dilihat efisiensi secara umum pada algoritma

Knuth-Morris-Pratt adalah 25,1%. Sedangkan untuk algoritma Boyer-Moore-

Hoorspool, angkanya 72,5%. Tabel 3 Hasil perhitungan efisiensi bagian 3

Total Pergeseran dgn metode Naive 2189

Selisih Pergeseran (dibanding dgn Naive) 159 1540.8

Efisiensi umum (selisih / jml pergeseran) % 0% 7.20% 70.30%

Dari tabel bagian ketigaini bisa dilihat bahwa efisiensi secara umum pada

algoritma Knuth-Morris-Pratt adalah 7,2%. Sedangkan untuk algoritma Boyer-

Moore-Hoorspool, angkanya 70,3%. Tabel 4 Hasil perhitungan efisiensi bagian 4


Selisih Pergeseran (dibanding dgn Naive) 56.1 862.4

Efisiensi umum (selisih / jml pergeseran) % 0% 4.70% 72.40%

Dari tabel bagian keempatini bisa dilihat efisiensi secara umum pada algoritma

Knuth-morris-pratt adalah 4,7%. Sedangkan untuk algoritma Boyer-Moore-

Hoorspool, angkanya 72,4%.

Berikut contoh beberapa kata kunci yang efisiensi nya cukup besar, sehingga

bisa dilihat bahwa algoritma Boyer-Moore-Hoorspoollebih efektif dibandingkan

dengan Knuth-morris-pratt. Efisiensi dihitung dengan rumus yang sama, berdasarkan

indikator yang sama yaitu besarnya nilai pergeseran dibanding dengan metode Naive.

Tabel 5 Kata kunci dengan angka efisiensi yang baik

No. Kata Kunci Rata Rata Pergeseran Efisiensi

Naive KMP BMH KMP BMH

1 pemrograman 29 27 5 6.8 82.7

2 sistem 18.3 17.8 7 2.7 61.7

3 algoritma 36.6 34.3 8.8 6.2 75.9

4 aplikasi 15 14.8 4.6 1.3 69.3

5 perusahaan 65.5 64.3 14.6 1.8 77.7

6 file 61.7 61.5 38.7 0.3 37.2

7 gambar 37.6 37 13.6 0.8 63.8

8 sistem keuangan 55 55 7 0 87.2

9 pemberian kredit 24 23 3 4.1 87.5

10 edugame 26 26 8 0 69.2

11 google map 12 12 4 0 66.6

12 visualisasi 6.5 6.5 0 0 100

13 kecerdasan buatan 10 10 2 0 80

Berikut adalah grafik yang bisa di buat berdasarkan hasil perhitungan yang

sudah dilakukan dengan 250 data, 500 data, 750 data dan 1000 data. Hasil yang

tertera pada grafik ini adalah dalam satuan persen, berbanding dengan metode Naive,

atau Naive Method.

Gambar 10 Grafik efisiensi pencarian pada data sebanyak 250, 500, 750 dan 1000

a. Untuk 250 data, terlihat bahwa efisiensi algoritma Knuth-morris-pratt sebesar

23,6%, dan algoritma Boyer-Moore-Hoorspool sebesar 73,9%.

b. Untuk data sebanyak 500, perhitungan efisiensi bagian pertama dan kedua

dijumlahkan, dan dibagi dua untuk mendapatkan angka rata-ratanya. Jadi

untuk algoritma Knuth-morris-pratt, angka efisiensi algoritma yang dicapai

adalah ( 23,3 + 25,1 ) : 2. Yaitu sebesar 24,2%. Sedangkan untuk algoritma

Boyer-Moore-Hoorspool, angka efisiensinya sebesar ( 73,9 + 72,5 ) : 2. Yaitu

sebesar 73,5%

c. Untuk 750 data, perhitungan efisiensi bagian pertama, kedua dan ketiga

dijumlahkan, dan bagi tiga untuk mendapatkan angka rata-ratanya. Jadi untuk

algoritma Knuth-morris-pratt, angka efisiensi yan bisa dicapai adalah ( 23,3 +

25,1 + 7,2 ) : 3. Yaitu sebesar 18,5%. Sedangkan untuk algoritma Boyer-

Moore-Hoorspool, angka efisiensinya sebesar ( 73,9 + 75,5 + 70,3 ) : 3. Yaitu

sebesar 73,2%

d. Untuk 1000 data, perhitungan efisiensi bagian pertama, kedua, ketiga dan ke

empat dijumlahkan, dan dibagi empat untuk mendapatkan angka rata-ratanya.

Jadi untuk algoritma Knuth-morris-pratt, angka efisiensinya adalah (23,3 +

25,1 + 7,2 + 4.7 ) : 4. Yaitu sebesar 15%. Sedangkan untuk algoritma Boyer-

Moore-Hoorspool, angka efisiensinya sebesar (73,9 + 75,5 + 70,3 + 72,4 ) : 4.

Yaitu sebesar 73%

5. Kesimpulan

Berdasarkan tabel hasil percobaan dan tabel efisiensi yang ada, ada

beberapa kesimpulan yang dapat ditarik, yaitu aturan Aturan Bad Character

dan Good Suffix dalam algoritma Boyer-Moore dan pengembangan nya sangat

berpengaruh pada akurasi pencarian yang dilakukan. Dengan kedua tabel ini,

akurasi pencarian akan meningkat, dan pencarianmenjadi jauh lebih teliti,

23.6 24.218.5

15

73.9 73.5 73.2 73

0

10

20

30

40

50

60

70

80

data 250 data 500 data 750 data 1000

KMP

BMH

serta meminimalkan jumlah pergeseran. Panjang sebuah kata kunci dan pola

karakter ganda pada kata kunci tersebut akan sangat mempengaruhi efisiensi

yang dilakukan oleh algoritma Knuth-Morris-Pratt dan algoritma Boyer-

Moore-Hoorspool, karena kedua algoritma ini akan membangun sebuah tabel

perhitungan nilai pergeseran terlebih dahulu. Algoritma Boyer-Moore-

Hoorspool juga didapati lebih efektif dibandingkan dengan metode Naïve, dan

algoritma Knuth-morris-pratt pada saat digunakan pada data yang lebih dari

satu pola kalimat, dalam hal ini sebuah basisdata dengan 1000 record. Dan

yang terakhir, dengan melihat angka efisiensi yang dicapai, maka algoritma

Boyer-Moore-Hoorspool bisa diaplikasikan ke dalam sebuah aplikasi yang

lebih besar lagi cakupannya, seperti basisdata mahasiswa, atau basisdata

perpustakaan.

Berikut beberapa saran yang dapat penulis berikan untuk pengembangan

tulisan ini :

1. Selain menggunakan besarnya pergeseran algoritma sebagai parameter

efisiensi, bisa dilakukan pengkodean dan penghitungan waktu sebagai

salah satu parameter efisiensi.

2. Penulis berikutnya dapat melanjutkan penelitian ini dengan

membandingkan hasil penelitian ini dengan hasil penelitian pada algoritma

pencarian string lainnya.

6. Daftar Pustaka

[1]. Pratama, Satya Fajar. 2008. Pencocokan DNA Kata kunci dengan

algoritma Boyer-Moore. Bandung : Institut Teknologi Bandung

[2]. Aulia, Rama. 2008. Analisis Algoritma Knuth-morris-pratt dan Algoritma

Boyer-Moore-Hoorspool dalam proses pencarian String. Bandung :

Institut Teknologi Bandung

[3]. Hidayattulah, Priyanto. 2014. Visual Basic.Net. Bandung : Informatika

[4]. Kurniawan, Erick. 2011. Cepat Mahir Visual Basic 2010. Yogyakarta :

Andi Offset

[5]. Desy, D., 2005, Mesin pencari, www.total.or.id, diakses Maret 2015

[6]. Usman, A., 2009, Pengertian Prototipe, http://arifust.web.id, diakses

Maret 2015

http://www.total.or.id/

http://arifust.web.id/

studi perbandingan implementasi algoritma naive method

Documents