IMPLEMENTASI ALGORITMA RABIN-KARP MENGGUNAKAN STEMMING NAZIEF DAN ADRIANI UNTUK MENDETEKSI TINGKAT KEMIRIPAN FILE TEKS YANG BERBENTUK SKRIPSI
SKRIPSI
WINDI ARINDA 091401061
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
IMPLEMENTASI ALGORITMA RABIN-KARP MENGGUNAKAN STEMMING NAZIEF DAN ADRIANI UNTUK MENDETEKSI TINGKAT KEMIRIPAN FILE TEKS YANG BERBENTUK SKRIPSI
SKRIPSI
Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Komputer
WINDI ARINDA 091401061
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Fakultas
: IMPLEMENTASI ALGORITMA RABIN-KARP MENGGUNAKAN STEMMING NAZIEF DAN ADRIANI UNTUK MENDETEKSI TINGKAT KEMIRIPAN FILE TEKS YANG BERBENTUK SKRIPSI : SKRIPSI : WINDI ARINDA : 091401061 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI
Diluluskan di Medan, Februari 2015 Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Ade Candra, ST, M.Kom NIP. 197909042009121002
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
Diketahui/Disetujui oleh Program Studi S1 IlmuKomputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
PERNYATAAN
IMPLEMENTASI ALGORITMA RABIN-KARP MENGGUNAKAN STEMMING NAZIEF DAN ADRIANI UNTUK MENDETEKSI TINGKAT KEMIRIPAN FILE TEKS YANG BERBENTUK SKRIPSI
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
Februari 2015
WINDI ARINDA 091401061
PENGHARGAAN
Puji dan syukur penulis ucapkan kepada ALLAH SWT yang senantiasa melimpahkan rahmat dan karunia-NYA sehingga skripsi ini dapat diselesaikan. Ucapan terimakasih penulis sampaikan kepada semua pihak yang telah membantu penulis dalam menyelesaikan skripsi ini baik secara langsung maupun tidak langsung. Ucapan terima kasih penulis sampaikan kepada :
1. Bapak Dr. Poltak Sihombing, M.Kom, selaku Ketua Program Studi Ilmu Komputer Universitas Sumatera Utara. 2. Ibu Maya Silvi Lydia, B.Sc, M.Sc, selaku Sekretaris Program Studi Ilmu Komputer Universitas Sumatera Utara. 3. Dekan dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, semua dosen pada Program Studi Ilmu Komputer FASILKOM-TI USU, dan semua pegawai di Ilmu Komputer FASILKOM-TI USU. 4. Bapak Dr. Poltak Sihombing, M.Kom dan bapak Ade Candra, ST, M.Kom selaku pembimbing skripsi yang telah banyak memberikan bantuan, arahan, petunjuk, serta kesabaran dalam pengerjaan skripsi ini. 5. Bapak Prof. Dr. Muhammad Zarlis dan bapak Drs. Marihat Situmorang, M.Kom selaku pembanding skripsi yang telah banyak memberikan kritik dan saran serta arahan dalam pengerjaan skripsi ini. 6. Teristimewa untuk Ayahanda dan Ibunda penulis Bapak Sudiono dan Ibu Nurhasanah yang dengan tulus dan sabar memberikan doa dan dukungan moril dan materil kepada penulis selama ini, serta adik-adik tersayang Elvina Sari, Chici Tri Andani, dan Rizky yang telah banyak memberikan dukungan dan semangat dalam penyusunan skripsi ini. 7. Keluarga, sahabat dan pihak-pihak lainnya yang tidak dapat penulis sebutkan satu persatu yang telah memberikan bantuan dan dukungan selama penulisan skripsi ini.
Dan sekali lagi terima kasih yang sebesar-besarnya kepada semua pihak yang membantu penyelesaian skripsi ini.
Wassalam.
Medan,
Februari 2015
Penulis,
WINDI ARINDA
IMPLEMENTASI ALGORITMA RABIN-KARP MENGGUNAKAN STEMMING NAZIEF DAN ADRIANI UNTUK MENDETEKSI TINGKAT KEMIRIPAN FILE TEKS YANG BERBENTUK SKRIPSI
ABSTRAK
Di dunia pendidikan khususnya di kalangan universitas, rentan terjadi praktek plagiarisme. Misalnya dalam hal pembuatan Tugas Akhir, Skripsi. Untuk mendeteksi kemiripan antar Skripsi, banyak universitas masih melakukannya secara manual sehingga menghabiskan waktu yang lama dan tenaga yang ekstra. Seiring dengan perkembangan ilmu pengetahuan dan teknologi, algoritma untuk mencari tingkat kesamaan dokumen telah dikembangkan oleh para ahli. Stemming adalah salah satu cara untuk meningkatkan performa information retrieval. Data yang digunakan pada penelitian ini adalah skripsi mahasiswa S1 Ilmu komputer Universitas Sumatera Utara. Penulis menggunakan algoritma stemming Nazief dan Adriani dalam mencari kata dasar/root word untuk setiap kata dalam skripsi yang diuji. Setelah didapat kata dasar dari setiap kata, kemudian dari kata dasar tersebut dibentuk gram, dan dicari nilai hashnya menggunakan algoritma Rabin-Karp. Setelah didapat nilai hash, maka nilai hash skripsi yang diuji dibandingkan dengan nilai hash skripsi yang sudah tersimpan di database sistem menggunakan rumus Dice Coefficient Similarity. Hasil perbandingan antar skripsi dalam bentuk persen, disimpan ke database sistem dan ditampilkan di sistem secara berurut dari yang paling besar total persentase kemiripannya sampai yang paling kecil.
Kata kunci: plagiarisme, stemming, information retrieval, Rabin-Karp, Dice Coefficient Similarity.
IMPLEMENTATION OF RABIN-KARP ALGORITHM USING STEMMING NAZIEF AND ADRIANI TO DETECT SIMILARITY OF TEXT FILE IN FORM OF THESIS
ABSTRACT
In the world of education especially among the University, susceptible to the practice of plagiarism. For example, in terms of making a Final Project, Thesis. To detect the similarity between Thesis, many universities are still doing it manually so spend a long time and extra energy. Along with the development of science and technology, algorithm to find the degree of similarity of documents have been developed by experts. Stemming is one way to improve the performance of information retrieval. The Data used in this study is thesis of the students in Bachelor Computer Science in University of North Sumatera. The author uses stemming Nazief and Adriani algorithm in finding the basic word/root word for each word in the thesis are tested. After derived the root word of every word, then from the root word is formed to gram, and calculated it’s hash value uses Rabin-Karp algorithm. After getted the hash value, so the hash value of thesis tested to be compared with the hash value of thesis are saved in the database system uses the formula of Dice Coefficient Similarity. The result of the comparison between the thesis in the form of percent, are saved to database system and published in system sequencely from the biggest of total percentage of it’s similarity to the smallest.
Keyword: plagiarism, stemming, information retrieval, Rabin-Karp, Dice Coefficient Similarity.
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Daftar Lampiran Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
ii iii iv vi vii viii x xi xii 1 1 2 2 2 3 3 4
Bab 2 LandasanTeori 2.1 Text Mining 2.1.1 Ruang Lingkup Text Mining 2.2 Ekstraksi Dokumen 2.2.1 Stemming dengan Algoritma Nazief dan Adriani 2.3 Rabin-Karp 2.3.1 Hashing 2.3.2 K-grams 2.3.3 Konsep Algoritma Rabin-Karp 2.4 Dice Coefficient Similarity
6 6 7 9 10 13 15 16 16 17
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.1.1 Cause-and-Effect Analisis 3.1.2 Analisis Persyaratan 3.1.2.1 Analisis Fungsional Sistem 3.1.2.2 Analisis Non Fungsional Sistem 3.1.3 Pemodelan Sistem Dengan Use Case 3.1.3.1 Diagram Use Case 3.1.3.2 Use Case Membandingkan Skripsi 3.1.3.3 Activity Diagram Membandingkan Skripsi 3.1.3.4 Use Case Algoritma Stemming Nazief dan Adriani
18 18 18 18 20 20 21 21 22 22 24 25
3.1.3.5 Acitvity Diagram Algoritma Stemming Nazief dan Adriani 3.1.3.6 Use Case Algoritma Rabin-Karp 3.1.3.7 Activity Diagram Algoritma Rabin-Karp 3.1.3.8 Use Case Dice Coefficient Similarity 3.1.3.9 Activity Diagram Dice Coefficient Similarity 3.1.3.10 Use Case Melihat Skripsi 3.1.3.11 Activity Diagram Melihat Skripsi 3.1.4 Analisis Proses Sistem 3.1.5 Flow Chart 3.1.5.1 Flow Chart Algoritma Rabin-Karp 3.1.5.2 Flow Chart Algoritma Stemming Nazief dan Adriani 3.2 Perhitungan Kemiripan 3.3 Perancangan Antar Muka 3.3.1 Perancangan Antar Muka Form Home 3.3.2 Perancangan Antar Muka Form Masukkan Skripsi 3.3.3 Perancangan Antar Muka Form kemiripan 3.3.4 Perancangan Antar Muka Form Skripsi
26 27 28 29 31 32 32 33 34 34 35 37 37 37 38 40 41
Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi Sistem 4.1.1 Spesifikasi Perangkat Keras Yang Digunakan 4.1.2 Spesifikasi Perangkat Lunak Yang Digunakan 4.1.3 Implementasi Antarmuka Sistem 4.1.3.1 Tampilan Antarmuka Form Home 4.1.3.2 Tampilan Antarmuka Form Masukkan Skripsi 4.1.3.3 Tampilan Antarmuka Form Kemiripan 4.1.3.4 Tampilan Antarmuka Form Skripsi 4.2 Pengujian 4.2.1 Tujuan Pengujian 4.2.2 Data Pengujian 4.2.3 Skenario Pengujian 4.2.4 Output Hasil Pengujian 4.2.4.1 Perhitungan Manual 4.2.4.2 Perhitungan Dalam Sistem
42 42 42 43 43 43 44 46 48 50 50 50 51 51 51 58
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
62 62 62
Daftar Pustaka
64
Curriculum Vitae
65
Lampiran Tabel ASCII Listing program
A-1 B-1
DAFTAR TABEL
Nomor Tabel 2.1 2.2 2.3 3.1 3.2 3.3 3.4 3.5 3.6
Nama Tabel Daftar Prefiks Yang Meluluh Daftar Kemungkinan Perubahan Prefiks Daftar Kombinasi Prefiks dan Sufiks Yang Tidak Diperbolehkan Cause-And-Effect Analysis Dokumentasi Naratif Use Case Membandingkan Skripsi Dokumentasi Naratif Use Case Algoritma Stemming Nazief dan Adriani Dokumentasi Naratif Use Case Algoritma Rabin-Karp Dokumentasi Naratif Use Case Dice Coefficient Similarity Dokumentasi Naratif Use Case Melihat Skripsi
Halaman 12 12 13 19 23 25 28 29 32
DAFTAR GAMBAR
Nomor Gambar 2.1 2.2 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13
Nama Gambar Tahap Preprocessing Format Kata Berimbuhan Dalam Bahasa Indonesia Diagram Ishikawa Untuk Analisis Permasalahan Sistem Use Case Diagram Activity Diagram Membandingkan Skripsi Activity Diagram Algoritma Stemming Nazief dan Adriani Activity Diagram Algoritma Rabin-Karp Activity Diagram Dice Coefficient Similairty Activity Diagram Melihat Skripsi Sequence Diagram Sistem Flow Chart Algoritma Rabin-Karp Flow Chart Algoritma Stemming Nazief dan Adriani Tampilan Form Home Tampilan Form Masukkan Skripsi Tampilan Form Kemiripan Tampilan Form Skripsi Tampilan Antarmuka Form Home Tampilan Antarmuka Form Masukkan Skripsi Tampilan Form Masukkan Skripsi setelah Nim dan Judul dari Skripsi yang akan dibandingkan dimasukkan Tampilan Antarmuka Form Kemiripan Tampilan Form Kemiripan file skripsi yang terakhir di bandingkan Tampilan Antarmuka Form Skripsi Tampilan Antarmuka Form Skripsi yang terakhir diinput Tampilan Form Skripsi setelah diklik Judul dari skripsi Proses Sistem Step 1 Dokumen 1 Proses Sistem Step 2, Step 3 dan step 4 Proses Sistem Step 4, Step 5 dan Step 6 Proses Sistem Dokumen 2 Persentase Kemiripan Dokumen 1 dan Dokumen 2
Halaman 9 11 20 22 25 27 29 31 33 34 35 36 38 39 40 41 44 44 45 47 48 49 49 50 58 59 59 60 61
DAFTAR LAMPIRAN
Nomor Lampiran A B
Nama Lampiran
Tabel ASCII Listing Program
Halaman
A-1 B-1