IMPLEMENTASI ALGORITMA WINNOWING DAN PORTER STEMMER MENDETEKSI KEMIRIPAN DUA DOKUMEN BERBASIS WEB
SKRIPSI
LIDIA ARTA FERARI 081401077
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
IMPLEMENTASI ALGORITMA WINNOWING DAN PORTER STEMMER MENDETEKSI KEMIRIPAN DUA DOKUMEN BERBASIS WEB SKRIPSI
Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Komputer
LIDIA ARTA FERARI 081401077
PROGRAM STUDI SARJANA ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMATIKA UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
PERSETUJUAN
Judul
: IMPLEMENTASI ALGORITMA WINNOWING DAN PORTER STEMMER MENDETEKSI KEMIRIPAN DUA DOKUMEN BERBASIS WEB
Kategori Nama NomorIndukMahasiswa Program Studi Departemen Fakultas
: : : : : :
SKRIPSI LIDIA ARTA FERARI 081401077 SARJANA (S1) ILMU KOMPUTER ILMU KOMPUTER ILMU KOMPUTER DAN INFORMASI
TEKNOLOGI
Diluluskan di Medan, Agustus 2014 Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Drs. Marihat Situmorang, M.Kom NIP. 196312141986031001
NIP. 197103101997031004
Syahriol Sitorus, S.Si, MIT
Diketahui/Disetujui oleh Program Studi S1 IlmuKomputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
Universitas Sumatera Utara
PERNYATAAN
IMPLEMENTASI ALGORITMA WINNOWING DAN PORTER STEMMER MENDETEKSI KEMIRIPAN DUA DOKUMEN BERBASIS WEB
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
Agustus 2014
Lidia Arta Ferari 081401077
Universitas Sumatera Utara
PENGHARGAAN Puji dan syukur penulis ucapkan kepada Tuhan Yang Maha Kuasa atas segala berkat dan kasih karuniaNya sehingga penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, pada Program Studi S1 Ilmu Komputer Departemen Ilmu Komputer Universitas Sumatera Utara. Ucapan terima kasih penulis sampaikan kepada : 1. Bapak Dr. Poltak Sihombing, M.Kom, selaku Ketua Departemen Ilmu Komputer Universitas Sumatera Utara. 2. Ibu Maya Silvi Lydia, B.Sc, M.Sc, selaku Sekretaris Departemen Ilmu Komputer Universitas Sumatera Utara 3. Dekan dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, semua dosen pada Departemen Ilmu Komputer Fasilkom-TI USU, dan pegawai di Ilmu Komputer Fasilkom-TI USU. 4. Bapak Syahriol Sitorus, S.Si, MIT dan bapak Drs. Marihat Situmorang, 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 Dr. Poltak Sihombing, M.Kom selaku pembanding skripsi yang telah banyak memberikan kritik dan saran serta arahan dalam pengerjaan skripsi ini. 6. Papa dan mama kami tercinta, Nukman Siahaan dan Erline Madeline Listerine Hutagaol untuk semua keringat dan jerih payah yang begitu tulus. 7. Zonny Mega Siahaan beserta keluarga, Yannuke Patricia Siahaan beserta keluarga, Sephilda Kristi Siahaan beserta keluarga, Decerwin Charsten Benediksta Siahaan, untuk semua dukungan hebatnya. 8. Hawe Numerouno yang telah memberi semangat di setiap kondisi. 9. Seluruh teman-teman Program Studi S1 Ilmu Komputer Departemen Ilmu Komputer Universitas Sumatera Utara yang telah memberikan bantuan dan dukungan selama penulisan skripsi ini. Semoga Tuhan Yang Maha Kuasa memberikan berkat yang berlimpah kepada semua pihak yang telah memberikan bantuan, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini. Medan, Penulis
Agustus 2014
Lidia Arta Ferari Siahaan
Universitas Sumatera Utara
IMPLEMENTASI ALGORITMA WINNOWING DAN PORTER STEMMER MENDETEKSI KEMIRIPAN DUA DOKUMEN BERBASIS WEB
ABSTRAK
Skripsi ini membahas tentang perancangan aplikasi penerapan algoritma Stemmer Porter dan Winnowing. Penelitian yang dilakukan bertujuan untuk mengetahui tingkat kemiripan antara satu file dengan file yang lain. Stemmer Porter merupakan suatu algoritma yang pertama kali ditemukan oleh Martin Porter pada tahun 1980 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. Stemming adalah salah satu cara yang digunakan untuk meningkatkan performa IR dengan cara mentransformasi kata-kata dalam sebuah dokumen teks ke kata dasarnya. Sedangkan winnowing sendiri merupakan Algoritma Winnowing merupakan algoritma yang digunakan untuk deteksi tingkat kemiripan file. Dengan menggunakan kedua algoritma ini diharapkan mampu mengetahui tingkat kemiripan satu file dengan yang lain. Kata kunci: Kemiripan file, Stemmer Porter, Winnowing.
Universitas Sumatera Utara
IMPLEMENTATION WINNOWING ALGORITHM AND PORTER STEMMER DETECT TWO DOCUMENT SIMILARITY WEB-BASED ABSTRACT
This thesis discusses the application design and implementation Winnowing Porter Stemmer algorithm. Research conducted aimed to determine the degree of similarity between a file with another file. Porter Stemmer is an algorithm that was first discovered by Martin Porter in 1980 for stemming English, and because the process is different from English Stemming Indonesian then, algorithms developed specifically for Indonesian porter (Porter Stemmer for Indonesian) by WB Frakes in 1992. Stemming is one of the means used to improve the performance of the IR by transforming the way the words in a text document to word basically. While Winnowing Winnowing algorithm itself is an algorithm used for file similarity detection. By using the two algorithms is expected to determine the level of similarity of one file to another.
Keyword: Similarities files, Porter Stemmer, Winnowing.
Universitas Sumatera Utara
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 v vi vii x xi xiii 1 1 3 3 3 4 4 5
Bab 2 LandasanTeori 2.1 Pengertian Stemming 2.2 Stemming Porter 2.3 Winnowing 2.3.1 Hashing 2.3.2 K-gram 2.4 Jaccard’s Similarity Coefficient
7 7 8 16 17 18 19
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.2 Analisis Masalah 3.3 Analisis Persyaratan (Requirement Analysis)
20 20 20 21
Universitas Sumatera Utara
3.3.1 Analisis persyaratan fungsional
22
3.3.2 Analisis persyaratan non-fungsional
22
3.4 Pemodelan Sistem dengan Usecase dan Activity Diagram 3.5 Perancangan Algoritma 3.5.1 Flow chart porter 3.5.2 Flow chart Winnowing 3.5.3 Algoritma Stemmer Porter 3.5.4 Algoritma Winnowing 3.5.5 Penghitungan kemiripan 3.6 Perancangan Sistem 3.6.1 Perancangan antar muka form home 3.6.2 Perancangan antar muka form journal 3.6.3 Perancangan antar muka form similarity 3.6.4 Perancangan antar muka form about
23 28 28 30 31 38 41 42 43 44 45 46
Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi Sistem 4.1.1 Tampilan halaman form home (awal) 4.1.2 Tampilan halaman form journal 4.1.3 Tampilan halaman form similarity 4.1.4 Tampilan halaman form about 4.2 Pengujian Sistem 4.2.1 Pengujian Sistem Pilih File 4.2.2 Pengujian Hasil Proses Pilih File
47 47
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
65 65 66
DaftarPustaka
67
49 50 51 52 52 59
Universitas Sumatera Utara
DAFTAR TABEL
Nomor Tabel 2.1
Nama Tabel
Halaman
Kelompok rule pertama : inflectional particles
9
2.2
Kelompok rule kedua :inflectional possesive pronouns
9
2.3
Kelompok rule ketiga: first order of derivational prefixes
10
2.4
Kelompok rule keempat: second order of derivational prefixes
10
2.5
Kelompok rule kelima: derivational suffixes
11
3.1
Usecase Penghitungan Kemiripan File
24
3.2
Kombinasi Awalan Akhiran Yang Tidak Diijinkan
31
3.3
Cara Menentukan Tipe Awalan Untuk awalan “te-”
31
3.4
Jenis Awalan Berdasarkan Tipe Awalannya
32
Universitas Sumatera Utara
DAFTAR GAMBAR
Nomor Gambar 2.1 2.2 2.3 3.1 3.2 3.3
Nama Gambar
Halaman
Diagram Stemming Flowchart Stemmer Porter Persamaan Winnowing Diagram Ishikawa Usecase Diagram Activity Diagram
12 14 17 21 23 26
3.4
Sequence Diagram
27
3.5
Flow Chart Stemmer Porter
29
Universitas Sumatera Utara
3.6 3.7 3.8 3.9 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9
Flow chart Winnowing Tampilan Form Home Tampilan Form Journal Tampilan Form Similarity Form Home Form Journal Form Similarity Form About Tampilan hasil open file jurnal Tampilan hasil pilih file Tampilan Show Content Tampilan hasil proses Tampilan hasil fingerprint judul
30 43 44 45 48 49 50 51 52 53 54 55 56
4.10
Tampilan hasil fingerprint isi
57
4.11
Tampilan hasil kemiripan jurnal
58
Universitas Sumatera Utara
