SISTEM PENGUKUR KEMIRIPAN DOKUMEN MENGGGUNAKAN ALGORITMA JARO-WINKLER DISTANCE Yuninda Faranika Mahasiswa Informatika, FT UMRAH,
[email protected] Nerfita Nikentari Dosen Informatika, FT UMRAH,
[email protected] Hendra Kurniawan Dosen Informatika, FT UMRAH,
[email protected]
ABSTRAK Tindakan mengambil sebagian atau seluruh ide seseorang berupa dokumen maupun teks tanpa mencantumkan sumber pengambilan informasi atau sering disebut dengan plagiarisme. Berdasarkan masalah tersebut, maka dibutuhkan adanya sistem yang memudahkan dalam mendeteksi dan mengukur kemiripan antara 2 dokumen. Untuk dapat mengetahui seberapa besar kemiripan antara dokumen satu dengan dokumen lainnya diperlukan perbandingan string antara 2 dokumen secara matematis. Dalam penelitian kali ini akan dibuat sebuah sistem berbasis web untuk menghitung tingkat kemiripan dokumen dengan algoritma yang digunakan penulis adalah algoritma Jaro-Winkler Distance. Nilai yang didapat dari perhitungan di normalisasi sehingga 0 setara dengan tidak ada kemiripan dan 1 adalah sama persis. Semakin besar nilai tersebut, semakin besar tingkat kemiripannya. Dalam pengembangan sistem, menggunakan model sekuensial liniear dengan melakukan pendekatan pada perkembangan perangkat lunak yang sistemik dimulai pada tingkat dan kemajuan sistem pada analysis, design, code, dan test. Pengujian sistem menggunakan beberapa dokumen dan berhasil menerapkan algoritma Jaro-Winkler distance dalam pengukuran kemiripan pada dokumen. Dalam pengecekkan dibutuhkan waktu 90.58989 detik. Sehingga ratarata waktu yang digunakan dalam sebuah pengecekan adalah 6.039326 detik. Cepat dan lambatnya waktu yang digunakan dalam pengecekkan dokumen dipengaruhi oleh size dokumen, tipe dokumen dan kandungan isi dokumen. Kata kunci : plagiarisme, Algoritma Jaro-Winkler distance, sekuensial liniear
ABSTRACT The act of taking a part or all of someone's ideas in the documents or text without acknowledgment of the source or the information’s retrieval is often referred to as plagiarism. Based on these problems, we need to have a system to detect and to measure the similarity between two documents easily. To know how much similarity between document and other document, it is required string comparisons between 2 documents mathematically. In this research, it will be made of a web-based system to calculate the similarity of document using the JaroWinkler Distance algorithm. Values that obtained from the calculation have to be normalized, so that 0 is equivalent to have not similarity and 1 is exactly the same. When the value is high, the degree of similarity will be higher. In developing the system, researcher use the linear sequential model with approach to software systemic development start from level and progress of the systems analysis, design, code, and test. The test system uses multiple documents and successfully implement Jaro-Winkler distance algorithm to measure the document’s similarity. The test system need 90.58989 second. Average time about 6.039326. Slow or fast of processing time is influenced by the size, type and content of the document. Keywords: plagiarism, Jaro-Winkler distance algorithm, sequential linear
1
1.
I. PENDAHULUAN
bagi
Cepatnya
persebaran
informasi
pengukur kemiripan antara 2 dokumen
pengguna
internet.
Cepatnya
berbasis web
persebaran informasi memudahkan orang untuk
Merancang dan membangun sistem
mengetahui
2.
informasi-informasi
secara up-to-date. Internet
Implementasi algoritma Jaro-Winkler Distance dalam pengukuran kemiripan
memberikan
antara 2 dokumen
dampak negatif. Salah satunya adalah
3.
terjadinya tindakan mengambil sebagian
Mengetahui adanya tindakan plagiat terhadap dokumen
atau seluruh ide seseorang berupa dokumen
Penelitian ini diharapkan memiliki manfaat
maupun teks tanpa mencantumkan sumber
sebagai berikut :
pengambilan informasi atau sering disebut
1.
dengan plagiarisme.
Dapat
digunakan
untuk
membantu
pengecekkan kemiripan pada dokumen-
Menurut Tia Septiani Widi (2012),
dokumen.
plagiarisme
adalah
tindakan
2.
Sebagai bahan studi dan pengembangan
penyalahgunaan,
pencurian/perampasan,
lebih lanjut mengenai penelitian dan
penerbitan, pernyataan, atau menyatakan
aplikasi pengukur kemiripan dokumen
sebagai milik sendiri sebuah pikiran, ide,
dengan
tulisan, atau ciptaan yang sebenarnya milik
Distance.
algoritma
Jaro-Winkler
orang lain. Berdasarkan
masalah
tersebut,
II. TINJAUAN PUSTAKA
maka dibutuhkan adanya sistem yang memudahkan
dalam
mendeteksi
2.1 Kajan Terdahulu
dan
Dalam
mengukur kemiripan antara 2 dokumen.
dicantumkan
Untuk dapat mengetahui seberapa besar
beberapa
hasil
ini
akan
penelitian
terdahulu antara lain sebagai berikut :
kemiripan antara dokumen satu dengan
Willy
dokumen lainnya diperlukan perbandingan
Goenawan,
Ronald
Augustinus, Krisantus Sembiring dalam
string antara 2 dokumen secara matematis. Maka penulis
penelitian
penelitiannya di tahun 2009 yang berjudul
mengambil judul yaitu
"Penerapan Algoritma Edit Distance Pada
Sistem Pengukur Kemiripan Dokumen
Pendeteksian Praktik Plagiat" menggunakan
Mengggunakan Algoritma Jaro-Winkler
algoritma Edit Distance dalam pendeteksian
Distance".
dalam tindakan plagiat. Penelitian dilakukan
Berdasarkan uraian latar belakang
dalam ruang lingkup dunia informatika,
penelitian dan perumusan masalah yang
praktik plagiat yang dilakukan dengan cara
telah diuraikan diatas, maka dapat disusun
penyalinan kode program (source code)
tujuan penelitian sebagai berikut :
yang dilakukan ketika ada suatu tugas yang harus diselesaikan oleh mahasiswa. Di
2
kalangan
mahasiswa
informatika,
yang
pengetikan. Hasil dari program pencarian
selalu berinteraksi dengan komputer yang
nama
mempermudah praktik plagiat mengingat
menggunakan Jaro-Winkler Distance ini
adanya
dan
berupa nama-nama yang mempunyai skor /
mengubah teks (copy and paste) dan
nilai dengan batasan tertentu. Nama dengan
fasilitas koneksi yang memungkinkan untuk
nilai tertinggi akan ditampilkan pada urutan
mengakses hasil karya orang lain secara
paling atas, tetapi belum tentu nama yang
bebas melalui internet. Dalam penelitian ini
paling benar dalam proses pencarian.
fasilitas
didapat
bahwa
untuk
menyalin
kompleksitas
pasien
rumah
sakit
dengan
waktu
Penelitian di tahun 2010 oleh Anna
algoritma Edit Distance ini adalah O
Kurniawati, Sulistyo Puspitodjati dan Sazali
(|String1|*|String2|) atau kuadratik O(n2)
Rahman
jika panjang kedua string sama. Algoritma
Algoritma Jaro-Winkler Distance untuk
pemrograman
Membandingkan
dinamis
ini
lebih
baik
daripada algoritma brute force dengan
dengan
judul
"Implementasi
Kesamaan
Dokumen
Berbahasa
Indonesia".
kompleksitas waktu eksponensial O(3 ).
menggunakan
algoritma
Sehingga ia menyimpulkan bahwa algoritma
Distance dalam dalam membandingkan
ini sangat baik untuk diterapkan dalam
kesamaan
dokumen
pendeteksian praktik plagiat
indonesia.
Aplikasi
n
William
E.
Yancey
Mereka Jaro-Winkler
khusus yang
dibuat
telah
algoritma
Jaro-
(2005)
berhasil
melakukan evaluasi pada String Comparator
Winkler
yaitu Jaro-Winkler Distance, Edit Distace,
kinerjanya. Dalam ujicobanya aplikasi dapat
dan Hybrid dengan judul penelitian yaitu "
berjalan dengan baik untuk memeriksa
Evaluating String Comparator Performance
kemiripan dokumen yang identik atau sama
for Record Linkage ". Dari Uji coba yang
seratus persen. Hal ini dikarenakan urutan
dilakukan,
bahwa
kata-kata yang dibandingkan sangat sesuai.
ketiganya
Akan tetapi, saat memeriksa kemiripan
didapatkan
perbandingan
hasil
dengan
menggunakan
berbahasa
Distance
untuk
menghasilkan kinerja yang baik dalam
dokumen
dengan
mengklasifikasikan kesalahan ketik data
berbeda,aplikasi
nama pada Sensus dengan menggunakan
mendeteksi kemiripannya.
mendukung
urutan
ini
tidak
yang mampu
algoritma pada string. Polo
Kartono
(2009)
2.2 Landasan Teori
dengan
penelitiannya yang berjudul " Implementasi Jaro-Winkler
Distance
Metric
2.2.1 Plagiarisme
Untuk
Tia Septiana Widi (2012) menuliskan
Pencocokan String" menggunakan algoritma
bahwa
Jaro-Winkler Distance dalam
penyalahgunaan,
membantu
plagiarisme
adalah
tindakan
pencurian/perampasan,
pencarian nama pasien jika terjadi kesalahan
penerbitan, pernyataan, atau menyatakan
dalam
sebagai milik sendiri sebuah pikiran, ide,
pengejaan
maupun
dalam
3
tulisan, atau ciptaan yang sebenarnya milik orang
lain.
Faktor-faktor
1.
penyebab
plagiarisme adalah
Data teks, seperti essay, artikel, jurnal, penelitian dn sebagainya.
2.
1. Adanya tekanan formal (biasanya didapat
Dokumen teks yang lebih terstruktur seperti bahasa pemrograman.
dari institusi formal yang menekankan perlunya
mencapai
penerbitan
artikel)
prestasi maupun
dalam 2.2.2 Algoritma Jaro-Winkler Distance
informal
Algoritma Jaro-Winkler Distance
(biasanya didapat dari rasa ingin diakui
adalah algoritma pengukur kemiripan antara
oleh komunitas). 2. Keterbatasan seberapa
pengetahuan jauh
mengambil
seseorang
atau
dua string dan sebagian besar digunakan
mengenai
dalam bidang deteksi duplikasi. Algoritma
dapat
menyadur
ini merupakan algortima Jaro Distance yang
hasil
ditemukan oleh Matthew A. Jaro (1989,
penelitian/pemikiran orang lain, serta
1995) yang kemudiaan dikembangkan oleh
konsekuensi-konsekuensi yang timbul
William E. Winkler dan Thibaudeau dengan
baik terhadap plagiator maupun orang-
memodifikasi
orang yang menjadi korbannya.
karya
untuk
prefix kemiripan.
seseorang
Algoritma Jaro-Winkler Distance
maupun sulitnya mengganjar pelaku
memiliki kompleksitas waktu quadratic
plagiarisme karena kompleksitas dari
runtime complexity yang sangat efektif pada
sistem. Adapun
Distance
memberikan bobot yang lebih tinggi untuk
3. Adanya kecenderungan akan sulitnya mempertahankan
Jaro
tipe-tipe
plagiarisme
string pendek dan dapat bekerja lebih cepat
menurut
dari algoritma edit distance. Dasar dari
Parvati Iyer dan Abhipsita Sing, yaitu : 1. Word-forword
plagiarism,
algoritma ini memiliki tiga bagian yaitu:
adalah
menyalin setiap kata secara langsung
1. Menghitung panjang string,
tanpa diubah sedikitpun.
2. Menemukan jumlah karakter yang sama
2. Plagiarism
of
authorship,
adalah
di dalam dua string, dan
mengakui hasil karya orang lain sebagai
3. Menemukan jumlah transposisi.
hasil karya sendiri.
(Anna Kurniawati, Sulistyo Puspitodjati,
3. Plagiarism of ideas, adalah mengakui
Sazali Rahman, 2010)
hasil pemikiran atau ide orang lain.
Pada algoritma Jaro (dj) digunakan
4. Plagiarism of sources, jika seseorang penulis
mengggunakan
penulis
lain
tanpa
kutipan
rumus untuk menghitung jarak antara dua
dari
string yaitu s1 dan s2 adalah sebagai berikut :
mencantumkan
sumbernya. Sistem
pendeteksi
plagiarisme
dapat
dikembangkan untuk :
4
dimana :
Dalam
pengembangan
sistem,
m adalah jumlah karakter yang sama
memilih model sekuensial liniear.
penulis
|s1| adalah panjang string 1 Model
|s2| adalah panjang string 2
sekuensial
linear
melakukan
pendekatan pada perkembangan perangkat
t adalah jumlah transposisi
lunak yang sistemik dimulai pada tingkat
Dua karakter dari s1 dan s2 dianggap mirip
dan kemajuan sistem pada analysis, design,
hanya jika sama dan tidak lebih dari
code, dan test.
IV. PEMBAHASAN Dan pada Algoritma Jaro-Winkler (dw) Sistem
digunakan skala prefix (p) yang memberi
pengukur
kemiripan
dokumen dengan algoritma Jaro-Winkler
awalan pada set string. Dengan rumus
Distance
sebagai berikut :
dikembangkan
menggunakan
bahasa pemrograman berbasis web dan database Mysql. Adapun alur kerja sistem dimana :
ini yaitu sebagai berikut :
dj adalah hasil perhitungan kemiripan string 1.
s1 dan s2 dengan algoritma Jaro Distance
Upload file dokumen berformat .txt,
l adalah panjang karakter yang sama pada
.docx atau .pdf yang akan digunakan
awalan string sebelum ditemukan adanya
untuk melakukan proses pengecekkan
ketidaksamaan dengan batas maksimum
dengan mengisi nama penulis, file
sampai 4 karakter.
dokumen dan keterangan dokumen
p adalah
sehingga dokumen-dokumen yang telah
nilai standar untuk konstanta
di-upload menjadi kumpulan dokumen.
dalam karya Winkler adalah p = 0,1 2.
Nilai perhitungan yang didapat dari 0 hingga
Lakukan
pengecekkan
kemiripan
1. Dengan nilai 0 setara dengan tidak ada
dokumen dengan memilih dokumen 1
kemiripan dan 1 adalah sama persis.
dan dokumen 2 yang akan di cek pada combobox yang telah berisi nama-nama dokumen
III. METODE PENELITIAN
yang
telah
di
upload
sebelumnya. Metode
pengumpulan
data
3.
dilakukan dengan cara mempelajari teori-
berdasarkan
teori berhubungan dengan penelitian yang diangkat
yaitu
mengenai
Tampilkan hasil uji kemiripan dokumen algoritma
Jaro-Winkler
Distance dalam prosentase kemiripan
penerapan
dan waktu yang dibutuhkan dalam
algoritma Jaro-Winkler Distance dan alur
pemrosesan.
pengecekan dokumen dari berbagai sumber-
Sistem ini secara umum dirancang
sumber yang ada seperti buku, artikel, jurnal
untuk dapat mendeteksi kemiripan isi pada
dan situs-situs internet.
5
dokumen
teks,
yang
dimungkinkan
3.
Dokumen uji diambil dari dokumen
kemiripan ini adalah hasil plagiat. Inputan
yang berbeda dengan file format yang
sistem diperoleh dari file/dokumen yang
sama.
diupload oleh user dapat berupa file dengan
4.
Dokumen uji diambil dari dokumen
ekstensi .txt, .docx, maupun .pdf. Dokumen
yang berbeda dengan file format yang
yang diupload otomatis akan tersimpan
berbeda.
dalam database sistem, kemudian dokumen
Aplikasi diuji dengan beberapa dokumen
dibaca untuk mendapatkan informasi berupa
dengan berbagai tingkat kesamaan, baik
id file, penulis, judul, type, ukuran file, dan
melalui dokumen yang telah dipilih maupun
tanggal upload.
secara acak.
Selanjutnya melewati
tahap
dokumen
preprocessing
akan
Jika ada data sampel yang digunakan
sebelum
sebagai
dasar
pengetahuan
untuk
dibandingkan dengan dokumen-dokumen
mengetahui kemiripan antara 2 dokumen
yang ada pada database sistem. Tahap ini
berdasarkan variabel.
terdiri dari tahap pengubahan huruf dalam dokumen menjadi huruf kecil/lowercase,
Diketahui
dan filtering (membuang semua tanda baca).
pengukuran kemiripan dokumen dengan
Kemudian,
dokumen
hasil
Distance.
algoritma
Tahap
ini
pada
sistem
berupa
Sejak zaman pertengahan, universitas telah
Jaro-Winkler adalah
data
algoritma Jaro-Winkler distance
preprocess akan melewati tahap processing menggunakan
inputan
berkembang sebagai institusi tempat kebenaran
tahap
dipertanyakan dan pengetahuan dihasilkan tanpa
pencocokan string-string pada dokumen.
memedulikan
semua
kekangan
sejarah.
Universitas adalah tempat sejarah dibuat, dan
sistem
penentuan misi waktu. Universitas bukan tempat
pengecekkan kemiripan dokumen dengan
seperti lembaga bimbingan belajar ataupun
algoritma Jaro-Winkler Distance dilakukan
persiapan masuk perguruan tinggi yang kamu
Dalam
pengujian
kenal sekarang. . Menghasilkan pengetahuan
4 jenis pengujian terhadap dokumen uji
yang kreatif pada dasarnya merupakan fungsi
yaitu: 1.
2.
paling utama dari institusi pendidikan primer
Dokumen uji diambil dari salah satu
yang kita sebut universitas.
Jadi, bakat yang
kumpulan dokumen tanpa melakukan
sebenarnya ingin dihasilkan universitas bukanlah
perubahan
bakat
apapun dengan file format
fungsional
yang
diinginkan
oleh
yang sama.
masyarakat maupun perusahaan, melainkan bakat
Dokumen uji diambil dari salah satu
inteligensia
kumpulan dokumen tanpa melakukan
melakukan penelitian. Diambil dari buku time of
perubahan
your life karangan rando kim.
apapun dengan file format
dengan
kemampuan
untuk
dokumen berjudul Time of your life dan
yang berbeda.
Your life yang isi dokumen sebagai berikut:
6
Sejak zaman pertengahan, universitas telah
mendapatkan nilai persentase kemiripan
berkembang sebagai institusi tempat kebenaran
sehingga didapat 0.19192 dengan persentase
dipertanyakan dan pengetahuan dihasilkan tanpa
sejumlah 19.192%.
memedulikan
semua
kekangan
sejarah.
Adapun hasil penentuan kesamaan
Menurutku ada tiga hal yang harus kamu raih
data
dengan cara apa pun ketika kamu berada di
Distance
universitas. Ketiga hal itu adalah: pengetahuan, tanggung
jawab,
dan
mimpi
yang
antara
perhitungan
secara
manual
Jaro-Winkler dan
secara
penalaran pada sistem adalah sama.
besar.
Menghasilkan pengetahuan yang kreatif pada
Dengan asumsi sistem berhasil
dasarnya merupakan fungsi paling utama dari
mengimplementasi algoritma jaro-winkler
institusi pendidikan primer yang kita sebut
distance
universitas. Jadi, bakat yang sebenarnya ingin
dokumen dengan beberapa dokumen yang
dihasilkan universitas bukanlah bakat fungsional
telah di-upload. Pengecekkan ini dilakukan
yang
diinginkan
oleh
masyarakat
maupun
untuk
melakukan
dengan ekstensi .docx dengan beberapa dokumen pada database. Dengan jumlah
rando kim.
kedua
dokumen
tersebut
kata 96 pada dokumen Time of your life dan
dapat
62
ditemukan variabel sebagai berikut: -
jumlah karakter dokumen 1
:
:
universitas.
detik. Cepat dan lambatnya waktu yang
Langkah
selanjutnya
menghitung
jarak yang
menggunakan
(dj)
karakter
ditentukan
rumus
digunakan dalam pengecekkan dokumen
adalah
dipengaruhi
pada
persamaan
2.1.
dari
1.
kemiripan dengan nilai sama dengan 1 di
pengecekkan
kemiripan
Sistem ini telah berhasil menerapkan algoritma Jaro-Winkler distance dalam
jumlahkan. Nilai tersebut dibagi dengan
pengukuran kemiripan pada dokumen.
sehingga
2.
didapat nilai kemiripan string yang terdapat
Algoritma
Jaro-Winkler
Distance
memperhatikan susunan string sehingga
diantara kedua dokumen. Nilai kemiripan di 100
penelitian
Distance adalah sebagai berikut.
Selanjutnya nilai hasil yang memiliki
nilai
tipe
dokumen dengan algoritma Jaro-Winkler
dengan menggunakan rumus persamaan 2.3.
dengan
dokumen,
Kesimpulan yang dapat diambil
jarak Jaro yang telah didapat sebelumnya
string
size
V. SIMPULAN DAN SARAN
Jaro-Winkler Distance berdasarkan nilai
perbandingan
oleh
dokumen dan kandungan isi dokumen.
dengan
Perhitungan kemiripan dengan algoritma
kalikan
dokumen
dalam sebuah pengecekan adalah 6.039326
99
karakter
jumlah
pada
Sehingga rata-rata waktu yang digunakan
jumlah karakter dokumen 2
dokumen
kata
Dibutuhkan waktu 90.58989 detik.
96
karakter -
satu
dengan ekstensi .docx dan universitas
penelitian.
Diambil dari buku time of your life karangan
Dari
pengecekkan
pada dokumen berjudul Time of your life
perusahaan, melainkan bakat inteligensia dengan kemampuan
dilakukan
tidak
untuk
7
cocok
digunakan
untuk
3.
membandingkan dokumen yang mirip
VI. DAFTAR PUSTAKA
namun susunannya berbeda.
Abdul Rouf, 2012. Pengujian Perangkat
Sistem ini berhasil membandingkan
Lunak Dengan Menggunakan Metode
kemiripan
White Box Dan Black Box. Semarang:
dengan
algoritma
Jaro-
Winkler Distance pada 3 ekstensi
STMIK HIMSYA
dokumen yaitu .txt, .docx, .pdf. Baik
4.
Agus
Sistem
berbeda.
Diperoleh
Juni
Dalam
melakukan
dari
kemiripan dokuemen algoritma jaro-
ologi-pengembangan-sistem-informasi
distance
yang
Anna Kurniawati, Sulistyo Puspitodjati,
dibutuhkan bergantung pada banyak
Sazali Rahman, 2010. Implementasi
konten sebuah file, size, type.
Algoritma
penelitian
waktu
pengecekkan
untuk
kemiripan
Jaro-Winkler
Membandingkan
Dokumen
Distance Kesamaan
Berbahasa
Indonesia.
Depok: Universitas Gunadarma Kartono,
P.
2009. Implementasi
Jaro-
Distance
Untuk
Sistem ini telah berhasil menerapkan
winkler
algoritma Jaro-Winkler distance dalam
Pencocokan
pengukuran kemiripan pada dokumen.
Universitas Kristen Duta Wacana.
Algoritma
Jaro-Winkler
Metric
String.
Yogyakarta:
Distance
Tia Septiana Widi, 2012. Plagiarisme.
memperhatikan susunan string sehingga
Diperoleh pada 17 Desember 2013
tidak
dari
cocok
digunakan
untuk
membandingkan dokumen yang mirip
http://tiaseptianawidi.blogspot.com/20
namun susunannya berbeda.
12/02/plagiarisme.html
Sistem ini berhasil membandingkan kemiripan
dengan
algoritma
William E. Yancey, 2005. Evaluating String
Jaro-
Comparator Performance for Record
Winkler Distance pada 3 ekstensi
Linkage. Amerika Serikat: Statistical
dokumen yaitu .txt, .docx, .pdf. Baik
Research
dengan ekstensi yang sama maupun
Bureau.
berbeda. 4.
2014
http://sisfo08.blog.com/2011/10/metod
Distance adalah sebagai berikut.
3.
24
Informasi.
pengecekkan
dokumen dengan algoritma Jaro-Winkler
2.
Metodologi
Pengembangan
Kesimpulan yang dapat diambil
1.
2011.
dengan ekstensi yang sama maupun
winkler
dari
Bongsu,
Dalam
Willy melakukan
pengecekkan
Division
Goenawan,
Algoritma
winkler
Pendeteksian
waktu
Ronald
Census
Augustinus,
Krisantus Sembiring, 2005. Penerapan
kemiripan dokuemen algoritma jarodistance
U.S.
yang
dibutuhkan bergantung pada banyak
Edit
Distance Praktik
Pada Plagiat.
Bandung: Institut Teknologi Bandung
konten sebuah file, size, type.
8
