DETEKSI PLAGIARISME DENGAN ALGORITMA RABIN KARP DAN ALGORITMA KLASTERISASI SUFFIX TREE PADA TEKS DOKUMEN
TUGAS AKHIR Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Oleh :
RIFKY FIRDAUS 09560375
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2013
DETEKSI PLAGIARISME DENGAN ALGORITMA RABIN KARP DAN ALGORITMA KLASTERISASI SUFFIX TREE PADA TEKS DOKUMEN
TUGAS AKHIR Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Oleh :
RIFKY FIRDAUS 09560375
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2013
LEMBAR PERSETUJUAN
DETEKSI PLAGIARISME DENGAN ALGORITMA RABIN KARP DAN ALGORITMA KLASTERISASI SUFFIX TREE PADA TEKS DOKUMEN
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 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.0811.0462
LEMBAR PENGESAHAN DETEKSI PLAGIARISME DENGAN ALGORITMA RABIN KARP DAN ALGORITMA KLASTERISASI SUFFIX TREE PADA TEKS DOKUMEN TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh : RIFKY FIRDAUS 09560375 Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal 25 Oktober 2013
Menyetujui, Penguji I
Penguji II
Ir.M.Irfan, MT NIP : 10892030255
Hariyady, S.Kom, MT NIP : 10194060262
Mengetahui, Ketua Jurusan Teknik Informatika
Eko Budi Cahyono, S.Kom, MT NIP : 10895040330
LEMBAR PERNYATAAN
Yang bertanda tangan dibawah ini : NAMA
: RIFKY FIRDAUS
NIM
: 09560375
FAK/JUR.
: TEKNIK/INFORMATIKA
Dengan ini saya menyatakan bahwa Tugas Akhir dengan judul “DETEKSI
PLAGIARISME DENGAN ALGORITMA RABIN KARP DAN ALGORITMA KLASTERISASI SUFFIX TREE PADA TEKS DOKUMEN” beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain, baik sebagian maupun seluruhnya, kecuali dalam 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.
Mengetahui, Dosen Pembimbing
Malang, 9 Oktober 2013 Yang Membuat Pernyataan
Yuda Munarko,S.Kom,M.Sc NIP : 108.0611.0443
Rifky Firdaus
KATA PENGANTAR
Dengan mengucap puji syukur kehadirat Allah SWT atas segala rahmat dan ridho-Nya yang telah memberikan berkah dan hidayah-Nya sehingga peneliti dapat mneyelesaikan tugas akhir yang berjudul : “DETEKSI PLAGIARISME DENGAN ALGORITMA RABIN KARP DAN ALGORITMA KLASTERISASI SUFFIX TREE PADA TEKS DOKUMEN” Di dalam tulisan ini disajikan pokok – pokok bahasan yang meliputi latar belakang penelitian, landasan teori penelitian, analisa dan perancangan aplikasi, implementasi dan pengujian aplikasi, kesimpulan dan saran serta daftar pustaka. Peneliti menyadari sepenuhnya bahwa dalam penulisan tugas akhir ini masih banyak kekurangan dan keterbatasan. Oleh karena itu peneliti mengharapkan saran yang membangun agar tulisan ini bermanfaat bagi perkembangan ilmu pengetahuan kedepan.
Malang, 9 Oktober 2013
Rifky Firdaus
iv
DAFTAR ISI Halaman ABSTRAK ............................................................................................................. i ABSTRACT ........................................................................................................... ii LEMBAR PERSEMBAHAN ............................................................................. iii KATA PENGANTAR ......................................................................................... iv DAFTAR ISI ........................................................................................................ v DAFTAR GAMBAR ......................................................................................... viii DAFTAR TABEL ................................................................................................ x DAFTAR GRAFIK ............................................................................................. xi BAB I PENDAHULUAN ..................................................................................... 1 1.1. Latar Belakang ............................................................................................. 1 1.2. Rumusan Masalah ........................................................................................ 2 1.3. Batasan Masalah ........................................................................................... 2 1.4. Tujuan ........................................................................................................... 3 1.5. Metodologi Penelitian .................................................................................. 3 1.6. Sistematika Penulisan ................................................................................... 5 BAB II DASAR TEORI ....................................................................................... 6 2.1. Plagiarisme .................................................................................................. 6 2.1.1. Pengertian Plagiarisme ......................................................................... 6 2.1.2. Metode Pendeteksi Plagiarisme ............................................................ 6 2.2. Algoritma Plagiarisme .................................................................................. 7 2.2.1. Perbandingan Algoritma ........................................................................ 7 2.2.2. Algoritma Rabin Karp ........................................................................... 9 2.3. Teks Mining ............................................................................................... 13 2.3.1. Pengertian Teks Mining ....................................................................... 13 2.3.2. Koleksi Dokumen ................................................................................ 14 2.3.3. Respresentasi Fitur pada Dokumen ..................................................... 14 2.3.4. Teks Preprocessing .............................................................................. 14 2.3.5. Ekstrasi Dokumen ................................................................................ 15 2.3.2. Kategori Teks ....................................................................................... 17
v
2.4. Klasterisasi ................................................................................................ 17 2.4.1. Pengertian Klasterisasi ......................................................................... 17 2.4.2. Perbandingan Algoritma Klasterisasi .................................................. 18 2.4.3. Algoritma Klasterisasi Suffix Tree ...................................................... 19 2.5. Tabel ASCII .............................................................................................. 24 BAB III ANALISA DAN PERANCANGAN SISTEM ................................... 25 3.1. Analisis ....................................................................................................... 25 3.1.1. Analisis Kebutuhan .............................................................................. 25 3.1.1.1. Analisis Kebutuhan User............................................................... 25 3.1.1.2. Use Case ....................................................................................... 25 3.1.1.3. Activity Diagram ........................................................................... 28 3.1.1.4. Sequence Diagram ........................................................................ 30 3.1.1.5. Class Diagram .............................................................................. 33 3.2. Perancangan ................................................................................................ 34 3.2.1. Perancangan Database......................................................................... 34 3.2.1.1. Tabel Abaikan_Char ..................................................................... 34 3.2.1.2. Tabel Stopword ............................................................................. 34 3.2.1.3. Tabel Dokumen Abstrak ............................................................... 35 3.2.1.4. Tabel Kata Dasar ........................................................................... 35 3.2.2. Perancangan Desain Sistem ................................................................. 36 3.2.3. Perancangan Antar Muka..................................................................... 36 3.2.3.1. Desain Antarmuka Menu Utama ................................................... 36 3.2.3.2. Desain Antarmuka Memasukkan Teks Dokumen......................... 37 BAB IV IMPLEMENTASI DAN PENGUJIAN .............................................. 38 4.1. Implementasi .............................................................................................. 38 4.1.1. Spesifikasi Kebutuhan Hardware dan Software .................................. 38 4.1.2. Implementasi Sistem ............................................................................ 38 4.1.2.1. Pembuatan Fungsi Koneksi Database .......................................... 39 4.1.2.2. Menu Memasukkan Teks Dokumen ............................................. 39 4.1.2.3. Menu Deteksi Plagiarisme ............................................................ 40 4.1.2.4. Menu Bantuan ............................................................................... 41 4.1.2.5. Menu Tentang ............................................................................... 42
vi
4.1.2.6. Kode Program Algoritma Klasterisasi Suffix Tree ....................... 42 4.1.2.7. Kode Program Algoritma Rabin Karp .......................................... 44 4.1.3. Implementasi Database ....................................................................... 46 4.1.3.1. Pembuatan Database..................................................................... 47 4.1.3.2. Pembuatan Tabel "abaikan_char" ................................................ 47 4.1.3.3. Pembuatan Tabel "dokumen_abstrak" .......................................... 47 4.1.3.4. Pembuatan Tabel "stopword" ........................................................ 48 4.1.3.5. Pembuatan Tabel "tb_katadasar" .................................................. 48 4.2. Pengujian Fungsionalitas Sistem ................................................................ 48 4.2.1. Pengujian Memasukkan Teks Dokumen ............................................. 49 4.2.2. Pengujian Simpan Teks Dokumen ....................................................... 49 4.2.3. Pengujian Hapus Teks Dokumen ......................................................... 50 4.2.4. Pengujian Klasterisasi .......................................................................... 50 4.2.5. Pengujian Memilih Teks Dokumen Hasil Klasterisasi ........................ 51 4.2.6. Pengujian Deteksi Plagiarisme ............................................................ 52 4.2.7. Pengujian Algoritma Klasterisasi Suffix Tree ..................................... 52 4.2.7.1. Pengujian Klasterisasi 1 ................................................................ 54 4.2.7.2. Pengujian Klasterisasi 2 ............................................................... 54 4.2.7.3. Pengujian Klasterisasi 3 ................................................................ 55 4.2.8. Pengujian Algoritma Rabin Karp ........................................................ 55 4.2.8.1. Pengujian Plagiarisme 1 ................................................................ 56 4.2.8.2. Pengujian Plagiarisme 2 ............................................................... 58 4.2.8.3. Pengujian Plagiarisme 3 ................................................................ 60 4.2.9. Analisis ................................................................................................ 61 4.2.9.1. Analisis Hasil Sistem Fungsionalitas ............................................ 61 4.2.9.2. Analisis Pengujian Klasterisasi .................................................... 61 4.2.9.3. Analisis Pengujian Plagiarisme .................................................... 62 BAB V KESIMPULAN DAN SARAN .............................................................. 65 5.1. Kesimpulan ................................................................................................. 65 5.2. Saran ........................................................................................................... 65 DAFTAR PUSTAKA ........................................................................................ 66
vii
DAFTAR GAMBAR
Halaman Gambar 2.1. Metode Pendeteksi Plagiarisme ........................................................ 6 Gambar 2.2. Flowchart Algoritma Rabin Karp ..................................................... 9 Gambar 2.3. Tahapan Ekstrasi Dokumen ............................................................ 15 Gambar 2.4. Tokenizing ........................................................................................ 16 Gambar 2.5. Filtering .......................................................................................... 16 Gambar 2.6. Stemming ......................................................................................... 17 Gambar 2.7. Algoritma Klasterisasi Suffix Tree ................................................. 19 Gambar 3.1. Use Case Diagram .......................................................................... 26 Gambar 3.2. Activity Diagram User Memasukkan Teks Dokumen Baru ............ 29 Gambar 3.3. Activity Diagram User Mengklasterisasi Teks Dokumen ............... 29 Gambar 3.4. Activity Diagram User Mendeteksi Plagiarisme .............................. 30 Gambar 3.5. Activity Diagram User Mendapatkan Informasi .............................. 30 Gambar 3.6. Sequence Diagram Memasukan Dokumen ...................................... 31 Gambar 3.7. Sequence Diagram Mengklasterisasi Dokumen .............................. 31 Gambar 3.8. Sequence Diagram Mendeteksi Plagiarisme .................................... 32 Gambar 3.9. Sequence Diagram Melihat Informasi ............................................. 32 Gambar 3.10. Class Diagram Deteksi Plagiarisme .............................................. 33 Gambar 3.11. Struktur Tabel dan Relasi antar Tabel ............................................ 34 Gambar 3.12. Deskripsi Umum Sistem................................................................. 36 Gambar 3.13. Desain Antar Muka Menu Utama .................................................. 36 Gambar 3.14. Desain Antar Muka Memasukkan Teks Dokumen ........................ 37 Gambar 4.1. Potongan Kode Koneksi Database ................................................... 39 Gambar 4.2. Tampilan Menu Memasukkan Teks Dokumen ................................ 39 Gambar 4.3. Potongan Kode Program Pilih Teks Dokumen ................................ 40 Gambar 4.4. Potongan Kode Program Simpan Teks Dokumen............................ 40 Gambar 4.5. Tampilan Menu Deteksi Plagiarisme ............................................... 40 Gambar 4.6. Potongan Kode Program Klasterisasi ............................................... 41 Gambar 4.7. Potongan Kode Program Penghitungan Tingkat Kemiripan ............ 41 Gambar 4.8. Tampilan Menu Bantuan .................................................................. 42
viii
Gambar 4.9. Tampilan Menu Tentang .................................................................. 42 Gambar 4.10. Potongan Kode Program Algoritma Kalsterisasi ........................... 43 Gambar 4.11. Potongan Kode Program Stemming................................................ 43 Gambar 4.12. Potongan Kode Program Stopword ................................................ 44 Gambar 4.13. Potongan Kode Program Abaikan Karakter ................................... 44 Gambar 4.14. Potongan Kode Program Tokenizing .............................................. 44 Gambar 4.15. Potongan Kode Program K-Gram ................................................. 45 Gambar 4.16. Potongan Kode Program Konversi Ascii dan Penghitungan Hash 45 Gambar 4.17. Potongan Kode Program Pengelompokan Nilai Hashing ............. 46 Gambar 4.18. Potongan Kode Program Hitung Jumlah Nilai Hashing ................ 46 Gambar 4.19. Data Tabel MySQL ........................................................................ 46 Gambar 4.20. Query Untuk Membuat Database “Kalsterisasi” ............................ 47 Gambar 4.21. Query Untuk Membuat Tabel “Abaikan_Char”............................. 47 Gambar 4.22. Query Untuk Membuat Tabel “Dokumen_Abstrak” ..................... 48 Gambar 4.23. Query Untuk Membuat Tabel “Stopword” .................................... 48 Gambar 4.24. Query Untuk Membuat Tabel “Tb_Katadasar” ............................. 48 Gambar 4.25. Pengujian Menu Pilih Teks Dokumen ........................................... 49 Gambar 4.26. Pengujian Simpan Teks Dokumen ................................................. 50 Gambar 4.27. Pengujian Hapus Teks Dokumen ................................................... 50 Gambar 4.28. Pengujian Klasterisasi .................................................................... 51 Gambar 4.29. Pengujian Pilih Teks Dokumen Hasil Klasterisasi ......................... 51 Gambar 4.30. Pengujian Deteksi Plagiarisme ....................................................... 52
ix
DAFTAR TABEL
Halaman Tabel 2.1. Pemotongan Teks Menggunakan K-Gram........................................... 10 Tabel 2.2. Penghitungan Nilai Hash ..................................................................... 11 Tabel 2.3. Pencocokan Nilai Hashing No 1 .......................................................... 12 Tabel 2.4. Pencocokan Nilai Hashing No 6 .......................................................... 12 Tabel 2.5. Hasil Pencarian Dengan Kata Kunci “Deteksi Plagiat” ....................... 21 Tabel 2.6. Penghitungan Score Cluster ................................................................. 22 Tabel 2.7. Tabel ASCII ......................................................................................... 24 Tabel 3.1. Skenario Memasukkan Teks Dokumen Baru....................................... 26 Tabel 3.2. Skenario Melihat Hasil Klasterisasi ..................................................... 27 Tabel 3.3. Skenario Skenario Mengatur Parameter .............................................. 28 Tabel 3.4. Skenario Melihat Informasi ................................................................. 28 Tabel 3.5. Struktur Tabel Abaikan_Char .............................................................. 34 Tabel 3.6. Struktur Tabel Stopword ...................................................................... 35 Tabel 3.7. Struktur Tabel Dokumen Abstrak ........................................................ 35 Tabel 3.8. Struktur Tabel Kata_Dasar................................................................... 35 Tabel 4.1. Sample Teks Dokumen ........................................................................ 52 Tabel 4.2. Pengujian Klasterisasi 1 ....................................................................... 54 Tabel 4.3. Pengujian Klasterisasi 2 ....................................................................... 55 Tabel 4.4. Pengujian Klasterisasi 3 ....................................................................... 55 Tabel 4.5. Pengujian Plagiarisme 1 ....................................................................... 57 Tabel 4.6. Pengujian Plagiarisme 2 ....................................................................... 59 Tabel 4.7. Pengujian Plagiarisme 3 ....................................................................... 60 Tabel 4.8. Analisis Hasil Pengujian Sistem .......................................................... 61 Tabel 4.9. Tabel Relevansi Klaster Terhadap Dokumen Uji ................................ 62
x
DAFTAR GRAFIK
Halaman Grafik 4.1. Pengujian Plagiarisme 1 ..................................................................... 63 Grafik 4.2. Pengujian Plagiarisme 2 ..................................................................... 63 Grafik 4.3. Pengujian Plagiarisme 3 ..................................................................... 64
xi
DAFTAR PUSTAKA
[1] Arief Soendjoto, Mochamad.2013. Plagiarisme, Kesalahan Berbahasa Tulis, Dan Penanggulangannya.http://www.dikti.go.id/?p=8281&lang=id. Diakses tanggal 20 Agustus 2013 [2] Widi,
Tia
Septiana.
2012.Metode
Pendeteksi
Plagiarisme.
http://goo.gl/hiCCGl. diakses tanggal 23 Agustus 2013
[3] Atmopawiro, Alsasian. 2007. Pengkajian Dan Analisis Tiga Algoritma Efisien Rabin-Karp, Knuth-Morris-Pratt, Dan Boyer-Moore Dalam Pencarian Pola Dalam Suatu Teks. Program Studi Teknik Informatika ITB. Bandung [4] Andres, Nicolas;
Christopher;
Saloko,
Hadi. 2007. Penelaahan
Algoritma Rabin-Karp dan Perbandingan Prosesnya dengan Algoritma Knut-Morris-Pratt.
Laboratorium
Ilmu
dan
Rekayasa
Komputasi,
Departemen Teknik Informatika, ITB, Bandung [5] Triawati, Chandra. 2009 . Metode Pembobotan Statistical Concept Based untuk Klastering dan Kategorisasi Dokumen Berbahasa Indonesia . Institut Teknologi Telkom. Bandung. [6] Zainal, Arifin Agus. 2008. Klasifikasi Online Dokumen Berita Dengan Menggunakan Algoritma Suffix Tree Clustering. Program Teknik Informatika, Institut Teknologi Sepuluh November, Surabaya [7] Pitaloka
Novialita.2009.
Pengelompokan
Data
Menggunakan
Hierarchical Clustering (AHC).Institut Teknologi Telkom. Bandung. [8] Rahman, Deddy.2010. Perbandingan performansi algoritma k-means dengan algoritma suffix tree clustering dalam pengelompokan berita berbahasa indonesia. Institut Teknologi Telkom. Bandung. [9] Kusmaya.2007. Pengembangan suffix tree clustering untuk comparative text mining.Program Teknik Elektro, ITB, Bandung.
66
