PERBANDINGAN ALGORITMA KNUTH MORRIS PRATT DAN BOYER MOORE PADA APLIKASI KAMUS BAHASA INDONESIA-KOREA BERBASIS ANDROID
SKRIPSI
VICI INDAH YANA 121401062
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA 2016
PERBANDINGAN ALGORITMA KNUTH MORRIS PRATT DAN BOYER MOORE PADA APLIKASI KAMUS BAHASA INDONESIA-KOREA BERBASIS ANDROID
SKRIPSI
Diajukan untuk melengkapi tugas akhir dan memenuhi syarat memperoleh gelar Sarjana Komputer
VICI INDAH YANA 121401062
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PERBANDINGAN ALGORITMA KNUTH MORRIS PRATT DAN BOYER MOORE PADA APLIKASI KAMUS BAHASA INDONESIA-KOREA BERBASIS ANDROID : SKRIPSI : VICI INDAH YANA : 121401062 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI Diluluskan di Medan,
Komisi Pembimbing
2016
:
Pembimbing 2
Pembimbing 1
Maya Silvi Lydia, B.Sc, M.Sc NIP. 19740127 200212 2 001
Dr. Poltak Sihombing, M.Kom NIP. 19620317 199103 1 001
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
iii
PERNYATAAN
PERBANDINGAN ALGORITMA KNUTH MORRIS PRATT DAN BOYER MOORE PADA APLIKASI KAMUS BAHASA INDONESIA-KOREA 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,
Vici Indah Yana 121401062
2016
iv
PENGHARGAAN
Puji dan syukur kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya, sehingga Penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer pada Program Studi S1 Ilmu Komputer Universitas Sumatera Utara. Pada pengerjaan skripsi dengan judul Perbandingan Algoritma Knuth Morris Pratt dan Boyer-Moore pada Aplikasi Kamus Bahasa Indonesia-Korea berbasis 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. Runtung Sitepu, SH, M.Hum selaku Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. 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 dan selaku Dosen Pembimbing I yang telah memberikan bimbingan, saran, dan masukan kepada penulis dalam pengerjaan skripsi ini. 4. Ibu Maya Silvi Lydia, B.Sc, M.Sc selaku Dosen Pembimbing II yang telah memberikan bimbingan, saran, dan masukan kepada penulis dalam pengerjaan skripsi ini. 5. Bapak Prof. Dr. Iryanto, M.Si selaku Dosen Pembanding I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini. 6. Bapak Ade Candra, S.T, M.Kom selaku Dosen Pembanding II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini. 7. Bapak M.Andri Budiman, ST, M.Comp. Sc, M.E.M dan Ibu Dian Rachmawati, S.Si, M.Kom yang telah memberikan ilmu bermanfaat kepada penulis dalam pengerjaan skripsi ini 8. Wakil Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, seluruh tenaga pengajar, seluruh staff
v
akademik serta pegawai di Program Studi S1 Ilmu Komputer Fasilkom-TI USU. 9. Ayahanda Gama Solihin dan Ibunda Elfina Septi, yang selalu memberikan doa dan dukungan serta kasih sayang kepada penulis, Adik tersayang Ega yang terus memberikan dukungan dan dorongan bagi penulis untuk menyelesaikan skripsi ini. 10. Teman-teman kuliah, kepada Akhiruddin, Novi, Ricky, Rizky, Ila, Nurmardiah, Novita, Boris, Siti, Evelin, Neno, Dian, Ica, Zahra, Arif Maulana dan seluruh anak Kom B yang tidak bisa disebutkan satu-persatu, yang telah berbagi suka dan duka, semangat dan dorongan sehingga penulis dapat menyelesaikan skripsi ini. 11. Teman-teman stambuk 2012 dan para Senior 2010 - 2011 yang telah banyak membagi ilmu dan membantu pengerjaan skripsi ini 12. Teman-teman belajar bahasa korea, kepada Achmad Gadavi, Cici Henny Mauliza yang telah membantu penulis untuk mempelajari bahasa Korea pada pengerjaan skripsi ini 13. Dan semua pihak yang telah banyak membantu yang tidak bisa disebutkan satu-persatu. Semoga Allah SWT melimpahkan berkah kepada semua pihak yang telah memberikan bantuan, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini.
Medan,
2016 Penulis,
Vici Indah Yana
vi
ABSTRAK
Penelitian ini membahas tentang bagaimana melakukan pencarian kata pada Kamus Bahasa Asing dengan menggunakan Algoritma pencocokan kata. Penelitian ini bertujuan untuk mengetahui Algoritma yang lebih baik diantara Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore untuk proses pencocokan kata. Pencocokan kata merupakan bagian penting dari sebuah proses pencarian kata dalam sebuah dokumen. Algoritma pencocokan kata yang digunakan dalam penelitian ini adalah Algoritma Knuth Morris Pratt dan Boyer Moore. Algoritma Knuth Morris Pratt melakukan perbandingan teks dan pola dimulai dari kiri ke kanan sedangkan Algoritma Boyer Moore melakukan perbandingan teks dan pola dimulai dari kanan ke kiri, tetapi pergeseran window tetap dari kiri ke kanan. Hasil dari penelitian ini menunjukkan bahwa Algoritma Knuth Morris Pratt lebih cepat dibandingkan Algoritma Boyer Moore untuk proses pencarian kata. Hasil rata-rata Running Time Algoritma Knuth Morris Pratt adalah 132.1 ms dan Algoritma Boyer Moore adalah 134.6 ms.
Kata kunci : Pencocokan kata, Algoritma Knuth Morris Pratt, Algoritma Boyer Moore.
vii
THE COMPARISON BETWEEN KNUTH MORRIS PRATT ALGORITHM AND BOYER MOORE ALGORITHM IN INDONESIAN KOREAN DICTIONARY APPLICATION ON ANDROID
ABSTRACT
This research discusses about how to do a word searching in foreign language dictionary using string matching algorithm. This research is aimed to know which algorithm is better between Knuth Morrish Pratt algorithm and Boyer Moore algorithm in string matching process. String matching is an important parts of string searching process in a document. String matching algorithm that is used in this research are Knuth Morris Pratt algorithm and Boyer Moore algorithm. Knuth Morris Pratt algorithm performs the comparisons of the text and the pattern from left to right. Whereas Boyer Moore algorithm performs the comparisons of the text and the pattern from right to left, but the shifting of the window remains from left to right.The result of this research shows that Knuth Morris Pratt algorithm is faster than Boyer Moore algorithm in word searching process. The running time average of Knuth Morris Pratt algorithm is 132.1 ms and Boyer Moore algorithm is 134.6 ms
Keywords: String Matching, Knuth Morris Pratt Algorithm, Boyer Moore 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 Perumusan Masalah 1.3 Ruang Lingkup Penelitian 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan
1 3 3 3 4 4 5
Bab 2 Landasan Teori 2.1 Definisi Kamus 2.2 Definisi Algoritma 2.2.1 Algoritma String Matching (pencocokan kata) 2.2.1.1 Algoritma Knuth Morris Pratt 2.2.1.2 Algoritma Boyer Moore 2.2.1.2.1 Suffix 2.2.1.2.2 Good-Suffix Shift (Match Heuristic) 2.2.1.2.3 Bad-Character Shift (Occurance Heuristic) 2.3 Definisi Kompleksitas Algoritma 2.4 Definisi Android 2.5 Penelitian yang Relevan
7 7 7 8 13 13 14 16 19 20 21
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.2. Pemodelan 3.2.1 Use Case Diagram
23 23 24 25 25 26 26
ix
3.2.2 Activity Diagram 3.2.3 Sequance Diagram 3.3 Pseudocode 3.3.1 Pseudocode Algoritma Knuth Morris Pratt 3.3.2 Pseudocode Algoritma Boyer Moore 3.4 Flowchart 3.5 Perancangan Antarmuka Sistem (Interface) 3.5.1 Rancangan Halaman Splash Screen 3.5.2 Rancangan Navigation Drawer 3.5.3 Rancangan Halaman Beranda 3.5.4 Rancangan Halaman Pencarian 3.5.5 Rancangan Halaman Fitur 3.5.6 Rancangan Halaman Bantuan 3.5.7 Rancangan Halaman Tentang 3.5.8 Rancangan Halaman Keluar Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi 4.1.1 Tampilan Halaman Splash Screen 4.1.2 Tampilan Navigation Drawer 4.1.3 Tampilan Halaman Beranda 4.1.4 Tampilan Halaman Pencarian 4.1.5 Tampilan Halaman Fitur 4.1.6 Tampilan Halaman Bantuan 4.1.7 Tampilan Halaman Tentang 4.1.8 Tampilan Halaman Keluar 4.2 Pengujian Sistem 4.2.1 Pengujian pencarian kata pada Kamus Bahasa Indonesia-Korea dengan Algoritma Knuth Morris Pratt 4.2.2 Pengujian pencarian kata pada Kamus Bahasa Indonesia-Korea dengan Algoritma Boyer Moore 4.3 Hasil Pengujian 4.4 Kompleksitas Algoritma 4.4.1 Kompleksitas Algoritma Knuth Morris Pratt 4.4.2 Kompleksitas Algoritma Boyer Moore
29 30 31 31 32 34 37 37 38 39 39 43 43 44 45
47 47 48 48 49 50 51 51 52 53 53 59 65 68 68 71
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2. Saran
76 77
Daftar Pustaka
78
x
DAFTAR TABEL
Nomor Tabel 2.1 2.2 2.3 2.4 2.5 2.6 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.25 4.26 4.27 4.28
Nama Tabel
Halaman
Hasil Perhitungan kmpNext[i] dan shift[i] Hasil Perhitungan Suffix Hasil Perhitungan bmGs Hasil Perhitungan bmBc Pergeseran karakter untuk bmBc Pergeseran posisi untuk bmGs Use Case Proses Menentukan tipe terjemahan Use Case Proses Input kata Use Case Proses Algoritma Knuth Morris Pratt Use Case Proses Algoritma Boyer Moore Pseudecode preKmp Pseudecode KMP Pseudecode suffix Pseudecode bmGs Pseudecode bmBc Pseudecode BM Hasil Pencarian kata “a” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “an” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “ma” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “perempuan” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “komput” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “ch” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “imnida” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “keopyuteogong” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “xy” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “samuso” dengan Algoritma Knuth Morris Pratt Hasil Pencarian kata “a” dengan Algoritma Boyer Moore Hasil Pencarian kata “an” dengan Algoritma Boyer Moore Hasil Pencarian kata “ma” dengan Algoritma Boyer Moore Hasil Pencarian kata “perempuan” dengan Algoritma Boyer Moore Hasil Pencarian kata “komput” dengan Algoritma Boyer Moore Hasil Pencarian kata “ch” dengan Algoritma Boyer Moore Hasil Pencarian kata “imnida” dengan Algoritma Boyer Moore Hasil Pencarian kata “keopyuteogong” dengan Algoritma Boyer Moore Hasil Pencarian kata “xy” dengan Algoritma Boyer Moore Hasil Pencarian kata “samuso” dengan Algoritma Boyer Moore Hasil Pengujian Algoritma Knuth Morris Pratt Hasil Pengujian Algoritma Boyer Moore Kompleksitas fungsi preKmp Algoritma Knuth Morris Pratt Kompleksitas fungsi KMP Algoritma Knuth Morris Pratt Kompleksitas fungsi preBmBc Algoritma Boyer Moore Kompleksitas fungsi suffixes Algoritma Boyer Moore Kompleksitas fungsi preBmGs Algoritma Boyer Moore Kompleksitas fungsi BM Algoritma Boyer Moore
9 14 15 17 18 18 27 27 28 28 31 31 32 32 33 33 53 54 54 55 55 56 56 57 57 58 59 60 60 61 61 62 62 63 63 64 65 66 68 69 71 71 72 73
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 3.13 3.14 3.15 13.16 13.17 13.18 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12
Nama Gambar
Halaman
Diagram Ishikawa Use Case Diagram Sistem Activity Diagram Sistem Sequence Diagram Sistem Flowchart Gambaran Umum Sistem Kamus Flowchart Algoritma Knuth Morris Pratt Flowchart Algoritma Boyer Moore Rancangan Splash Screen Rancangan Navigation Drawer Rancangan Beranda Rancangan Pencarian Rancangan Hasil Pencarian Rancangan Alert dialog Terjemahan Rancangan Alert dialog Hasil Rancangan Fitur Rancangan Bantuan Rancangan Tentang Rancangan Keluar Halaman Splash Screen Halaman Navigation Drawer Halaman Beranda Halaman Pencarian Alert dialog Hasil Alert dialog Terjemahan Halaman Fitur Halaman Bantuan Halaman Tentang Halaman Keluar Perbandingan hasil Running Time Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore Perbandingan total Running Time Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore
24 26 29 30 34 35 36 37 38 39 40 41 42 42 43 44 45 45 47 48 48 49 49 50 50 51 51 52 67 67
xii
DAFTAR LAMPIRAN
Halaman A. Listing Program B. Daftar Riwayat Hidup
A-1 B-1
