IMPLEMENTASI ALGORITMA BOYER MOORE DAN METODE N-GRAM UNTUK APLIKASI AUTOCOMPLETE DAN AUTOCORRECT TUGAS AKHIR
Diajukan Untuk Memenuhi Persyaratan Akademik Studi Strata Satu (S1) Teknik Informatika Universitas Muhammadyah Malang
Oleh : Ririn Ernawati 09560036
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADYAH MALANG 2013
LEMBAR PERSETUJUAN
IMPLEMENTASI ALGORITMA BOYER MOORE DAN METODE N-GRAM UNTUK APLIKASI AUTOCOMPLETE DAN AUTOCORRECT
TUGAS AKHIR
Oleh : Ririn Ernawati 09560036
Telah Direkomendasikan Untuk Diajukan Sebagai Judul Tugas Akhir Di Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui, Pembimbing I
Pembimbing II
(Yuda Munarko, S.kom, M.Sc) NIP. 108.0611.0443
(Gita Indah Marthasari, ST) NIP. 108.0611.0442
LEMBAR PENGESAHAN
IMPLEMENTASI ALGORITMA BOYER MOORE DAN METODE N-GRAM UNTUK APLIKASI AUTOCOMPLETE DAN AUTOCORRECT
TUGAS AKHIR
Diajukan Untuk Memenuhi Persyaratan Guna Meraih Gelar Sarjana Strata Satu Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh : RIRIN ERNAWATI 09560036
Tugas Akhir ini telah diuji dan dinyatakan lulus oleh tim penguji pada tanggal 22 Oktober 2013
Mengetahui/Menyetujui Penguji I
Penguji II
(Eko Budi Cahyono, S.Kom, MT)
(Wahyu Andhyka, S.Kom, M.Kom)
Mengetahui Ketua Jurusan Teknik Informatika
(Eko Budi Cahyono, S.Kom, MT )
LEMBAR PERNYATAAN Yang bertanda tangan di bawah ini: Nama Tempat / Tgl Lahir NIM Fakulats / Jurusan Dengan
ini
saya
: Ririn Ernawati : Gresik, 09 Februari 1990 :09560036 : Teknik / Teknik Informatika menyatakan
bahwa
Tugas
Akhir
dengan
judul
“IMPLEMENTASI ALGORITMA BOYER MOORE DAN METODE NGRAM UNTUK APLIKASI AUTOCOMPLETE DAN AUTOCORRECT” beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain, baik sebagian maupun keseluruhan, kecuali dalam bentuk kutipan yang telah disebutkan sumbernya. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya. Apabila kemudian ditemukan adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada klaim dari pihak lain terhadap keaslian karya saya ini maka saya siap menanggung segala bentuk resiko/sanksi yang berlaku.
Malang, 12 Oktober 2013 Yang Membuat Pernyataan
(Ririn Ernawati) Mengetahui, Dosen Pembimbing I
Dosen Pembimbing II
(Yuda Munarko, S.Kom, M.Sc)
(Gita Indah Marthasari, ST)
NIP. 108.0611.0443
NIP. 108.0611.0442
KATA PENGANTAR Bismillahirahmanirrahim. Dengan mengucap puji dan syukur kehadirat Allah SWT atas berkat rahmat dan hidayah-Nya tugas akhir berjudul “IMPLEMENTASI ALGORITMA BOYER MOORE DAN METODE N-GRAM UNTUK APLIKASI AUTOCOMPLETE DAN AUTOCORRECT” ini dapat terselesaikan dengan baik. Dengan menyadari adanya keterbatasan waktu, kemampuan, pengetahuan, referensi dan pengalaman, Tugas Akhir ini masih jauh dari sempurna. Untuk itu saran dan masukkan untuk kesempurnaan sangat penulis harapkan. Akhir kata penulis berharap semoga Tugas Akhir ini dapat bermanfaat dan menjadi tambahan ilmu pengetahuan.
Malang, 12 Oktober 2013
Penulis
DAFTAR ISI
ABSTRAK..............................................................................................
i
ABSTRACT ...........................................................................................
ii
KATA PENGANTAR ............................................................................
iii
LEMBAR PERSEMBAHAN ................................................................
iv
DAFTAR ISI ..........................................................................................
v
DAFTAR GAMBAR ..............................................................................
viii
DAFTAR TABEL ..................................................................................
x
BAB I PENDAHULUAN 1.1. Latar Belakang Masalah .............................................................
1
1.2. Rumusan Masalah ......................................................................
2
1.3. Tujuan ........................................................................................
2
1.4. Batasan Masalah ........................................................................
3
1.5. Metodologi Penyelesaian Masalah ..............................................
3
1.6. Sistematika Penulisan .................................................................
4
BAB II LANDASAN TEORI 2.1 Pencocokan String ......................................................................
5
2.1.1 Definisi Pencocokan String ............................................
5
2.1.2 Klasifikasi Pencocokan String ........................................
5
2.2 Algoritma Pencocokan String (String Matching) ........................
6
2.2.1 Algoritma Brute Force ...................................................
7
2.2.2 Algoritma Knuth Morris Pratt ........................................
8
2.3 Algoritma Boyer Moore ............................................................
9
2.3.1 Definisi Algoritma Boyer Moore....................................
9
2.3.2 Definisi Kerja Algoritma Boyer Moore ..........................
9
2.4 Metode Pemotongan karakter ....................................................
20
2.4.1 Definisi N-gram .............................................................
20
2.4.2 Similarity Dokumen .......................................................
22
2.5 Autcomplete ..............................................................................
20
2.5.1 Definisi Autocomplete ...................................................
23
2.6 Autocorrect ...............................................................................
24
2.6.1 Definisi Autocorrect.......................................................
24
2.6 Java ...........................................................................................
25
BAB III ANALISA DAN PERENCANAAN SISTEM 3.1 Analisa Sistem ...........................................................................
29
3.1.1 Flowchart Perangkat lunak .............................................
30
3.1.2 Use Case Diagram .........................................................
32
3.1.3 Activity Diagram ...........................................................
33
3.2 Perancangan Sistem....................................................................
37
3.2.1 Sequence Diagram .........................................................
37
3.2.2 Class Diagram ...............................................................
39
3.2.3 Desain Interface .............................................................
40
3.2.4 Perancangan Basis Data .................................................
42
BAB IV IMPLEMENTASI DAN PENGUJIAN 4.1 Implementasi Sistem ..................................................................
44
4.1.1 Implementasi Aplikasi ...................................................
44
4.1.1.1 Proses Input kata ................................................
45
4.1.1.2 Proses Algoritma Boyer Moore ..........................
46
4.1.1.3 Proses Autocorrect .............................................
47
4.1.1.4 Proses Metode N-gram .......................................
48
4.2 Pengujian Sistem ........................................................................
48
4.2.1 Pengujian Form Menu ....................................................
48
4.2.2 Pengujian Aplikasi Autocomplete ..................................
49
4.2.3 Pengujian Aplikasi Autocorrect......................................
51
4.2.4 Pengujian Tambah Kata .................................................
53
4.2.5 PengujianKata................................................................
56
4.2.5.1 Pengujian Kata Autocorrect Metode N-gram ......
56
4.2.5.2 Pengujian Kata Autocomplete Boyer Moore .......
69
4.2.5.3 Pengujian Kata Autocorrect Boyer Moore ..........
72
4.2.5.4 Pengujian Kata Autocomplete N-gram ...............
75
4.2.6 Perbandingan Hasil Pengujian Algoritma Boyer Moore dan Metode N-gram ......................................................
76
BAB V KESIMPULAN DAN SARAN 5.1 Kesimpulan ................................................................................
79
5.2 Saran ..........................................................................................
80
DAFTAR PUSTAKA
DAFTAR GAMBAR
Gambar 2.1 Good Suffix shift ..................................................................
15
Gambar 2.2 Good Suffix Shift ..................................................................
15
Gambar 2.3 Bad Character Shift .............................................................
16
Gambar 2.4 Bad Character Shift .............................................................
16
Gambar 3.1 Flowchart Gambaran Aplikasi .............................................
30
Gambar 3.2 Flowchart Proses Algoritma Boyer Moore ...........................
30
Gambar 3.3 Flowchart Proses Metode N-gram .......................................
31
Gambar 3.4 Usecase Diagram Sistem .....................................................
32
Gambar 3.5 Activity Diagram Pengujian Autocomplete ...........................
34
Gambar 3.6 Activity Diagram Pengujian Autocorrect ...............................
35
Gambar 3.7 Activity Diagram Tambah Kata ............................................
36
Gambar 3.8 Sequence Diagram Autocomplete ........................................
37
Gambar 3.9 Sequence Diagram Autocorrect ...........................................
38
Gambar 3.10 Sequence Diagram Tambah Kata ........................................
38
Gambar 3.11 Class Diagram ...................................................................
39
Gambar 3.12 Tampilan Awal Index Aplikasi ...........................................
40
Gambar 3.13 Tampilan Menu Pengujian .................................................
41
Gambar 3.14 Tampilan Halaman Add .....................................................
41
Gambar 3.15 Tampilan Halaman Keterangan ..........................................
42
Gambar 3.16 Perancangan Basis Data .....................................................
43
Gambar 4.1 Proses Input Kata ..................................................................
45
Gambar 4.2 Preprocessing Algoritma Boyer Moore ................................
46
Gambar 4.3 Proses Autocorrect ...............................................................
47
Gambar 4.4 Metode N-gram ...................................................................
48
Gambar 4.5 Pengujian Form Menu...........................................................
49
Gambar 4.6 Pengujian Aplikasi ...............................................................
50
Gambar 4.7 Pengujian Autocomplete ........................................................
50
Gambar 4.8 Penulisan Kata Salah ...........................................................
52
Gambar 4.9 Pengujian Autocorrect .........................................................
52
Gambar 4.10 Pengujian Tambah Kata .....................................................
53
Gambar 4.11 Tombol Tambah Kata ........................................................
54
Gambar 4.12 Input Kata ..........................................................................
54
Gambar 4.13 Proses Tambah Kata ...........................................................
54
Gambar 4.14 Grafik Hasil ........................................................................
69
Gambar 4.15 Hasil Inputan Awal Autocomplete ......................................
75
Gambar 4.16 Hasil Penambahan Karakter ................................................
75
Gambar 4.17 Hasil Inputan Seluruh Kata .................................................
76
Gambar 4.18 Autocomplete Dengan Boyer Moore ...................................
77
Gambar 4.19 Autocomplete Dengan N-gram............................................
77
DAFTAR TABEL
Table 2.1 Table Occurrence Heuristic ......................................................
11
Table 2.2 Table Match Heuristic ..............................................................
12
Table 2.3 Table Posisi Ketidakcocokkan Karakter....................................
13
Table 2.4 Table Revisi Kolom..................................................................
19
Tabel 4.1 Tabel Penyerapan Bahasa Inggris ke dalam Bahasa Indonesia .
56
Tabel 4.2 Tabel Pengetikan Huruf Salah dengan Akhiran Bahasa Inggris .
57
Tabel 4.3 Tabel Pengetikan Huruf Salah (a menjadi e) .............................
57
Tabel 4.4 Tabel Pengetikan Huruf Salah (e menjadi a) .............................
58
Tabel 4.5 Tabel Pengetikan Huruf Salah (a menjadi i) ..............................
58
Tabel 4.6 Tabel Pengetikan Huruf Salah (e menjadi i) ..............................
58
Tabel 4.7 Tabel Pengetikan Huruf Salah (u menjadi o) .............................
59
Tabel 4.8 Tabel Pengetikan Huruf Salah (ua/ue/ui menjadi wa/we/wi) .....
60
Tabel 4.9 Tabel Pengetikan Huruf Salah (i menjadi e) ..............................
60
Tabel 4.10 Tabel Pengetikan Huruf Salah (gugus konsonan ks menjadi x)
61
Tabel 4.11 Tabel Pengetikan Huruf Salah (gugus konsonan sy) ................
61
Tabel 4.12 Tabel Hasil Pengujian Autocorrect Metode N-gram................
62
Tabel 4.13 Tabel Matriks Confusion ........................................................
67
Tabel 4.14 Tabel True Positif Value .........................................................
67
Tabel 4.15 Tabel False Positif Value........................................................
68
Tabel 4.16 Tabel Precision Recall Metode N-gram ..................................
68
Tabel 4.17 Tabel Hasil Pengujian Autocomplete Algoritma Boyer Moore
69
Tabel 4.18 Tabel Hasil Pengujian Autocorrect Algoritma Boyer Moore ...
72
Tabel 4.19 Tabel Precision Recall Algoritma Boyer Moore .....................
75
Tabel 4.20 Tabel Perbandingan Precision Recall .....................................
78
DAFTAR PUSTAKA [1] Algoritma Boyer Moore. Diakses tanggal 28 Januari 2013 http://edwardgr.wordpress.com/2009/01/06/algoritma-boyer-moore/ [2] Arini Rahmawati R. 2011. Pembangunan Sistem Pendeteksi Pengunaan Situs Wikipedia Sebagai Referensi Algoritma Winnowing Menggunakan Metode N-gram, Universitas Muhammadiyah Malang, Malang. [3] Bickel Steffen,dkk. Predecting Sentences using N-gram Language Models, Humbolt-Universitat zu Berlin, Germany. [4] id ibnu daqiqil. 2007. Perancangan dan Penerapan Algoritma Stemming Kata Berbahasa Indonesia,Universitas Brawijaya, Malang. [5] Islam Aminul, Inkpen Diana. Real-World Spelling Correction using Google Web 1T n-gram Data Set, University of Otawa, Canada. [6] Kamus Kata Dasar dan Stopword List Bahasa Indonesia. Diakses tanggal 09 Juni 2013. http://hikaruyuuki.lecture.ub.ac.id/kamus-kata-dasar-dan-stopword-listbahasa-indonesia/ [7] Kurnaedi Andri. 2011. Penerapan String Matching Menggunakan Algoritma Boyer Moore Pada Translator Bahasa Pascal Ke C, Universitas Komputer Indonesia, Bandung. [8] kustiyahningsih yeni. Rancang Bangun Aplikasi (E-DMS) Electronic Document Management System Denngan Metode TF/IDF Berbasis WEB, UNiversitas Trunojoyo, Madura. [9] Lalwani Mahesh,dkk. Efficient Algorithm for Auto Correction Using Ngram Indexing,Nirma University, India. [10] Nuriza Choirul R. 2013. Penerapan Algoritma Boyer Moore Pada Layanan SMS Auto Replay (Studi Kasus UPT PMB UMM), Universitas Muhammadiyah Malang, Malang. [11] Purwitasari Diana,dkk. Deteksi Keberadaan Kalimat Sama Sebagai Indikasi Penjiplakan dengan Algoritma Hashing Berbasis N-gram, Institut Teknologi Sepuluh Nopember Surabaya, Surabaya.
[12] Pradhana Fandi. 2012. Penerapan String Matching pada Fitur Auto Correct dan Fitur Auto Text di Smart Phone,Institut Teknologi Bandung, Bandung.
[13] Ridok Achmad. 2012. Pembuatan Judul Otomatis Dokumen Berita Berbahasa Indonesia Menggunakan Metode KNN, Universitas Brawijaya, Malang. [14] Syaroni Mokhamad,dkk. 2005. Pencocokan String Berdasarkan Kemiripan Ucapan (Phonetic String Matching) Dalam Bahasa Inggris, Institut Teknologi Bandung, Bandung. [15] Tryas Ayu P. 2012. Membangun Aplikasi Pencocokan String Berdasarkan Penulisan dan Kemiripan Ucapan, Sekolah Tinggi Manajemen Informatika dan Komputer AMIKOM, Yogyakarta. [16] Wikipedia. Diakses tanggal 28 Januari 2013 http://id.wikipedia.org/wiki/Algoritma_Boyer-Moore
