IMPLEMENTASI ALGORITMA SYMSPELL DAN BAYESIAN …

IMPLEMENTASI ALGORITMA SYMSPELL DAN BAYESIAN

NETWORK DALAM PENGEMBANGAN SISTEM SPELL

CHECKER BAHASA INDONESIA

SKRIPSI

Diajukan sebagai salah satu syarat untuk memperoleh gelar

Sarjana Komputer (S.Kom.)

Alvin Valenciano

00000019893

PROGRAM STUDI INFORMATIKA

FAKULTAS TEKNIK DAN INFORMATIKA

UNIVERSITAS MULTIMEDIA NUSANTARA

TANGERANG

2021

ii

LEMBAR PENGESAHAN


NETWORK DALAM PENGEMBANGAN SISTEM SPELL CHECKER

BAHASA INDONESIA

Oleh

Nama : Alvin Valenciano

NIM : 00000019893

Program Studi : Informatika

Fakultas : Teknik dan Informatika

Tangerang, 22 Juni 2021

Ketua Sidang Dosen Penguji

Moeljono Widjaja, B.Sc., M.Sc., Ph.D. Marlinda Vasty Overbeek, S.Kom., M.Kom.

Dosen Pembimbing I Dosen Pembimbing II

Julio Christian Young, S.Kom., M.Kom. Alethea Suryadibrata, S.Kom., M.Eng.

Mengetahui,

Ketua Program Studi Informatika

Marlinda Vasty Overbeek, S.Kom., M.Kom.

iii

PERNYATAAN TIDAK MELAKUKAN PLAGIAT

Dengan ini saya:


NIM : 00000019893



menyatakan bahwa Skripsi yang berjudul “Implementasi Algoritma Symspell

dan Bayesian Network dalam Pengembangan Sistem Spell Checker Bahasa

Indonesia” ini adalah karya ilmiah saya sendiri, bukan plagiat dari karya ilmiah

yang ditulis oleh orang lain atau lembaga lain, dan semua karya ilmiah orang lain

atau lembaga lain yang dirujuk dalam Skripsi ini telah disebutkan sumber

kutipannya serta dicantumkan di Daftar Pustaka.

Jika di kemudian hari terbukti ditemukan kecurangan / penyimpangan, baik dalam

pelaksanaan Skripsi maupun dalam penulisan laporan Skripsi, saya bersedia

menerima konsekuensi dinyatakan TIDAK LULUS untuk mata kuliah Skripsi yang

telah saya tempuh.

Tangerang, 30 Mei 2021

Alvin Valenciano

iv

PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH

UNTUK KEPENTINGAN AKADEMIS

Sebagai sivitas akademik Universitas Multimedia Nusantara, saya yang bertanda

tangan di bawah ini:


NIM : 00000019893



Jenis Karya : Skripsi

Demi pengembangan ilmu pengetahuan, menyetujui dan memberikan izin kepada

Universitas Multimedia Nusantara hak Bebas Royalti Non-eksklusif (Non-

exclusive Royalty-Free Right) atas karya ilmiah saya yang berjudul:

Implementasi Algoritma Symspell dan Bayesian Network dalam

Pengembangan Sistem Spell Checker Bahasa Indonesia

beserta perangkat yang diperlukan.

Dengan Hak Bebas Royalti Non-eksklusif ini, pihak Universitas Multimedia

Nusantara berhak menyimpan, mengalihmedia atau format-kan, mengelola dalam

bentuk pangkalan data (database), merawat, dan mendistribusi dan menampilkan

atau mempublikasikan karya ilmiah saya di internet atau media lain untuk

kepentingan akademis, tanpa perlu meminta izin dari saya maupun memberikan

royalti kepada saya, selama tetap mencantumkan nama saya sebagai penulis karya

ilmiah tersebut.

Demikian pernyataan ini saya buat dengan sebenarnya untuk dipergunakan

sebagaimana mestinya.

v


Alvin Valenciano

vi

HALAMAN PERSEMBAHAN

Legends Never Die

They Respawn

vii

KATA PENGANTAR

Puji syukur kepada Tuhan Yang Maha Esa atas segala kasih, karunia dan

rahmat-Nya, sehingga penulis dapat menyelesaikan Skripsi dengan baik dan tepat

waktu.

Penulis juga mengucapkan terima kasih kepada:

1. Bapak Dr. Ninok Leksono selaku Rektor Universitas Multimedia Nusantara,

2. Bapak Dr. Eng. Niki Prastomo, S.T., M.Sc. selaku Dekan Fakultas Teknik dan

Informatika Universitas Multimedia Nusantara,

3. Ibu Marlinda Vasty Overbeek, S.Kom., M.Kom. selaku Kepala Program Studi

Informatika Universitas Multimedia Nusantara,

4. Bapak Julio Christian Young, S.Kom., M.Kom., yang telah membimbing

penulis dan memberikan saran selama pembuatan Skripsi, serta mengajar

penulis tata cara menulis karya ilmiah dengan benar,

5. Ibu Alethea Suryadibrata, S.Kom., M.Eng., yang juga telah membimbing

penulis dan memberikan saran selama pembuatan Skripsi,

6. Orang tua penulis atas segala dukungan dan bantuan yang diberikan selama

pengerjaan Skripsi,

7. Teman-teman penulis yang sejak pertama kuliah hingga sekarang yang juga

sama-sama berjuang menyelesaikan studi tingkat sarjana,

8. Semua pihak lain yang tidak dapat disebutkan satu per satu namanya yang telah

tulus dan ikhlas memberikan doa dan dukungan hingga akhirnya penyusunan

laporan Skripsi ini dapat diselesaikan dengan baik.

viii

Semoga Skripsi ini dapat bermanfaat sebagai sumber informasi dan inspirasi bagi

pembaca.


Alvin Valenciano

ix


NETWORK DALAM PENGEMBANGAN SISTEM SPELL

CHECKER BAHASA INDONESIA

ABSTRAK

Perkembangan teknologi yang pesat memungkinkan berita dan buku elektronik

yang diunggah pada situs di internet untuk diakses dan dibaca oleh umum. Tulisan

yang diketik pada berita dan buku elektronik tersebut merupakan hasil ketikan

manusia yang tidak luput dari kesalahan penulisan kata atau typo. Penelitian ini

dilakukan dengan tujuan untuk meminimalisir kesalahan penulisan kata pada suatu

tulisan. Hasil dari penelitian ini ialah sistem pendeteksi dan pengoreksi kesalahan

penulisan kata bahasa Indonesia yang dibuat dalam bentuk aplikasi desktop.

Algoritma yang digunakan antara lain, algoritma Symspell untuk menghasilkan

daftar kandidat kata pengganti untuk setiap kata typo yang terdeteksi oleh sistem

dan Bayesian network untuk menyeleksi kata pengganti yang tepat berdasarkan

frekuensi pasangan dua kata (bigram) yang telah dikumpulkan pada korpus. Sistem

spell checker diuji pada tiga tipe typo (deletion, substitution, dan transposition)

dengan variasi parameter kedalaman pencarian algoritma Symspell (depth search)

dan jumlah daftar kata pengganti (suggestions limit). Kombinasi parameter terbaik

didapat dengan nilai parameter depth search sebesar satu (1) dan nilai parameter

suggestions limit sebesar sepuluh (10) menghasilkan rata-rata akurasi deteksi

sebesar 96,3020% dan rata-rata akurasi koreksi sebesar 82,7056%.

Kata Kunci: Bayesian Network, Dynamic Programming, String Matching,

Symspell, Typography

x

IMPLEMENTATION OF SYMSPELL AND BAYESIAN

NETWORK ALGORITHM FOR DEVELOPING INDONESIAN

SPELL CHECKER SYSTEM

ABSTRACT

Rapid development of technology allows news and electronic books uploaded to

sites on the internet to be accessed and read by people. Writings typed in the news

and electronic books are the result of human typing which is not free from mistyped

words or typos. This research is conducted with purpose of minimizing mistyped

words in those writings. The result of this research is a desktop application which

can detect and correct mistyped Indonesian words. Algorithms used in this research

consists of Symspell algorithm which is used for generating list of candidate words

for each typo word detected by system and Bayesian network algorithm which is

used for selecting the right candidate word among the previous list based on

frequencies of two-word pairs (bigram) that have been collected in the form of

corpus. Spell checker system is tested on three types of typos (deletion, substitution,

and transposition) with variations of Symspell’s depth search parameter and

number of suggestions limit. The best combination of tested parameters is obtained

with depth search parameter value of one (1) and suggestions limit parameter value

of ten (10) resulting in an average detection accuracy of 96,3020% and average

correction accuracy of 82,7056%.

Keywords: Bayesian Network, Dynamic Programming, String Matching, Symspell,

Typography

xi

DAFTAR ISI

HALAMAN JUDUL ................................................................................................ i

LEMBAR PENGESAHAN .................................................................................... ii

PERNYATAAN TIDAK MELAKUKAN PLAGIAT .......................................... iii

PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH ................... iv

HALAMAN PERSEMBAHAN ............................................................................ vi

KATA PENGANTAR .......................................................................................... vii

ABSTRAK ............................................................................................................. ix

ABSTRACT ............................................................................................................ x

DAFTAR ISI .......................................................................................................... xi

DAFTAR GAMBAR ........................................................................................... xiii

DAFTAR TABEL ................................................................................................ xiv

DAFTAR LAMPIRAN ......................................................................................... xv

BAB 1 PENDAHULUAN ...................................................................................... 1

1.1 Latar Belakang Masalah ........................................................................... 1

1.2 Rumusan Masalah .................................................................................... 5

1.3 Batasan Masalah ....................................................................................... 5

1.4 Tujuan Penelitian ...................................................................................... 7

1.5 Manfaat Penelitian .................................................................................... 7

1.6 Sistematika Penulisan ............................................................................... 8

BAB 2 LANDASAN TEORI ................................................................................ 10

2.1 Typographical Error ............................................................................... 10

2.2 Algoritma Symspell ................................................................................ 10

2.3 Bayesian Network .................................................................................. 12

2.4 Optimisasi Dynamic Programming ........................................................ 13

BAB 3 METODOLOGI PENELITIAN DAN PERANCANGAN SISTEM ....... 17

3.1 Metodologi Penelitian ............................................................................ 17

3.2 Perancangan Korpus ............................................................................... 20

3.3 Perancangan Sistem ................................................................................ 21

3.3.1 Flowchart Utama .................................................................................... 21

3.3.2 Flowchart Preprocess Corpus ............................................................... 22

3.3.3 Flowchart Check and Correct Text ...................................................... 24

3.3.4 Flowchart Generate Typo ...................................................................... 26

3.4 Perancangan Antarmuka Pengguna ........................................................ 27

BAB 4 HASIL DAN DISKUSI ............................................................................ 29

4.1 Implementasi Sistem Spell Checker ....................................................... 29

4.1.1 Implementasi Preprocess Corpus ......................................................... 30

4.1.2 Implementasi Check and Correct Text ................................................ 31

4.1.3 Implementasi Generate Typo ................................................................ 35

4.2 Hasil Eksperimen ................................................................................... 38

4.2.1 Data Uji Coba ......................................................................................... 40

4.2.2 Hasil Eksperimen Deletion Typo ......................................................... 41

4.2.3 Hasil Eksperimen Substitution Typo ................................................... 43

4.2.4 Hasil Eksperimen Transposition Typo ................................................ 45

4.3 Evaluasi Hasil Eksperimen ..................................................................... 47

xii

BAB 5 SIMPULAN DAN SARAN ...................................................................... 50

5.1 Simpulan ................................................................................................. 50

5.2 Saran ....................................................................................................... 51

DAFTAR PUSTAKA ........................................................................................... 52

DAFTAR LAMPIRAN ......................................................................................... 54

xiii

DAFTAR GAMBAR

Gambar 3.1 Flowchart prosedur penelitian ........................................................... 19

Gambar 3.2 Flowchart utama sistem spell checker ............................................... 21

Gambar 3.3 Flowchart preprocess corpus ............................................................ 22

Gambar 3.4 Flowchart pengumpulan data ............................................................ 23

Gambar 3.5 Flowchart check and correct text ...................................................... 24

Gambar 3.6 Flowchart generate typo .................................................................... 26

Gambar 4.1 Halaman utama sistem spell checker ................................................ 29

Gambar 4.2 Implementasi algoritma symspell ...................................................... 30

Gambar 4.3 Tampilan antarmuka fitur check and correct text ............................. 31

Gambar 4.4 Implementasi generate suggestion word list ..................................... 32

Gambar 4.5 Tampilan antarmuka konfigurasi parameter ..................................... 33

Gambar 4.6 Implementasi rumus probabilitas dua kata ........................................ 34

Gambar 4.7 Implementasi Bayesian network dan dynamic programming ........... 34

Gambar 4.8 Implementasi konstruksi kalimat terbaik .......................................... 35

Gambar 4.9 Tampilan antarmuka fitur generate typo ........................................... 36

Gambar 4.10 Tampilan antarmuka pengaturan tipe typo ...................................... 36

Gambar 4.11 Implementasi generate typo (Bagian 1) .......................................... 37



Gambar 4.14 Gambar word clouds 30 kata yang paling sering dikoreksi ............ 49

xiv

DAFTAR TABEL

Tabel 2.1 Hasil pendekatan algoritma Symspell ................................................... 11

Tabel 4.1 Tabel jumlah kata typo pada data uji coba ............................................ 41

Tabel 4.2 Tabel rata-rata akurasi deteksi deletion typo ......................................... 41

Tabel 4.3 Tabel rata-rata akurasi koreksi deletion typo ........................................ 42

Tabel 4.4 Tabel rata-rata akurasi deteksi substitution typo ................................... 43

Tabel 4.5 Tabel rata-rata akurasi koreksi substitution typo .................................. 44

Tabel 4.6 Tabel rata-rata akurasi deteksi transposition typo ................................ 45

Tabel 4.7 Tabel rata-rata akurasi koreksi transposition typo ................................ 46

Tabel 4.8 Tabel umum rata-rata akurasi deteksi ................................................... 47

Tabel 4.9 Tabel umum rata-rata akurasi koreksi ................................................... 48

xv

DAFTAR LAMPIRAN

Lampiran 1. Formulir Bimbingan Skripsi (Dosen Pembimbing I) ....................... 54

Lampiran 2. Formulir Bimbingan Skripsi (Dosen Pembimbing II) ...................... 55

Lampiran 3. Gambar summary report pengecekan Turnitin ................................. 56

IMPLEMENTASI ALGORITMA SYMSPELL DAN BAYESIAN …

Documents

Transcript of IMPLEMENTASI ALGORITMA SYMSPELL DAN BAYESIAN …