PERBANDINGAN ALGORITMA BOYER-MOORE DAN ALGORITMA RABINKARP PADA PENCARIAN TEKS DALAM UNDANGUNDANG PERLINDUNGAN ANAK
SKRIPSI
PRADITA OKTAVIANI 121401041
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PERBANDINGAN ALGORITMA BOYERMOORE DAN ALGORITMA RABIN-KARP PADA PENCARIAN TEKS DALAM UNDANG-UNDANG PERLINDUNGAN ANAK : SKRIPSI : PRADITA OKTAVIANI : 121401041 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATRA UTARA Diluluskan di Medan, April 2016
Komisi Pembimbing : Pembimbing 2
Pembimbing 1
Amalia, S.T., M.T.
Dr. Poltak Sihombing, M.Kom
NIP. 19781221 201401 2 001
NIP. 196203171991031001
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
Universitas Sumatera Utara
iii
PERNYATAAN
PERBANDINGAN ALGORITMA BOYER- MOORE DAN ALGORITMA RABIN-KARP PADA PENCARIAN TEKS DALAM UNDANG-UNDANG PERLINDUNGAN ANAK SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, Juni 2016
Pradita Oktaviani 121401041
Universitas Sumatera Utara
iv
PENGHARGAAN
Syukur Alhamdulillah selalu terucap kehadirat Allah SWT yang dengan rahmat dan hidayahNya penulis dapat menyelesaikan menyusun 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 Perbandingan Algoritma Boyer-Moore dan Algoritma Rabin-Karp pada Pencarian Teks dalam Undang-Undang Perlindungan Anak, penulis menyadari bahwa banyak pihak yang turut membantu, baik dari pihak keluarga, sahabat dan orang-orang tercinta yang mendukung dalam pengerjaan skripsi ini. Dalam kesempatan ini, penulis mengucapkan terima kasih kepada: 1. Bapak Prof. Runtung Sitepu, SH, M.Hum selaku Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. Opim Salim Sitompul, MSc selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 3. Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara sekaligus Dosen Pembimbing I yang telah memberikan arahan, kritik dan saran serta motivasi kepada penulis dalam pengerjaan skripsi ini. 4. Ibu Amalia, S.T., M.T. selaku Dosen Pembanding II yang telah banyak memberikan arahan, motivasi dan masukan yang sangat berharga kepada penulis. 5. Bapak M. Andri Budiman, S.T.,M.Comp.Sc.,M.E.M. selaku Dosen Pembanding I yang telah banyak membarikan kritik dan saran yang membangun kepada penulis 6. Bapak Amer Sharif, S.Si.,M.Kom. selaku Dosen Pembanding II yang telah banyak membarikan kritik dan saran yang membangun kepada penulis 7. Seluruh tenaga pengajar dan pegawai di Fakultas Ilmu Komputer dan Teknologi Informasi USU, terkhusus Ibu maya Silvia, Ibu dian Rachmawati, Ibu siti Dara Fadillla, Ibu Amalia, Bapak Agus Salim Harahap, Bapak Mohammad Andri Budiman,
Universitas Sumatera Utara
v
Bapak Ade Candra, Bapak Syurahbil Hadi yang selama ini sudah menjadi orang tua kedua bagi penulis. 8. Keluarga tercinta yang selalu mendoakan serta memberikan kasih sayang, semangat, serta dorongan kepada penulis dan memberi segalanya tanpa pamrih, ayahanda Prayitno, Ibunda Rosini, Kakak tercinta Prayanti Dewi Anggraini, Pratika Dwi Septiani dan Pratiwi Tria May Latifani. 9. Teman-teman yang selalu menghibur, memberi semangat dan membantu saat penulisan skripsi, Aulia Tarindah Putri, Citra Eka Mutia, Indri Hidayati, Khalida Zia, Muzdalifa, Rizky Adawiyah, dan Tika Linavia. 10. Teman-teman kuliah, Stambuk 2012 terkhusus KOM A teman-teman seperjuangan saat menimba ilmu di S1 Ilmu Komputer. 11. 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, Juni 2016 Penulis,
Pradita Oktaviani
Universitas Sumatera Utara
vi
ABSTRAK
Anak adalah seseorang yang belum berusia 18 (delapan belas) tahun, termasuk anak yang dalam kandungan. Kekerasan terhadap anak sering kali terjadi di Indonesia. Jumlah kasus kekerasan pada anak di Indonesia terus meningkat. Selain tindak kekerasan terhadap anak, anak juga sering menjadi korban eksploitasi pihak yang tidak bertanggung jawab. Kebanyakan dari anak Indonesia belum memahami betul apa saja hak-hak dan perlindungan yang sepantasnya mereka dapatkan dari negara. Pentingnya memahami hak-hak dan perlindungan bagi anak merupakan pembekalan yang baik bagi anak untuk melindungi diri dari pelanggaran hak anak. Untuk memberikan solusi tentang masalah undang-undang perlindungan anak, maka penulis mencoba merancang sebuah aplikasi pencarian undangundang perlindungan anak berbasis android dengan menggunakan algoritma Boyer-Moore dan Rabin-Karp. Hasil dari pengujian dan perbandingan dari kedua algoritma : kompleksitas kedua algoritma sama, yaitu : θ(mn). Sedangkan real-running-time algoritma Boyer-Moore memiliki rata-rata penemuan string : 0,091818181818s dan algortima Rabin-Karp memiliki rata-rata penemuan string : 0,618181818282s.
KataKunci : Anak,eksploitasi, algoritma, Boyer-Moore, Rabin-Karp
Universitas Sumatera Utara
vii
An Comparison Boyer-Moore Algorithm and Rabin-Karp Algorithm On Searching Text in Children Protection Laws
ABSTRACT
Child is someone whom under 18 (eighteen) years old, including child whom still in womb. Child abuse often happens in Indonesia. The amount of child abuse in Indonesia is getting higher. Not only child abuse, but also children in Indonesia become a victim of exploitation by the irresponsible part. Mostly children in Indonesia not quite understand what are their rights and the protections that they should has from the country. The importance children to understand what is their rights and their protections are really good suply for children to protect them from violation of their rights. To give an solution about the problems of children protection laws, author try to devise an aplication for children protection laws based on android with applying Boyer-Moore algorithm dan Rabin-Karp algrithm. The result of testing and comparison from both algorithms are: the complexity of both algorithms are the same : θ(mn), Meanwhile the real-running-time Boyer-Moore algorithm has average time to found string is : 0,091818181818s and Rabin-Karp algorithm has average time to found string is : 0,618181818282s. Keywords : Child, expliotation, algorithm, Boyer-Moore, Rabin-Karp
Universitas Sumatera Utara
viii
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Daftar Lampiran
ii iii iv vi vii viii x xii xiii
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 Anak 2.2 Android 2.3 Sejarah Android 2.4 Fitur Android 2.5 Versi Android 2.6 Query 2.7 Search Engine 2.8 Algoritma 2.8.1 AlgoritmaString Mathcing 2.8.2 Klasifikasi Pencocokan String 2.8.3 Algoritma Boyer-Moore 2.8.3.1 Ilustrasi Pencarian String Algoritma Boyer-Moore 2.8.4 Algoritma Rabin-Karp 2.8.5 Hashing 2.8.5.1 Ilustrasi Pencarian String Algoritma Rabin-Karp 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 Preprocessing
1 2 2 3 3 3 4 6 6 6 7 7 9 9 9 10 10 11 11 20 20 20 23 23 24 24 25 25 26
Universitas Sumatera Utara
ix
3.1.3.1.1 Case Folding 3.1.3.2 Use Case Diagram 3.1.3.3 Activity Diagram 3.1.3.4 Sequence Diagram 3.1.3.5 Flowchart Sistem 3.2 Perancangan Sistem 3.2.1 Menu Intro 3.2.2 Menu Pemilihan 3.2.3 Menu Tentang 3.2.4 Menu Utama
26 28 29 30 31 35 35 36 36 37
Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi 4.1.1 Implementasi Algoritma Boyer-Moore dan Rabin-Karp 4.2 Antarmuka Sistem 4.2.1 Menu Intro 4.2.2 Menu Pemilihan 4.2.3 Menu Tentang 4.2.4 Menu Utama 4.3 Hasil Pengujian 4.3.1 Komplesitas Algoritma Big θ 4.3.2 Real-Running-Time
38 38 38 39 39 40 40 44 45 53
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
61 62
Daftar Pustaka Listing Program Curriculum Vitae
63 A-1 B-1
Universitas Sumatera Utara
x
DAFTAR TABEL
Nomor Tabel 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20 2.21 2.22 2.23 2.24 2.25 2.26 2.27 2.28 2.29 2.30 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 4.1
Nama Tabel
Halaman
Suffix Proses Pencarian Suffix (a) Proses Pencarian Suffix (b) Proses Pencarian Suffix (c) Proses Pencarian BmGs Proses Pencarian BmGs (a) Proses Pencarian BmGs (b) Proses Pencarian BmGs (c) Proses Pencarian BmGs (d) Proses Pencarian BmGs (e) Proses Pencarian BmGs (f) Proses Pencarian BmGs (g) Proses Pencarian BmGs (h) Proses Pencarian BmGs (i) Proses Pencarian BmGs (j) Proses Pencarian BmGs (k) Proses Pencarian BmGs (l) Proses Pencarian BmGs (m) BmBc Proses Pencarian BmBc (a) Proses Pencarian BmBc (b) Proses Pencocokan String Proses Pencocokan String (a) Proses Pencocokan String (b) Proses Pencocokan String (c) Mencari Nilai Hash Memeriksa Pencocokan String (a) Memeriksa Pencocokan String (b) Memeriksa Pencocokan String (c) Memeriksa Pencocokan String (d) Kebutuhan Fungsional Kebutuhan Non-Fungsional Use Case Masukkan String Use Case Memilih Algoritma Keterangan Gambar Rancangan Interface Menu Intro Keterangan Gambar Rancangan Interface Menu Pemilihan Keterangan Gambar Rancangan Interface Menu Tentang Keterangan Gambar Rancangan Interface Menu Utama Komplesitas Boyer-Moore PreBmBc
12 12 12 13 13 13 14 14 14 14 15 15 16 16 16 17 17 17 17 18 18 18 19 19 19 20 21 21 21 22 25 25 29 29 35 36 37 37 45
Universitas Sumatera Utara
xi
4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9
Kompleksitas Boyer-Moore Suffixes Kompleksitas Boyer-Moore BmGs Kompleksitas Boyer-Moore Check Kompleksitas Rabin-Karp Kompleksitas Rabin-Karp (a) Running-Time Boyer-Moore Running-Time Rabin-Karp Running-Time Boyer-Moore dan Rabin-Karp
46 47 48 50 51 53 56 58
Universitas Sumatera Utara
xii
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
Halaman
Diagram Ishikawa Preprocessing-Case Folding Use Case Diagram Activity Diagram Sequence Diagram Flowchart Sistem Flowchart Boyer-Moore Flowchart Rabin-Karp Rancangan Interface menu Intro Rancangan Interface menu Pemilihan Rancangan Interface menu Tentang Rancangan Interface menu Utama Menu Intro Menu Pemilihan Menu Tentang Hasil Pencarian Algoritma Boyer-Moore (a) Hasil Pencarian Algoritma Boyer-Moore (b) Hasil Pencarian Algoritma Rabin-Karp (a) Hasil Pencarian Algoritma Rabin-Karp (b) Grafik Running-Time Boyer-Moore Grafik Running-Time Rabin-Karp Grafik Running-Time Boyer-Moore dan Rabin-Karp
24 27 28 30 31 32 33 34 35 36 36 37 39 40 40 41 42 43 44 54 57 60
Universitas Sumatera Utara
xiii
DAFTAR LAMPIRAN
Halaman Listing Program Curriculum Vitae
A-1 B-1
Universitas Sumatera Utara
