IMPLEMENTASI ALGORITMA KNUTH-MORRIS-PRATH STRING MATCHING UNTUK MENCARI KATA ATAU ISTILAH PADA KAMUS KOMPUTER BERBASIS ANDROID.
SKRIPSI
INDAH MUSTIKA TANJUNG 121421004
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
IMPLEMENTASI ALGORITMA KNUTH-MORRIS-PRATH STRING MATCHING UNTUK MENCARI KATA ATAU ISTILAH PADA KAMUS KOMPUTER BERBASIS ANDROID.
SKRIPSI
Diajukan untuk melengkapi tugas akhir dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer
Oleh : INDAH MUSTIKA TANJUNG 121421099
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
ii
PERSETUJUAN
Judul
: IMPLEMENTASI
ALGORITMA KNUTH-MORRIS
PRATT STRING
MATCHING UNTUK MENCARI
KATA ATAU ISTILAH PADA KAMUS KOMPUTER BERBASIS ANDROID. Kategori
: SKRIPSI
Nama
: INDAH MUSTIKA TANJUNG
Nomor Induk Mahasiswa
: 121421004
Program Studi
: EKSTENSI S1 ILMU KOMPUTER
Departemen
: ILMU KOMPUTER
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan,
Januari 2015
Komisi Pembimbing : Pembimbing 2
Pembimbing 1
Ade Candra, ST, M.Kom NIP. 19790904 200912 1 002
Drs. Agus Salim Harahap, M.Si NIP. 19540828 198103 1 004
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 19620317 199103 1 011
iii
PERNYATAAN
IMPLEMENTASI ALGORITMA KNUTH-MORRIS PRATH STRING MATCHING UNTUK MENCARI KATA ATAU ISTILAH PADA KAMUS KOMPUTER BERBASIS ANDROID.
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan,
Indah Mustika Tanjung 121421004
iv
PENGHARGAAN
Alhamdulillah segala puji dan syukur atas nikmat yang luas kepada Allah Yang Maha Esa sehingga 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. Ucapan terima kasih Penulis sampaikan kepada semua pihak yang
telah
membantu Penulis dalam menyelesaikan skripsi ini baik secara langsung maupun tidak langsung, teristimewa orangtua penulis yang sangat mengasihi dan menyayangi penulis dan memberi dukungan tiada henti. Pada kesempatan ini penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada:
1.
Bapak Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara.
2.
Bapak Prof. Dr. Muhammad Zarlis 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 dan sebagai Dosen Pembanding I yang telah memberikan kritik dan saran dalam penyempurnaan skrisi ini .
4.
Ibu Maya Silvi Lydia, B.Sc, M.Sc selaku Sekretaris Program Studi S1 Ilmu Komputer Universitas Sumatera Utara.
5.
Bapak Drs. Agus Salim Harahap, M.Si selaku Dosen Pembimbing I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
6.
Bapak Ade Candra, ST, M.Kom selaku Dosen Pembimbing II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
7.
Ibu Dian Rachmawati, M.Kom selaku Dosen Pembanding II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
v
8.
Semua dosen dan semua pegawai di Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.
9.
Keluarga besar penulis, Orang tua yang senantiasa mendoakan dan mendukung serta adik- adik tersayang Habib, Putri, Pipin, Tita
10. Teman-teman seperjuangan mahasiswa Ekstensi S1-Ilmu Komputer stambuk 2012, teman-teman D3 Mipa teruntuk M. Iqbal dalam diskusi pembuatan program. Dan adik-adik junior yang telah memberikan semangat dan menjadi teman diskusi penulis dalam menyelesaikan skripsi ini. 11. Semua pihak yang terlibat langsung ataupun tidak langsung yang tidak dapat penulis ucapkan satu per satu yang telah membantu penyelesaian skripsi ini.
Penulis menyadari bahwa skripsi ini masih terdapat kekurangan. Oleh karena itu, kepada pembaca agar kiranya memberikan kritik dan saran yang bersifat membangun demi kesempurnaan skripsi ini. Sehingga dapat bermanfaat bagi kita semuanya.
Medan,
Februari 2015
Penulis,
( Indah Mustika Tanjung )
IMPLEMENTASI ALGORITMA KNUTH-MORRIS-PRATH STRING MATCHING UNTUK MENCARI KATA ATAU ISTILAH PADA KAMUS KOMPUTER BERBASIS ANDROID
vi
ABSTRAK
Kamus adalah buku acuan yang digunakan manusia untuk menerjemahkan suatu bahasa/istilah asing. Pada umumnya disusun menurut abjad berikut keterangan tentang maknanya, pemakaiannya, atau terjemahannya. Demikian halnya dengan kamus istilah komputer sangat diperlukan dalam menerjemahkan istilah komputer. Begitu banyak metode algoritma yang dapat digunakan dalam pembuatan aplikasi kamus, salah satunya dengan menggunakan algoritma Knuth Morris Pratt (KMP). Dengan algoritma ini, setiap teks yang akan diterjemahkan akan ditinjau kata-kata untuk kemudian dicari kecocokannya dengan kata padanan dalam istilah yang diinginkan. Dalam kajian ini penulis akan melakukan analisa sekaligus uji coba terhadap penerapan algoritma Knuth Morris Pratt ini dalam aplikasi kamus istilah komputer pada smartphone Android. Didapatkan hasil dengan menggunakan Algoritma Knuth Morris Pratt bahwa aplikasi ini dapat membantu pengguna gadget untuk mencari kata atau istilah pada kamus komputer berbasis Android. Kata-kata Kunci : Algoritma, String Matching, Knuth-Morris-Pratt (KMP), Kamus, Android.
IMPLEMENTATION OF KNUTH-MORRIS-PRATH ALGORITHM
vii
TO FIND THE WORD OR TERM ON ANDROID BASED COMPUTER DICTIONARY
ABSTRACT
Dictionary is a reference book that we used to translate a language / foreign terms. Generally, the following is alphabetical with description of its meaning, its use, or its translation. Similarly, the dictionary of computer terms is needed in translating the computer term. So many methods of algorithms that can be used in the making of an dictionary application, one of them by using the algorithm of Knuth Morris Pratt (KMP). With this algorithm, any text that we translated will be reviewed by words then searched for compatibility with the word equivalent in terms desired. In this study the authors will perform an analysis and a tests on the application of this Knuth Morris Pratt algorithm in computer terms dictionary app on Android smartphone. Is obtained by using the algorithm of Knuth Morris Pratt that this application can help users gadget to search for words or terms in the dictionary of computer -based Android . Keywords: Algoritm, String Matching, Knuth - Morris - Pratt ( KMP ) , Dictionary, Android.
viii
DAFTAR ISI
halaman Persetujuan Pernyataaan Penghargaan Abstrak Abstract Daftar isi Daftar tabel Daftar gambar 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
ii iii iv v vi vii ix x 1 1 2 3 3 3 4 5
BAB 2. TINJAUAN PUSTAKA 2.1. Definisi Algoritma 2.1.1. Algoritma 2.2. String 2.2.1. String Matching 2.2.2. Algoritma Knuth Morris Pratt String Matching 2.2.3. Fungsi Pinggiran 2.2.4. Fungsi Pembanding String 2.2.5. Klasifikasi Pencocokan String 2.3. Mobile Device 2.4. Android 2.4.1. Sejarah Android 2.4.2. Pengertian Android 2.4.3. Versi Android 2.4.4. Arsitektur Android 2.5. Database 2.5.1. Menggunakan Format CSV 2.6. Kamus
6 6 6 7 7 8 8 10 12 14 15 15 16 16 18 19 19 21
BAB 3. ANALISIS DAN PERANCANGAN SISTEM 3.1. Analisis System 3.1.1. Analisis kebutuhan Sistem 3.2. Analisis Kebutuhan Sistem 3.2.1. Kebutuhan Fungsional
22 22 23 23 23
ix
3.2.2. Kebutuhan Non-Fungsioanal 3.3. Pemodelan Sistem 3.3.1. Use-Case Diagram 3.3.2. Activity Diagram 3.3.3. Sequence Diagram 3.4. Perancangan Sistem 3.4.1. Flowchart System 3.4.2. Flowchart Algoritma Knuth Moriis Pratt 3.5. Perancangan Antarmuka Sistem (Interface) 3.5.1. Halaman Utama 3.5.2. Rancangan Halaman Cari Kata 3.5.3. Rancangan Halaman Tambah Kata 3.5.4. Rancangan Halaman Tentang 3.5.5. Rancangan Halaman Bantuan BAB 4. IMPLEMENTASI DAN PENGUJIAN 4.1. Pengujian Sistem 4.2. Implementasi Sistem 4.2.1. Halaman Utama 4.2.2. Halaman Cari kata 4.2.3. Halaman Tambah Kata 4.2.4. Dataset .csv 4.2.5. Halaman Tentang 4.2.6. Halaman Bantuan Kompleksitas Waktu Algoritma PROMETHEE BAB 5. KESIMPULAN DAN SARAN 5.1. Kesimpulan 5.2. Saran DAFTAR PUSTAKA
24 24 24 25 31 32 33 34 36 36 38 40 41 42 43 43 54 55 55 57 58 60 62 86 64 64
x
DAFTAR TABEL
halaman Tabel 2.1. Tabel 2.2 Tabel 2.3. Tabel 3.1. Tabel 3.2. Tabel 3.3. Tabel 3.4. Tabel 3.5.
Fungsi Pinggiran Untuk Pattern abcabd Pengklasifikasian dalam Use Case Diagram Tabel Relasi-relasi dalam Use Case Diagram Keterangan Bagian-Bagian Rancangan Halaman Utama Keterangan Bagian-Bagian Rancangan Pencarian Kata Keterangan Bagian-Bagian Rancangan Tambah Kata Keterangan Bagian-Bagian Rancangan Tentang Aplikasi Keterangan Bagian-Bagian Rancangan Bantuan Aplikasi
8 21 21 39 41 42 43 44
xi
DAFTAR GAMBAR
halaman Gambar 2.1. Gambar 3.1. Gambar 3.2. Gambar 3.3. Gambar 3.4. Gambar 3.5 Gambar 3.6. Gambar 3.7. Gambar 3.8. Gambar 3.9. Gambar 3.10. Gambar 3.11. Gambar 3.12. Gambar 3.13. Gambar 3.14. Gambar 3.15. Gambar 4.1. Gambar 4.2. Gambar 4.3. Gambar 4.4. Gambar 4.5. Gambar 4.6. Gambar 4.7. Gambar 4.8. Gambar 4.9. Gambar 4.10. Gambar 4.11. Gambar 4.12
Android Architecture Diagram Ishikawa Untuk Analisis Masalah Use Case Algoritma Knuth Morris Pratt Activity Diagram Panjang Teks dan Pattern Activity Diagram Proses Awal Menemukan Karakter Activity Diagram Menghitung Nilai Pergeseran Karakter Activity Diagram Membandingkan Karakter Per Karakter Activity Diagram System Sequence System Pada Kamus komputer Flowchart System Flowchart Proses KMP Rancangan Halaman Utama Rancangan Halaman Cari Kata Rancangan Halaman Tambah Kata Rancangan Halaman Tentang Aplikasi Rancangan Halaman Bantuan Aplikasi Perbatasan r, s dari a string x Perpanjangan Perbatasan Awalan Panjang i Dari Pola Dengan Batas Lebar b[i] Batas Panjang m Dari Awalan x pt Pergeseran Pola Ketika Ketidakcocokan Pada Posisi j Terjadi Hasil Pencarian Menggunakan Algoritma KMP Halaman Utama Contoh Fungsi Autocomplete Tambah Kata Penyimpanan Kata Istilah Komputer Tentang Aplikasi Komputer Bantuan Aplikasi Komputer
25 28 28 29 30 31 32 33 35 36 37 39 40 42 43 44 47 47 48 49 50 55 57 58 59 60 63 63
