IMPLEMENTASI ALGORITMA RABIN-KARP UNTUK SISTEM PENDETEKSI KESAMAAN DOKUMEN PROPOSAL TUGAS AKHIR
KOMPETENSI RPL
SKRIPSI
I GEDE WIRA KUSUMA JAYA NIM. 1008605019
LEMBAR JUDUL
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2014 i
IMPLEMENTASI ALGORITMA RABIN-KARP UNTUK SISTEM PENDETEKSI KESAMAAN DOKUMEN PROPOSAL TUGAS AKHIR
KOMPETINSI 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
I GEDE WIRA KUSUMA JAYA NIM. 1008605019
Pembimbing I
Pembimbing II
Ida Bagus Gede Dwidasmara, S.Kom., M.Cs.
Ngurah Agus Sanjaya ER, S.Kom, M.Kom
NIP. 198503152010121007
NIP. 197803212005011001
ii
LEMBAR PENGESAHAN TUGAS AKHIR
Judul
: Implementasi
Algoritma
Rabin-Karp
untuk
Sistem
Pendeteksi Kesamaan Dokumen Proposal Tugas Akhir Kompetensi
: RPL
Nama
: I Gede Wira Kusuma Jaya
NIM
: 1008605019
Tanggal Seminar
: 3 Oktober 2014
Disetujui oleh:
Pembimbing I
Penguji I
Ida Bagus Gede Dwidasmara, S.Kom.,M.Cs NIP. 198503152010121007
Dra. Luh Gede Astuti, M.Kom NIP. 196401141994022001
Pembimbing II
Penguji II
Ngurah Agus Sanjaya ER, S.Kom, M.Kom NIP. 19800616 2005011001
I Made Widiartha, S.Si, M.Kom NIP. 198212202008011008 Penguji III
Ida Bagus Made Mahendra, S.Kom, M.Kom NIP. 198006212008121002 Mengetahui, Jurusan Ilmu Komputer FMIPA UNUD Ketua,
Drs. I Wayan Santiyasa, M.Si NIP. 196704141992031002
iii
Judul
: Implementasi Algoritma Rabin-Karp untuk Sistem Pendeteksi Kesamaan Dokumen Proposal Tugas Akhir
Nama
: I Gede Wira Kusuma Jaya (NIM: 1008605019)
Pembimbing : 1. Ida Bagus Gede Dwidasmara, S.Kom.,M.Cs 2. Ngurah Agus Sanjaya ER, S.Kom., M.Kom
ABSTRAK Plagiarisme adalah penjiplakan atau pengambilan karangan, pendapat, ide atau gagasan dari orang lain dan menjadikannya seolah-olah karangan atau pendapat sendiri. Tindak plagiarisme juga dapat terjadi pada proposal tugas akhir yang dibuat oleh mahasiswa. Untuk mengatasi masalah tersebut, perlu dibuatkan sistem untuk mendeteksi kesamaan dokumen proposal tugas akhir. Algoritma rabin-karp adalah algoritma pencarian kata yang mencari sebuah pola berupa substring dalam sebuah teks menggunakan hashing. Teknik hashing merupakan transformasi aritmatik sebuah string dari karakter menjadi nilai
numerik
yang
merepresentasikan
string
aslinya.
Algoritma
ini
diimplementasikan ke dalam sistem berbasis web pada sistem informasi tugas akhir. Sistem dikembangkan dimulai dari pengumpulan kebutuhan sistem dari pengguna, perancangan dan kemudian implementasi sistem. Sistem yang sudah terimplementasi diuji dengan empat metode pengujian, yakni static testing, black box testing, white box testing dan peformance testing. Uji kinerja dilakukan dengan cara data-data perbandingan ditingkatkan mulai dari 1 data sampai 100 data perbandingan. Berdasarkan pengujian yang dilakukan, didapatkan bahwa implementasi algoritma rabin-karp telah berhasil mendeteksi tingkat kesamaan antar proposal tugas akhir. Waktu yang diperlukan untuk melakukan proses deteksi kesamaan semakin bertambah seiring bertambahnya jumlah data yang digunakan, dimana peningkatan waktu yang terjadi adalah 0,054 detik.
Kata kunci: plagiarisme, rabin-karp, model spiral, pengujian sistem iv
Title
: The Implementation of the Rabin-Karp Algorithm for the Detection System of the Document of the Final Project Proposals
Name
: I Gede Wira Kusuma Jaya (Registration: 1008605019)
First Supervisior : Ida Bagus Gede Dwidasmara, S.Kom.,M.Cs Second Supervisior : Ngurah Agus Sanjaya ER, S.Kom., M.Kom
ABSTRACT Plagiarism is taking the writing, opinions, ideas from other people and make it as if the writing or her own opinion. Acts of plagiarism may also occur in the final project proposal made by the the students. To overcome these problems, the system needs to be made to detect the similarity of the final project proposal document. Rabin-Karp algorithm is a word search algorithm, which search for a panem in the form of a substring in the text using the hashing. Hashing technique is an arithmetic transformation of a character string become numeric value that represents the original string. This algorithm is implemented into a system based on the user system requirements, designing and then implementing the system. The implemented system was tested by four test methods, namely static testing, black box testing, white box testing and performance testing. The performance testing was carried out by means of enhanced comparative data from 1 of data, up to 100 comparative data. Based on the tests performed, it was found that the implementation of rabin-Karp algorithm has successfully detected the degree of similarity between the final project proposals. The time required to perform the similarity detection process is increasing, in line with the increasing amount of data used.
Keywords: plagiarism, rabin-karp, spiral model, system testing
v
KATA PENGANTAR
Puji syukur penulis panjatkan kehadapat Tuhan Yang Maha Esa, karena berkat rahmat dan karunia-Nya, skripsi dengan judul “Implementasi Algoritma Rabin-Karp untuk Sistem Pendeteksi Kesamaan Dokumen Proposal Tugas Akhir” ini dapat diselesaikan tepat pada waktu yang diberikan Secara khusus penulis mengucapkan terima kasih dan penghargaan kepada berbagai pihak yang telah membantu proposal ini, yaitu : 1. Ida Bagus Gede Dwidasmara, S.Kom., M.Cs. sebagai Pembimbing 1 yang telah
bersedia
mengkritisi,
membantu
dan
memeriksa
serta
menyempurnakan skripsi ini. 2. Bapak Ngurah Agus Sanjaya ER, S.Kom., M.Kom. sebagai Pembimbing 2 yang telah bersedia mengkritisi, membantu dan memeriksa serta menyempurnakan skripsi ini. 3. Bapak-bapak dan ibu-ibu dosen di Jurusan Ilmu Komputer yang telah meluangkan waktu turut memberikan saran dan masukan dalam penyempurnaan skripsi ini. 4. Komisi Seminar dan Tugas Akhir Jurusan Ilmu Komputer FMIPA UNUD, yang telah memberikan petunjuk dalam penyusunan skripsi. 5. Teman-teman di Jurusan Ilmu Komputer yang telah memberikan dukungan moral dalam penyelesaian skripsi ini. 6. Semua pihak yang telah memberi dukungan sehingga laporan ini dapat diselesaikan sesuai dengan waktu yang ditentukan. Pada akhirnya penulis berharap agar adanya perbaikan pada skripsi ini mengingat keterbatasan penulis, sehingga sangat diharapkan untuk adanya kritik dan saran yang membangun untuk pencapaian yang lebih baik.
Denpasar, Oktober 2014
Penulis
vi
DAFTAR ISI LEMBAR JUDUL ................................................................................................ i LEMBAR PENGESAHAN TUGAS AKHIR ...................................................... iii ABSTRAK ......................................................................................................... iv KATA PENGANTAR.......................................................................................... vi DAFTAR ISI ..................................................................................................... vii DAFTAR TABEL ............................................................................................... ix DAFTAR GAMBAR ........................................................................................... x BAB I 1PENDAHULUAN .................................................................................. 1 1.1 Latar Belakang ......................................................................................... 1 1.2 Rumusan Masalah .................................................................................... 2 1.3 Tujuan Peneltian ....................................................................................... 2 1.4 Batasan Masalah ....................................................................................... 3 1.5 Manfaat Penelitian .................................................................................... 3 1.6 Metodologi Penelitian............................................................................... 3 1.6.1 Desain Penelitian ............................................................................. 3 1.6.2 Pengumpulan Data .......................................................................... 3 1.6.3 Pengolahan Data Awal ..................................................................... 4 1.6.4 Metode yang Digunakan .................................................................. 4 1.6.5 Eksperimen dan Pengujian Metode .................................................. 5 1.6.6 Evaluasi dan Validasi Hasil .............................................................. 6 BAB II TINJAUAN PUSTAKA........................................................................... 9 2.1 Algoritma Rabin-Karp .............................................................................. 9 2.2 Pengembangan dan Pengujian Perangkat Lunak ..................................... 13 2.2.1 Pengembangan Model Spiral ......................................................... 13 2.2.2 Pengujian Perangkat Lunak ........................................................... 15 2.2.2.1 Strategi Pengujian Dua Dimensi ......................................... 17 2.3 Tinjaun Studi .......................................................................................... 18 BAB III ANALISIS DAN PERANCANGAN SISTEM ..................................... 20 3.1 Pengumpulan Kebutuhan ........................................................................ 20 3.1.2 Kebutuhan Fungsional ................................................................... 20 3.1.2 Kebutuhan Non Fungsional ........................................................... 21 3.2 Perancangan Sistem ................................................................................ 21 3.2.1 Digram ER .................................................................................... 22 3.2.2 Diagram Alir ................................................................................. 23 3.2.2.1 Diagram Alir Preprocessing ............................................... 24 3.2.2.2 Diagram Alir Kesamaan ..................................................... 25 3.2.2.3 Diagram Alir Penandaan .................................................... 26 3.2.3 Diagram Aliran Data...................................................................... 26
vii
3.2.3.1 Context Diagram ................................................................ 27 3.2.3.2 DFD Level 0 ...................................................................... 27 3.2.4 Perancangan Antarmuka ................................................................ 28 BAB IV HASIL DAN PEMBAHASAN ............................................................. 30 4.1 Lingkungan Implementasi ...................................................................... 30 4.2 Implementasi Basis Data ........................................................................ 30 4.2.1 Implementasi Basis Data pada Komputer....................................... 31 4.2.1 Implementasi Basis Data pada Server ............................................ 32 4.3 Implementasi Antarmuka ........................................................................ 34 4.3.1 Antarmuka pada Komputer ............................................................ 34 4.3.2 Antarmuka pada Server ................................................................. 36 4.4 Implementasi Program............................................................................ 40 4.4.1 Implementasi Program pada Komputer .......................................... 40 4.4.2 Implementasi Program pada Server ............................................... 48 4.5 Pengujian ............................................................................................... 51 4.5.1 Static Testing ................................................................................. 51 4.5.2.1 Static Testing (Komputer) .................................................. 52 4.5.2.2 Static Testing (Server) ........................................................ 52 4.5.2 Black Box Testing ......................................................................... 53 4.5.2.1 Black Box Testing (Komputer) ........................................... 53 4.5.2.2 Black Box Testing (Server) ................................................ 55 4.5.3 White Box Testing ......................................................................... 56 4.5.4 Performance Testing ...................................................................... 58 4.5.4.1 Performance Testing (Komputer) ....................................... 59 4.5.4.2 Performance Testing (Server) ............................................. 61 BAB V KESIMPULAN DAN SARAN .............................................................. 64 5.1 Kesimpulan ............................................................................................. 64 5.2 Saran ...................................................................................................... 64 DAFTAR PUSTAKA ......................................................................................... 65
viii
DAFTAR TABEL Tabel 1.1 Rancangan Tabel Pengujian Statis ......................................................... 6 Tabel 1.2 Rancangan Tabel Pengujian Black box.................................................. 7 Tabel 1.3 Rancangan Tabel Uji Dua Dimensi Papan Catur ................................... 8 Tabel 2.1 Hubungan Cyclomatic Complexity dan Resiko (Bray, 1997)................ 16 Tabel 4.1 Static Testing Sistem pada Komputer .................................................. 52 Tabel 4.2 Static Testing Sistem pada Server ....................................................... 52 Tabel 4.3 Black Box Testing Sistem pada Komputer .......................................... 53 Tabel 4.4 Black Box Testing Sistem pada Server ................................................ 55 Tabel 4.5 Waktu Uji Preprocessing Berkas ......................................................... 59 Tabel 4.6 Waktu Uji Pencocokan Kesamaan ....................................................... 60
ix
DAFTAR GAMBAR Gambar 2.1 Diagram Alir Algoritma Rabin-Karp ................................................. 9 Gambar 2.2 Model Spiral Boehm (Sommerville, 2007) ...................................... 14 Gambar 2.3 Strategi Pengujian Papan Catur (Everett, 2007) ............................... 17 Gambar 3.1 Diagram ER Sistem Deteksi Kesamaan ........................................... 22 Gambar 3.2 Diagram Alir Preprocessing ............................................................ 24 Gambar 3.3 Diagram Alir Kesamaan .................................................................. 25 Gambar 3.4 Diagram Alir Penandaan ................................................................. 26 Gambar 3.5 Context Diagram............................................................................. 27 Gambar 3.6 DFD Level 0 ................................................................................... 28 Gambar 3.7 Rancangan Antarmuka Pengajuan Proposal Tugas Akhir ................. 28 Gambar 3.8 Rancangan Antarmuka Hasil Pemeriksaan ...................................... 29 Gambar 3.9 Rancangan Antarmuka Marking ...................................................... 29 Gambar 4.1 Skema Database .............................................................................. 31 Gambar 4.2 Tabel z_proposal_data..................................................................... 31 Gambar 4.3 Tabel z_proposal_kesamaan ............................................................ 32 Gambar 4.4 Tabel z_proposal_kategori .............................................................. 32 Gambar 4.5 Data pada Tabel z_proposal_kategori .............................................. 32 Gambar 4.6 Tabel-tabel Hasil Implementasi di Server ........................................ 33 Gambar 4.7 Tabel zp_kesamaan (pre, deteksi dan kategori) ................................ 33 Gambar 4.8 Implementasi Antarmuka Pengajaun Proposal TA ........................... 34 Gambar 4.9 Antarmuka Awal Proses Deteksi Kesamaan ..................................... 35 Gambar 4.10 Antarmuka Hasil Deteksi Kesamaan ............................................. 35 Gambar 4.11 Antarmuka Notifikasi Kategori Kesamaan..................................... 35 Gambar 4.12 Widget Deteksi Kesamaan (Dosen, KTA dan Mahasiswa) ............. 36 Gambar 4.13 Upload Proposal yang Dilengkapi Preprocessing .......................... 36 Gambar 4.14 Antarmuka Hasil Deteksi Kesamaan ............................................. 37 Gambar 4.15 Antarmuka Informasi Kesamaan Proposal Tugas Akhir ................. 37 Gambar 4.16 Antarmuka Marking Berdasarkan Kalimat .................................... 38 Gambar 4.17 Antarmuka Marking Berdasarkan N-gram ..................................... 38
x
Gambar 4.18 Antarmuka Deteksi Kesamaan untuk Pengguna KTA .................... 39 Gambar 4.19 Antarmuka Hasil Deteksi Kesamaan ............................................. 39 Gambar 4.20 Kode Koneksi ke Database Plagiat ................................................ 40 Gambar 4.21 Kode Pemeriksaan Data Pengajuan Proposal ................................. 41 Gambar 4.22 Kode Baca Jenis Berkas doc ......................................................... 42 Gambar 4.23 Kode Baca Jenis Berkas docx ....................................................... 42 Gambar 4.24 Kode Pembersihan Teks ................................................................ 43 Gambar 4.25 Kode Pemecahan Teks .................................................................. 44 Gambar 4.26 Kode Pemecahan Teks berdasar N-gram ....................................... 44 Gambar 4.27 Kode Hashing Teks ....................................................................... 45 Gambar 4.28 Kode Penyimpanan Data Proposal ke Database ............................. 46 Gambar 4.29 Kode Pengambilan Data dari Dokumen Baru Masuk ..................... 47 Gambar 4.30 Kode Proses Pencocokan Dokumen .............................................. 47 Gambar 4.31 Kode Marking Teks....................................................................... 48 Gambar 4.32 Implementasi Program dalam Bentuk Modul ................................ 48 Gambar 4.33 Kode Form Pencarian Judul Proposal ............................................ 49 Gambar 4.34 Kode Penampilan Data dengan Grid ............................................. 50 Gambar 4.35 Kode Javascript Deteksi Kesamaan ............................................... 51 Gambar 4.36 Flowgraph Preprocessing .............................................................. 56 Gambar 4.37 Flowgraph Deteksi Kesaman......................................................... 57 Gambar 4.38 Flowgraph Penandaan Bagian Teks Sama ..................................... 58 Gambar 4.39 Grafik Hasil Uji Preprocessing Berkas .......................................... 59 Gambar 4.40 Grafik Hasil Uji Pencocokan Kesamaan ........................................ 60 Gambar 4.41 Waktu Deteksi Kesaaman (Stopwatch) .......................................... 61 Gambar 4.42 Waktu Deteksi Kesamaan (Sintak PHP) ........................................ 62 Gambar 4.44 Perbandingan Pengukuran Waktu Deteksi Kesamaan .................... 63
xi
