PENERAPAN ALGORITMA SMITH-WATERMAN DALAM SISTEM PENDETEKSI KESAMAAN DOKUMEN Farid Bangkit Djafar1, Agus Lahinta2, Lillyan Hadjaratie3
Intisari Plagiarisme atau tindakan memalsukan hasil tulisan orang lain bisa dilakukan oleh siapa saja, dan dapat merugikan penulis aslinya. Namun, banyak yang tidak peduli dengan tindakan tersebut. Padahal pelanggaran hak cipta telah diatur dalam Undang-Undang Republik Indonesia Nomor 19 Tahun 2003. Agar tindakan ini tidak meluas, maka diperlukan sebuah sistem yang bisa mendeteksi kesamaan dari tulisan atau dokumen. Penelitian ini bertujuan menerapkan algoritma SmithWaterman dalam sistem pendeteksi kesamaan dokumen. Algoritma ini sudah dikenal luas dalam bidang bioteknologi untuk pendeteksian kesamaan DNA. Algoritma ini akan membandingkan dua dokumen dalam sebuah matriks. Dari matriks ini, nantinya akan dilakukan traceback untuk mencari letak kesamaan dan apakah terdapat penghapusan dan penyisipan dari dokumen aslinya. Hasil yang akan didapat oleh pengguna adalah seberapa besar persentasi dari kesamaan dokumen dan menunjukkan kepada pengguna letak kesamaannya. Algoritma ini berhasil diterapkan untuk sistem pendeteksian kesamaan dokumen, hanya saja tidak cocok digunakan untuk perbandingan dokumen dengan data yang lebih besar dan diperlukan waktu yang agak lama untuk mendapatkan hasil pendeteksian dari kedua dokumen yang dibandingkan. Kata Kunci : Plagiarisme, Smith-Waterman, Deteksi kesamaan dokumen
1.
Pengantar Seiring berjalannya zaman, teknologi pun berkembang menjadi semakin
canggih. Dapat mengubah berkas yang awalnya harus ditulis atau diketik ke dalam lembaran kertas menjadi sebuah teknologi berupa data komputer yang disebut sebagai dokumen digital yang bisa dicetak untuk keperluan tertentu atau digunakan sebagai data yang akan digunakan di masa yang akan datang. 1
Mahasiswa Jurusan Teknik Informatika, Prodi Sistem Informasi UNG Dosen Fakultas Teknik, Teknik Informatika, Prodi Sistem Informasi UNG 3 Dosen Fakultas Teknik, Teknik Informatika, Prodi Sistem Informasi UNG 2
Akan tetapi dokumen digital ini bisa disalin sewaktu-waktu ke komputer atau user lain untuk keperluan tertentu yang dapat menguntungkan dirinya sendiri. Plagiarisme merupakan salah satu tindakan yang sering dilakukan orang-orang dalam mencari keuntungan dari dokumen digital tersebut. Dikutip dari tulisan Indriyanto, menurut Adimihardja (2005), Plagiarisme adalah pencurian dan penggunaan gagasan atau tulisan orang lain (tanpa cara-cara yang sah) dan diakui sebagai miliknya sendiri. Dengan plagiarisme, maka dapat merugikan pemilik sah dari sebuah laporan atau penelitiannya. Setiap dokumen buatan setiap orang yang melakukan plagiat akan susah dikenali tanpa adanya sistem yang dapat mengenali kesamaan dokumen tersebut. Berdasarkan permasalahan diatas maka penulis membatasi ruang lingkup permasalahan, yaitu sistem menggunakan algoritma Smith-Waterman, Hanya menguji data berupa teks yang memiliki ekstensi (.txt) ,(.doc) dan (.pdf) , dan mengabaikan data berupa gambar atau suara, tabel, dan data yang diuji menggunakan bahasa Indonesia.
Ada beberapa definisi menurut para ahli lainnya (dalam Novanta, 2009), yaitu : 1. Menurut Ir. Balza Achmad, M.Sc.E, plagiarisme adalah berbuat sesuatu seolah-olah karya orang lain tersebut adalah karya kita dan mengakui hasil karya tersebut adalah milik kita, 2. Menurut Brotowidjoyo, plagiarisme merupakan pembajakan berupa fakta, penjelasan, ungkapan, dan kalimat orang lain secara tidak sah. Algoritma Smith-Waterman merupakan algoritma klasik yang telah dikenal luas dalam bidang bioinformatika sebagai metode yang dapat mengidentifikasi local similarities (penyejajaran sekuens) yaitu proses penyusunan dua local sequences (rangkaian/susunan atau rentetan) nucleotide atau protein sequences sehingga kemiripan antara dua sequence tersebut akan terlihat. Berdasarkan fungsi proses penyejajaran sekuens tersebut, maka algoritma ini dapat dikonversikan ke dalam pemrograman komputer untuk digunakan membantu proses pendeteksian
dokumen teks yang dianggap cenderung plagiat dengan cara melihat kesamaan isi (local similarities) dari beberapa dokumen teks.
Abcbadbca |||||| ||| Ab–b–dbda Gambar 1. Optimal Alignment Dari Dua Substring Algoritma standar Smith-Waterman yang dipakai untuk penghitungan local alignment berdasarkan dokumen dari situs Baylor College of Medicine HGSC adalah (Novanta, 2009) : 1. Menambahkan sebuah nilai pada setiap perbandingan a. Menggunakan nilai positif, apabila memiliki kemiripan. b. Menggunakan nilai negatif, apabila memiliki perbedaan. 2. Inisialisasi awal matriks dengan nilai 0 (nol). 3. Semua nilai yang terdapat dalam matriks apabila lebih kecil dari 0 (nol), maka nilai dianggap 0 (nol). 4. Memulai traceback dari nilai yang tertinggi yang ditemukan dimanapun pada matriks. 5. Penghitungan dilanjutkan hingga skor bernilai 0 (nol).
Penelitian sebelumnya telah dilakukan oleh Audi Novanta (2009) dengan judul Pendeteksian Plagiarisme Pada Dokumen Teks Dengan Menggunakan Algoritma Smith-Waterman. Dari penelitian ini disimpulkan bahwa Algoritma Smith-Waterman memiliki keakuratan yang lebih baik pada saat membandingkan dokumen yang mengandung perubahan struktur kalimat khususnya dalam paragraf ketimbang perubahan struktur kata di dalam kalimat. Penelitian lain mengenai sistem pendeteksi plagiarisme juga telah dilakukan oleh Novian, dkk. (2012), dengan menggunakan algoritma Rabin-Karp. Judul yang digunakan dalam penelitiannya
yaitu Aplikasi Pendeteksian Plagiat Pada Karya Ilmiah
Menggunakan Algoritma Rabin-Karp. Aplikasi yang dibuat menggunakan
Microsoft Visual C++, dan modifikasi dari algoritma pencocokan string RabinKarp. Untuk pengembangan sistem yang lebih baik, penulis akan mengembangkan sistem yang menggunakan algoritma Smith-Waterman yang mampu melakukan perbandingan dokumen bukan hanya terbatas pada tipe data .txt, akan tetapi bisa digunakan untuk pembacaan dokumen bertipe .doc, .pdf, dan juga disertai kemampuan untuk menampilkan letak kesamaan dari kedua dokumen.
2.
Metodologi Penelitian Metode yang digunakan pada penelitian ini adalah Metode Eksperimen.
Menurut Riduwan (2010), penelitian dengan pendekatan eksperimen adalah suatu penelitian yang berusaha mencari pengaruh variabel tertentu terhadap variabel yang lain dalam kondisi yang terkontrol secara ketat. Dengan pendekatan ini, peneliti dapat menemukan hubungan sebab akibat dikarenakan peneliti dimungkinkan untuk melakukan perlakuan terhadap penelitian. Adapun tahapan penelitian yang akan dilakukan oleh penyusun dalam penelitian dengan menggunakan tahapan SDLC yaitu waterfall, adalah sebagai berikut :
Persiapan & Pengumpulan Data
Wawancara
Kepustakaan Analisis Sistem Perancangan Sistem Implementasi Sistem Testing & Evaluasi Sistem
Menyusun Laporan Gambar 2. Tahapan Penelitian
3.
Hasil dan Pembahasan
3.1. Hasil 3.1.1. Analisis Permasalahan Penelitian ini akan menjelaskan pembuatan sebuah sistem pendeteksi kesamaan dokumen dengan menggunakan algoritma Smith-Waterman. Sistem yang dibutuhkan dalam pendeteksian kesamaan dokumen tentunya harus bisa menerima masukkan dokumen dengan beberapa tipe diantaranya adalah yang bertipe Text Files dengan ekstensi (.txt), Word Documents yang berekstensi (.doc), dan Portable Document Format dengan ekstensi (.pdf), dan menampilkan hasil dari perbandingan.
3.1.2. Analisis Kebutuhan Sistem 1. Sistem mampu menerima file yang memiliki ekstensi (.txt), (.doc), dan (.pdf) 2. Sistem dapat menerima masukan file lebih dari 1. 3. Sistem dapat menerima masukan file dari lokasi mana saja yang ada di komputer. 4. Sistem dapat menampilkan hasil perbandingan dokumen. 5. Sistem dapat digunakan pada komputer dengan sistem operasi Microsoft Windows.
3.1.3. Perhitungan Bobot Dalam mendapatkan local similarities dan bobot kesamaan kata dari dua dokumen, maka diperlukan beberapa tahap. Adapun tahap-tahapnya adalah sebagai berikut : 1.
Input Dokumen Dokumen yang bisa diinput ke dalam sistem adalah 3 ekstensi file. Tipe
dokumen tersebut adalah ekstensi Plain Text (.txt), Word Document (.doc), dan Portable Document Format (.pdf).
2.
Konversi Huruf Untuk membuat sistem mampu menyamakan tiap karakter dari dokumen 1
dengan dokumen lainnya, maka semua huruf dalam kalimat atau kata dari tiap dokumen perlu diubah menjadi huruf kecil. 3.
Tokenisasi Proses Tokenisasi yaitu proses untuk membagi kalimat menjadi token-token
atau bagian-bagian terkecil. Karakter spasi dan karakter lain berupa tanda baca pun dipisahkan. Adapun beberapa tanda baca yang dipisahkan adalah koma (,), titik (.), titik dua (:), garis miring (/), tanda tanya (?), dan tanda garis/pisah (-). Tanda baca dipisahkan guna memisahkan kata dari karakter tanda baca. 4.
Stop Words Removal Stop Words adalah kata-kata yang disaring sebelum, atau sesudah
pengolahan data teks. Dalam mesin pencarian, kata-kata umum (common words) yang sering digunakan akan dimasukkan ke dalam daftar Stop Words. Stop Words untuk bahasa Inggris diantaranya ‘of’, ‘the’, sedangkan untuk bahasa Indonesia diantaranya ‘yang’,’di’,’ke’. Penghapusan kata-kata Stop Words ini dimaksudkan untuk lebih mempermudah sistem dalam pembandingan dokumen. 5.
Algoritma Smith-Waterman Berikut adalah cara kerja dari algoritma Smith-Waterman dalam
menemukan kesamaan dari dua DNA : DNA Sequence 1 = AGCAA
Nilai Match = +2
DNA Sequence 2 = ATGCA
Nilai Mismatch = -1 Nilai Gap = -1
Langkah awal dari algoritma Smith-Waterman adalah mendefinisikan nilai 0 pada matriks di titik (0,0), (i,0), dan (0,j). Kemudian dilakukan perhitungan pada titik (1,1). Apabila DNA i sama dengan DNA j, maka akan digunakan nilai match. Sebaliknya, apabila DNA dari kedua sequence berbeda, maka akan digunakan nilai mismatch.
0 H(i-1,j-1) + Nilai Match/Mismatch
H(1,1) = maks.
H(i-1,j) + Nilai Gap H(i,j-1) + Nilai Gap
0 0+2=2
H(1,1) = maks.
0 + -1 = -1 0 + -1 = -1
Gambar 3. Penentuan nilai pada titik (1,1)
bisa dilihat bahwa DNA dari i dan dari j memiliki kesamaan, sehingga menggunakan nilai match. Nilai yang paling besar adalah 2, maka nilai pada titik (1,1) adalah 2. Perhitungan pada titik selanjutnya ditentukan dengan cara yang sama seperti pada titik (1,1).
-
A
G
C
A
G
-
0
0
0
0
0
0
A
0
2
1
0
2
1
T
0
1
1
0
1
1
G
0
0
3
2
1
3
C
0
0
2
5
4
3
G
0
0
2
4
4
6
Gambar 4. Nilai Matriks dari dua pasangan DNA
Setelah dilakukan perhitungan dalam matriks, kemudian dilakukan traceback dari nilai tertinggi dalam matriks, yaitu dari titik (5,5). Hasil dari traceback yang dilakukan pada matriks adalah sebagai berikut.
-
A
G
C
A
G
-
0
0
0
0
0
0
A
0
2
1
0
2
1
T
0
1
1
0
1
1
G
0
0
3
2
1
3
C
0
0
2
5
4
3
G
0
0
2
4
4
6
Gambar 5. Traceback pada matriks
Dari traceback tersebut bisa ditentukan local similarities. Local Similarities dari kedua DNA tersebut adalah :
Sequence 1 = A- GCAG Sequence 2 = ATGC - G
Gambar 6. Local Similarities dari dua sequence DNA
6.
Perhitungan Bobot Dari Local Similarities, kita bisa menghitung bobot kesamaan. Dari satu
alignment tersebut terdapat 4 karakter yang sama dari total karakter masingmasing dokumen adalah 5 karakter, maka hasilnya adalah (((4/5) + (4/5)) x 100) / 2 = 80. Jadi, dapat disimpulkan dari kedua sequence DNA tersebut terdapat kecocokan 80%. Dalam pengujian sistem, program diberi masukan beberapa dokumen contoh untuk dibandingkan. Isi dari tiap dokumen memiliki beberapa kesamaan dan perbedaan. Isi dari dokumen contoh disajikan pada tabel berikut.
Tabel 1. Dokumen Contoh No. Dokumen
Isi Dokumen
1.
D1
2.
D2
3.
D3
4.
D4
5.
D5
Pada zaman dahulu di suatu tempat di tanah U Duluo lo’u Limo lo Pohite, hiduplah seorang pemuda bernama Lahilote. Perawakannya tegap, badan tinggi besar dan mempunyai kegemaran berburu. Dengan pekerjaan mengejar binatang buruan itu memaksa ia sering moleleyangi (mengembara masuk hutan keluar hutan). Pada zaman dahulu, di suatu tempat di tanah U Duluo Lo'u Limo Lo Pohite, hiduplah seorang pemuda bernama Lahilote. Perawakan tegap,badan tinggi besar dan suka berburu. Dengan pekerjaan mengejar binatang buruan, ia sering moleleyangi (mengembara masuk keluar hutan). Alkisah, pada jaman dahulu kala di hulu sungai dekat sebuah mata air sebuah dusun terpencil di Gorontalo tinggallah seorang pemuda sederhana bernama Lahilote yang sering mencari rotan di hutan sebagai mata pencahariannya. Hiduplah seorang pemuda bernama Lahilote. Kegemarannya berburu di hutan dan moleleyangi (mengembara). Suatu hari, saat sedang berburu di hutan, dia melihat putri-putri kahyangan yang sedang mandi di kolam yang ada di hutan tempat Lahilote berburu, dia berniat memperistri salah satu dari putri-putri kahyangan tersebut. Alkisah, di Tanah U Duluo Lo'u Limo Lo Pohite, Gorontalo, ada seorang pemuda tampan dan gagah bernama Piilu Le Lahilote, yang akrab dipanggil Lahilote. Ia tinggal di sebuah rumah kecil di pinggir hutan. Untuk memenuhi kebutuhan hidupnya, setiap hari ia moleleyangi (mengembara masuk keluar hutan).
Hasil pengujian dari dokumen contoh diatas, adalah sebagai berikut : Tabel 2. Hasil Pengujian Dokumen Contoh Dokumen
D1
D2
D3
D4
D5
D1
100 %
87%
12%
12%
20%
D2
87%
100%
13%
13%
23%
D3
12%
13%
100%
12%
9%
D4
12%
13%
12%
100%
5%
D5
20%
23%
9%
5%
100%
Berdasarkan dari pengujian yang telah dilakukan sebelumnya, maka dapat disimpulkan beberapa kelebihan dan kekurangan yang bisa didapat dari penggunaan algoritma Smith-Waterman. Kelebihan dari algoritma ini adalah :
1. Algoritma Smith-Waterman ini bisa digunakan untuk menemukan letak kesamaan dari kedua dokumen yang dibandingkan. 2. Mampu menemukan letak terjadinya penghapusan atau penyisipan kata pada dokumen. Dan juga kelemahan dari algoritma Smith-Waterman yaitu : 1. Algoritma ini tidak mampu membandingkan dokumen dengan data yang lebih banyak. Dengan data yang lebih banyak, maka waktu yang dibutuhkan pun akan lebih banyak. 2. Perlu digabungkan dengan metode lain guna mendapatkan hasil yang lebih maksimal dan mampu mengefisienkan waktu.
3.2. Pembahasan Algoritma Smith-Waterman dalam penerapan di program ini mampu melakukan pendeteksian kesamaan dari dokumen-dokumen yang memiliki format berkas yang berbeda. Algoritma ini mampu menemukan letak kesamaan dari kedua dokumen yang dibandingkan. Adapun algoritma Smith-Waterman yang digunakan dalam penelitian ini dan program yang dibuat bukanlah sistem yang mampu melakukan justifikasi bahwa dokumen yang memiliki tingkat persentasi kesamaan yang tinggi adalah dokumen yang melakukan plagiat. Dalam proses perbandingan dokumen, algoritma Smith-Waterman ini memiliki kekurangan dalam hal efisiensi waktu. Jumlah kata yang harus dituliskan dalam abstrak adalah 150-200 kata. Dalam membandingkan berkas berisi abstrak yang memiliki jumlah kata berkisar antara 170-an kata, maka program membutuhkan waktu yang cukup lama, yakni sekitaran 10-12 menit untuk menghitung matriks yang dibuat dari algoritma dan menemukan letak kesamaannya. Dari hasil perbandingan dokumen abstrak ini, bisa diperkirakan apabila digunakan dalam membandingkan dokumen laporan penelitian yang utuh, maka akan dibutuhkan waktu yang lebih lama lagi. Algoritma Smith-Waterman ini bisa digunakan dalam membandingkan dokumen, namun alangkah lebih baiknya algoritma ini tetap dipergunakan dalam bioinformatika yaitu dalam menemukan kesamaan DNA.
4.
Penutup
4.1. Kesimpulan 1.
Sistem mampu membandingkan beberapa dokumen dengan berbagai format.
2.
Algoritma Smith-Waterman berhasil diimplementasikan dalam sistem pendeteksi kesamaan dokumen dan mampu menemukan kesamaan antara dokumen satu dengan dokumen lainnya serta menampilkan persentasi kesamaan dari kedua dokumen.
4.2. Saran 1.
Diharapkan dalam pengembangannya, sistem mampu membandingkan dokumen dengan waktu yang lebih cepat sehingga lebih mengefisienkan waktu.
2.
Algoritma
Smith-Waterman
lebih
tepatnya
digunakan
pada
sistem
perbandingan DNA.
Daftar Pustaka 1.
Adimihadja, M. 2005. Plagiarisme. Makalah Disampaikan dalam Lokakarya Etika di Perguruan Tinggi yang Dilaksanakan di Medan pada Tanggal 19—20 April 2005. Fakultas Ekonomi Universitas Sumatera Utara. Medan. (online), (http://staff.unila.ac.id/indriyanto/2012/01/17/plagiarisme/, diakses 3 Oktober 2012)
2.
Novanta, A. 2009. Pendeteksian Plagiarisme Pada Dokumen Teks Dengan Menggunakan Algoritma Smith-Waterman. [Skripsi] tidak diterbitkan. FMIPA Universitas Sumatera Utara. Medan. (http://repository.usu.ac.id/bitstream/123456789/7830/1/09E01594.pdf, diakses 6 September 2012)
3.
Novian, D., Abdillah, T., Tuloli, M.S., Yassin, R.M.T. 2012. Aplikasi Pendeteksian Plagiat Pada Karya Ilmiah Menggunakan Algoritma RabinKarp. Fakultas Teknik Universitas Negeri Gorontalo. Gorontalo.
4.
Riduwan. 2010. Metode & Teknik Menyusun Tesis. Bandung : Alfabeta
