PERANCANGAN SISTEM DETEKSI PLAGIAT PADA DOKUMEN TEKS DENGAN KONSEP SIMILARITY MENGGUNAKAN ALGORITMA RABIN KARP
NASKAH PUBLIKASI
diajukan oleh Salmuasih 08.11.2281
kepada SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER AMIKOM YOGYAKARTA 2013
1
2
DESIGN OF PLAGIARISM DETECTION SYSTEM FOR TEXT DOCUMENT WITH SIMILARITY CONCEPT USING RABIN KARP ALGORITHM PERANCANGAN SISTEM DETEKSI PLAGIAT PADA DOKUMEN TEKS DENGAN KONSEP SIMILARITY MENGGUNAKAN ALGORITMA RABIN KARP Salmuasih Andi Sunyoto Jurusan Teknik Informatika STMIK AMIKOM YOGYAKARTA
ABSTRACT Plagiarism is becoming increasingly serious problem as the rapid development of technology. Various people can easily access digital content such as images, video, mp3, text documents, and source code that is usually the target of plagiarism. Ironically acts of plagiarism is most prevalent among academics as students and learners. In this case most often done is copy-paste-edit text documents. Plagiarism is a crime, because it recognizes people's property as a personal masterpiece. As anticipated, detection tools needed to analyze the acts committed plagiarism. This detection tool is built with a strategic approach Rabin-Karp algorithm, which is a multiple-pattern search algorithm. This algorithm is one of the best in analyzing compatibility between documents. It uses a hashing technique. The search will be more efficient with this technique because it will compare multiple digit numbers. Keywords: Plagiarism, String matching, Pattern Matching, Rabin-Karp, Hashing, Similarity
3
1.
Pendahuluan Plagiarisme selalu menjadi perhatian di banyak sektor, terutama sektor akademis.
Sering kita temui pekerjaan teman yang dihargai dengan nilai “0” karena diketahui telah menyalin hasil pekerjaan temannya yang lain. Praktik menyalin beberapa bagian atau keseluruhan tulisan tanpa mencantumkan sumber
menjadi hal biasa yang sering
ditemukan pada tugas harian, makalah, bahkan skripsi. Pencegahan dan pendeteksian merupakan cara yang dapat dilakukan untuk mengurangi plagiarisme. Pencegahan berarti menghalangi munculnya plagiarisme yang lebih ditekankan kepada moral masyarakat dan sistem pendidikan. Cara ini akan memberikan efek jangka panjang yang luar biasa. Pendeteksian berarti cara untuk mengungkapkan plagiarisme. Beberapa perangkat lunak yang didesain untuk mendeteksi plagiarisme dokumen, diantaranya
Turnitin,
Eve2,
CopyCatchGold,
WordCheck,
Glatt,
Moss,
JPlag.
Berdasarkan analisis informasi yang ada di web, pendeteksi terbaik sesuai fungsinya adalah Turnitin (Lukashenko, dkk, 2007). Pendeteksian plagiarisme atau plagiat menggunakan konsep similarity atau kemiripan dokumen merupakan salah satu cara untuk mendeteksi copy&paste plagiarism dan disguised plagiarism. Menggunakan metode fingerprinting, pendeteksian plagiat ini tidak memperhatikan adanya penulisan sumber rujukan. Pada sistem deteksi ini akan diaplikasikan text mining untuk tahap preprocessing dan algoritma Rabin Karp untuk string matching. Algoritma Rabin Karp adalah algoritma multiple pattern search yang sangat efisien untuk mencari string dengan pola banyak. Selanjutnya akan dibahas bagaimana algoritma Rabin Karp bekerja sekaligus implementasinya pada sebuah aplikasi dalam mendeteksi plagiarisme dokumen. 2. Landasan Teori 2.1
Plagiarisme Plagiarisme atau plagiat adalah penjiplakan atau pengambilan karangan, pendapat
orang lain dan menjadikannya seolah-olah karangan sendiri (KBBI, 1997: 775). Berdasarkan penelitian, Gipp dan Meuschke (2011) mengkategorikan praktek plagiat berdasarkan cara yang digunakan, diantaranya : 1.
Copy&Paste plagiarism, menyalin setiap kata tanpa perubahan.
2.
Disguised plagiarism, tergolong kedalam praktek menutupi bagian yang disalin, teridentifikasi ke dalam empat teknik, yaitu shake&paste, expansive plagiarism, contractive plagiarism, dan mosaic plagiarism.
3. Technical disguise, teknik meringkas untuk menyembunyikan konten plagiat dari deteksi otomatis dengan memanfaatkan kelemahan dari metode analisis teks dasar,
4
misal dengan mengganti huruf dengan simbol huruf asing. 4. Undue paraphrasing, sengaja menuliskan ulang pemikiran asing dengan pemilihan kata dan gaya plagiator dengan menyembunyikan sumber asli. 5. Translated plagiarism, mengkonversi konten dari satu bahasa ke bahasa lain. 6. Idea plagiarism, menggunakan ide asing tanpa menyatakan sumber. 7. Self plagiarism, penggunaan sebagian atau keseluruhan tulisan pribadi yang tidak dibenarkan secara ilmiah. Taxonomy plagiat menurut Alzahrani, dkk digambarkan sebagai berikut: 2.2
Pendekatan Deteksi Plagiat Pendekatan sistem deteksi plagiat digolongkan menjadi dua, yaitu external dan
intrinsic. Pendekatan external bertujuan untuk menemukan kesesuaian bagian teks secara harfiah, sedangkan pendekatan intrinsic mencoba untuk mengenali perubahan gaya penulisan (Stein, 2006). Strategi pendekatan external diantaranya:
Perbandingan Teks Lengkap. Metode ini diterapkan dengan membandingkan semua isi dokumen (Gipp, Meusche, Beel 2011). Solusi untuk metode ini adalah algoritma Boyer-Moore dan algoritma Knuth-Morris-Pratt.
Kesamaan Kata Kunci. Prinsip dari metode ini adalah mengekstrak kata kunci dari dokumen dan kemudian dibandingkan dengan kata kunci pada dokumen yang lain.
Metode Fingerprinting, digunakan untuk mendeteksi keakuratan salinan antar dokumen, baik semua teks atau hanya sebagian teks saja. Prinsip kerja dari metode ini menggunakan teknik hashing, yaitu fungsi yang mengkonversi setiap string menjadi bilangan. Misalnya Rabin-Karp, Winnowing dan Manber.
2.3
Similarity Dokumen Konsep similarity sudah menjadi isu yang sangat penting di hampir setiap bidang
ilmu pengetahuan. Zaka (2009) dalam disertasinya menjelaskan tiga macam teknik yang dibangun untuk menentukan nilai similarity (kemiripan) dokumen. 1.
Distance-based similarity measure Distance-based similarity measure mengukur tingkat kesamaan dua buah objek
dari segi jarak geometris dari variabel-variabel yang tercakup di dalam kedua objek tersebut.
Metode
Distance-based
similarity
ini
meliputi
Minkowski
Distance,
Manhattan/City block distance, Euclidean distance, Jaccard distance, Dice’s Coefficient, Cosine similarity, Levenshtein Distance, Hamming distance, dan Soundex distance. 2.
Feature-based similarity measure Feature-based similarity measure melakukan penghitungan tingkat kemiripan
dengan merepresentasikan objek ke dalam bentuk
feature-feature yang ingin
5
diperbandingkan. Feature-based similarity measure banyak digunakan dalam melakukan pengklasifikasian atau pattern maching untuk gambar dan teks. 3.
Probabilistic-based similarity measure Probabilistic-based similarity measure menghitung tingkat kemiripan dua objek
dengan merepresentasikan dua set objek yang dibandingkan dalam bentuk probability. Kullback Leibler Distance dan Posterior Probability termasuk dalam metode ini. 2.4
Text Mining Text mining adalah salah satu bidang khusus dari data mining. Feldman dan
Sanger (2007) mendefinisikan text mining sebagai suatu proses menggali informasi dimana seorang user berinteraksi dengan sekumpulan dokumen menggunakan tools analisis yang merupakan komponen-komponen dalam data mining. Tujuan dari text mining adalah untuk mendapatkan informasi yang berguna dari sekumpulan dokumen. Dalam memberikan solusi, text mining mengadopsi dan mengembangkan banyak teknik dari bidang lain, seperti Data mining, Information Retrieval (IR), Statistic and Mathematic, Machine Learning, Linguistic, Natural Languange Processing (NLP), dan Visualization. Kegiatan riset untuk text mining antara lain ekstraksi dan penyimpanan teks, preprocessing akan konten teks, pengumpulan data statistik dan indexing, dan analisa konten (Triawati, 2009). Tahapan dalam text mining meliputi tokenizing, filtering, stemming, tagging dan analyzing (Mooney, 2006). 2.5
Indonesian Porter Stemmer Algoritma Porter ditemukan oleh Martin Porter 1980. Algoritma tersebut
digunakan untuk stemming bahasa Inggris, kemudian karena proses stemming bahasa Inggris berbeda dengan bahasa Indonesia, maka dikembangkan algoritma Porter khusus untuk bahasa Indonesia (Porter Stemmer for Bahasa Indonesia) oleh W.B. Frakes pada tahun 1992. Algoritma / langkah-langkah pada Porter Stemmer:
Menghapus partikel seperti: -kah, -lah, -tah
Mengapus kata ganti (Possesive Pronoun), seperti –ku, -mu, -nya
Mengapus awalan pertama. Jika tidak ditemukan, maka lanjut ke langkah 4a, dan jika ada maka lanjut ke langkah 4b.
a. Menghapus awalan kedua, dan dilanjutkan pada langkah ke 5a b. Menghapus akhiran, jika tidak ditemukan maka kata tersebut diasumsikan sebagai kata dasar (root word). Jika ditemukan maka lanjut ke langkah 5b.
a. Menghapus akhiran dan kata akhir diasumsikan sebagai kata dasar (root word). b. Menghapus awalan kedua dan kata akhir diasumsikan sebagai kata dasar (root word).
6
2.6
String Matching String matching atau pencocokan string adalah subjek yang penting dalam
kaitannya dengan text-processing. String matching merupakan bahasan yang sangat penting dalam ilmu komputer, karena teks adalah bentuk utama dalam pertukaran informasi (Charras-Lecroq, 2006). Persoalan pencarian string dirumuskan sebagai berikut (Munir, 2004) : 1. teks (text), yaitu (long) string yang panjangnya n karakter 2. pattern, yaitu string dengan panjang m karakter (m < n) yang akan dicari di dalam teks. Cara kerjanya adalah mencari lokasi pertama di dalam teks yang bersesuaian dengan pattern. Contoh :
Pattern : hari Teks
: kami pulang hari kamis target
Penggunaan string matching mencakup pencarian pola dalam DNA sequence, search engine internet, menemukan halaman web yang relevan pada query, dapat pula dimanfaatkan untuk mendeteksi adanya plagiarisme karya tulis. Termasuk dalam algoritma string matching diantaranya algoritma Naive, algoritma Rabin Karp, algoritma Finite Automaton, dan algoritma Knuth Morris Pratt (Cormen, dkk, 2009). 2.7
Algoritma Rabin Karp Algoritma Rabin Karp ditemukan oleh Michael O. Rabin dan Richard M. Karp.
Algoritma ini menggunakan metode hash dalam mencari suatu kata. Teori ini jarang digunakan untuk mencari kata tunggal, namun cukup penting dan sangat efektif bila digunakan untuk pencarian jamak (Atmopawiro, 2006). Rabin Karp merepresentasikan setiap karakter ke dalam bentuk desimal digit (digit radix-d) ∑ = {0, 1, 2, 3, …, d}, dimana d = |∑|. Sehingga didapat masukan string k berturut-turut sebagai perwakilan panjang k desimal. Karakter string 31415 sesuai dengan jumlah desimal 31,415. Kemudian pola p dihash menjadi nilai desimal dan string direpresentasikan dengan penjumlahan digit-digit angka menggunakan aturan Horner's, misal (Elchison, 2004) : { A, B, C, ..., Z } → { 0, 1, 2, ..., 26 } • BAN
→ 1 + 0 + 13
= 14
• CARD
→ 2 + 0 + 17 + 3
= 22
Untuk pola yang panjang dan teks yang besar, algoritma ini menggunakan operasi mod, setelah dikenai operasi mod q, nilainya akan menjadi lebih kecil dari q, misal:
7
• BAN = 1 + 0 + 13 = 14 = 14 mod 13 = 1 = BAN → 1 • CARD= 2 + 0 + 17 + 3 = 22 = 22 mod 13 = 9 = CARD → 9 Tetapi tidak semua nilai hash yang cocok berarti polanya cocok. Hal ini sering terjadi pada beberapa kasus, ini disebut spurious hits. Kemungkinan terjadinya diantaranya karena: Operasi mod terinterfensi oleh keunikan nilai hash (nilai mod q biasanya dipilih
bilangan prima sehingga 10q hanya cocok dengan 1 kata komputer) 14 mod 13 = 1 27 mod 13 = 1
Informasi hilang setelah penjumlahan BAN → 1 + 0 + 13 = 14 CAM → 2 + 0 + 12 = 14 Sedangkan pseudocode dan rumus matematis yang digunakan adalah sebagai
berikut (Cormen, dkk, 2009): RABIN-KARP-MATCHER (T, P, d, q) n = T.length m = P.length h = dm-1 mod q p =0 t0 = 0 for i = 1 to m // preprocessing p = (dp + P[i]) mod q t0 = (dt0 + T[i]) mod q for s = 0 to n – m if p == ts // matching if P[1 .. m] == T[s + 1 .. s + m] print “Pattern occurs with shift” s if s < n – m ts+1 = (d(ts - T[s + 1] h) + T[s + m + 1]) mod q
Rumus matematis: ts+1 = (d (ts – T [s + 1] h) + T [s + m + 1] mod q dimana ts
= nilai desimal dengan panjang m dari substring T [s + 1 .. s + m], untuk s = 0,
1, ..., n - m
ts+1
= nilai desimal selanjutnya yang dihitung dari ts
d
= radix desimal (bilangan basis 10)
8
h
= dm-1
n
= panjang teks
m
= panjang pola
q
= nilai modulo Pengurangan dengan T [s + 1] * h adalah untuk menghilangkan high-order digit
dari ts, mengalikan hasilnya dengan 10 untuk menggeser satu digit angka ke kiri, dan menambahkan low-order digit dengan T [s + m + 1]. Misalnya, jika m = 5 dan ts = 31415, maka kita ingin menghapus high-order digit T [s +1] = 3, masukkan low-order digit baru (anggap T [s +5 +1] = 2) dan modulo = 3 untuk memperoleh ts +1
= (10 (31415 - 3 * 10000)) + 2 mod 13 = 14152 mod 13 =8
Gambar 2. 1 Algoritma Rabin Karp 2.8
Peningkatan Performa Algoritma Rabin Karp Telah kita pahami bahwa spurious hit adalah beban tambahan bagi algoritma yang
akan meningkatkan waktu proses. Hal ini dikarenakan algoritma harus membandingkan pola terhadap teks yang hasil modulonya sama tetapi nilai hashnya berbeda. Untuk menghindari pencocokan yang tidak perlu, Singh dan Kochar (2008) memberikan solusi untuk tidak hanya membandingkan sisa hasil bagi, tetapi membandingkan hasil baginya juga. REM (n1/q) = REM (n2/q) and QUOTIENT (n1/q) = QUOTIENT (n2/q) Jadi, successful hit harus memenuhi dua syarat, yaitu nilai sisa hasil bagi dan nilai hasil baginya harus sama. Selebihnya adalah unsuccessful hit tanpa perlu melakukan
9
pencocokan lagi. Hal ini berarti tidak ada pemborosan waktu untuk mengecek spurious hit. RB_IMPROVED (T, P, d, q) n = T.length m = P.length h = dm-1 mod q p =0 t0 = 0 Q=0 pq = 0 m-1 h=d mod q for i = 1 to m // preprocessing p = (dp + P[i]) mod q t0 = (dt0 + T[i]) mod q for s = 0 to n – m Q=T{s+1..........s+ m] div q If ( ts = p and Q = pq) // matching print “Pattern occurs with shift” s if s < n – m ts+1 = (d(ts - T[s + 1] h) + T[s + m + 1]) mod q
2.9
Pengukuran Nilai Similarity Mengukur similarity (kemiripan) 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 aplikasi, salah satunya adalah sistem deteksi plagiat. Penggunaan ukuran similarity yang tepat tidak hanya meningkatkan kualitas pilihan informasi tetapi juga membantu mengurangi waktu dan biaya proses (Zaka, 2009). Kosinov (2001) menyarankan untuk mengaplikasikan Dice's Similarity Coefficient dalam penghitungan nilai similarity yang menggunakan pendekatan k-gram. K*C
S=
(A + B)
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.
3.
Analisis
3.1
Analisis Masalah Kegiatan plagiat dokumen teks adalah satu hal yang penting untuk diperhatikan.
Berbagai macam cara telah ditawarkan sebagai solusi dari permasalahan ini, baik yang berefek jangka panjang maupun jangka pendek. Salah satunya adalah sistem deteksi plagiat. Jika selama ini mayoritas penanganan plagiat dilakukan secara manual, yang
10
selain menyita banyak waktu, tingkat ketelitian dan objektivitasnya juga relatif, sistem deteksi plagiat menawarkan hasil yang sebaliknya. Terlepas dari apakah sistem yang dibangun sudah dapat mengenali jenis plagiat lain yang tidak hanya copy-paste. Semua itu perlu kerjasama untuk pengembangan lebih lanjut sehingga sistem deteksi plagiat dapat bekerja lebih canggih sesuai tuntutan permasalahan. Tahap perancangan memutuskan bagaimana sistem akan berjalan, dalam hal hardware, software, dan infrastruktur jaringan; user interface, form dan laporan; spesifik program, database, serta dokumen-dokumen yang akan dibutuhkan. Meskipun sebagian besar keputusan strategis tentang sistem telah dibuat pada saat pembangunan konsep sistem selama tahap analisis, langkah-langkah pada tahap perancangan menentukan bagaimana tepatnya sistem akan berjalan (Alan Dennis, dkk, 2009).
Gambar 3. 1 Skema aliran data pada sistem Sistem deteksi plagiat secara umum dirancang untuk dapat mendeteksi kemiripan isi pada dokumen teks, yang dimungkinkan kemiripan ini adalah hasil plagiat. Inputan sistem diperoleh dari file/dokumen (dalam hal ini file berupa plain text) yang diupload oleh user. Dokumen yang diupload otomatis akan tersimpan dalam database sistem, kemudian dokumen dibaca untuk mendapatkan informasi berupa id file, judul, penulis, jumlah kata, dan ukuran file. Selanjutnya dokumen akan melewati tahap preprocessing menggunakan text mining sebelum dibandingkan dengan dokumen-dokumen yang ada pada database sistem. Tahap ini terdiri dari tokenizing (memecah kalimat ke dalam potongan kata sekaligus mengubah huruf dalam dokumen menjadi huruf kecil/lowercase), filtering (membuang stopword/ kata yang tidak deskriptif), dan stemming (mengembalikan setiap kata ke bentuk dasarnya). Setelah itu, dokumen hasil preprocess akan melewati tahap processing menggunakan algoritma Rabin Karp. Tahap ini adalah tahap pencocokan dokumen. Tahap ini terdiri dari parsing K-gram (memecah kata ke dalam potongan karakter sebanyak k), hashing (mengubah potongan karakter k ke dalam nilai hash), dan string matching (pencocokan string hasil hashing).
11
Hasil pencocokan string kemudian dihitung nilai similarity nya menggunakan Dice's Similarity Coefficient, yang kemudian nilai tersebut diubah ke dalam bentuk prosentase similarity.
Gambar 3. 2 Arsitektur sistem 3.2
Perancangan Proses System
input dokumen
<
>
cek originality
<> User
laporan originality
<<extend>>
detail laporan
Gambar 3. 3 Use case diagram
12
1.
Use case deskripsi Tabel 3. 1 Tabel Use case
Nama Use Case
Input File
Aktor
User
Stakeholders dan Interests
User ingin mengecek keaslian file dengan menginput file terlebih dahulu
Deskripsi Singkat
Use case ini mendeskripsikan bagaimana User dapat mengecek keaslian file yang diinputkan
Trigger
User mengunjungi website PDS
Relationships: Extend
Cek Originality, Laporan originality, Detail laporan
Normal Flow of Events User
System
1. Masuk ke halaman utama website 2. Memilih menu Cek Originality 3. Menampilkan halaman Upload File 4. Input data file 5. Klik tombol Submit 6. Menyimpan file dan menampilkan halaman konfirmasi 7. Klik Cek Originality 8. Mengecek originality dan menampilkan laporan dalam bentuk prosentase similarity 9. Klik pada prosentase similarity 10. Menampilkan laporan dalam bentuk detail similarity 11. Klik Download 12. Mengunduh file Alternate/exceptional Flows User
System
9a. Klik Upload File lain 11a-1. Klik Print 11a-2. Mencetak file 11a-3. Klik Lihat Teks Penuh 11a-4. Menampilkan teks sumber
13
PreProcess:preProcess
ProcessMining:processMining
ProcessRabin:processRabin
PostProcess:postProcess
: User 1 : inputFile(id_file, judul, penulis, namafile) 2 : bacaFile() 3 : tampil info file, jmlkata, ukfile 4 : pilih cek originality
5 : tokenizing() 6 : filtering() 7 : stemming() 8 : parsingKgram()
9 : hashing() 10 : stringMatching() 11 : similarity()
12 : tampil lap similarity
opt
13 : uploadFile
14 : tampil form upload file 15 : detailSimilarity() 16 : tampil detail similarity
17 : lihatTeksSumber() 18 : teks sumber 19 : downloadPdf() 20 : download Pdf 21 : cetak() 22 : cetak file
Gambar 3. 4 Sequence diagram 3.3
Perhitungan Manual Berikut contoh perhitungan manual dalam pengecekan dua buah file.
File 1 : Dokumen akan dilakukan pengecekan kemiripan. File 2 : Mengecek kemiripan dokumen. Hasil tokenizing, filtering, dan stemming : File 1 : dokumenlakuecekmirip File 2 : ecekmiripdokumen
14
Tabel 3. 2 Hasil parsing k-gram
Ket. :
No
Parsing File 1
1
doku
Hash
Parsing File 2 ecek
2
okum
cekm
3
kume
ekmi
4
umen
kmir
5
menl
miri
6
enla
irip
7
nlak
ripd
8
laku
ipdo
9
akue
pdok
10
kuec
doku
11
uece
okum
12
ecek
kume
13
cekm
umen
14
ekmi
15
kmir
16
miri
17
irip
Hash
K-gram = 4 Modulo = 101
Berikut adalah penghitungan nilai hash : doku
3
2
1
0
= (100*10 ) + (111*10 ) + (111*10 ) + (111*10 ) = 100,000 + 11,100 + 1,070 + 117 = 112,287
okum
Mod
= 112,287 mod 101 =76
Rem
= 112,287 / 101 = 1111.7524752475 3
2
1
0
= (111*10 ) + (107*10 ) + (117*10 ) + (109*10 ) = 111,000 + 10,700 + 1,170 + 109 = 122,979 Mod
= 122,979 mod 101 = 62
Rem
= 122,979 / 101 = 1217.6138613861
… Perhitungan ini dilakukan untuk seluruh parsing file 1 dan file 2, sehingga menghasilkan hashing modulo dan remainder untuk seluruh substring. Kemudian nilainilai tersebut akan dicocokkan menggunakan string matching dan dilakukan pembobotan menggunakan Dice's Similarity Coefficient.
15
Tabel 3. 3 Hasil penghitungan modulo dan remainder (hasil bagi) File 1 No
File 2
Parsing
Hashmod
Remainder
Parsing
Hashmod
Remainder
Match no
1
doku
76
1111,752475
ecek
8
1109,07921
…
…
…
…
…
…
…
…
10
doku
76
1111,752475
doku
76
1111,75248
yes
11
okum
62
1217,613861
okum
62
1217,61386
yes
12
kume
4
1187,039604
kume
4
1187,0396
yes
13
umen
43
1277,425743
umen
43
1277,42574
yes
14
ecek
8
1109,079208
ecek
8
1109,07921
yes
15
cekm
88
1091,871287
cekm
88
1091,87129
yes
16
ekmi
78
1117,772277
ekmi
78
1117,77228
yes
17
kmir
86
1178,851485
kmir
86
1178,85149
yes
18
miri
50
1195,49505
miri
50
1195,49505
yes
19
irip
99
1163,980198
irip
99
1163,9802
yes
…
…
…
…
…
…
…
…
Similarity
= ((10*2) / (17+13)) * 100% = (20 / 30) * 100% = 2/3 * 100% = 66.67%
4. 4.1
Hasil Penelitian dan Pembahasan Hasil uji berdasarkan banyaknya konten file Tabel 4.1 berikut adalah informasi file yang akan digunakan untuk pengujian pada
tabel 4.2 dan tabel 4.3. File uji terdiri dari empat buah file yang masing-masing telah dilakukan penghapusan sebanyak 15%. Tabel 4. 1 Informasi file uji No 1 2 3 4
Id 152 153 154 155
Nama 11_File_uji_14_kata.txt 12_File_uji_28_kata.txt 13_File_uji_42_kata.txt 14_File_uji_56_kata.txt
Kata 14 28 42 58
Ukuran (byte) 95 194 316 431
Tabel 4. 2 Hasil uji berdasarkan banyaknya konten file No Uji 147 148 149 150
File 1 11_File_uji_14_kata.txt 12_File_uji_28_kata.txt 13_File_uji_42_kata.txt 14_File_uji_56_kata.txt
File 2 Similarity (%) 10_File_uji_14_kata.txt 100 10_File_uji_14_kata.txt 69 11_File_uji_14_kata.txt 50 12_File_uji_14_kata.txt 44
Waktu (s) 0.213548 -0.139719 0.387906 0.335834
Dari tabel 4.2 diatas dapat diketahui bahwa semakin banyak konten file, maka semakin lama waktu proses.
16
4.2
Hasil uji tanpa menggunakan stemming Tabel 4. 3 Hasil uji tanpa mengunakan stemming No Uji
File 1
File 2
Similarity (%)
Waktu (s)
151 152 153 154
11_File_uji_14_kata.txt 12_File_uji_28_kata.txt 13_File_uji_42_kata.txt 14_File_uji_56_kata.txt
10_File_uji_14_kata.txt 10_File_uji_14_kata.txt 11_File_uji_14_kata.txt 12_File_uji_14_kata.txt
100 67 46 39
0.038528 0.057912 0.061899 0.084752
Dari tabel 4.3 diatas dapat diketahui bahwa tanpa menggunakan stemming akan mempercepat waktu proses, tetapi akurasi yang similarity nya rendah. 4.3
Hasil uji modulo pada algoritma Rabin-Karp File yang digunakan untuk pengujian modulo dan k-gram adalah file 1 dan 2 pada
tabel 4.1. Tabel 4. 4 Hasil uji modulo No Uji 159 161 163 164 165 166 167 168
Berdasarkan
Kgram 1 1 1 1 1 1 1 1
tebel
4.4
Modulo 13 23 43 71 101 151 173 251
Similarity (%) 523.944 523.944 523.944 523.944 523.944 523.944 523.944 523.944
diatas dapat
disimpulkan
Waktu (s) 0.871916 0.153122 0.175531 0.209635 0.093315 0.151603 0.125665 0.177291
bahwa
modulo tidak
berpengaruh pada prosentase similarity, tapi berpengaruh pada waktu proses. 4.4
Hasil uji k-gram pada algoritma Rabin-Karp Tabel 4. 5 Hasil uji k-gram No Uji 172 173 174 175 176 177 178
Kgram 1 2 3 4 5 6 7
Modulo 101 101 101 101 101 101 101
Similarity (%) 523.944 128.571 71.0145 69.1176 68.6567 68.1818 67.6923
Waktu (s) 0.045441 0.105267 0.101174 0.020179 0.150793 0.183669 0.235006
Berdasarkan tabel 4.5 dapat diketahui bahwa semakin kecil k-gram, akurasi similarity nya semakin tinggi.
17
5.
Kesimpulan dan Saran
5.1
Kesimpulan Berdasarkan
percobaan-percobaan
yang
telah
dilakukan,
dapat
ditarik
kesimpulan sebagai berikut: 1. Sistem dalam membandingkan file memberikan hasil berupa prosentase similarity. 2. Berikut faktor yang mempengaruhi performa algoritma Rabin Karp : a. Semakin banyak konten sebuah file, waktu prosesnya (running time) akan semakin lama. b. Penggunaan stemming berpengaruh pada keakuratan nilai similarity dan waktu proses. Dengan menggunakan stemming waktu proses cenderung lebih lama, tetapi tingkat akurasi similaritynya lebih tinggi. c. Nilai modulo berpengaruh pada waktu proses, tetapi tidak pada nilai similarity. d. Semakin kecil k-gram menghasilkan akurasi nilai similarity yang lebih baik, dibandingkan k-gram yang lebih besar. 5.2
Saran Berikut saran-saran untuk penelitian lebih lanjut:
1. Sistem dapat membandingkan file uji dengan semua file sumber pada database sistem. 2. Jika masih menggunakan algoritma Rabin-Karp, lebih dibenahi pada tahap stemming agar hasil pencocokannya lebih akurat. 3. Sistem dapat mengkonversi dokumen teks dengan ekstensi lain seperti .doc dan .pdf, untuk kemudahan pengguna. 4. Sistem diharapkan dapat mendeteksi sinonim dan berbagai bentuk plagiat.
18
Daftar Pustaka Atmopawiro, Alsasian.2006. Pengkajian dan Analisis Tiga Algoritma Efisien Rabin-Karp, Knuth-Morris-Pratt, dan Boyer-Moore dalam Pencarian Pola dalam Suatu Teks. Makalah tidak Terpublikasi. Program Studi Teknik Informatika Institut Teknologi Bandung. Cormen, Thomas H, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press, USA. Dennis, Alan. Haley, Barbara Wixom, David Tegarden. 2009. System Analysis Design UML Version 2.0 An Object-Oriented Approach Third Edition. John Wiley & Sons, Inc. USA. Feldman, Ronen, James Sanger. 2007. The Text Mining Handbook. Cambridge University Press. Gipp, Bela, Norman Meuschke. 2011. Citation Pattern Matching Algorithms for Citationbased Plagiarism Detection: Greedy Citation Tiling, Citation Chunking and th
Longest Common Citation Sequence. Proceeding of the 11 ACM Symposium on Document Engineering. Mountain View, CA, USA. Information
Retrieval
Tutorial
:
Stemming
Porter
untuk
Bahasa
Indonesia.
“http://kabulkurniawan.com/2012/03/17/information-retrieval-tutorial-stemmingporter-untuk-bahasa-indonesia/” diakses Selasa, 3 juli 2012 jam 10.49 wib. KBBI 1997, 775. Kosinov, Serhiy. 2001. Evaluation of n-grams conflation approach in text-based information retrieval. Unpublished journal. Computing Science Department, University of Alberta, Canada.
Lecroq. Thierry, Christian Charras. 2006. Handbook of Exact String-Matching Algoritms.
http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
didownload Sabtu, 19 Mei 2012 jam 08.21 wib Lukashenko, Romans, Vita Graudina, Janis Grundspenkis. 2007. Computer-Based Plagiarism Detection Methods and Tools: An Overview. International Conference on Computer Systems and Technologies – CompSysTech’07. Mooney, Raymond J. 2006. CS 391L: Machine Learning Text Categorization. Lecture slides. University of Texas at Austin. Munir, Rinaldi. 2004. Bahan Kuliah IF2251 Strategi Algoritmik : Algoritma Pencarian String (String Matching). Departemen Teknik Informatika. ITB Bandung. Rabin Karp Matching. http://www.cedarville.edu/ personal/ personalpages/ shomper/ cs3410_web/ resources/ rabin_karp_matching.ppt diakses Senin, 5 November 2012 jam 14.12 wib.
19
Similarity
Measure.
“http://yudiagusta.wordpress.com/2008/05/13/similarity-measure/”
diakses Kamis, 7 Maret 2013 jam 21.52 wib. Singh, Rajender Chillar, Barjesh Kochar. 2008. RB-Matcher: String Matching Technique. World Academy of Science, Engineering and Technology 42. Stein, Benno, Sven Meyer zu Eissen. 2006.
Selected Papers from the 29th Annual
Conference of the German Classification Society (GfKl) Magdeburg: Near Similarity Search and Plagiarism Analysis. ISBN 1431-8814, pp. 430-437, c Springer 2006. Triawati, Candra. 2009. Metode Pembobotan Statistical Concept Based untuk Klastering dan Kategorisasi Dokumen Berbahasa Indonesia. IT TELKOM Bandung. Zaka, Bilal. 2009. Theory and Applications of Similarity Detection Technique. Disertation. Institute for Information Systems and Computer Media (IISCM), Graz University of Technology Austria.
20
