jurnal_nisahidayani

Jurnal . ………….. Vol. XX …, No. X, Bulan 20XX, XX-XX 1

Perancangan dan Implementasi Metode Brute Force untuk Pencarian String pada Website PCR

Nisa Hidayani1, Juni Nurma Sari2, Rahmat Suhatman3

Program Studi Teknik Informatika dan Multimedia, Politeknik Caltex Riau

Jl. Umbansari (Patin) No. 1, Rumbai-Pekanbaru

E-mail : [email protected], [email protected], [email protected]

Abstrak

Website merupakan salah satu sarana informasi yang biasa dimanfaatkan untuk media promosi. Tidak hanya bagi para pelaku bisnis, namun juga bagi instansi-instansi pendidikan seperti perguruan tinggi, salah satunya adalah perguruan tinggi Politeknik Caltex Riau. Dengan menambahkan sebuah textfield untuk pencarian content pada website PCR, maka diterapkanlah algoritma Brute Force untuk melakukan pencarian string dalam lingkup website PCR. Algoritma Brute Force merupakan algoritma pencarian string yang menggunakan metode pemeriksaan setiap karakter pada pattern dengan setiap karakter pada teks. Sistem yang dirancang menggunakan bahasa pemrograman web PHP dan MySQL sebagai database sistemnya ini, dapat membantu para pengguna untuk melakukan pencarian dan memperoleh informasi yang tersedia pada website PCR. Namun hasil pencarian menggunakan metode ini, tidak secepat dan seakurat hasil apabila menggunakan SQL LIKE%.

Kata Kunci: website, pattern matching, Brute Force

Abstract

Website is one of information media that usually used for promoting media. Not only used by business executives, but also used by education institutes such as Politeknik Caltex Riau. By complementing a textfield for content searching in the website of PCR, Brute Force Algorithm is implemented for string content searching which is used in the website scope. Brute Force is a String Matching method which compares each character of the pattern with the text. This system will be developed by using PHP as the web programming codes and MySQL as the database system. It will help the website visitors in doing content search and getting available information of the website. Nevertheless, the searching result of this method is not as quick and accurate as the SQL LIKE%’s. Keywords : website, pattern matching, Brute Force 1. Pendahuluan

Banyak perguruan-perguruan tinggi telah menjadikan website sebagai media promosi maupun informasi bagi para mahasiswa dan calon mahasiswanya. Salah satu perguruan tinggi yang menerapkan website sebagai media informasinya adalah perguruan tinggi Politeknik Caltex Riau (PCR). Pada website PCR ini tersedia informasi mengenai PCR, mulai dari sejarah PCR hingga forum alumni. Pada tugas akhir ini diimplementasikan algoritma Brute Force untuk melakukan pencarian string. Pada web ini disediakan sebuah textfield dimana pengunjung dapat memasukkan keyword yang akan dicari pada web tersebut, dan sistem akan menelusuri semua content yang terdapat di dalam web tersebut untuk kemudian ditampilkan di halaman hasil pencarian. Algoritma Brute Force merupakan algoritma yang sederhana dan mudah untuk dimengerti serta memang dirancang sehingga menghasilkan algoritma yang layak untuk beberapa masalah penting seperti pencarian, pengurutan, pencocokan string, dan perkalian matriks (Munir, 2004). Dengan diimplementasikannya textfield pencarian yang dirancang dengan bahasa pemrograman web PHP ini, diharapkan dapat membantu pengunjung website dalam melakukan pencarian content yang diinginkan pada website www.pcr.ac.id.

2 Nisa Hidayani

Adapun tujuan dari proyek akhir ini adalah : 1. Menerapkan metode “Pattern Matching” khususnya algoritma brute force dalam pencarian content

pada website PCR. 2. Membangun sebuah fasilitas pencarian content pada website PCR

Perumusan masalah dari implementasi ini adalah : 1. Bagaimana membangun sebuah metode pencarian pada website PCR menggunakan algoritma brute

force. 2. Bagaimana menerapkan metode brute force pada yang diharapkan dapat membantu pengunjung

website dalam mencari content yang terdapat pada website PCR.

3. Tinjauan Pustaka 3.1 Website PCR

Website PCR merupakan media informasi yang dibangun dengan tujuan untuk memberikan berbagai macam informasi mengenai PCR. Mulai dari sejarah PCR, program studi yang ada di PCR, fasilitas yang tersedia, informasi mengenai penerimaan mahasiswa baru setiap tahunnya, informasi prestasi yang dicapai oleh PCR, penelitian hingga info lowongan pekerjaan dan forum untuk para alumni PCR. 3.2 Metode Brute Force Brute Force merupakan algoritma pencarian string termudah. Dengan asusi bahwa teks berada di dalam array T[1..n] dan pattern berada di dalam array P[1..m], maka algoritma Brute Force pencocokan string adalah sebagai berikut ( Munir, 2004) : 1. Mula-mula pattern P dicocokkan pada awal teks T. 2. Dengan bergerak dari kiri ke kanan, bandingkan setiap karakter di dalam pattern P dengan karakter

yang bersesuaian di dalam teks T sampai: - Semua karakter yang dibandingkan cocok atau sama (pencarian berhasil), atau - Dijumpai sebuah ketidakcocokan karakter (pencarian belum berhasil)

3. Bila pattern P belum ditemukan kecocokannya dan teks T belum habis, geser pattern P satu karakter ke kanan dan ulangi langkah 2.

Persoalan pencocokan string dapat dirumuskan sebagai berikut: 1. Teks (text), yaitu (long) string yang panjangnya n karakter 2. Pattern, yaitu string dengan panjang m karakter (m < n) yang akan dicari di dalam teks Contoh cara kerja algoritma Brute Force: Pattern : FORMASI Teks : INFO INFORM DIINFORMASIKAN

Gambar 1.1 Contoh Pencarian Brute Force

Sumber : bulansabit.blogdetik.com 3. Perancangan 3.1 Perancangan Pencarian Content Pada Web PCR Menggunakan Metode Brute Force Pada bagian ini akan dijelaskan bagaimana metode brute force tersebut bekerja di dalam program. Pada system ini pencarian pattern dilakukan tidak hanya pada page yang aktif saja, tetapi pencarian dilakukan pada semua page. Data yang akan diproses diasumsikan sebagai berikut : Pattern : UMPCR Teks : ujian masuk PCR I (UMPCR)


Gambar 2.1 Perancangan Metode Brute Force pada system

Proses :

1. Mula-mula pattern disejajarkan dengan teks pada posisi paling kiri (lihat baris 1 pada contoh diatas) perbandingan dilakukan mulai dari karakter pertama pattern, maka didapatkan karakter “U” dari pattern sejajar dengan karakter pertama teks, yaitu “U”.

2. Karena terdapat kesamaan karakter antara pattern dengan teks, maka geser karakter satu langkah ke kanan dan mulai membandingkan karakter ke-dua pada pattern dengan karakter berikutnya dan ternyata masih sama, lalu lakukan pergeseran satu karakter lagi ke kanan, namun tidak terdapat kesejajaran, sehingga harus dilakukan pencocokan kembali dari awal pattern. Geser pattern satu indeks ke kanan.

3. Cocokkan kembali setiap karakter hingga terdapat kecocokan antara pattern dan teks. 4. Lakukan langkah-langkah diatas sampai teks habis.

Gambaran Output yang dihasilkan :

3.2 Flowchart Flowchart adalah penggambaran secara grafis dari langkah-langkah dan urutan-urutan prosedur dari suatu program. Flowchart menolong analisis dan programmer untuk memecahkan masalah ke dalam segmen-segmen yang lebih kecil dan menolong dalam menganalisis alternatif-alternatif lain dalam pengoperasian (Mrirfan, 2010).

3.2.1 Flowchart User

Start

Keywords

Pencarian

Ketersedian data Tidak ada hasil

Tampilkan hasil

End

tersedia

tidak

Gambar 2.3 Flowchart User

Ujian masuk PCR I (UMPCR I) Ujian masuk PCR I (UMPCR I) akan diadakan pada tanggal Ujian masuk PCR II (UMPCR II) Ujian masuk PCR II (UMPCR II) akan diadakan pada tanggal

4 Nisa Hidayani

3.2.2 Flowchart Brute Force

Gambar 2.2 Flowchart Algoritma Brute Force

3.3 Tabel 1. Tabel Admin, berisi data-data admin yang ada dalam sistem

Tabel 5.1 Tabel Admin No NamaField Tipe Data Keterangan

1 Username String 2 Password String

2. Tabel Berita, berisi berita-berita yang berhubungan dengan PCR

5.2 Tabel Berita No Nama Field Tipe Data Keterangan 1 Id_berita Number Primary Key 2 jenis_berita String 3 Judul_berita String 4 Waktu Date 5 Gambar String 6 Isi_berita String 7 Deskripsi String


4. Hasil dan Pembahasan 4.1 Tampilan Awal Website

Gambar 3.3 Tampilan Awal website

Pada halaman ini terdapat dua text field, satu text field digunakan untuk pencarian menggunakan metode brute force, dan satu textfield untuk melakukan pencarian menggunakan SQL LIKE %.

a. Tampilan Hasil pencarian brute force

Tampilan halaman apabila melakukan pencarian menggunakan metode brute force.

Gambar 3.4 Tampilan hasil pencarian brute force

b. Tampilan Hasil Pencarian SQL LIKE%

Gambar 3.4 Tampilan hasil pencarian SQL LIKE%

4.2 Metode Pengujian

Sistem ini diuji sebelum diimplementasikan. Metode pengujian yang dilakukan adalah : 1. Membandingkan berapa lama waktu pencarian satu pattern dan output yang dihasilkan dari metode

brute force dan SQL LIKE%. 2. Membandingkan berapa lama waktu pencarian dua pattern dan output yang dihasilkan dari metode

brute force dan SQL LIKE%.

6 Nisa Hidayani

3. Membandingkan berapa lama waktu pencarian lebih dari tiga pattern dan output yang dihasilkan dari metode brute force dan SQL LIKE%.

4. Meng-inputkan beberapa pattern yang tidak sama persis dengan data yang ada di dalam database namun terdapat beberapa kata saja dari pattern inputan yang sama dengan teks yang ada di dalam database dan kemudian membandingkannya dengan hasil yang akan muncul apabila dilakukan hal yang sama menggunakan SQL %LIKE.

5. Melakukan pencarian pattern yang sama sekali tidak terdapat di dalam database dan kemudian membandingkannya dengan hasil yang akan muncul apabila menggunakan SQL %LIKE.

6. Untuk melakukan pencatatan waktu pencarian, dilakukan secara otomatis dengan menggunakan PHP code. Berikut source code PHP untuk melakukan pencatatan waktu.

Sesuai dengan metode pengujian yang telah dilakukan, berikut data hasil perbandingan yang didapat :

1. Pengujian I : pencarian satu pattern

Tabel 5.3 Pengujian I

Analisa dari pengujian I adalah :

a. Hasil Pencarian : ௬ ௦ ௬ ௦௬ ௗ௧

sama %100 = %100 ݔ

b. Waktu yang dibutuhkan: ௧ି௧ ௪௧௨ ௨௧ି௧ି௧ ௪௧௨ %௧ି௧ ௪௧௨ ௨௧ା௧ି௧ ௪௧௨ %

%100 ݔ

= ଵ.ି.ସଷଵ.ା.ସଷ

%100 ݔ = LIKE % lebih cepat 1.006% daripada Bruteforce

2. Pengujian II : pencarian dua pattern

Tabel 5.4 Pengujian II

Pattern Banyak hasil Lama Pencarian(seconds) BruteForce LIKE % BruteForce LIKE%

Lowongan kerja 18 18 4.06 0.088 Job vacancy 6 6 0.08 0.053 Mahasiswa PCR 2 5 0.0174 0.0172 Ujian masuk 2 2 0.022 0.040 Hasil seleksi 1 1 0.040 0.013 Biaya kuliah 1 1 0.046 0.016

Pattern Banyak hasil Lama pencarian (seconds)

BruteForce LIKE% BruteForce LIKE % Pengumuman 6 6 1.65 0.121

PCR 31 31 2.64 0.03 Mahasiswa 6 6 0.01 0.009

ss Seminar 5 5 1.20 0.03 UMPCR 2 2 0.4 0.04 Lomba 3 3 0.03 0.02

Jurusan 1 1 1.97 0.09 Jadwal

1 1 0.02 0.02

Gemastik 1 1 2.11 0.03 Politeknik 4 4 0.03 0.04

JUMLAH 60 60 10.06 0.43 RATA-RATA 6 6 1.006 0.043


Cisco academy 1 1 0.039 0.025 Kuliah umum 1 1 0.035 0.009 Lowongan magang 2 2 0.042 0.014 Pengumuman hasil 4 4 0.06 0.041 JUMLAH 38 41 4.441 0.316 RATA-RATA 3.8 4.1 0.4441 0.0316

Analisa dari pengujian II adalah :

a. Hasil : ௬ ௦ ௬ ௦௬ ௗ௧

%100 ݔ

= ଽଵ %100 ݔ

= 90% sama., terdapat perbedaan pada pencarian pattern “Mahasiswa PCR”

b. Waktu yang dibutuhkan : = ௧ି௧ ௪௧௨ ௨௧ି௧ି௧ ௪௧௨ %௧ି௧ ௪௧௨ ௨௧ା௧ି௧ ௪௧௨ %

%100 ݔ

= .ସସସଵି.ଷଵ.ସସସଵା.ଷଵ

%100 ݔ

= SQL LIKE% lebih cepat 0.40% daripada metode brute force. Untuk pencarian pattern “Mahasiswa PCR”, SQL LIKE% membutuhkan waktu yang lebih lama, namun hasilnya lebih banyak.

3. Pengujian III : pencarian lebih dari dua pattern Tabel 5.5 Pengujian III

Pattern Banyak hasil Lama pencarian(seconds)

BruteForce LIKE% BruteForce LIKE %

Penjaringan siswa unggul daerah 2 2 1.57 0.064 Ujian masuk PCR 2 2 0.018 0.013 PCR gelar lomba seni 1 1 0.082 0.045 Biaya kuliah di PCR 1 1 0.030 0.009 Inter high school accounting 1 1 0.037 0.027 Pengumuman hasil ujian masuk PCR

1 1 0.035 0.013

Pengumuman hasil seleksi Trakindo

1 1 0.025 0.011

Persyaratan mahasiswa berprestasi

1 1 0.075 0.034

KTM sekaligus ATM bagi mahasiswa baru

1 1 0.030 0.007

Applied engineer seminar 1 1 0.052 0.047 JUMLAH 12 12 1.954 0.27 RATA-RATA 1.2 1.2 0.1954 0.027

Analisa dari pengujian III adalah :

a. Hasil pencarian : = ௬ ௦ ௬ ௦௬ ௗ௧

%100 ݔ

= ଵଵ %100 ݔ

= 100 % sama.

8 Nisa Hidayani


%100 ݔ

= .ଵଽହସି.ଶ.ଵଽହସା.ଶ

%100 ݔ SQL LIKE% lebih cepat 0.084% daripada metode brute force.

4. Pengujian IV : pencarian beberapa pattern yang tidak sama persis dengan teks Tabel 5.6 Pengujian IV

Pattern Banyak hasil Lama Pencarian BruteForce LIKE % BruteForce LIKE %

Inter high school olimpiade

0 0 0.026 0.017

Pemberitahuan hasil UMPCR

0 0 0.057 0.044

JUMLAH 0 0 0.083 0.061 RATA-RATA 0 0 0.0415 0.0305

Analisa dari pengujian IV adalah :

a. Hasil = ௬ ௦ ௬ ௦௬ ௗ௧

%100 ݔ

= ଶଶ sama % 100 = %100 ݔ


%100 ݔ

= .ସଵହି.ଷହ.ସଵହା.ଷହ

%100 ݔ SQL LIKE% 0.37 % lebih cepat daripada metode brute force.

5. Pengujian V : pencarian pattern yang sama sekali tidak tersedia di dalam database

Tabel 5.7 Pengujian V

Pattern Banyak hasil Lama pencarian BruteForce LIKE % BruteForce LIKE %

Teknik Informatika 0 0 4.050 0.717 Elearning PCR 0 0 0.042 0.035 JUMLAH 0 0 4.092 0.752 RATA-RATA 0 0 2.046 0.376

Analisa dari pengujian V adalah :

a. Hasil = ௬ ௦ ௬ ௦௬ ௗ௧

%100 ݔ

= ଶଶ sama %100 = %100 ݔ

b. Waktu yang dibutuhkan

= ௧ି௧ ௪௧௨ ௨௧ି௧ି௧ ௪௧௨ %௧ି௧ ௪௧௨ ௨௧ା௧ି௧ ௪௧௨ %

%100 ݔ

= ଶ.ସି.ଷଶ.ସା.ଷ

%100 ݔ SQL LIKE% 2.24% lebih cepat daripada metode brute force.


4.3 Analisa dan Evaluasi Berdasarkan hasil pengujian-pengujian yang dilakukan, dapat dianalisa bahwa hasil pencarian metode brute force tidak jauh berbeda dengan LIKE%. Terdapat kasus tertentu yang menyebabkan perbedaan hasil ini. Seperti pada pengujian II, terjadi perbedaan hasil pencarian keyword “Mahasiswa PCR”, hal ini dikarenakan proses pengecekan karakter pada metode ini yang membandingkan setiap karakter pattern dengan karakter dan sub kata pada teks harus sesuai satu sama lain. Metode brute force juga memiliki kekurangan dalam waktu pencarian, semakin panjang pattern inputan atau semakin panjang teks yang ditelusuri, semakin lama waktu pencarian. Sedangkan apabila menggunakan SQL LIKE%, output yang dihasilkan lebih akurat. Data pattern tidak harus sesuai dengan susunan kata yang terdapat di dalam satu teks. Waktu yang dibutuhkan untuk pencarian pattern pun tidak terlalu lama, kecuali apabila SQL LIKE% mencari dua pattern yang susunannya tidak sama persis dengan teks atau terdapat jarak antara kedua pattern tersebut seperti pada kata “Mahasiswa PCR” pada hasil pengujian II. Untuk mengimplementasikan metode brute force pada system, dibuatlah source code sebagai berikut :

Gambar 4.23 Gambar Bruteforce PHP Source Code

5.1 Kesimpulan Setelah dilakukan beberapa pengujian, dapat disimpulkan bahwa: 1. Metode pencocokan string brute force cukup baik dalam menyelesaikan masalah pencarian. 2. Metode ini melakukan pengecekan karakter yang benar-benar sesuai dengan teks. Apabila terdapat

ketidaksamaan, maka brute force tidak menghasilkan output bahkan yang mengandung pattern inputan.

3. Pada sistem ini, setelah didapat satu solusi, brute force akan terus melakukan pengecekan karakter hingga record yang tersimpan di dalam database habis.

4. Pada sistem ini, penyimpanan pattern tidak diperlukan. Untuk melakukan pencarian dan menghasilkan solusi sesuai dengan pattern yang diinputkan, metode ini menampung setiap record yang mengandung kata inputan atau pattern dan kemudian menampilkan hasilnya.

5. Dalam hal akurasi hasil dan kecepatan, SQL LIKE% lebih unggul dibandingkan dengan metode brute force.

6. Metode brute force mengasumsikan spasi sebagai karakter. Sehingga meskipun user menginputkan beberapa pattern, brute force akan melakukan pengecekan karakter sesuai dengan inputan user.

5.2 Saran Untuk mendapatkan waktu pencarian yang lebih cepat dan hasil yang lebih akurat, modifikasi algoritma diharapkan dapat dilakukan tanpa mengubah prinsip dasar dari algoritma brute force tersebut.

10 Nisa Hidayani

5 Daftar Pustaka

Akbar, Mohammad, Ipan Fuadina, and Jaya Pramadesa. “Algoritma Pencarian String Menggunakan Metode Brute Force yang Diperkaya.” 2003. http://webmail.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik36.pdf (accessed 6 Januari, 2012).

Azhar. Pengantar Direktur. http://www.pcr.ac.id/site/main.php?page=direktur&id=0 (accessed 22 Januari, 2012).

Budiasa, Rheno Manggala. Aplikasi Sederhana Pattern Matching dengan Algoritma Brute Force pada, 2009: 1.

Kadir, Abdul. Dasar Pemrograman Web Dinamis Menggunakan PHP. Yogyakarta: ANDI, 2008. Karame, Ghassan O. “Privacy-Preserving Outsourcing of Brute-Force Key Searches.” October 2011. Kristanto, Andri. Kecerdasan Buatan. Yogyakarta: Graha Ilmu, 2004. Kusrini. Sistem Pakar Teori dan Aplikasi. Yogyakarta: ANDI, 2006. MADCOMS. Aplikasi Program PHP & MySQL untuk Membuat Website Interaktif. Yogyakarta: ANDI,

2004. MakalahStmik36. 2003. http://webmail.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik36.pdf

(accessed 6 Januari, 2012). MMSI, Parno S.Kom. Data Flow Diagram, 2011: 1. Mrirfan. “Flowchart.” 15 Februari, 2010. http://www.slideshare.net/Mrirfan/flowchart-3191144 (accessed

18 Januari, 2012). Munir, Rinaldy. “Program Studi Teknik Informatika ITB.” Diktat Kuliah Strategi Algoritmik, 2004 -

2007. W, Darren. Displaying Load Time with PHP. 2004-2010.

http://www.developertutorials.com/tutorials/php/displaying-load-time-php-050620-1077/ (accessed 24 August, 2012).

http://bulansabit.blogdetik.com (accessed 11 July, 2012).

jurnal_nisahidayani

Documents