KOMPARASI ALGORITMA WINNOWING DAN RABIN
KARP MENDETEKSI KEMIRIPAN TUGAS MAHASISWA
Ida Bagus Ketut Surya Arnawa Program Studi Sistem Informasi Institut Teknologi Dan Bisins STIKOM Bali.
Denpasar.
Bali arnawa@stikom-bali.
ABSTRACT
Learning is a process of improving one's self-quality both in terms of knowledge, attitudes and behavior.
In the learning process in higher education, a lecturer often gives assignments to students.
The purpose of giving assignments to students is to train them to want to learn, to be responsible and as material for evaluating the ability of students to understand a material that has been given.
In making assignments, students often commit acts of plagiarism either intentionally or unintentionally.
Many factors encourage students to take plagiarism, one of which is arrogance in making assignments whose goal is to finish assignments quickly and the lack of a sense of responsibility for students in doing assignments.
One way to prevent and minimize plagiarism is to use document matching techniques with one another.
with the aim of knowing the level of similarity of a text document.
There are many algorithms in Text Mining that can be used such as the Jaro-Winkler algorithm.
Rabin-Karp.
Winnowing and so on.
Referring to the description above, the author is interested in conducting a comparison analysis of the performance of the Jaro-Winkler.
Rabin Karp and Winnowing algorithms in measuring the level of similarity of a In the trial process, it was found that the Rabin Karp algorithm has better performance than the Winnowing algorithm in detecting the similarity of student assignments.
Keywords: comparison, winnowing.
Rabin Karp.
ABSTRAK
Belajar merupakan sebuah proses peningkatan kualitas diri seseorang baik dari segi pengetahuan, sikap maupun tingkah laku.
Dalam proses belajar di perguruan tinggi sering kali seorang dosen memberikan tugas kepada mahasiswa.
Adapun tujuan dari pemberian tugas kepada peserta didik yaitu melatih agar mau belajar, bisa bertanggung jawab serta sebagai bahan untuk evaluasi terhadap kemampuan peserta didik dalam memahami suatu materi yang sudah diberikan.
Dalam pembuatan tugas mahasiswa sering melakukan tindakan plagiarisme baik dilakukan secara sengaja maupun tidak sengaja.
Banyak faktor yang mendorong mahasiswa melakukan tindakan plagiarisme salah satunya sikap arogansi dalam pembuatan tugas yang tujuannya supaya tugas cepat selesai serta kurangnya rasa tanggung jawab mahasiswa dalam mengerjakan tugas.
Salah satu cara untuk mencegah serta meminimalisir tindakan plagiarisme yaitu dengan menggunakan teknik pencocokan dokumen satu dengan yang lainnya dengan tujuan untuk mengetahui tingkat kemiripan suatu dokumen text.
Ada banyak algoritma dalam Text Mining yang dapat digunakan seperti algoritma Jaro-Winkler.
Rabin-Karp.
Winnowing dan lain Merujuk dari uraian diatas penulis tertarik untuk melakukan analisis perbandingan kinerja algoritma Jaro-Winkler.
Rabin Karp serta Winnowing dalam mengukur tingkat kemiripan suatu dokumen text.
Dalam proses uji coba ditemukan bahwa algoritma Rabin Karp memiliki unjuk kerja yang lebih baik dibandingkan algoritma Winnowing dalam kasus mendeteksi kemiripan tugas mahasiswa.
Kata Kunci : komparasi, winnowing.
Rabin-Karp.
346 Jurnal Teknologi Informasi dan Komputer.
Volume 7.
Nomor 4.
Oktober 2021
PENDAHULUAN
Belajar merupakan sebuah proses peningkatan kualitas diri seseorang baik dari segi pengetahuan, sikap maupun tingkah laku.
Banyak cara yang dapat ditempuh oleh seseorang untuk dapat belajar salah satunya dengan masuk perguruan tinggi.
Dalam proses belajar di perguruan tinggi sering kali seorang dosen memberikan tugas kepada mahasiswa.
Tugas merupakan suatu kewajiban yang harus dikerjakan oleh mahasiswa.
Ada beberapa macam tugas diantaranya tugas perseorangan dan tugas kelompok.
Adapun tujuan dari pemberian tugas kepada peserta didik yaitu melatih agar mau belajar, bisa bertanggung jawab serta sebagai bahan untuk evaluasi terhadap kemampuan peserta didik dalam memahami suatu materi yang sudah diberikan.
Dalam pembuatan tugas mahasiswa sering melakukan tindakan plagiarisme baik dilakukan secara sengaja maupun tidak sengaja.
plagiarisme merupakan suatu tidakan dimana ide atau gagasan orang lain diambil begitu saja tanpa menyebutkan sumbernya atau tanpa seijin dari yang memiliki ide atau gagasan Dalam dunia pendidikan plagiarisme merupakan suatu tindakan yang sangat tidak UU No.
9 tahun 2012 pasal 2 ayat .
, pasal 3 ayat .
, pasal 12, pasal, pasal 15 dan pasal 26 ayat .
menyebutkan tentang pelarangan terhadap tindakan plagiarisme.
Banyak faktor yang mendorong mahasiswa melakukan tindakan plagiarisme salah satunya sikap arogansi dalam pembuatan tugas yang tujuannya supaya tugas cepat selesai serta kurangnya rasa tanggung jawab mahasiswa dalam mengerjakan tugas.
Hal ini perlu dicegah supaya tidak menjadi kebiasan bagi mahasiswa.
Banyak kendala yang dialami oleh seorang dosen dalam mengetahui tugas mahasiswa tersebut termasuk melakukan tindakan plagiarisme atau tidak karena banyak tugas yang perlu dikoreksi serta banyak memerlukan waktu dalam mencocokan kemiripan suatu Salah satu cara untuk mencegah serta meminimalisir tindakan plagiarisme yaitu dengan menggunakan teknik pencocokan dokumen satu dengan yang lainnya dengan tujuan untuk mengetahui tingkat kemiripan suatu dokumen text.
Text Mining merupakan salah satu solusi yang bisa digunakan untuk mengetahui tingkat kemiripan suatu dokumen Ada banyak algoritma dalam Text Mining yang dapat digunakan seperti algoritma JaroWinkler.
Rabin-Karp.
Winnowing dan lain Semua algoritma pencocokan string memiliki kekurangan dan kelebihan masing-masing.
Merujuk dari uraian diatas penulis tertarik untuk melakukan analisis perbandingan kinerja algoritma Winnowing dan Rabin Karp dalam mengukur tingkat kemiripan suatu dokumen text.
TINJAUAN PUSTAKA
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 Nilai hash merupakan nilai numerik yang terbentuk dari perhitungan ASCII setiap karakter.
Langkah-langkah dalam penerapan Algoritma Winnowing adalah sebagai berikut .
Langkah Pertama Penghapusan karakter yang tidak relevan yaitu berupa spasi, tanda baca serta spesial karakter seperti !,@,#,$,%,^,&,*,(,),_,-? Contoh :
Belajar Pemrograman C# Arnawa.
Komparasi Algoritma Winnowing Dan Rabin Karp Mendeteksi Kemiripan.
Akan dirubah menjadi Pembentukan window dari nilai hash dari window dengan ukuran 3 yaitu sebagai Langkah Kedua 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 ngram 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 .
{ 1672790
Langkah Kelima Langkah terakhir yaitu memilih nilai terkecil dari setiap window untuk dijadikan fingerprint, hasil dari nilai fingerprintnya sebagai berikut:
Nilai fingerprint yang dibentuk dari algoritma winnowing digunakan untuk mengukur 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.
Algoritma Rabin-Karp Algoritma Rabin-Karp diciptakan oleh Michael O.
Rabin dan Richard M.
Karp pada tahun 1987 yang menggunakan fungsi hashing untuk menemukan pattern di dalam 348 Jurnal Teknologi Informasi dan Komputer.
Volume 7.
Nomor 4.
Oktober 2021 string teks.
Algoritma RabinAeKarp digunakan sebagai algoritma deteksi kesamaan pada Algoritma ini penerapannya, salah satunya adalah algoritma ini sangat cocok digunakan untuk string yang Karakteristik algoritma Rabin-Karp .
, yaitu :
Menggunakan sebuah fungsi hashing.
Tahap kompleksitas waktu O.
Untuk tahap pencarian kompleksitasnya :
Waktu yang diperlukan O.
Dalam algoritma Rabin-Karp, beberapa tahap yang harus dilelalui dalam implementasi algoritma tersebut.
Preprocessing Tahap ini melakukan analisis semantik .
ebenaran art.
dan sintaktik .
ebenaran susuna.
Tujuan dari pemrosesan untuk mempersiapkan teks menjadi data yang mengalami pengolahan lebih lanjut.
Pembersihan yang dilakukan adalah pembersihan suatu teks dari karakterkarakter yang bersifat sebagai stoplist, dimana karakter tersebut banyak dan pasti muncul dalam setiap teks.
Rolling Hash Fungsi yang digunakan untuk menghasilkan nilai hash dari rangkaian gram dalam Algoritma Rabin-Karp adalah dengan menggunakan fungsi rolling hash.
Fungsi hash .
a1Ayayc.
didefinisikan sebagai berikut, yca1O.
coOe.
yca2Oyca.
coOe.
U yca.
coOe.
Oycayco ycaycoA .
Keterangan :
c : nilai ASCII karakter b : basis .
ilangan prim.
k : banyak karakter Metode hashing digunakan untuk mempercepat pencarian atau pencocokan suatu string.
Apabila tidak di-hash, pencarian akan dilakukan karakter per karakter.
Namun pencarian akan menjadi lebih mangkus setelah di-hash karena hanya akan membandingkan empat digit angka untuk mengetahui kesamaan suatu substring.
Berikut ini merupakan contoh penghitungan rolling hash dengan k-grams = 6 dan basis = Diketahui Teks : abracadabra ASCII : a = 97, b = 98, r = 114 Maka hash(AuabrA.
= ( 97 x 1012 ) ( 98 x 1011 ) ( 114 x 1010 ) = 999.
509 Untuk menghitung nilai hash dari substring selanjutnya, dapat dilakukan dengan mengurangi hash dengan nilai dari karakter yang hilang kemudian menambahkannya dengan nilai karakter yang hash(AubraA.
= .
x ( 999.
509 Ae .
x 1012 ))] ( 97 x 1010 ) = 1.
Pencocokan Proses pencocokan dalam Algoritma RabinKarp dilakukan dengan menggunakan sebuah teorema yaitu:
Sebuah stringA identik dengan stringB, jika .
yarat perl.
stringA memliki hash key yang sama dengan hash key yang dimiliki oleh Pengukuran Nilai Kemiripan Mengukur similarity .
dan jarak antara dua entitas informasi adalah syarat inti pada semua kasus penemuan informasi, seperti pada Information Retrieval dan Data Mining yang kemudian dikembangkan dalam bentuk perangkat lunak, salah satunya adalah sistem deteksi kesamaan .
Penggunaan ukuran similarity yang tepat tidak hanya meningkatkan kualitas pilihan informasi tetapi juga membantu mengurangi waktu dan biaya proses sehingga Arnawa.
Komparasi Algoritma Winnowing Dan Rabin Karp Mendeteksi Kemiripan.
memperangkat lunakkan Dice's Similarity Coefficient dalam penghitungan nilai similarity yang menggunakan pendekatan k-gram.
ycI= ya y ya / .
a yaA)a.
Dimana S adalah nilai similarity.
A dan B adalah jumlah dari kumpulan k-grams dalam teks 1 dan teks 2.
C adalah jumlah dari k-grams yang sama dari teks yang dibandingkan.
Berikut adalah contoh dari penggunaan rumus Terdapat dua buah dokumen teks .
ok A dan dok B) dengan nilai k-gram masingmasing dokumen secara bertutur-turut adalah 2608 dan 3040, sedangkan nilai k-gram yang sama adalah sebesar 1203.
Maka hasil nilai dari kemiripan kedua dokumen tersebut adalah :
ycI = ya y ya/.
a yaA) = 2 y 1203/.
= 2406/5648 = 0,4259 ycu 100% = 42,59% METODE PENELITIAN Arsitektur Sistem 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 mahasiswa akan dicocokkan dengan tugas lainnya dengan menggunakan masing-masing metode yaitu Jaro-Winkler dan Winnowing.
Masing-masing metode akan menghasilkan persentase kemiripan tugas mahasiswa yang satu dengan yang lainnya.
Kemudian dari hasil tersebut dianalisis untuk mengetahui metode mana yang memiliki unjuk kerja yang paling Gambar 1 merupakan gambaran arsitektur sistem komparasi algoritma text mining dalam mendeteksi kemiripan tugas mahasiswa.
Gambar 1.
Arsitektur Sistem
HASIL DAN PEMBAHASAN
Implementasi Perbandingan Algoritma Tahapan - tahapan untuk meng implementasikan perbandingan algoritma Winnowing dengan algoritma rabin karp untuk mendeteksi presentase plagiarisme pada tugas mahasiswa adalah sebagai berikut :
Ambil 2 buah teks hasil tugas mahasiswa yang akan dibandingkan.
Tugas Mahasiswa 1 Harddisk adalah salah satu perangkat keras komputer yang menyediakan ruang penyimpanan yang digunakan untuk menyimpan atau membaca data pada Harddisk merupakan jenis memori komputer yang memiliki sifat non-volatile memory yang berarti data pada memori jenis ini tidak akan hilang meski perangkat tersebut telah 350 Jurnal Teknologi Informasi dan Komputer.
Volume 7.
Nomor 4.
Oktober 2021 Tugas Mahasiswa 2 Haddisk merupakan perangkat keras komputer yang3.
digunakan untuk Harddisk merupakan salah satu jenis memory yang non-volatile yaitu tidak akan hilang meskipun perangkat dimatikan Tabel 1 Algoritma Winnowing nwindow waktu kemiripan .
(%) .
Tabel 2 Hasil window dan kemiripan terbaik algoritma winnowing nwindow waktu kemiripan .
(%) .
Tabel 3 Algoritma Rabin Karp n-gram .
86,87 72,24 64,63 58,29 53,39 48,68 43,44 38,56 33,96 Dari hasil perbandingan pendekatan algoritma winnowing dengan algoritma rabin karp dapat dilihat kemungkinan kemiripan tugas mahasiswa yang terbesar adalah dengan penggunakan pendekatan algoritma rabin karp yaitu pada uji coba ke 1 dengan nilai n-gram = 2, proses waktu 0.
0177 dengan tingkat kemiripan terbesar yaitu 86,87 %.
SIMPULAN
Pendekatan Algoritma Rabin Karp lebih baik daripada pendekatan algoritma Winnowing karena menghasilkan tingkat presentase yang lebih besar.
Terdapat perbedaan mendasar dari kedua algoritma yaitu pada algoritma winnowing memiliki window sedangkan algoritma rabin karp hanya memiliki k-gram Berdasarkan Pengujian Arnawa.
Komparasi Algoritma Winnowing Dan Rabin Karp Mendeteksi Kemiripan.
winnowing dengan algoritma rabin karp dapat dilihat kemungkinan kemiripan teks Tugas Mahasiswa yang terbesar adalah dengan penggunakan pendekatan algoritma rabin karp yaitu pada ujicoba ke 1 dengan nilai n-gram = 2 proses waktu 0.
0177dengan tingkat kemiripan terkecil yaitu 86,87 % DAFTAR PUSTAKA