PERBANDINGAN ALGORITMA STRING MATCHING NOT SO NAIVE DAN SKIP SEARCH PADA PLATFORM ANDROID SKRIPSI RICKY WIJAYA

PERBANDINGAN ALGORITMA STRING MATCHING NOT SO NAIVE DAN SKIP SEARCH PADA PLATFORM ANDROID

SKRIPSI RICKY WIJAYA 121401081

PROGRAM STUDI S-1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas akhir dan memenuhi syarat memperoleh gelar Sarjana Komputer

RICKY WIJAYA 121401081

PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016


ii

PERSETUJUAN

Judul

Kategori

: PERBANDINGAN ALGORITMA STRING MATCHING NOT SO NAIVE DAN SKIP SEARCH PADA PLATFORM ANDROID : SKRIPSI

Nama

: RICKY WIJAYA

Nomor Induk Mahasiswa

: 121401081

Program Studi

: SARJANA (S1) ILMU KOMPUTER

Departemen

: ILMU KOMPUTER

Fakultas

: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA

Diluluskan di Medan, 25 Oktober 2016

Komisi Pembimbing :

Pembimbing 2

Pembimbing 1

Dr. Maya Silvi Lydia, M.Sc NIP. 19740127 200212 2 001

Prof. Dr. Muhammad Zarlis, M.Sc NIP. 19570701 198601 1 003

Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,

Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001


iii

PERNYATAAN


SKRIPSI

Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.

Medan, 25 Oktober 2016

Ricky Wijaya 121401081


iv

PENGHARGAAN

Puji dan syukur penulis ucapkan kepada Tuhan Yang Maha Esa, karena rahmat dan izinNya 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. Banyak bantuan berupa kebaikan, buah pikiran dan kerjasama yang telah penulis peroleh selama menjalani studi sampai dengan penyelesaian skripsi ini. Oleh karena itu, sudah sepantutnya penulis menyampaikan ucapan terimakasih kepada pihak-pihak yang telah membantu.

Ucapan terima kasih penulis sampaikan kepada: 1.

Bapak Prof. Dr. Runtung Sitepu, SH, M.Hum selaku Rektor Universitas Sumatera Utara.

2.

Bapak Prof. Opim Salim Sitompul, M. Sc 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 Universitas Sumatera Utara.

4.

Ayahanda Oei Jian Min, Ibu tercinta Merry, dan kepada adik Cindy Wijaya yang selalu memberikan perhatian dan dukungan serta kasih sayang kepada penulis.

5.

Bapak Prof. Dr. Muhammad Zarlis selaku Dosen Pembimbing I yang telah memberikan bimbingan, saran, dan masukan kepada penulis dalam pengerjaan skripsi ini.

6.

Ibu Dr. Maya Silvi Lydia, M.Sc selaku Wakil Dekan I Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara sekaligus Dosen Pembimbing II yang telah memberikan bimbingan, saran, dan masukan kepada penulis dalam pengerjaan skripsi ini.

7.

Ibu Dian Rachmawati, S.Si, M.Kom selaku Dosen Pembanding I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.

8.

Bapak Jos Timanta Tarigan, S.Kom., M.Sc Dosen Pembanding II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.


v 9.

Bapak Ade Candra, S.T, M.Kom selaku Dosen Pembimbing Akademik yang telah memberikan bimbingan, saran dan perhatian selama penulis menjalani studi di S1 Ilmu Komputer Universitas Sumatera Utara.

10. Seluruh tenaga pengajar dan pegawai di Fakultas Ilmu Komputer dan Teknologi Informasi USU. 11. Teman - teman kuliah, kepada Johan, Boris, S.Kom, Vici, S.Kom, Ade Mutiara, S.Kom dan seluruh anak Kom B yang tidak bisa disebutkan satu-persatu, yang telah berbagi suka dan duka, semangat dan dorongan selama kuliah di S1 Ilmu Komputer hingga penulis dapat menyelesaikan skripsi ini 12. Stambuk 2012 yang telah memberikan semangat, teman diskusi dan teman seperjuangan dalam menggapai gelar Sarjana Komputer, terutama Jeklin, S.Kom, Maya, S.Kom, dan Nurhasbiah, S.Kom yang membagi ilmu dan membantu pengerjaan skripsi ini. 13. Teman – teman CBT Family (Khusuma, S.T, Melinda S.Psi, Conan, S.T, Ferani, Stephanie dan Stanley) dan Stephanie Regina yang selalu memberikan semangat, dorongan, kesabaran dan hiburan sehingga penulis dapat menyelesaikan skripsi ini. 14. Senior 2011 terutama kepada Bang Satya, S.Kom dan Bang Andrus, S.Kom, Junior 013, teman – teman KTI dan teman – teman PAILITONG USU yang selalu menemani penulis mengerjakan revisi skripsi, memberikan saran dan bimbingan, serta hiburan agar penulis dapat menyelesaikan skripsi dengan lancar. 15. Semua pihak yang terlibat langsung atau tidak langsung yang penulis tidak dapat tuliskan satu per satu.

Semoga Tuhan Yang Maha Esa memberikan berkah kepada semua pihak yang telah memberikan bantuan, semangat, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini. Semoga skripsi ini dapat bermanfaat bagi pribadi, keluarga, masyarakat, organisasi dan negara.

Medan, 25 Oktober 2016 Penulis,

Ricky Wijaya


vi

ABSTRAK

Ilmu psikologi mempunyai fungsi untuk menjelaskan apa, bagaimana, dan mengapa suatu tingkah laku bisa terjadi. Berdasarkan fungsi ilmu psikologi tersebut muncul istilah-istilah psikologi, media yang digunakan untuk memperkenalkan istilah psikologi adalah melalui kamus. Namun, diperlukan sebuah media baru yang praktis dan efektif seperti media Smartphone yang mendukung berbagai macam aplikasi seperti aplikasi kamus. Penelitian ini membahas tentang bagaimana melakukan pencarian kata pada Kamus Istilah Psikologi dengan menggunakan Algoritma String Matching. String matching merupakan bagian penting dari sebuah proses pencarian string (string searching) dalam sebuah dokumen. Algoritma string matching yang digunakan dalam penelitian ini adalah Algoritma Not So Naive dan Skip Search. Penelitian ini bertujuan untuk membandingkan kompleksitas waktu (O) serta running time untuk Algoritma Not So Naive dan Skip Search yang diimplementasikan di dalam Aplikasi Kamus Istilah Psikologi yang dibuat. Hasil dari penelitian ini menunjukkan bahwa Algoritma Not So Naive lebih lambat dibanding Algoritma Skip Search untuk proses pencarian kata. Hasil rata-rata Running Time Algoritma Not So Naive adalah 38 ms dan Algoritma Skip Search hanya 33 ms, dimana Algoritma Not So Naive dan Skip Search sama – sama memiliki kompleksitas O (mn).

Kata kunci : Kamus, String Matching, Algoritma Skip Search, Algoritma Not So Naive.


vii THE COMPARISON OF STRING MATCHING ALGORITHM NOT SO NAIVE AND SKIP SEARCH ON ANDROID PLATFORM

ABSTRACT

The Science of Psychology have a function to explain what, how and why a certain desired behavior can happen. Based on the function of the science of psychology appear term psychology, the medium used to introduce term psychology is through a dictionary. However, we required a new media that is pratical and efficient such as Smartphone that support various application such as dictionary application. This research discusses about how to search word on Term Psychology Dictionary with String Matching Algorithm. String matching is an important part of string searching process on a document. String Matching Algorithm used in this research is Not So Naive Algorithm and Skip Search Algorithm. This research attempts to compare Complexity Time (O) and Running time for Not So Naive Algorithm and Skip Search Algorithm which implemented in the Term Psychology Dictionary. The results of this research indicate that Not So Naive Algorithm is slower than Skip Search Algorithm in searching word. The average yield Running Time for Not So Naive Algorithm is 38 ms and Skip Search algorithm only 33 ms, where Not So Naive Algortihm and Skip Search Algortihm complexity is O(mn)

Keywords : Dictionary, String Matching, Skip Search Algorithm, Not So Naive Algorithm.


viii

DAFTAR ISI

Halaman

Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Daftar Lampiran

ii iii iv vi vii viii x xi xii

Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan penelitian 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan

1 3 3 3 3 4 4

Bab 2 Landasan Teori 2.1 Algoritma 2.1.1 Algoritma String Matching (pencocokan string) 2.1.1.1 Algoritma Not So Naive 2.1.1.1.1 Pencarian Algoritma Not So Naive 2.1.1.2 Algoritma Skip Search 2.1.1.2.1 Fase Preprocessing Algoritma Skip Search 2.1.1.2.2 Fase Pencarian Algoritma Skip Search 2.2 Kompleksitas Algoritma 2.3 Kamus 2.4 Android 2.4.1 Versi Android 2.5 Penelitian yang Relevan

6 6 8 8 10 11 12 13 14 15 15 17

Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Persyaratan 3.1.2.1 Persyaratan Fungsional 3.1.2.2 Persyaratan Non-Fungsional 3.1.3 Pemodelan

18 18 19 19 20 20


ix

3.1.3.1 Use Case Diagram 3.1.3.2 Activity Diagram 3.1.3.3 Sequance Diagram 3.2 Flowchart 3.2.1 Flowchart Gambaran Umum Sistem 3.2.2 Flowchart Algoritma Not So Naive 3.2.3 Flowchart Algoritma Skip Search 3.3 Kamus Data 3.4 Perancangan Antarmuka Sistem (Interface) 3.4.1 Rancangan Halaman Splash Screen 3.4.2 Rancangan Navigation Drawer 3.4.3 Rancangan Halaman Home 3.4.4 Rancangan Halaman About 3.4.5 Rancangan Halaman Help Bab 4 Implementasi dan Pengujian 4.1 Implementasi 4.1.1 Tampilan Halaman Splash Screen 4.1.2 Tampilan Navigation Drawer 4.1.3 Tampilan Halaman Home 4.1.4 Tampilan Halaman About 4.1.5 Tampilan Halaman Help 4.1.6 Tampilan Halaman Exit 4.2 Pengujian Sistem 4.2.1 Pengujian pencarian kata pada Kamus Istilah Psikologi dengan Algoritma Not So Naive 4.2.2 Pengujian pencarian kata pada Kamus Istilah Psikologi dengan Algoritma Skip Search 4.3 Hasil Pengujian 4.4 Kompleksitas Algoritma 4.4.1 Kompleksitas Algoritma Not So Naive 4.4.2 Kompleksitas Algoritma Skip Search

21 24 26 27 28 29 30 31 32 32 33 34 37 37

39 39 40 41 42 43 44 44 44 51 56 60 60 62

Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2. Saran

64 65

Daftar Pustaka

66


x

DAFTAR TABEL

Halaman

Tabel 2.1 Proses Pencocokan Algoritma Not So Naive di Percobaan Pertama Tabel 2.2 Proses Pencocokan Algoritma Not So Naive di Percobaan Kedua Tabel 2.3 Proses Pencocokan Algoritma Not So Naive di Percobaan Ketiga Tabel 2.4 Proses Pencocokan Algoritma Not So Naive di Percobaan Keempat Tabel 2.5 Proses Pencocokan Algoritma Not So Naive di Percobaan Kelima Tabel 2.6 Proses Pencocokan algoritma Not So Naive di Percobaan Keenam Tabel 2.7 Tabel Teks dan Pola yang akan Dijadikan Contoh Kasus Tabel 2.8 Tabel Hasil preprocessing dari Algoritma Skip Search Tabel 2.9 Versi – Versi Android Tabel 3.1 Tabel Use Case Memilih Mode untuk kata yang akan diartikan Tabel 3.2 Tabel Use Case Proses Input kata Tabel 3.3 Tabel Use Case Proses Algoritma Not So Naive Tabel 3.4 Tabel Use Case Proses Algoritma Skip Search Tabel 3.5 Kamus Data Tabel 4.1 Hasil Pencarian kata Algoritma Not So Naive Tabel 4.2 Hasil Pencarian kata Algoritma Skip Search Tabel 4.3 Hasil Pengujian Algoritma Not So Naive Tabel 4.4 Hasil Pengujian Algoritma Skip Search Tabel 4.5 Kompleksitas fungsi preproses dari Algoritma Not So Naive Tabel 4.6 Kompleksitas fungsi proses pencarian dari Algoritma Not So Naive Tabel 4.7 Kompleksitas fungsi preproses dari Algoritma Skip Search Tabel 4.8 Kompleksitas fungsi proses pencarian dari Algoritma Skip Search

9 9 9 9 10 10 11 12 15 22 23 23 24 32 45 51 57 58 60 61 62 63


xi

DAFTAR GAMBAR

Halaman

Gambar 2.1 Penentuan Panjang window dan Karakter Tengah yang akan Digunakan dalam Proses Pencocokan 1 Gambar 2.2 Penentuan Panjang window dan Karakter Tengah yang akan Digunakan dalam Proses Pencocokan 2 Gambar 2.3 Logo-logo android dari versi 1.0 – 6.0 Gambar 3.1 Diagram Ishikawa Gambar 3.2 Use Case Diagram Sistem Gambar 3.3 Activity Diagram Sistem Gambar 3.4 Sequence Diagram Sistem Gambar 3.5 Flowchart Gambaran Umum Sistem Kamus Istilah Psikologi Gambar 3.6 Flowchart Algoritma Not So Naïve Gambar 3.7 Flowchart Algoritma Skip Search Gambar 3.8 Pre-processing Algoritma Skip Search Gambar 3.9 Rancangan Tampilan Splash Screen Gambar 3.10 Rancangan Tampilan Navigation Drawer Gambar 3.11 Rancangan Tampilan Home Gambar 3.12 Rancangan Intent dari List View Mode Istilah Psikologi – Definisi Gambar 3.13 Rancangan Halaman About Gambar 3.14 Rancangan Halaman Help Gambar 4.1 Tampilan Halaman Splash Screen Gambar 4.2 Tampilan Halaman Navigation Drawer Gambar 4.3 Tampilan Halaman Home Gambar 4.3.1 Tampilan Toast Message Gambar 4.3.2 Tampilan Halaman Intent Saat Salah Satu Kata di List View di Klik Gambar 4.4 Tampilan Halaman About Gambar 4.5 Tampilan Halaman Help Gambar 4.6 Tampilan Halaman Exit Gambar 4.7 Perbandingan Hasil Running Time Algoritma Not So Naive dan Algoritma Skip Search Gambar 4.8 Perbandingan Total Running Time Algoritma Not So Naive dan Algoritma Skip Search

12 13 16 19 21 25 26 28 29 30 31 33 34 35 36 37 38 40 40 41 42 42 43 43 44 59 60


xii DAFTAR LAMPIRAN

Halaman A. Listing Program B. Daftar Riwayat Hidup

A-1 B-1


PERBANDINGAN ALGORITMA STRING MATCHING NOT SO NAIVE DAN SKIP SEARCH PADA PLATFORM ANDROID SKRIPSI RICKY WIJAYA

Recommend Documents