Jurnal informasi dan Komputer Vol: 10 No:2.
P-ISSN: 2337-8344
E-ISSN: 2623-1247
KOMPARASI ALGORITMA WINNOWING DAN ALGORITMA MANBER DALAM
MENDETEKSI KEMIRIPAN TUGAS MAHASISWA
Ida Bagus Ketut Surya Arnawa ITB STIKOM Bali Jl.
Raya Puputan No 86 Renon.
Denpasar E-mail : arnawa@stikom-bali.
ABSTRAK
Seiring dengan perkembangan teknologi yang begitu pesat, proses belajar mengajar baik yang dilaksanakan disekolah maupun diperguruan tinggi sudah banyak memanfaatkan teknologi informasi untuk menunjang proses belajar mengajar.
Institut Teknologi dan Bisnis STIKOM Bali merupakan salah satu perguruan tinggi yang sebagian besar proses belajar mengajar menggunakan teknologi Dalam melaksanakan perkuliahan online beberapa dosen mengalami permasalahan terutama dalam mengkoreksi tugas yang dikumpulkan oleh mahasiswa.
Dalam beberapa kasus terdapat tugas mahasiswa terindikasi hampir sama persis dengan tugas mahasiswa yang lainnya serta beberapa tugas mahasiswa tidak mencantumkan sumber yang digunakan.
Untuk mengatasi permasalahan tindakan plagiarism, perlu mengimplementasikan teknik pencocokan dokumen tugas guna untuk mengetahui tingkat kemiripan dokumen tugas mahasiswa.
Banyak algoritma text mining dapat digunakan untuk melakukan pencocokan string.
Penelitian sebelumnya penulis telah melakukan perbandingan unjuk kerja algoritma Rabin-Karp.
Winnowing.
Jaro Winkler dengan hasil algoritma Winnowing memiliki unjuk kerja yang lebih baik diantara algoritma Rabin-Karp dan Jaro Winkler.
Dalam penelitian ini penulis membandingkan algoritma Winnowing dengan algoritma Manber dalam melakukan pencocokan dokumen.
Hasil dari penelitian ini yaitu algoritma winnoing memiliki unjuk kerja yang lebih baik dari pada algoritma manber.
Kata kunci : Text Mining.
Winnowing.
Manber
ABSTRACTS
Along with the rapid development of technology, the teaching and learning process, both carried out in schools and universities, has used information technology a lot to support the teaching and learning process.
STIKOM Bali Institute of Technology and Business is one of the universities where most of the teaching and learning process uses information technology.
In carrying out online lectures, several lecturers experienced problems, especially in correcting assignments collected by In some cases, student assignments are indicated to be almost exactly the same as other student assignments and some student assignments do not include the sources used.
To overcome the problem of plagiarism, it is necessary to implement the matching technique of assig nment documents in order to determine the level of similarity of student assignment documents.
Many text mining algorithms can be used to perform string matching.
In previous research, the author has compared the performance of the Rabin-Karp.
Winnowing.
Jaro Winkler algorithms with the results that the Winnowing algorithm has better performance between the Rabin-Karp and Jaro Winkler algorithms.
In this study, the authors compare the Winnowing algorithm with the Manber algorithm in document The result of this research is that the winnoing algorithm has better performance than the manber algorithm.
39 | S T M I K D i a n C i p t a C e n d i k i a K o t a b u m i Jurnal informasi dan Komputer Vol: 10 No:2.
P-ISSN: 2337-8344
E-ISSN: 2623-1247
Keywords: Text Mining.
Winnowing.
Manber
PENDAHULUAN
Manusia merupakan satu satunya mahluk ciptaan Tuhan yang memiliki akal dan Hal yang membedakan manusia dengan ciptaan Tuhan yang lainnya yaitu manusia diberikan pikiran, akal, perasaan untuk meningkatkan kualitas hidup.
Dalam meningkatkan kualitas hidup manusia tidak akan pernah berhenti untuk belajar, baik secara formal maupun informal.
Dengan belajar memberikan beberapa manfaat diantaranya otak akan tetap sehat, menambah pengetahuan dan pengalaman serta dapat meningkatkan kualitas hidup.
Indonesia mewajibkan warga negaranya untuk belajar selama 9 tahun di sekolah.
Hal ini tertuang dalam Peraturan Pemerintah Republik Indonesia Nomor 47 Tahun 2008 Tentang Wajib Belajar.
Seiring dengan perkembangan teknologi yang begitu pesat, proses belajar mengajar baik yang dilaksanakan disekolah maupun diperguruan tinggi sudah banyak memanfaatkan teknologi informasi untuk menunjang proses belajar mengajar.
Institut Teknologi dan Bisnis STIKOM Bali merupakan salah satu perguruan tinggi yang sebagian besar proses belajar mengajar menggunakan teknologi informasi.
Saat ini Institut Teknologi dan Bisnis STIKOM Bali memiliki beberapa sistem yaitu SION (Sistem informasi onlin.
yang diperuntukan bagi mahasiswa untuk melihat berbagai informasi mengenai perkuliahan seperti jadwal kuliah, hasil studi, indeks prestasi semester, indeks prestasi kumulatif serta informasi-informasi lainnya yang terkait dengan perkuliahan.
Selain SION Institut Teknologi dan Bisnis juga memliki sistem E-learning dimana sistem ini diperuntukan bagi mahasiswa dan Melalui sistem ini perkuliahan secara online dilaksanakan, dosen dapat memberikan pengumuman serta memberikan tugas kuliah.
Mahasiswa perkuliahan yang diberikan oleh dosen, ikut serta dalam forum diskusi serta mahasiswa dapat mengumpulkan tugas yang diberikan oleh dosen.
Dalam melaksanakan perkuliahan online beberapa dosen mengalami permasalahan terutama dalam mengkoreksi tugas yang dikumpulkan oleh mahasiswa.
Dalam beberapa kasus terdapat tugas mahasiswa terindikasi hampir sama persis dengan tugas mahasiswa yang lainnya serta beberapa tugas mahasiswa tidak mencantumkan sumber yang Hal ini sudah termasuk tindakan Plagiarisme merupakan tindakan yang tidak terpuji dimana seseorang dengan ide/gagasan/karya orang lain tanpa seijin yang memiliki ide/gagasan/karya.
Ada beberapa faktor yang mendorong mahasiswa melakukan tindakan plagiarism diantaranya kurangnya ide dalam membuat tugas, kurangnya rasa percaya diri yang dimiliki, plagiarism dan undang-undang hak cipta.
Untuk mengatasi permasalahan tindakan teknik pencocokan dokumen tugas guna dokumen tugas mahasiswa.
Banyak algoritma text mining dapat digunakan untuk melakukan pencocokan string.
Penelitian perbandingan unjuk kerja algoritma RabinKarp.
Winnowing.
Jaro Winkler dengan hasil algoritma Winnowing memiliki unjuk kerja yang lebih baik diantara algoritma RabinKarp dan Jaro Winkler.
Merujuk dari uraian diatas penulis tertarik untuk mencari algoritma yang memiliki unjuk kerja yang lebih baik dengan melakukan perbandingan algoritma Winnowing dimana algoritma ini dalam penelitian sebelumnya memiliki unjuk kerja yang paling baik.
Dalam penelitian ini penulis akan membandingkan algoritma Winnowing dengan algoritma Manber dalam melakukan pencocokan dokumen.
40 | S T M I K D i a n C i p t a C e n d i k i a K o t a b u m i Jurnal informasi dan Komputer Vol: 10 No:2.
METODE PENELITIAN
Adapun alur penelitian yang digunakan dalam penelitian ini dapat dilihat pada Gambar 1.
P-ISSN: 2337-8344
E-ISSN: 2623-1247
Penghapusan karakter yang tidak relevan yaitu berupa spasi, tanda baca serta spesial karakter seperti !,@,#,$,%,^,&,*,(,),_,-? Contoh :
Akan dirubah menjadi Langkah Kedua Gambar 1.
Alur Penelitian Gambar 1.
merupakan alur penelitian yang digunakan dalam penelitia ini.
Tahap pertama diawali dengan melakukan studi literatur terkait bidang penelitian yang dibuat yaitu text mining.
Tahap kedua melakukan analisis kebutuhan yang diperlukan dalam melakukan penelitian dan dilanjutkan dengan pengumpulan data, dimana data yang digunakan bersumber dari tugas mahasiswa ITB STIKOM Bali.
Tugas mahasiswa tersebut akan melalui proses preprosessing seperti case folding / lowercase, tokenizing / pemotongan kata, filtering / membuang kata kurang penting.
Setelah proses preprosesing dilakukan maka tahap selanjutnya dilakukan impementasi algoritma winnowing dan algoritma manber dalam mengukur tingkat kemiripan tugas Hasil dari masing-masing algoritma akan dianalisis dan dibandingkan untuk mengetahui algoritma yang memiliki kenerja yang paling baik.
Algoritma Winnowing Algortima winnowing merupakan salah satu algoritma yang dapat digunakan untuk mengukur tingkat kesamaan kata .
ocument fingerprintin.
untuk mendeteksi plagiarism.
Rolling hash merupakan algoritma yang digunakan mencari nilai hash dalam winnowing.
Nilai hash merupakan nilai numerik yang terbentuk dari perhitungan ASCII setiap karakter.
Langkahlangkah dalam penerapan Algoritma Winnowing adalah sebagai berikut .
Langkah Pertama Pembentukan Rangkaian n-gram yaitu dengan cara membentuk rangkaian karakter sepanjang n dari hasil pembuangan karakter yang tidak relevan pada langkang pertama.
Dari text diatas telah dibersihkan dengan ukuran k=5 belaj elaja lajar ajarp jarpe arpem rpemr pemro emrog mrogr rogra ogram grama raman amanc Langkah Ketiga Menghitung fungsi hash untuk setiap n-gram yaitu dengan cara menghitung nilai - nilai hash dari setiap gram, algoritma holling hash digunakan untuk menghitung nilai hash dalam algoritma winnowing.
Rolling hash merupakan suatu teknik untuk mentransformasikan sebuah string menjadi nilai yang unik dengan panjang tertentu yang berfungsi sebagai penanda string Fungsi tersebut menghasilkan nilai ini disebut fungsi hash, sedangkan nilai yang dihasilkan disebut nilai hash.
Fungsi hash H.
didefinisikan sebagai berikut :
= c1*b.
c2*b.
ck*b.
Keterangan :
c = nilai ascii karakter b = basis .
ilangan prim.
k = banyak karakter hasil rolling hash dari kalimat diatas yaitu 1583490 1635489 1724342 1574366
1696180 1586683 1831680 1788777
1638938 1762281 1830629 1777214
1672790 1812547 1578302
Langkah Keempat Pembentukan window dari nilai hash dari window dengan ukuran 3 yaitu sebagai berikut :
41 | S T M I K D i a n C i p t a C e n d i k i a K o t a b u m i Jurnal informasi dan Komputer Vol: 10 No:2.
3490 1635489 1724.
5489 1724342 1574.
4342 1574366 1696.
4366 1696180 1586.
6180 1586683 1831.
6683 1831680 1788.
1680 1788777 1638.
8777 1638938 1762.
8938 1762281 1830.
2281 1830629 1777.
0629 1777214 1672.
7214 1672790 1812.
{ 1672790 1812547 1578302 }
P-ISSN: 2337-8344
E-ISSN: 2623-1247
Penghitungan nilai hash dari setiap gram.
Membagi ke dalam window tertentu.
Pemilihan beberapa nilai hash menjadi document fingerprinting Prosentase kesamaan antara 2 dokumen dengan persamaan Jaccard Coefficient Pendekatan Manber memilih hasil dari proses hashing dengan cara memilih semua hasil hashing dengan yang memenuhi kriteria 0 mod Dengan cara ini fingerprints yang terpilih tidak tergantung dari posisinya.
Pendekatan ini mudah untuk diimplementasikan.
HASIL DAN PEMBAHASAN
Langkah Kelima Perancangan Sistem Langkah terakhir yaitu memilih nilai terkecil dari setiap window untuk dijadikan fingerprint, hasil dari nilai fingerprintnya sebagai berikut:
Nilai fingerprint yang dibentuk dari algoritma prosentase kemiripan teks pada persamaan Jaccard Coeficient.
Persamaan Jaccard Coefficient digunakan untuk menghitung kemiripan .
dari kumpulan kata-kata yang telah dihitung nilai hash nya.
Berikut ini rumus persamaan Jaccard Coefficient.
Algotirma Manber Proses Algoritma Manber hampir sama dengan Algoritma Winnowing, yang membedakan adalah Algoritma winnowing menentukan posisi dari fingerprint, sedangkan Algoritma Manber tidak menampilkan informasi posisi fingerprint .
Penghapusan karakter-karakter yang tidak relevan .
hitespace insensitivit.
, antara lain spasi atau tanda baca.
Pembentukan rangkaian gram dengan ukuran k.
Perancangan sistem yang dibuat merupakan sistem untuk mendeteksi kemiripan tugas mahasiswa satu dengan yang lainnya.
Sistem ini dapat menerima inputan berupa text yang merupakan tugas dari mahasiswa.
Tahap awal sistem melakukan preprocessing terlebih dahulu terhadap tugas mahasiswa.
Setelah melalui tahapan preprocessing tugas mahasiswa akan dicocokkan dengan tugas lainnya dengan menggunakan masing-masing metode yaitu Winnowing dan Manber.
Masing-masing kemiripan tugas mahasiswa yang satu dengan yang lainnya.
Kemudian dari hasil tersebut dianalisis untuk mengetahui metode mana yang memiliki unjuk kerja yang paling baik.
(Gipp, and Meuschke.
Gambar 2 komparasi algoritma text mining dalam mendeteksi kemiripan tugas mahasiswa.
Start file tugas Preprocessing Implementasi Komparasi Hasil Hasil Komparas Selesai Gambar.
2 Arsitektur Sistem Flowchart Preprocessing Pada tahapan preprocessing dilakukan beberapa tahapan yaitu diawali dengan case folding yaitu mengkonversi seluruh huruf dalam tugas 42 | S T M I K D i a n C i p t a C e n d i k i a K o t a b u m i Jurnal informasi dan Komputer Vol: 10 No:2.
mahasiswa menjadi huruf kecil.
Kemudian dilanjutkan dengan tahap tokenizing yaitu proses memisahkan setiap kata yang menyusun memanfaatkan karakter spasi.
Tahap selanjutnya yaitu filtering dimana tahap ini akan mengambil kata yang penting dari tahap tokenizing.
Tahap terakhir yaitu stemming dimana pada tahap ini mengubah sebuah kata menjadi kata dasar dengan menghilangkan imbuhan.
Gambar 3 merupakan flowchart preprocessing .
P-ISSN: 2337-8344
E-ISSN: 2623-1247
Mulai Tugas Mahasiswa Preprocessing Parsing K-Gram Pemilihan nilai hash menjadi Membagi nilai hash ke dalam Hasing Selesai Mulai Tugas Mahasiswa Case Folding Tokenizing Filtering Gambar 4.
Flowchart Winnowing Implementasi Perbandingan Algoritma Berikut ini merupakan tahapan-tahapan dalam mengimplementasikan perbandingan algoritma winnowing dengan algoritma manber untuk mendeteksi presentase plagiarisme pada tugas mahasiswa yaitu :
Stemming Tabel 1.
Data Uji Coba Selesai Gambar.
3 Flowchat Preprocessing Flowchart Winnowing Pada Algoritma Winnowing setelah melakukan tahap preprocessing dilanjutkan dengan membentuk teks hasil langkah preprocessing ke dalam rangkaian k-gram.
Selanjutnya dilakukan proses rolling hash untuk menghasilkan nilai hash dari setiap gram yang terbentuk.
Langkah selanjutnya setelah mendapat nilai hash dari setiap gram dilanjutkan dengan membentuk window, proses pembentukan window sama seperti proses k-gram dari nilai-nilai yang dihasilkan dengan besar window = 3 Percobaan 1.
Tugas Mahasiswa dengan tingkat kemiripan 100 % Bahasa pemrograman Bahasa ini merupakan suatu pemrograman ini himpunan dari aturan merupakan suatu sintaks dan semantik himpunan dari yang dipakai untuk aturan sintaks dan semantik yang program komputer.
dipakai untuk Bahasa ini program komputer.
seorang programmer Bahasa ini dapat menentukan secara persis data seorang programmer mana yang akan dapat menentukan diolah oleh secara persis data mana yang akan bagaimana data ini diolah oleh disimpan/diteruskan, bagaimana data ini dan jenis langkah apa akan yang akan diambil disimpan/diteruskan, dalam berbagai dan jenis langkah apa situasi secara persis.
yang akan diambil 43 | S T M I K D i a n C i p t a C e n d i k i a K o t a b u m i Jurnal informasi dan Komputer Vol: 10 No:2.
dalam berbagai situasi secara persis.
Percobaan 2.
Tugas Mahasiswa dengan tingkat kemiripan 50 % Bahasa pemrograman Bahasa ini merupakan suatu pemrograman adalah himpunan dari aturan himpunan perintah sintaks dan semantik sintaks semantik yang dipakai untuk yang dipakai membuat program program komputer.
Bahasa ini programmer dapat menentukan data seorang programmer yang akan diolah dapat menentukan komputer untuk secara persis data membuat program mana yang akan Ada diolah oleh beberapa Bahasa pemrograman yang bagaimana data ini sering digunakan disimpan/diteruskan, javascript, php, c , dan jenis langkah apa asp.
net dan masih yang akan diambil banyak lagi yang dalam berbagai Setiap situasi secara persis.
memiliki kekurangan dan kelebihan masing-masing.
Percobaan 3.
Tugas Mahasiswa dengan tingkat kemiripan 30 % Bahasa pemrograman Kemampuan seorang ini merupakan suatu programmer bisa himpunan dari aturan didapat dari sintaks dan semantik pendidikan formal yang dipakai untuk atau informal.
Programmer program komputer.
membuat program Bahasa ini komputer dengan seorang programmer pemrograman.
Ada dapat menentukan beberapa Bahasa
secara persis data
pemrograman yang mana yang akan sering digunakan P-ISSN: 2337-8344
E-ISSN: 2623-1247
diolah oleh bagaimana data ini disimpan/diteruskan, dan jenis langkah apa yang akan diambil dalam berbagai situasi secara persis.
javascript, php, c , net dan masih banyak lagi yang Setiap memiliki kekurangan dan kelebihan masing-masing.
Tabel.
2 Percobaan 1.
Tingkat kemiripan 100 % dengan winnowing Tabel.
3 Percobaan 2.
Tingkat kemiripan 50 % dengan winnowing Tabel.
4 Percobaan 3.
Ttingkat kemiripan 30 % dengan winnowing 44 | S T M I K D i a n C i p t a C e n d i k i a K o t a b u m i Jurnal informasi dan Komputer Vol: 10 No:2.
P-ISSN: 2337-8344
E-ISSN: 2623-1247
Tabel.
5 Percobaan 1.
Ttingkat kemiripan 100 % dengan manber Gambar 2.
Tingkat Akurasi Pengujian KESIMPULAN Tabel.
6 Percobaan 2.
Ttingkat kemiripan 50 % dengan manber Tabel.
7 Percobaan 3.
Ttingkat kemiripan 30 % dengan manber Tabel.
8 Hasil Perbandingan algoritma winnowing dan manber Berdasarkan hasil penelitian yang dilakukan pada proses pelatihan maka dapat disimpulkan bahwa, metode bag of visual word dapat melakukan proses klasifikasi pada penggunaan Proses yang dilakukan adalah mendeteksi citra input menggunakan metode SURF untuk mendapatkan nilai interest point, kemudian dikelompokkan dengan metode KMeans.
Hasil dari k-means dibuatkan sebuah matriks yang menampung nilai histogram pada masing-masing citra input.
Hasil tersebut dilakukan klasifikasi menggunakan metode SVM untuk mendapatkan model proses Pada proses pelatihan metode bag of visual Words dapat memeberikan hasil yang baik dimana tingkat akurasi yang diroleh mencapai 94% dan pada proses pengujian dapat diperoleh tingkat akurasi sebesar 85%.
Adapun saran yang dikemukan peneliti pada penelitian ini adalah mengambil sampel lebih banyak lagi dalam proses pelatihan dan diperlukan metode keberhasilan antara masing-masing metode yang Berdasarkan hasil percobaan yang telah dilakukan pada masing-masing algoritma yaitu algoritma winnowing dengan algoritma manber terhadap tugas mahasiswa, maka dapat ditarik kesimpulan sebagai berikut.
Algoritma winnowing memiliki kinerja yang lebih baik dibandingkan dengan algoritma Terdapat perbedaan mendasar dari kedua algoritma yaitu pada algoritma winnowing 45 | S T M I K D i a n C i p t a C e n d i k i a K o t a b u m i Jurnal informasi dan Komputer Vol: 10 No:2.
P-ISSN: 2337-8344
E-ISSN: 2623-1247
memiliki window dan k-gram sedangkan algoritma manber hanya memiliki k-gram.
DAFTAR
PUSTAKA