Bab 2 Tinjauan Pustaka 2.1 Penelitian Terdahulu Penelitian mengenai penggunaan metode String Matching salah satunya adalah oleh McCulloch dan Pitts pada Finite automata. Finite automata dapat dinyatakan sebagai model pengenal bahasa. Bahasa yang dikenal finite automata adalah bahasa sederhana. Ada dua macam finite automata yaitu deterministic finite automata dan non deterministic finite automata. Finite automata merupakan alat abstrak yang berguna untuk mengkomputasi suatu string. Sebagai contoh, automata dapat dipakai untuk komputasi biologi yaitu mencocokkan string DNA. Pada artikel ini akan diangkat permasalahan untuk mencocokkan string DNA pada Aves. Salah satu cara untuk mempercepat proses komputasi adalah dengan memperlakukan string sebagai vektor pada algoritma vektor yang dikerjakan oleh finite automata (Yessica Nataliani, 2007). Sedangkan
penelitian
tentang
penggunaan
algoritma
Levensthein adalah oleh Dra. Sulis Janu Hartati, MT dan Soliq, ST ., M.Kom tentang Penerapan Text Mining Pada Aplikasi Penilaian Kinerja Pegawai di BKKBN. Penilaian kinerja untuk setiap pegawai sangat diperlukan oleh perusahaan. Namun masih ada permasalahan yang sering timbul dalam proses penilaian kinerja. Sering kali pegawai kurang puas dengan hasil penilaian
6
7
dari atasan. Hal tersebut disebabkan karena kurang adanya transparansi antara atasan dengan pegawai. Oleh karena itu, diperlukan adanya suatu transparansi dalam penilaian kinerja untuk menghindari masalah-masalah yang muncul karena terjadinya ketidakpuasan dalam penilaian kinerja pegawai dalam suatu perusahaan. Uji coba tugas akhir terhadap pegawai BKKBN Kabupaten Madiun dilakukan dengan memasukkan nilai (Free Text) berupa kalimat sederhana maupun kalimat bertingkat yang diperoleh dari Manager Bagian (Pejabat Penilai) kemudian dilakukan proses sehingga menghasilkan nilai yang berupa angka. Nilai angka tersebut dapat dijadikan ukuran terhadap hasil kinerja pegawai tiap periode di BKKBN Kabupaten Madiun (Prasetyo, 2008). Pada penelitian ini menjelaskan tentang seberapa besar tingkat
kemiripan
judul
dan
abstract
skripsi.
Dengan
menginputkan judul dan abstract maka aplikasi ini akan memberi saran dengan menampilkan skripsi yang serupa atau hampir sama dengan yang diinputkan.
2.2 Plagiarisme Plagiarisme merupakan tindakan menjiplak, mencuri atau mengambil ide, hasil karya atau tulisan orang lain, baik seluruh, sebagian besar maupun sebagian kecil, untuk jadi ide atau karya tulisan sendiri tanpa menyebutkan nama penulis dan sumber aslinya.
8
Ada sejumlah pola umum atau modus operandi yang biasanya dilakukan seorang penulis dalam melakukan plagiasi terhadap karya orang lain maupun karyanya sendiri. Pertama, seorang penulis mengambil tulisan orang lain dan mengklaim sebagai tulisannya sendiri. Kedua, seorang penulis mengambil gagasan orang lain menjadi gagasannya sendiri. Misalnya, dalam suatu diskusi, peserta diskusi mengajukan sejumlah gagasan unik yang menarik. Dalam menulis suatu artikel, penulis yang menjadi narasumber atau peserta diskusi lalu menulis dan menyatakan gagasan itu berasal dari dirinya. Ketiga, mengambil hasil riset orang lain jadi temuannya sendiri. Keempat, mengakuisisi hasil riset atau hasil karya kelompok jadi hasil riset atau hasil karya sendiri. Kelima, menerbitkan kembali hasil tulisannya sendiri yang sudah diterbitkan sebelumnya dalam suatu buku atau jurnal meskipun menyebutkan
sumbernya.
Keenam,
meringkas
dan
memparafrasekan (mengutip tak langsung) suatu pemikiran dari suatu sumber ke dalam karya tulisnya tanpa menyebutkan sumbernya (Lako, 2012). Klasifikasi mengenai plagiarisme dapat dibuat tergantung dari berbagai aspek pandang : –
Dari segi substansi yang dicuri,
–
Dari segi kesengajaan,
–
Dari segi volume/proporsi
9
–
Dari pola pencurian, dapat dilakukan kata demi kata, maupun dapat diseling dari berbagai sumber dan dengan kata-kata sendiri,
–
Ada pula Auto-plagiarism/self-plagiarism. Self-plagiarism terjadi ketika seseorang menggunakan
ulang karya sendiri dari suatu
publikasi sebelumnya tanpa
mencantumkan referensi karya lama ke suatu publikasi yang baru. Jenis plagiarism ini sebenarnya dapat dianggap “ringan”, namun bila dimaksudkan atau di kemudian hari dimanfaatkan misal untuk menambah kredit akademik, maka dapat dianggap sebagai pelanggaran “berat” etika akademik. Terdapat pula jenis plagiarisme lainnya, yakni accidental plagiarism. Sebagai contoh, seorang ibu membacakan sebuah cerita kepada anaknya yang masih kecil secara berkala. Saat dewasa, anak itu membuat tugas atau laporan berdasarkan cerita ibunya tersebut. Jika beberapa orang secara independen menuangkan ide dan analisis yang sama maka hal ini bukan dikatakan sebagai plagiat. Sedangkan plagiarisme dalam penulisan akademik ada dua tipe utama yaitu:
Plagiarisme ide adalah menggunakan ide (misalnya penjelasan, teori, kesimpulan, hipotesis, kiasan) secara keseluruhan atau sebagian, atau dengan pengubahan sedikit tanpa memberi kredit pada penciptanya. Pencipta ide tadi
10
tidak menuliskan idenya di media publikasi yang bisa dirujuk.
Plagiarisme teks.
2.3 Net Beans Pengembangan NetBeans diawali dari Xelfi, sebuah proyek mahasiswa tahun 1997 di bawah bimbingan Fakultas Matematika dan Fisika Universitas Charles, Praha. Sebuah perusahaan kemudian dibentuk untuk proyek tersebut dan menghasilkan versi komersial NetBeans IDE hingga kemudian dibeli oleh Sun Microsystem pada tahun 1999. Sun kemudian menjadikan NetBeans open source pada bulan Juni tahun 2000. Sejak itu komunitas NetBeans terus berkembang. NetBeans mengacu pada dua hal, yakni platform untuk pengembangan aplikasi desktop java, dan sebuah Integrated Development Environment (IDE) yang dibangun menggunakan platform NetBeans. Platform NetBeans memungkinkan aplikasi dibangun dari sekumpulan komponen perangkat lunak moduler yang disebut „modul‟. Sebuah modul adalah suatu arsip Java (Java archive) yang memuat kelas-kelas Java untuk berinteraksi dengan NetBeans Open API dan file manifestasi yang mengidentifikasinya sebagai modul. Karena modul dapat dikembangkan secara independen, aplikasi berbasis platform NetBeans dapat dengan mudah dikembangkan oleh pihak ketiga secara mudah dan powerful.
11
2.4 Bahasa Pemrograman Java Bahasa Java merupakan bahasa pemrograman Object Oriented Programming (OOP) karya Sun Microsystem Inc. Rilis resmi level beta dilakukan pada November 1995. Dua bulan berikutnya
Netscape
menjadi
perusahaan
pertama
yang
memperoleh lisensi bahasa Java dari Sun Microsystem Inc (Hariyanto, 2007). Java dirancang untuk menjadi bahasa yang memiliki kemampuan tinggi dalam hal portabilitas dan pemanfaatan jaringan
tanpa
mengabaikan
kestabilan,
keamanan,
serta
kemudahan dari sisi desain dan pemrograman aplikasi. Java yang semula ditujukan untuk pemprograman applet di web browser telah berkembang menjadi bahasa pemprograman pengembangan aneka ragam aplikasi, mulai dari yang berjalan di handheld devices seperti handphone, PDA (Personal Digital Assistant) sampai aplikasi tersebar skala enterprise di beragam komputer server. Java merupakan bahasa orientasi objek untuk pengembangan aplikasi mandiri, aplikasi berbasis internet, aplikasi untuk perangkat cerdas yang dapat berkomunikasi lewat internet/jaringan komunikasi. Java tidak lagi hanya bahasa untuk membuat applet yang memperindah halaman web tapi Java telah menjadi bahasa untuk pengembangan aplikasi skala enterprise berbasis jaringan besar (Hariyanto, 2007). Sebutan Java 2 diberikan untuk java versi 1.2 dan versi berikutnya. Java 2 terbagi dalam 3 kategori, yaitu:
12
Java 2 Standart Edition (J2SE). Kategori ini digunakan untuk menjalankan aplikasi Java pada level komputer personal. Java
2
Enterprise
Edition
(J2EE).
Kategori
ini
dikhususkan untuk pengembangan aplikasi Java pada lingkungan enterprise/server. Java 2 Micro Edition (J2ME). Kategori ini digunakan untuk
pengembangan
aplikasi
Java
yang
diimplementasikan pada perangkat semacam ponsel, Palm, PDA, dan PocketPC.
2.5 String Matching Pengertian string menurut Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology (NIST) adalah susunan dari karakter-karakter (angka, alfabet atau karakter yang lain) dan biasanya direpresentasikan sebagai struktur data array. String dapat berupa kata, frase, atau kalimat. Pencocokan string merupakan bagian penting dari sebuah proses pencarian string (string searching) dalam sebuah dokumen. Hasil dari pencarian sebuah string dalam dokumen tergantung dari teknik atau cara pencocokan string yang digunakan. Pencocokan string (string matching) menurut Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology (NIST), diartikan sebagai sebuah permasalahan
13
untuk menemukan pola susunan karakter string di dalam string lain atau bagian dari isi teks. Pencocokan string (string matching) secara garis besar dapat dibedakan menjadi dua yaitu : 1
Exact string matching, merupakan pencocokan string secara tepat dengan susunan karakter dalam string yang dicocokkan memiliki jumlah maupun urutan karakter dalam string yang sama. Contoh : kata step akan menunjukkan kecocokan hanya dengan kata step.
2
Inexact string matching atau Fuzzy string matching, merupakan pencocokan string secara samar, maksudnya pencocokan string dimana string yang dicocokkan memiliki kemiripan dimana keduanya memiliki susunan karakter yang berbeda (mungkin jumlah atau urutannya) tetapi string-string tersebut memiliki kemiripan baik kemiripan tekstual/penulisan (approximate string matching) atau kemiripan ucapan (phonetic string matching). Inexact string matching masih dapat dibagi lagi menjadi dua yaitu : a. Pencocokan string berdasarkan kemiripan penulisan (approximate string matching) merupakan pencocokan string dengan dasar kemiripan dari segi penulisannya (jumlah karakter, susunan karakter dalam dokumen). Tingkat kemiripan ditentukan dengan jauh tidaknya beda penulisan dua buah string yang dibandingkan tersebut dan nilai tingkat kemiripan ini ditentukan oleh
14
pemrogram (programmer). Contoh : c mpuler dengan compiler, memiliki jumlah karakter yang sama tetapi ada dua karakter yang berbeda. Jika perbedaan dua karakter ini dapat ditoleransi sebagai sebuah kesalahan penulisan maka dua string tersebut dikatakan cocok. b. Pencocokan
string
berdasarkan
kemiripan
ucapan
(phonetic string matching) merupakan pencocokan string dengan dasar kemiripan dari segi pengucapannya meskipun ada perbedaan penulisan dua string yang dibandingkan tersebut. Contoh step dengan steb dari tulisan berbeda tetapi dalam pengucapannya mirip sehingga dua string tersebut dianggap cocok. Contoh yang lain adalah step, dengan steppe, sttep, stepp, stepe.
2.5.1
Approximate String Matching Dalam metode ini, dilakukan suatu penghitungan perbedaan
antara dua string. Penghitungan tersebut meliputi tiga operasi string yaitu operasi penghapusan, operasi penyisipan dan operasi penggantian. Untuk contoh yang akan digunakan, diasumsikan S adalah string sumber pencarian dan T adalah string yang ingin dicari.
Operasi Penghapusan Misalnya S = memori dan T = meri. Penghapusan dilakukan
untuk karakter m pada lokasi ke-3 dan o pada lokasi ke-4. Dua
15
operasi penghapusan tersebut menunjukkan transformasi S ke T yang diilustrasikan pada Rumus 2.1. 1 2 3 4 5 6 T=m e - - r i S=m e m o r i Rumus 2.1 Operasi Penghapusan
Operasi Penyisipan Misalnya S = brian dan T = barisan. Operasi sisip
dilakukan dengan menyisipkan a dan s pada posisi 2 dan 5 yang dapat ditunjukkan pada Rumus 2.2. 1 2 3 4 5 6 7 T = b a r
i
S = b – r
i –
a
s a n a n
s
Rumus 2.2 Operasi Penyisipan
Operasi Penggantian Misalnya S = perasa dan T = pewara. String T
ditransformasikan menjadi S dengan melakukan penggantian (subtitusi) pada posisi ke-3 dan ke-5. Huruf r dan s pada S digantikan dengan w dan r pada T. Prosesnya dapat ditunjukkan pada Rumus 2.3.
16
1 2 3 4 5 6 T = p e w a r a S = p e r
a s a
w
r
Rumus 2.3 Operasi Penggantian
Ketiga operasi di atas dapat digunakan dalam contoh berikut ini. Misalnya T = abrakadabra dan S = avrakhadabah. S dapat ditransformasikan menjadi T pada Rumus 2.4. 1
2
3
4
5
6
7
8
9 10 11 12 13
T = a
b
r
a
k -
a
d
a
b
r
a
-
S = a
v r
a
k h
a
d
a
b
- a
h
b
r Rumus 2.4 Operasi Gabungan
Operasi yang dilakukan pada Rumus 2.4 yaitu:
mengganti v pada posisi 2
menghapus h pada posisi 6
menyisipkan r pada posisi 11
menghapus h pada posisi 13
Secara keseluruhan terdapat 4 operasi, yaitu 1 penggantian, 2 penghapusan, dan 1 penyisipan.
17
2.6 Levenshtein Distance Algoritma
Levenshtein,
atau
sering disebut
dengan
Levenshtein Distance atau Edit Distance merupakan algoritma pencarian jumlah perbedaan string yang ditemukan oleh Vladimir Levenshtein, seorang ilmuwan Rusia, pada tahun 1965. Algoritma ini digunakan secara luas dalam berbagai bidang, misalnya mesin pencari, pengecek ejaan (spell checking), pengenal pembicaraan (speech recognition), pengucapan dialek, analisis DNA, pendeteksi pemalsuan, dan lain-lain. Pada dasarnya, algoritma ini menghitung jumlah minimum pentransformasian suatu string menjadi string lain yang meliputi penggantian, penghapusan, dan penyisipan. Algoritma ini digunakan untuk mengoptimalkan pencarian tersebut karena sangat tidak efisien jika dilakukan pencarian setiap kombinasi operasi-operasi string tersebut. Oleh karena itu, algoritma ini tergolong program dinamis dalam pencarian nilai minimal tersebut. Dalam algoritma ini, dilakukan penyeleksian panjang kedua string terlebih dahulu. Jika salah satu atau kedua string merupakan string kosong, jalannya algoritma ini berhenti dan memberikan hasil edit distance yang bernilai nol atau panjang string yang tidak kosong. levDis( “”, “” ) = 0 levDis( s , “” ) = levDis( “” , s ) = |s| Rumus 2.5 Edit Distance
18
Jika panjang string keduanya tidak nol, setiap string memiliki sebuah karakter terakhir, misalnya c1 dan c2. Misalnya bagian string pertama tanpa c1 adalah s1 dan bagian string kedua tanpa c2 adalah s2, dapat dikatakan penghitungan yang dilakukan adalah cara mentransformasikan s1+c1 menjadi s2+c2. Jika c1 sama dengan c2, dapat diberikan nilai cost 0 dan nilai edit distance-nya adalah nilai edit distance dari pentransformasian s1 menjadi s2. Jika c1 berbeda dengan c2, dibutuhkan pengubahan c1 menjadi c2 sehingga nilai cost-nya 1. Akibanya, nilai edit distance-nya adalah nilai edit distance dari pentransformasian s1 menjadi s2 ditambah 1. Kemungkinan lain adalah dengan menghapus c1 dan merubah s1 menjadi s2+c2 sehingga nilai edit distance-nya dari pentransformasian s1 menjadi s2+c2 ditambah 1. Begitu pula dengan penghapusan c2 dan merubah s1+c1 menjadi s2. Digunakan s1 sebagai string sumber dan s2 sebagai string target maka implementasinya pada Java seperti pada Gambar 2.1.
Gambar 2.1 Implementation Edit Distance
19
Untuk dua string, X adalah panjang dari n dan Y adalah panjang dari m. ditetapkan D(i,j) dengan edit distance diantara X[1..i] dan Y[1..j] di mana i adalah karakter pertama dari X dan j adalah karakter pertama dari Y. Maka edit distance diantara X dan Y adalah D(n,m). Untuk menghitung edit distance ed(x,y) diantara string x dan y, menyusun matrik M1...m+1,1...n+1 dimana Mi,j adalah nilai minimum dari operasi perubahan yang diperlukan untuk menyamakan x1..i ke y1..j ditunjukan pada Rumus 2.6. D(i,0) = i
i = 1 ... M
D(0,j) = j
j = 1 ... N D(i-1 , j) + 1
D(i , j) = min
D(i , j-1) + 1 D(i-1 , j-1) + 1 ;
if X(i) ≠ Y(j)
0;
if X(i) = Y(j)
Rumus 2.6 Min Edit Distance
Tabel 2.1 Edit Distance
20
Dari Tabel 2.1 ditetapkan tabel untuk i adalah kata PENJARA dan untuk
j adalah kata JARAK. Dengan
menerapakan Rumus 2.6 maka diperoleh hasil seperti pada Tabel 2.2. Tabel 2.2 Hasil Min Edit Distance
Recurrence relation : For each i = 1…M For each j = 1…N
D(i , j) = min
D(i-1 , j) + 1
deletion
D(i , j-1) + 1
insertion
D(i-1 , j-1) +
1 ; if X(i) ≠ Y(j)
substitution
0 ; if X(i) = Y(j)
ptr(i,j) =
LEFT
deletion
DOWN
insertion
DIAG
subtitution
Rumus 2.7 Arah Min Edit Distance
21
Dari Tabel 2.2 diambil contoh untuk tabel distance (1,1) yaitu : D(1-1 , 1) + 1 D(1,1) = min
D(1 , 1-1) + 1 D(1-1 , 1-1) + 0 →
+0 karena e = i dengan kondisi +1 if X(i) ≠ Y(j)
D(1,1) = min
+0 if X(i) = Y(j)
D(0 , 1) + 1
→
2
D(1 , 0) + 1
→
2
D(0 , 0) + 0
→
0
Rumus 2.8 Nilai Minimum
Dari Rumus 2.8 maka D(1,1) memiliki satu nilai minimum yaitu 0. Pada Tabel 2.2 Elemen terakhir (yang paling kanan bawah) adalah elemen yang nilainya menyatakan jarak kedua string yang dibandingkan atau disebut nilai distance, yaitu 4. Setelah didapatkan distance dari kedua string, maka dapat ditentukan formula untuk menghitung derajat plagiarisme kedua string.
Rumus 2.9 Derajat Plagiarisme
Keterangan untuk Rumus 2.9 yaitu: Diff
= distance
Max(CS,ST) = merupakan nilai yang paling panjang yang diberikan dari perbandingan CS dan ST
22
CS = PENJARA ST = JARAK Diff = 4 Maka perhitungannya adalah sebagai berikut : Plagiarized Value = {1 - (4 / 7)} * 100 = {3/7} * 100 = 42,857 Jadi, derajat plagiarismenya adalah 42,857%.
