Aplikasi Pendeteksi Duplikasi Dokumen Teks Bahasa Indonesia Menggunakan Algoritma Winnowing Dengan Metode K-Gram Dan Synonym Recognition Mudafiq Riyan Pratama1, Eko Budi Cahyono 2, Gita Indah Marthasari3 Jurusan Teknik Informatika Universitas Muhammadiyah Malang 1
[email protected],
[email protected],
[email protected]
Abstract The practice of document plagiarism is often applied by both academics in school and university level which does not reflect the attitude of a highly creative and educated as intellectuals. Sometimes the act of plagiarism was modified by replacing the words that contain synonyms, with the intention that looks different from the original article. Duplication detection system uses an winnowing algorithm which its output in the form of a set of hash values as a document fingerprinting obtained through the method of k-grams. Input from document fingerprinting process is a text file. Then its output will be a set of hash value, called a fingerprint. Fingerprint is what will be the basis of a comparison between the text files that have been entered. The existence of the concept synonym recognition is intended to be able to recognize words that contain synonyms as an act of plagiarism. Detecting duplicate using synonyms get a higher percentage than without using synonyms. Keywords: plagiarism, document fingerprinting, winnowing algorithm, k-grams, synonym recognition
1. Pendahuluan Pemanfaatan teknologi digital telah menjadi kebutuhan dalam era modern saat ini. Komponen yang ada di dalam dunia digital salah satunya adalah dokumen teks. Dokumen dalam bentuk digital memudahkan dalam hal penyimpanan, efisien, mudah dicari, bahkan mudah dalam hal penjiplakan. Penjiplakan atau plagiarisme berarti mencontoh atau meniru atau mencuri tulisan dan karya orang lain yang kemudian diakui sebagai karangannya sendiri dengan ataupun tanpa seizin penulisnya. Penjiplakan dokumen digital bukanlah hal yang susah, cukup dengan menggunakan teknik copy-paste-modify pada sebagian isi dokumen dan bahkan keseluruhan isi dokumen sudah bisa dikatakan bahwa dokumen tersebut merupakan hasil duplikasi dari dokumen lain. Praktek penjiplakan dokumen ini seringkali diterapkan oleh akademisi baik tingkat sekolah maupun perguruan tinggi. Tindakan plagiat yang dilakukan oleh siswa maupun mahasiswa ini sangat tidak mencerminkan sikap kreatif dan terpelajar sebagai kaum intelektual. Demi menyelesaikan tugastugasnya dengan cepat, siswa maupun mahasiswa dapat melakukan teknik copy-paste-modify tanpa perlu mempelajari dan mengeksplorasi materi terlebih dahulu. Kadangkala tindak penjiplakan ini dimodifikasi dengan mengganti kata-kata yang mengandung sinonim, dengan maksud agar terlihat berbeda dari pekerjaan teman. Hal semacam ini dapat menimbulkan masalah terhadap evaluasi hasil belajar siswa/mahasiswa. Proses pendeteksian penjiplakan ini menggunakan algoritma Winnowing yang mana
output-nya berupa sekumpulan nilai hash yang didapatkan melalui metode k-gram. Sedangkan konsep synonym recognition ini dimaksudkan untuk dapat mengenali kata-kata yang mengandung sinonim sebagai tindak penjiplakan.
2. Metode Deteksi Duplikasi Banyak cara atau metode yang dapat digunakan untuk mendeteksi penjiplakan dalam file text. Namun ada kebutuhan mendasar yang harus dipenuhi oleh algoritma deteksi penjiplakan[5], yaitu: Whitespace Insensitivity yang berarti dalam melakukan pencocokan terhadap file teks seharusnya tidak terpengaruh oleh spasi, jenis huruf (kapital atau normal), tanda baca dan sebagainya. Noise Surpression yang berarti menghindari penemuan kecocokan dengan panjang kata yang terlalu kecil atau kurang relevan, misal: „the‟. Panjang kata yang ditengarai merupakan penjiplakan harus cukup untuk membuktikan bahwa kata-kata tersebut telah dijiplak dan bukan merupakan kata yang umum digunakan. Position Independence yang berarti penemuan kecocokan/kesamaan harus tidak bergantung pada posisi kata-kata. Meskipun posisnya tidak sama, kecocokan harus dapat ditemukan. Sebuah karya tulis dikatakan telah menjiplak karya lain apabila memiliki tingkat kesamaan yang melebihi batas toleransi tertentu yang telah ditentukan.
Algoritma Winnowing Winnowing adalah algoritma yang digunakan untuk melakukan proses document fingerprinting [5]. Proses ini ditujukan agar dapat mengidentifikasi penjiplakan, termasuk bagian-bagian kecil yang mirip dalam dokumen yang berjumlah banyak. Input dari proses document fingerprinting adalah file teks. Kemudian output-nya akan berupa sekumpulan nilai hash yang disebut fingerprint. Fingerprint inilah yang akan dijadikan dasar pembanding antara file-file teks yang telah dimasukkan [5]. Salah satu prasyarat dari algoritma deteksi penjiplakan adalah whitespace insensitivity, dan algoritma Winnowing telah memenuhi prasyarat tersebut yaitu membuang seluruh karakter-karakter yang tidak relevan seperti: tanda baca, spasi dan juga karakter lain, sehingga nantinya hanya karakterkarakter yang berupa huruf atau angka yang akan diproses lebih lanjut [5]. Secara garis besar, berikut konsep algoritma Winnowing bekerja: (1) Penghapusan karakter-karakter yang tidak relevan (whitespace insensitivity). (2) Pembentukan rangkaian gram dengan ukuran k. (3) Penghitungan nilai hash. (4) Membagi ke dalam window tertentu. (5) Pemilihan beberapa nilai hash menjadi document fingerprinting. Berikut contoh implementasi algoritma Winnowing dalam melakukan proses document fingerprinting pada teks “Komputer adalah alat yang dipakai untuk mengolah data”: 1) Melakukan proses whitespace insensitivity, sehingga hal yang mengandung huruf kapital dijadikan ignore case, tanda baca, spasi, dan karakter-karakter yang tidak relevan lainnya dibuang. Sehingga dari kalimatnya diubah menjadi: komputeradalahalatyangdipakaiuntukmengolahdat a 2) Setelah kalimat tersebut dibersihkan, pembentukan rangkaian gram dengan ukuran 7-gram menjadi: kompute omputer mputera puterad uterada teradal eradala radalah adalaha dalahal alahala lahalat ahalaty halatya alatyan latyang atyangd tyangdi yangdip angdipa ngdipak gdipaka dipakai ipakaiu pakaiun akaiunt kaiuntu aiuntuk iuntukm untukme ntukmen tukmeng ukmengo kmengol mengola engolah ngolahd golahda olahdat lahdata 3) Penghitungan nilai-nilai hash dari setiap gram (sebuah hipotesis nilai hash yang muncul):
2180, 2211, 2412, 1214, 2432, 2643, 2222, 1243, 1543, 1632, 1632, 1444, 1234, 1523, 1132, 1161, 1453, 1121, 2412, 2112, 1254, 1612, 3245, 1235, 1083, 1208, 1802, 1902, 1309, 2309, 1459, 1092, 1280, 1902, 2839, 1218, 1682, 1562, 1717, 1828 4) Untuk memilih hasil yang telah di hash, dilakukan dengan membagi ke window w dengan panjang 4. Kemudian pilih nilai yang minimum. [2180, 2211, 2412, 1214] [2211, 2412, 1214, 2432] [2412, 1214, 2432, 2643] [1214, 2432, 2643, 2222] [2432, 2643, 2222, 1243] [2643, 2222, 1243, 1543] [2222, 1243, 1543, 1632] [1243, 1543, 1632, 1632] [1543, 1632, 1632, 1444] [1632, 1632, 1444, 1234] [1632, 1444, 1234, 1523] [1444, 1234, 1523, 1132] [1234, 1523, 1132, 1161] [1523, 1132, 1161, 1453] [1132, 1161, 1453, 1121] [1161, 1453, 1121, 2412] [1453, 1121, 2412, 2112] [1121, 2412, 2112, 1254] [2412, 2112, 1254, 1612] [2112, 1254, 1612, 3245] [1254, 1612, 3245, 1235] [1612, 3245, 1235, 1083] [3245, 1235, 1083, 1208] [1235, 1083, 1208, 1802] [1083, 1208, 1802, 1902] [1208, 1802, 1902, 1309] [1802, 1902, 1309, 2309] [1902, 1309, 2309, 1459] [1309, 2309, 1459, 1092] [2309, 1459, 1092, 1280] [1459, 1092, 1280, 1902] [1092, 1280, 1902, 2839] [1280, 1902, 2839, 1218] [1902, 2839, 1218, 1682] [2839, 1218, 1682, 1562] [1218, 1682, 1562, 1717] [1682, 1562, 1717, 1828] 5) Setelah itu memilih nilai hash yang paling minimum yang telah dibagi menjadi window dengan urutan nilai index array secara berkelanjutan. Berikut dengan penambahan informasi posisi fingerprint di dalam dokumen. Hasilnya adalah sebagai berikut: [1214, 3] [1243, 7] [1444, 11] [1234, 12] [1132, 14] [1121, 17] [1254, 20] [1235, 23] [1083, 24] [1208, 25] [1309, 28] [1092, 31] [1218, 35] [1562, 37]
Hashing Hashing adalah suatu cara untuk mentransformasi sebuah string menjadi suatu nilai yang unik dengan panjang tertentu (fixed-length) yang berfungsi sebagai penanda string tersebut. Fungsi untuk menghasilkan nilai ini disebut fungsi hash, sedangkan nilai yang dihasilkan disebut nilai hash. Contoh sederhana hashing adalah [7]: Firdaus, Hari Munir, Rinaldi Rabin, Michael Karp, Richard Menjadi 7864 = Firdaus, Hari 9802 = Munir, Rinaldi 1990 = Rabin, Michael 8822 = Karp, Richard
Synonym Recognition Synonym Recognition atau pengenalan sinonim adalah pendeteksian plagiarisme melalui pendekatan sinonim. Dalam hal ini dokumen satu dibandingkan dengan dokumen lain dengan mendeteksi kata-kata yang mengandung sinonim sehingga tingkat kesamaan dapat dikatakan lebih akurat. start
Isi database kamus sinonim
Input beberapa dokumen
Contoh di atas adalah penggunaan hashing dalam pencarian pada database. Apabila tidak di-hash, pencarian akan dilakukan karakter-per-karakter pada nama-nama yang panjangnya bervariasi dan ada 26 kemungkinan pada setiap karakter. Namun pencarian akan menjadi lebih efisien setelah di-hash karena kemungkinan setiap angka berbeda. Nilai hash pada umumnya digambarkan sebagai fingerprint yaitu string pendek yang terdiri atas huruf dan angka yang terlihat acak (data biner yang ditulis dalam heksadesimal) [7].
Scan isi database kamus sinonim dengan isi dokumen
Apakah isi dokumen terdapat pada database kamus sinonim?
yes
Rolling Hash Fungsi yang digunakan untuk menghasilkan nilai hash dari rangkaian gram dalam algoritma winnowing adalah rolling hash [5]. Fungsi hash H(c1...ck) didefinisikan sebagai berikut [2]:
no Ubah seluruh dokumen berdasarkan sinonim
return dokumen
Rumus 1. Formula rolling hash Keterangan: c : nilai ascii karakter b : basis (bilangan prima) k : banyak karakter Keuntungan dari rolling hash adalah untuk nilai hash berikutnya H(c2...ck+1) dapat dilakukan dengan cara:
Rumus 2. Formula unuk mencari nilah hash ke-2 sampai ke-n Dengan begitu tidak perlu melakukan iterasi dari indeks pertama sampai terakhir untuk menghitung nilai hash untuk gram ke-2 sampai terakhir. Hal ini tentu dapat menghemat biaya komputasi saat menghitung nilai hash dari sebuah gram [5].
end
Gambar 1. Flowchart synonym recognition Pada proses pencocokan sinonim, kaitannya antara isi dokumen dengan kamus sinonim yang terdapat pada database. Jika kata tidak tersedia pada kamus sinonim, maka tidak akan melakukan proses synonym recognition. Seluruh isi dokumen akan discan dan dicocokkan dengan kata yang ada dalam kamus, kemudian akan diubah berdasarkan isi kamus sinonim tersebut. 3. Hasil dan Pembahasan Pada tahap ini, perancangan perangkat lunak direalisasikan sebagai serangkaian program atau unit program dengan melakukan beberapa pengujian terhadap fungsi-fungsi yang dimiliki oleh sistem, performa dari sistem maupun dari algoritma yang digunakan.
Pengujian Synonym Recognition Pengujian kinerja sistem untuk synonym recognition dengan kalimat “komputer adalah alat yang dipakai untuk mengolah data”. Dan hasil pendeteksian sinonimnya adalah sebagai berikut: adalah = merupakan dipakai = digunakan Kata yang mengandung “adalah” akan di gantikan dengan kata “merupakan”, sedangkan kata “dipakai” akan diganti dengan kata “digunakan”. Sehingga kalimat yang semula “komputer adalah alat yang dipakai untuk mengolah data” diganti dengan kata “komputer merupakan alat yang digunakan untuk mengolah data”. Pengujian Similarity Threshold 1. Pengujian Pada Laporan Praktikum Hasil Deteksi Sistem Secara Penuh dan Parsial Dokumen Pada pengujian pembandingan dokumen ini dilakukan pada 2 dokumen laporan praktikum. Secara kualitatif, 2 dokumen berikut ini dianggap sebagai dokumen hasil copy-paste atau duplikasi. Dan berikut hasil pendeteksian menggunakan sistem yang dibuat pada Tugas Akhir ini.
deteksi dengan menggunakan fungsi synonym recognition. Tabel 2. Hasil Pembandingan Dengan dan Tanpa Synonym Recognition Similarity Similarity File 1 File 2 Tanpa Dengan Sinonim Sinonim 08560124_ 08560130_ 08560047.doc 27.58 % 28.43 % 08560137_ 08560161.doc 08560129_ 08560047.doc 08560155_ 26.75 % 27.42 % E.BISNIS.doc 08560140_ 08560261_ 08560047.doc 26.93 % 27.87 % 08560267 _ 08560203.doc Dari hasil pembandingan tersebut dapat diketahui bahwa hasil similarity dengan menggunakan sinonim lebih besar daripada similarity tanpa sinonim. 2. Pengujian Pada Artikel Terdapat dua dokumen yang isinya adalah sebagai berikut:
Tabel 1. Perbandingan Similarity 2 Dokumen Secara Penuh File 1 File 2 Similarity ebusiness4_ ebusiness4_ 88.78 % 08560264.pdf 07560276.pdf Dikarenakan pada laporan praktikum semua isi bab 1 sampai bab 3 pada dasarnya sama, sehingga dilakukan pengubahan isi dokumen dengan mengambil isi dari bab 4 dan bab 5 antara kedua dokumen tersebut. Dan berikut hasil persentase perbandingannya. Tabel 4.2 Perbandingan Similarity 2 Dokumen Secara Parsial File 1 File 2 Similarity ebusiness4_ ebusiness4_ 085602640756027699.01 % parsial.pdf parsial.pdf Didapatkan bahwa similarity threshold dari kedua dokumen tersebut mendekati 100% yaitu 99.00528% dan dapat dinyatakan bahwa kedua dokumen tersebut telah terduplikasi. Hasil Deteksi Dengan dan Tanpa Synonym Recognition Pada pengujian ini dilakukan pada dokumen yang sama dengan 2 kali pembandingan, yaitu pembandingan hasil deteksi tanpa menggunakan fungsi synonym recognition dan pembandingan hasil
Gambar 2. Dokumen Artikel Komputer 1
Gambar 3. Dokumen Artikel Komputer 2 Pada gambar dokumen artikel komputer 1 dan artikel komputer 2 terdapat cetak tebal yang menunjukkan bahwa kata tersebut mengandung sinonim. Pada dokumen tersebut memang dibuat untuk mendeteksi kinerja synonym recognition pada sistem yang telah dibuat dapat bekerja secara maksimal. Berikut hasil deteksi sistem: Tabel 3. Hasil Deteksi Dokumen Artikel Tanpa Synonym Recognition Similarity Tanpa File 1 File 2 Sinonim [doc] Artikel [doc] Artikel 84.13 % komputer 1 komputer 2
Tabel 4. Hasil Deteksi Dokumen Artikel Dengan Synonym Recognition Similarity Dengan File 1 File 2 Sinonim [doc] Artikel [doc] Artikel 100 % komputer 1 komputer 2 Pada pengujian di atas terdapat perubahan yang signifikan antara tanpa sinonim dan dengan sinonim. Sehingga kinerja synonym recognition pada sistem ini dapat bekerja maksimal.
4. Simpulan dan Saran Dari hasil pengamatan mulai tahap analisis, perancangan, implementasi, dan uji coba, dapat diambil beberapa kesimpulan sebagai berikut: 1. Pencarian menggunakan teknik hashing akan menjadi lebih efisien daripada pencarian karakterper-karakter pada nama-nama yang panjangnya bervariasi. 2. Tindak penjiplakan dapat dilakukan dengan modify yang mana dengan mengubah beberapa bagian bahkan keseluruhan, yaitu dengan mengubah katakata dengan sinonim. 3. Mendeteksi duplikasi menggunakan sinonim mendapatkan hasil persentase yang lebih tinggi daripada tanpa menggunakan sinonim. 4. Sistem yang dibangun telah dapat mendeteksi duplikasi dengan pendekatan sinonim dengan perbedaan ± 0.82 % lebih besar menggunakan synonym recognition daripada tanpa synonym recognition. 5. Jika dengan menggunakan metode kualitatif dalam menganalisa dokumen kemudian dihasilkan sebuah simpulan bahwa dokumen tersebut merupakan hasil penjiplakan, maka begitu halnya analisa dokumen secara kuantitatif pada aplikasi akan menghasilkan simpulan yang sama seperti halnya metode kualitatif. 6. Pada dokumen yang dinyatakan telah terduplikasi, pendeteksian secara full dokumen (bab 1 sampai bab 5) dan parsial dokumen (bab 4 dan bab 5) akan mengalami peningkatan persentase ± 10 %. Sedangkan pada dokumen yang dinyatakan tidak terduplikasi, pendeteksian secara full dokumen maupun parsial dokumen akan secara otomatis mengalami penurunan persentase kemiripan ± 4.67 %. 7. Dokumen dinyatakan terduplikasi jika persentase kemiripannya diatas 50 %. 8. Hasil synonym recognition berdasarkan pada isi kamus sinonim. Adapun saran yang diberikan oleh penulis untuk pengembangan aplikasi pendeteksi duplikasi ini, yaitu: 1. Aplikasi ini dapat dikembangkan dengan pendeteksi kalimat aktif dan pasif, karena tindak penjiplakan juga sering kali mengubah kalimat aktif menjadi pasif dan sebaliknya. 2. Penambahan fungsi tokening untuk pembuangan kata sambung seperti kata: „yang‟, „dan‟, „dengan‟, dan lain-lain agar kinerja pendeteksian duplikasi lebih cepat.
Daftar Pustaka [1] Elbegbayan, Norzima. Winnowing, a Document Fingerprinting Algorithm. Linkoping University.
[2] Schleimer, Saul, Daniel S. Wilkerson, dan Alex Aiken. Winnowing: Local Algorithms for Document Fingerprinting. Chicago. [3] Kurniawati, Ana, Wicaksana, I Wayan Simri. 2008. Perbandingan Pendekatan Deteksi Plagiarism Dokumen Dalam Bahasa Inggris. Fakultas Ilmu Komputer dan Teknologi Informasi, Universitas Gunadarma. [4] Kardhon, Roni. 2008. The Winnowing Algorithm. Department of Computer Science, Tufts University. [5] Kusmawan, Putu Yuwono, Umi Laili Yuhana, Diana Purwitasari. Aplikasi Pendeteksi Penjiplakan pada File Teks dengan Algoritma Winnowing. Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh November Surabaya. [6] Kamus Besar Bahasa Indonesia [Online]. http://www.pusatbahasa.diknas.go.id/kbbi, diakses tanggal 23 Januari 2011. [7] Nugroho, Eko. 2011. Perancangan Sistem Deteksi Plagiarisme Dokumen Teks Dengan Menggunakan Algoritma Rabin-Karp. Program Studi Ilmu Komputer, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Brawijaya. [8] Novanta, Audi. 2009. Pendeteksian Plagiarisme Pada Dokumen Teks Dengan Menggunakan Algoritma Smith-Waterman. Program Studi Ilmu Komputer, Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara. [9] Team_dakoop. 2008. OODBMS DB4O. http://dakoop.blogspot.com/2008/10/oodbmsdb4o.html, diakses tanggal 11 Mei 2011. [10] JENI. 2007. Jardiknas.
Pengenalan
Pemrograman 1.
[11] Antonius, Melvin, Damian Bayu Iman Santoso, Carneles. 2004. Membuat Animasi dengan Java. Jakarta: Penerbit PT Elex Media Komputindo. [12] Sagara, Dhafiq. 2010. Pemrograman Berorientasi Objek - Java Basic. http://dhafiqsan.blogspot.com/2010/10/pemrogramanberorientasi-objek-java.html, diakses tanggal 14 Mei 2011. [13] Suprasetiawan, Eko Budhi. 2006. Dasar-Dasar Pemrograman Java. IlmuKomputer.Com.
[14] Widyowaty, Dwi Sari. 2010. Analisa Sintaks Kalimat Bahasa Indonesia Menggunakan Algoritma Lookahead LR Parser. Jurusan Teknik Informatika, Fakultas Teknik, Universitas Muhammadiyah Malang. [15] Tim Redaksi. 2008. Tesaurus Bahasa Indonesia Pusat Bahasa. Pusat Bahasa, Departemen Pendidikan Nasional.
