IMPLEMENTASI ALGORITMA PENCOCOKAN STRING BOYER-MOORE DALAM PEMBUATAN CONTACT MANAGER PADA PLATFORM ANDROID SKRIPSI
MEGO SUNTORO 101401004
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: IMPLEMENTASI ALGORITMA PENCOCOKAN STRING BOYER – MOORE DALAM PEMBUATAN CONTACT MANAGER PADA PLATFORM ANDROID. : SKRIPSI : MEGO SUNTORO : 101401004 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 16 April 2015
Komisi Pembimbing : Pembimbing 2
Pembimbing 1
Romi Fadillah Rahmat, Bcomp.Sc, MSc
Dian Rachmawati, S.Si, M.Kom
NIP.198603032010121004
NIP. 198307232009122004
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
iii
PERNYATAAN
IMPLEMENTASI ALGORITMA PECOCOKAN STRING BOYER-MOORE DALAM PEMBUATAN CONTACT MANAGER PADA PLATFORM ANDROID
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, 16 April 2015
Mego Suntoro 101401004
iv
PENGHARGAAN
Alhamdulillah. Puji dan syukur kehadirat Allah SWT, yang dengan rahmat dan karunia-Nya penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, pada Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.
Pada pengerjaan skripsi dengan judul Implementasi Algoritma Pencocokan String Boyer-Moore Dalam Pembuatan Contact Manager Pada Platform Android, penulis menyadari bahwa banyak pihak yang turut membantu, baik dari pihak keluarga, sahabat dan orang-orang terkasih yang memotivasi dalam pengerjaannya. Dalam kesempatan ini, penulis mengucapkan terima kasih kepada:
1. Bapak Prof. Dr. dr. Syahril Pasaribu, DTM&H, Msc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara. 2. Bapak Prof. Muhammad Zarlis selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 3. Bapak Dr. Poltak Sihombing, M.Kom selaku Dosen Pembanding I dan selaku Ketua Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 4. Ibu Dian Rachmawati, S.Si, M.Kom. selaku Dosen Pembimbing I yang telah memberikan arahan, kritik dan saran serta motivasi kepada penulis dalam pengerjaan skripsi ini. 5. Bapak Romi Fadillah Rahmat,Bcomp.Sc,MSc selaku Dosen Pembimbing II yang telah memberikan arahan, kritik dan saran serta motivasi kepada penulis dalam pengerjaan skripsi ini. 6. Bapak M.Andri Budiman, ST, Mcomp.Sc, MEM selaku Dosen Pembanding II yang telah banyak memberikan arahan dan masukan yang sangat berharga kepada penulis.
v
7. Ayahanda Sumingkir, Ibunda Leginem, Abang dan Kakak Tercinta Sumariono, Suhelmi Daniati, dan Sri rahayu, yang mana telah banyak memberikan kasih sayang, semangat, serta dorongan kepada penulis. 8. Seluruh tenaga pengajar dan pegawai di Fakultas Ilmu Komputer dan Teknologi Informasi USU. 9. RHF yang selama ini telah menjadi keluarga kedua penulis selama mengikuti perkuliahan, tempat berbagi suka dan duka dalam pengerjaan skripsi ini, kepada Ali Huseini, Andri Agasi, Arief Try Hidayat, Dani Rizki, Suhaili Hamdi, Safriatullah, M.Khairil, M.Pristian, Sobirin, Gunalan, Fadli Herdika, Ivan Grace Halim, Yohanes Silitonga. 10. Teman-teman kuliah, khususnya Muhammad Reza Nasution, Dwi Rizki Ananda, Ahmad Rasydi, Umri Herdiansyah, Rudiansyah, Wahyu Eko Putra dan Novri Pramana, Hayatun Nufus, serta Stambuk 2010 yang tidak dapat disebut satu-persatu, yang
telah banyak membantu dalam selesainya
pengerjaan skripsi ini. 11. Rekan-rekan pengurus IMILKOM (Ikatan Mahasiswa S1 Ilmu Komputer) Fasilkom-TI 2013-2014 yang telah memberikan banyak dukungan, tempat belajar berorganisasi yang benar, dan menimba pengalaman. 12. Semua pihak yang terlibat langsung maupun tidak langsung yang tidak dapat penulis ucapkan satu demi satu yang telah membantu penyelesaian laporan ini.
Semoga Allah SWT melimpahkan berkah kepada semua pihak yang telah memberikan bantuan, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini.
Medan, 16 April 2015 Penulis,
Mego Suntoro
vi
ABSTRAK
Kebutuhan masyarakat terhadap layanan teknologi berbasis IT sangat bervariasi, penyimpanan serta pencarian identitas dengan cepat dan mendetail adalah salah satu kebutuhan tersebut, namun disamping itu masih jarang ditemukan aplikasi mobile yang dapat memenuhi kebutuhan tersebut, maka dibuatlah sebuah aplikasi contact manager yang menerapkan algoritma Boyer-Moore sebagai masalah pencariannya dan database SQLite sebagai penyimpanan data contact. Algoritma Boyer-Moore menerapkan prinsip good suffix dimana karakter yang dicari sejajar dengan karakter yang menyerupainya serta prinsip bad character dimana jika karakter tidak memiliki kemiripan maka langsung dieliminasi. Field yang dipakai dalam pencarian ini adalah nama contact, dengan memasukan nama sebagai inputannya dalam pencarian, kemudian kita dapat mengetahui data yang mendetail dari nama tersebut. Hasil dari aplikasi ini menampilkan keseluruhan pattern yang match dengan teks, dengan kecepatan pencarian 0,9 detik.
KataKunci : Rekayasa Perangkat Lunak, Algoritma Boyer-Moore, Contact Manager
vii
THE IMPLEMENTATION OF BOYER-MOORE STRING MATCHING TO MAKE 'CONTACT MANAGER' IN ANDROID PLATFORM ABSTRACT
The needs for IT-based technology is varied, Storing and fast detailed-identity search is one of the needs. But mobile application is hard to find, to solve this problem this contact manager application is built, using Boyer - Moore algorithm as the searching problem and SQLite as the contact data storage. Boyer - Moore uses good suffix principle which the searched-character has similarity with the stored - character and bad suffix principle will eliminated the character which has no similarity with any stored character. The field used in this process is contact name, the users use name as input in searching process, then detailed-data from the stored-name will be found. The result from this application is the whole pattern which is match with the text, with searching speed is 0.9 s. Keywords: Software engineering, Boyer-Moore algorithm, Contact Manager.
viii
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Daftar Lampiran Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan Bab 2 Landasan Teori 2.1 Android 2.2 Sejarah Android 2.3 Versi-versi Android 2.3.1 Android versi 1.1 2.3.2 Android versi 1.5 Cupcake 2.3.3 Android versi 1.6 Donut 2.3.4 Android versi 2.0/2.0.1/2.1 Eclair 2.3.5 Android versi 2.2 Froyo 2.3.6 Android versi 2.3 Gingerbread 2.3.7 Android versi 3.0 Honeycomb 2.3.8 Android versi 4.0 Ice Cream Sandwich 2.3.9 Android versi 4.1 Jelly Bean 2.3.10 Android versi 4.4 Kitkat 2.4 Eclipse 2.5 Struktur Data dan Algoritma 2.6 Algoritma Boyer-Moore 2.6.1 Kelebihan Algoritma Boyer-Moore 2.6.2 Kelemahan Algoritma Boyer-Moore 2.6.3 Pencarian Dengan Algoritma Boyer-Moore 2.7 Relevansi
ii iii iv vi vii viii x xi xii
1 2 2 3 3 4 5
6 6 7 7 7 8 8 8 8 9 9 9 9 10 10 11 11 12 13 18
ix
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Persyaratan 3.1.2.1 Kebutuhan Fungsional 3.1.2.2 Kebutuhan Non Fungsional 3.1.3 Pemodelan 3.1.3.1 Use Case Diagram 3.1.3.2 Activity Diagram 3.1.3.3 Sequence Diagram 3.1.3.4 Kamus Data 3.1.3.5 Flowchart Sistem 3.2 Perancangan Sistem 3.2.1 Menu Utama 3.2.2 Menu New Contact 3.2.3 Menu Edit Contact 3.2.4 Menu View Contact 3.2.5 Menu Navigation 3.2.6 Menu Help 3.2.7 Menu About
19 19 20 20 21 21 21 23 24 25 26 28 28 29 30 31 32 34 35
Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi 4.1.1 Implementasi Algoritma Boyer-Moore 4.2 Antarmuka Sistem 4.2.1 Menu Utama 4.2.2 Menu New 4.2.3 Menu View 4.2.4 Menu Edit 4.2.5 Menu Navigation 4.2.6 Menu Help dan About 4.3 Pengujian 4.3.1 Pengujian Dengan Algoritma Boyer-Moore 4.3.2 Pengujian Proses Tambah Data 4.3.3 Pengujian Proses Edit Data
37 37 42 42 43 44 45 46 56 47 48 50 51
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
52 52
Daftar Pustaka Listing Program
54 56
x
DAFTAR TABEL
Nomor Tabel 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9
Nama Tabel Versi-versi Android Contoh Algoritma Boyer-Moore Contoh Pergeseran Algoritma Boyer-Moore Occurence Heuristic Hasil pencarian Occurence Heuristic Hasil akhir pencarian Occurence Heuristic Match Heuristic Hasil akhir pencarian Match Heuristic Nilai Occurence Heuristic dan Match Heuristic Use Case Pencarian data contact dengan Algoritma Boyer-Moore Use Case Proses Pencarian Use Case Proses Hasil Kamus Data Keterangan gambar rancangan interface Menu Utama Keterangan gambar rancangan interface New Contact Keterangan gambar rancangan interface Menu Edit Contact Keterangan gambar rancangan interface Menu View Contat Keterangan gambar rancangan interface Menu Navigation Keterangan gambar rancangan interface Menu Help Keterangan gambar rancangan interface Menu About Contoh Algoritma Boyer-Moore Contoh Algoritma Boyer-Moore Contoh Algoritma Boyer-Moore Contoh Algoritma Boyer-Moore Contoh Algoritma Boyer-Moore Contoh Algoritma Boyer-Moore Contoh Algoritma Boyer-Moore Contoh Algoritma Boyer-Moore Hasil Pencarian Data Contact dengan Algoritma Boyer-Moore
Halaman 7 12 12 14 14 15 15 16 17 23 24 24 26 28 30 31 32 33 34 36 39 39 40 40 40 40 41 41 48
xi
DAFTAR GAMBAR
Nomor Gambar 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10
Nama Gambar Diagram Ishikawa Use Case Diagram Sistem Activity Diagram Sequence Diagram Flowchart Algoritma Boyer-Moore Rancangan Interface Menu Utama Rancangan Interface New Contact Rancangan Interface Menu Edit Contact Rancangan Interface Menu View Contact Rancangan Interface Menu Navigation Rancangan Interface Menu Help Rancangan Interface Menu About Contoh pencarian Menu Awal Menu New Menu View Menu Edit Menu Navigation Menu Help Menu About Menambah data Mengedit data
Halaman 20 22 24 25 27 28 29 30 31 33 Stable Marriage 34 35 38 42 Stable Marriage 43 44 Stable Marriage 45 46 47 47 50 51
u
u
3
xii
DAFTAR LAMPIRAN
Halaman Listing Program
56
Curriculum Vitae
82
