BAB 1 PENDAHULUAN
1.1
Latar Belakang Kemajuan teknologi telah melahirkan banyak perubahan mendasar dalam
kehidupan manusia saat ini. Salah satu produk teknologi yang sangat membantu manusia dalam kehidupan sehari-hari adalah komputer. Pada awalnya komputer hanyalah suatu alat untuk melakukan perhitungan, tetapi pada perkembangannya saat ini, komputer telah banyak dimanfaatkan di berbagai sektor seperti pendidikan sebagai alat bantu untuk proses administrasi, perbankan untuk mengolah dan menyimpan transaksi, industri untuk kontrol terhadap mesin, serta berbagai sektor lainnya. Sekarang ini komputer dipergunakan secara luas oleh semua orang mulai dari anak kecil hingga orang dewasa, dan digunakan hampir di seluruh lingkungan seperti di dalam rumah, universitas, sekolah, perkantoran, perdagangan, dan juga lingkungan sehari-hari. Komputer mempunyai berbagai macam kemampuan antara lain mengolah, menyimpan, dan mengakses data yang telah disimpan, memudahkan proses perhitungan, membuat file, serta mencari, menambahkan, dan mengirim data melalui internet. Jika kita berbicara tentang pencarian data dalam internet memakai kata kunci, maka proses pencarian data tersebut merupakan faktor penting yang harus diperhatikan. Oleh sebab itu, harus digunakan metode yang tepat agar kegiatan
2
pengolahan dan pengaksesan data dapat dilakukan dan ditemukan dengan cepat dan tepat. Salah satu kegiatan yang sering dilakukan adalah mencari data dalam pengolahan data menggunakan komputer, terutama dalam memanipulasi data seperti menghapus data, menambah data, dan mengubah data, karena pemakai harus mengetahui apakah data tersebut ada atau tersedia di dalam komputer. Salah satu contohnya adalah pencarian pola dalam suatu teks berupa abjad, angka atau tanda baca. Dalam melakukan pencarian biasanya kita harus memberikan key yang berisi pola dalam teks yang ingin dicari, dan kemudian diminta untuk menemukan bagian dalam teks yang mengandung pola yang diinginkan. Mencari key untuk menemukan record adalah kegiatan yang sering menghabiskan banyak waktu dalam sebuah program, sehingga dibutuhkan metode pencarian yang tepat agar dapat meningkatkan performansi program.Berbagai teknik pencarian telah dikembangkan dan diimplementasikan. Teknik-teknik pencarian ini dikembangkan berdasarkan algoritma-algoritma pencarian yang ada. Teknik pencarian bisa dikembangkan berdasarkan satu atau lebih algoritma yang saling mendukung untuk mendapatkan hasil optimal. Ketika akan mengimplementasikan suatu metode pencarian, pengguna dihadapkan pada pilihan untuk menentukan mana algoritma pencarian yang lebih sesuai dengan kebutuhannya. Karena masing-masing algoritma mempunyai kelebihan dan kekurangan masing-masing, ada algoritma yang mampu melakukan pencarian dalam waktu yang lebih singkat jika key berukuran kecil tetapi jika key berukuran
3
besar, algoritma tersebut malah membutuhkan waktu yang lebih lama dibandingkan dengan algoritma lain. Penulis akan membandingkan algoritma-algoritma pencarian string, dalam hal ini algoritma Maximal Shift, algoritma Optimal Mismatch dan algoritma Quick Search yang selanjutnya akan diteliti perbandingan perbedaan dalam jumlah hasil pencarian, waktu untuk proses pencarian, dan ukuran memory yang dibutuhkan masing-masing algoritma.
1.2
Ruang Lingkup Penelitian Dalam penulisan ini akan dilakukan perbandingan algoritma pencarian string
antara algoritma Maximal Shift, algoritma Optimal Mismatch dan algoritma Quick Search. Dengan variabel-variabel yang akan dibandingkan adalah jumlah hasil pencarian, waktu pencarian dan jumlah memory yang dibutuhkan. Data yang digunakan dalam penelitian ini didapatkan dari hasil percobaan dengan menjalankan program aplikasi pencarian string terhadap 20 buah file teks dengan ukuran 100 kilobytes yang akan dilakukan sebanyak 5 kali untuk mencari pola dengan panjang 2, 4, 6, 8, dan 10 karakter sehingga didapat 100 buah data yang akan dianalisa.
1.3
Rumusan Masalah Merancang program aplikasi pencarian string dengan menggunakan algoritma
Maximal Shift, algoritma Optimal Mismatch dan algoritma Quick Search yang selanjutnya akan digunakan untuk dianalisa ukuran-ukurannya seperti jumlah hasil
4
pencarian, waktu pencarian, dan jumlah memory yang dibutuhkan masing-masing algoritma. Rumusan masalah pada penelitian ini adalah: a. Apakah ada perbedaan jumlah hasil pencarian string antara algoritma Maximal Shift dan algoritma Optimal Mismatch? b. Apakah ada perbedaan jumlah hasil pencarian string antara algoritma Maximal Shift dan algoritma Quick Search? c. Apakah ada perbedaan jumlah hasil pencarian string antara algoritma Quick Search dan algoritma Optimal Mismatch? d. Apakah ada perbedaan waktu pencarian string antara algoritma Maximal Shift dan algoritma Optimal Mismatch? e. Apakah ada perbedaan waktu pencarian string antara algoritma Maximal Shift dan algoritma Quick Search? f. Apakah ada perbedaan waktu pencarian string antara algoritma Quick Search dan algoritma Optimal Mismatch? g. Apakah ada perbedaan jumlah pemakaian memory pencarian string antara algoritma Maximal Shift dan algoritma Optimal Mismatch? h. Apakah ada perbedaan jumlah pemakaian memory pencarian string antara algoritma Maximal Shift dan algoritma Quick Search? i. Apakah ada perbedaan jumlah pemakaian memory pencarian string antara algoritma Quick Search dan algoritma Optimal Mismatch?
5
1.4
Tujuan Penelitian Penulisan ini bertujuan menganalisa untuk mengetahui perbandingan kinerja
algoritma pencarian string dengan membandingkan jumlah hasil pencarian string, waktu pencarian string, dan jumlah memory yang dibutuhkan dari masing-masing algoritma yaitu algoritma Maximal Shift, algoritma Optimal Mismatch dan algoritma Quick Search.
1.5
Manfaat Penelitian Hasil dari penelitian ini diharapkan dapat memberi gambaran tentang
bagaimana pencarian pola dengan algoritma Maximal Shift, algoritma Optimal Mismatch dan algoritma Quick Search dalam sebuah teks. Selain itu, penelitian ini juga memberikan gambaran manakah algoritma yang tepat jika ingin mencari string dalam suatu teks dengan cepat. Kegunaan pembuatan program ini ditujukan untuk beberapa pihak seperti:
Bagi penulis: untuk memperkaya pengetahuan, terutama pada dalam bidang Teknik Informatika dan Statistika.
Bagi developer: agar dapat mengetahui perbandingan kinerja pencarian string algoritma Maximal Shift, algoritma Optimal Mismatch dan algoritma Quick Search.
1.6
Metodologi Penulis menggunakan dua metode, yaitu:
6
Studi kepustakaan Proses pengumpulan informasi dengan mencari dan membaca buku dari sumber data yang tersedia di perpustakaan, atau dapat juga berupa informasi yang berkaitan dengan objek penelitian.
Metode perancangan Penulis merancang suatu program aplikasi yang digunakan untuk mencari string menggunakan algoritma Maximal Shift, algoritma Optimal Mismatch dan algoritma Quick Search.
1.7
Penelitian yang Relevan Penelitian yang relevan dengan penelitian ini adalah sebagai berikut: 1. Penelitian dengan judul “STUDI ALGORITMA PENCARIAN STRING DENGAN METODE SUN WU-MANBER” ditulis oleh Ridlo Riyono (1998).
Skripsi
ini
dilakukan
untuk
mengukur
performansinya
dibandingkan dengan beberapa metode pencarian string yang ada. 2. Tugas akhir dengan judul “STUDI ALGORITMA PENCARIAN STRING DENGAN METODA KETIDAK SEPADANAN OPTIMUM” ditulis oleh Syafrudin (1996).
