RANCANG BANGUN SISTEM PENYELARASAN KATA BERBAHASA INDONESIA DENGAN MENGGUNAKAN ALGORITMA LEVENSHTEIN DISTANCE
KOMPETENSI REKAYASA PERANGKAT LUNAK SKRIPSI
NI MADE MUNI ADRIYANI NIM. 0808605046
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2012
RANCANG BANGUN SISTEM PENYELARASAN KATA BERBAHASA INDONESIA DENGAN MENGGUNAKAN ALGORITMA LEVENSHTEIN DISTANCE
KOMPETENSI REKAYASA PERANGKAT LUNAK
[SKRIPSI]
Sebagai syarat untuk memperoleh gelar Sarjana Komputer pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana Tulisan ini merupakan hasil penelitian yang belum pernah dipublikasikan
NI MADE MUNI ADRIYANI NIM. 0808605046
Pembimbing I
Pembimbing II
Drs. I Wayan Santiyasa, M.Si
Agus Muliantara, S.Kom., M.Kom.
NIP. 19670414 199203 1 002
NIP. 19800616 200501 1 001
ii
LEMBAR PENGESAHAN TUGAS AKHIR
Judul
: Rancang Bangun Sistem Penyelarasan Kata Berbahasa Indonesia Dengan Menggunakan Algoritma Levenshtein Distance
Kompetensi
:
Rekayasa Perangkat Lunak
Nama
:
Ni Made Muni Adriyani
NIM
:
0808605046
Tanggal Seminar :
28 September 2012 Disetujui oleh:
Pembimbing I
Penguji I
Drs. I Wayan Santiyasa, M.Si NIP. 19670414 199203 1 002
Dra. Luh Gede Astuti, M.Kom. NIP. 19640114 199402 2 001
Pembimbing II
Penguji II
Agus Muliantara, S.Kom., M.Kom. NIP. 19800616 200501 1 001
Ngurah Agus Sanjaya ER, S.Kom., M.Kom. NIP. 19780321 200501 1 001 Penguji III
I.B. Made Mahendra, S.Kom., M.Kom. NIP. 19800621 200812 1 002 Mengetahui, Jurusan Ilmu Komputer FMIPA UNUD Ketua,
Drs. I Wayan Santiyasa, M.Si NIP. 19670414 199203 1 002
iii
Judul
: Rancang Bangun Sistem Penyelarasan Kata Berbahasa Indonesia Dengan Menggunakan Algoritma Levenshtein Distance
Nama
:
Ni Made Muni Adriyani
Nama Pembimbing : 1. Drs. I Wayan Santiyasa, M.Si 2. Agus Muliantara, S.Kom., M.Kom.
ABSTRAK Bahasa merupakan alat komunikasi lingual manusia baik secara lisan maupun tulisan. Peran Bahasa Indonesia yang baik dan benar sangat diperlukan dalam penyusunan karya ilmiah. Hal ini disebabkan adanya data dan informasi yang ada didalamnya digunakan sebagai acuan untuk penelitian atau pengkajian selanjutnya bagi ilmuan lainnya. Hal itu tentu saja menimbulkan beberapa masalah seperti kesalahan pengetikan. Kontrol pegecekan bahasa yang baik dan benar jika dilakukan secara manual pastinya akan menghabiskan banyak waktu, apalagi dijaman serba modern seperti saat ini. Kesalahan penulisan pada umumnya disebabkan kedekatan letak keyboard, slip pada jari, ataupun karena dua karakter yang letaknya tertukar. Untuk permasalahan itu timbul ide untuk membuat Sistem Penyelarasan Ejaan Bahasa Indonesia yang dikembangkan dengan berbasis web menggunakan bahasa pemrograman PHP dan menggunakan basis data kumpulan kata berbahasa Indonesia yang mengacu pada KBBI. Algoritma yang digunakan untuk memberikan saran perbaikan adalah Levenshtein Distance yang dapat menghitung perbedaan antar string dan menghitung jumlah keterbedaan antar dua string dan metode empiris untuk memecah kata yang tidak terpisah oleh spasi. Berdasarkan hasil pengujian sistem didapatkan nilai precision sebesar 90%. Nilai recall sebesar 97,78%. Dan accuracy sistem dalam memperbaiki kesalahan penulisan kata berbahasa Indonesia sebesar 88%. Kata Kunci : Kesalahan Penulisan, Levenshtein Distance, Metode Empiris
iv
Judul
: Rancang Bangun Sistem Penyelarasan Kata Berbahasa Indonesia Dengan Menggunakan Algoritma Levenshtein Distance
Nama
:
Ni Made Muni Adriyani
Nama Pembimbing : 1. Drs. I Wayan Santiyasa, M.Si 2. Agus Muliantara, S.Kom., M.Kom.
ABSTRACT Bahasa merupakan alat komunikasi lingual manusia baik secara lisan maupun tulisan. Peran Bahasa Indonesia yang baik dan benar sangat diperlukan dalam penyusunan karya ilmiah. Hal ini disebabkan adanya data dan informasi yang ada didalamnya digunakan sebagai acuan untuk penelitian atau pengkajian selanjutnya bagi ilmuan lainnya. Hal itu tentu saja menimbulkan beberapa masalah seperti kesalahan pengetikan. Kontrol pegecekan bahasa yang baik dan benar jika dilakukan secara manual pastinya akan menghabiskan banyak waktu, apalagi dijaman serba modern seperti saat ini. Kesalahan penulisan pada umumnya disebabkan kedekatan letak keyboard, slip pada jari, ataupun karena dua karakter yang letaknya tertukar. Untuk permasalahan itu timbul ide untuk membuat Sistem Penyelarasan Ejaan Bahasa Indonesia yang dikembangkan dengan berbasis web menggunakan bahasa pemrograman PHP dan menggunakan basis data kumpulan kata berbahasa Indonesia yang mengacu pada KBBI. Algoritma yang digunakan untuk memberikan saran perbaikan adalah Levenshtein Distance yang dapat menghitung perbedaan antar string dan menghitung jumlah keterbedaan antar dua string dan metode empiris untuk memecah kata yang tidak terpisah oleh spasi. Berdasarkan hasil pengujian sistem didapatkan nilai precision sebesar 90%. Nilai recall sebesar 97,78%. Dan accuracy sistem dalam memperbaiki kesalahan penulisan kata berbahasa Indonesia sebesar 88%. Kata Kunci : Kesalahan Penulisan, Levenshtein Distance, Metode Empiris
v
KATA PENGANTAR
Puji dan syukur penulis panjatkan Kehadirat Tuhan Yang Maha Esa atas karunia-Nya karena dapat menyusun Tugas Akhir yang berjudul “Rancang Bangun
Sistem
Penyelarasan
Kata
Berbahasa
Indonesia
Dengan
Menggunakan Algoritma Levenshtein Distance” ini tepat pada waktunya. Dalam penyusunan laporan ini penulis banyak mendapatkan bantuan, bimbingan dan arahan dari berbagai pihak. Sehingga dalam kesempatan ini penulis ingin menyampaikan ucapan terima kasih kepada :
1. Bapak Drs. I Wayan Santiyasa, M.Si, selaku Ketua Jurusan Ilmu Komputer sekaligus sebagai Pembimbing I Tugas Akhir yang telah memberikan masukan, dukungan dan bimbingan dalam penyusunan Tugas Akhir. 2. Bapak Agus Muliantara S.Kom, M.Kom, selaku Dosen Pembimbing II Tugas Akhir yang senantiasa membimbing, memberikan pengarahan memberikan kritik, saran dan masukan-masukan dalam penyusunan Tugas Akhir ini. 3. Bapak dan Ibu Dosen Jurusan Ilmu Komputer yang memberikan bimbingan dan pengarahan dalam penyusunan Tugas Akhir. Pada akhirnya penulis berharap agar adanya perbaikan pada Tugas Akhir ini mengingat keterbatasan penulis. Mohon maaf jika dalam penulisan laporan ini belum sempurna untuk itu penulis mengharapkan kritik dan saran yang sifatnya membangun dari pembaca dan semoga laporan ini dapat bermanfaat bagi pembaca. Bukit Jimbaran, 28 September 2012 Penulis
vi
DAFTAR ISI LEMBAR PENGESAHAN ................................................................................... iii ABSTRAK ............................................................................................................. iv ABSTRACT ............................................................................................................ v KATA PENGANTAR ........................................................................................... vi DAFTAR ISI ......................................................................................................... vii DAFTAR GAMBAR .............................................................................................. x DAFTAR TABEL .................................................................................................. xi DAFTAR LAMPIRAN ......................................................................................... xii BAB I ...................................................................................................................... 1 PENDAHULUAN .................................................................................................. 1 1.1 Latar Belakang .............................................................................................. 1 1.2 Rumusan Masalah ......................................................................................... 3 1.3 Tujuan Penelitian ........................................................................................... 3 1.4 Batasan Masalah ............................................................................................ 3 1.5 Manfaat Penelitian ........................................................................................ 4 BAB II ..................................................................................................................... 5 TINJAUAN PUSTAKA ......................................................................................... 5 2.1 Pengertian Penyelarasan Kata ....................................................................... 5 2.2 Leveshtein Distance ....................................................................................... 5 2.2.1 Operasi Penghapusan ......................................................................... 6 2.2.2 Operasi Penyisipan ............................................................................. 6 2.2.3 Operasi Penggantian........................................................................... 6 2.3 Metode Empiris ........................................................................................... 11 2.4 Data Preprocessing ..................................................................................... 11 2.5 PHP (PHP Hypertext Preprocessor)........................................................... 12 2.6 Javascript .................................................................................................... 14 BAB III ................................................................................................................. 15 METODELOGI PENELITIAN ............................................................................ 15 3.1 Objek Penelitian .......................................................................................... 15
vii
3.2 Data Set ....................................................................................................... 15 3.3 Metode Penelitian ........................................................................................ 15 3.4 Perencanaan Sistem ..................................................................................... 15 3.5 Analisis Sistem ............................................................................................ 16 3.6 Perancangan Sistem ..................................................................................... 16 3.6.1 Flowchart Sistem ............................................................................. 16 3.6.2 Perancangan Data Flow Diagram.................................................... 22 3.6.3 Perancangan Tabel ........................................................................... 24 3.6.4 Perancangan Basis Data ................................................................... 24 3.7 Desain Antar Muka ..................................................................................... 24 3.8 Pengujian Sistem ......................................................................................... 26 3.9 Evaluasi Sistem ........................................................................................... 27 BAB IV ................................................................................................................. 28 HASIL DAN PEMBAHASAN ............................................................................. 28 4.1 Implementasi Sistem ................................................................................... 28 4.2 Implementasi Metode .................................................................................. 28 4.2.1 Implementasi Fungsi Token ............................................................. 29 4.2.2 Implementasi Fungsi Pengecekan Token Kata ............................... 30 4.2.3 Fungsi Levenshtein Distance ........................................................... 32 4.2.4 Implementasi Fungsi Cek Kata Tanpa Spasi ................................... 34 4.3 Uji Coba Sistem........................................................................................... 35 4.3.1 Lingkungan Uji Coba ....................................................................... 35 4.3.2 Pengujian Dengan White Box ........................................................... 35 4.3.2.1 Pengujian Fungsi Token .................................................................... 35 4.3.2.2 Pengujian Fungsi Pengecekan Token Kata ....................................... 36 4.3.2.3 Pengujian Fungsi Levenshtein Distance ............................................ 38 4.3.2.4 Pengujian Fungsi Kata Tanpa Spasi .................................................. 38 4.3.3 Pengujian Dengan Black Box ........................................................... 39 4.4 Implementasi Antarmuka Pengguna ........................................................... 40 4.5 Evaluasi nilai Accuracy, Precision dan Recall ........................................... 41
viii
BAB V................................................................................................................... 46 PENUTUP ............................................................................................................. 46 5.1 Kesimpulan .................................................................................................. 46 5.2 Saran ............................................................................................................ 46 DAFTAR PUSTAKA ........................................................................................... 48
ix
DAFTAR GAMBAR Gambar 2.1 Pseudocode Algoritma Levenshtein Distance ................................... 10 Gambar 2.2 Alur Eksekusi Kode PHP .................................................................. 14 Gambar 3.1 Flowchart Sistem Pengecekan Kata .................................................. 17 Gambar 3.2 Flowchart untuk proses token ........................................................... 18 Gambar 3.3 Flowchart untuk proses pengecekan token kata ................................ 19 Gambar 3.4 Flowchart proses Levenshtein Distance ........................................... 20 Gambar 3.5 Flowchart cek kata tanpa spasi ......................................................... 21 Gambar 3.6 Context Diagram ............................................................................... 22 Gambar 3.7 Data Flow Diagram Level 0 ............................................................. 22 Gambar 3.8 DFD Level 1...................................................................................... 23 Gambar 3.9 DFD Level 2...................................................................................... 23 Gambar 3.10 Isi Basis Data Sistem Pengecekan Kata .......................................... 24 Gambar 3.11 Desain Utama Antar Muka .............................................................. 25 Gambar 3.12 Contoh Kesalahan Penulisan ........................................................... 25 Gambar 3.13 Saran Penggantian Kata .................................................................. 26 Gambar 4.1 Path fungsi token ............................................................................... 36 Gambar 4.2 Path fungsi pengecekan kata ............................................................. 37 Gambar 4.3 Path fungsi Levenshtein Distance ..................................................... 38 Gambar 4.4 Path fungsi cek kata tanpa spasi ....................................................... 38 Gambar 4.5 Implementasi Antar Muka Sistem ..................................................... 40 Gambar 4.6 Tampilan Sistem Saat Menampilkan Saran Perbaikan ..................... 41
x
DAFTAR TABEL Tabel 2.1 Tabel Representasi Matriks ..................................................................... 9 Tabel 2.3 Daftar Karakter Huruf dan Tanda Baca ................................................ 12 Tabel 4.1 Data Pengujian Black Box ..................................................................... 39 Tabel 4.2 Tabel Data Pengujian Kata Yang Salah ................................................ 42 Tabel 4.3 Hasil Pengujian Kesalahan Kata ........................................................... 45
xi
DAFTAR LAMPIRAN
Lampiran 1. Dataset
xii
