BAB III ANALISIS DAN PERANCANGAN SISTEM
Pada pengembangan suatu sistem diperlukan analisis dan perancangan sistem yang tepat, sehingga proses pembuatan sistem dapat berjalan dengan lancar dan sesuai seperti yang diinginkan. Setelah dilakukan analisis perlu adanya desain sistem (desain interface) yang bertujuan untuk memberikan gambaran tentang jalannya sistem tersebut. 3.1
Analisis Masalah Perkembangan teknologi semakin hari semakin berkembang dengan pesat.
Kemajuan teknologi ini memunculkan banyaknya aplikasi-aplikasi berbasis web yang menampilkan berbagai macam informasi digital. Aplikasi-aplikasi berbasis web ini tidak menutup kemungkinan terdapat kemiripan informasi yang ditampilkan antara web satu dengan web yang lainnya. Kemiripan informasi tersebut bisa dilihat berdasarkan isi atau cara penulisan dari web satu dengan web yang lain. Tak jarang pula penggunaan kata dan kalimat dalam penyampaian informasi tersebut mempunyai persentase kemiripan hingga 100%. Aplikasi untuk membandingkan kemiripan dua buah teks untuk saat ini masih jarang ditemukan, dan kemungkinan dalam hal membandingkan dua buah teks ini masih dilakukan secara manual atau dengan kata lain hanya dibandingkan dengan cara membacanya saja, dan akan memakan waktu yang lama jika teks yang dibandingkan sangat banyak. Oleh karena itu, dalam laporan tugas akhir ini telah mencoba untuk merancang aplikasi tersebut salah satunya dengan maksud mengurangi adanya kemiripan dua buah teks ini. Aplikasi untuk membandingkan kemiripan dua buah teks dapat dibuat dengan menggunakan algoritma Winnowing dan fungsi similar_text yang ada
23
24
pada bahasa pemrograman PHP. Dalam laporan tugas akhir ini memilih menggunakan algoritma Winnowing untuk membuat aplikasi berbasis web untuk membandingkan kemiripan dua buah teks. Alasan memilih algoritma Winnowing dapat dilihat pada tabel perbandingan antara algoritma Winnowing dengan fungsi similar_text. Tabel perbandingan ini dibuat berdasarkan referensi buku mengenai algoritma Winnowing dan fungsi similar_text. Lihat Tabel 3.1. 1.
Tabel Perbandingan Tabel 3.1 Tabel perbandingan algoritma Winnowing dengan similar_text() No.
Proses
Algoritma Winnowing
Fungsi similar_text()
1.
Pembersihan teks
√
-
2.
Pembentukan k-gram
√
-
3.
Rolling hash
√
-
4.
Mengelompokkan nilai hash ke dalam window
√
-
5.
Memilih minimum hash
√
-
6.
Membuat fingerprint
√
-
7.
Menghitung nilai kemiripan
√
√
Kebutuhan dari aplikasi tersebut yaitu :
Input
a.
Teks 1 Teks 1 merupakan teks pembanding. Teks 1 ini dapat berupa bahasa Inggris
dan bahasa Indonesia. Tidak ada batas maksimum panjang teks dalam teks 1 ini. b.
Teks 2 Teks 2 merupakan teks yang dibandingkan. Teks 2 ini dapat berupa bahasa
Inggris dan bahasa Indonesia. Tidak ada batas maksimum panjang teks dalam teks 2 ini.
25
Proses
a.
Algoritma Winnowing Algoritma Winnowing merupakan algoritma yang digunakan dalam aplikasi
berbasis web untuk membandingkan kemiripan dua buah teks. Algoritma Winnowing adalah algoritma yang digunakan untuk melakukan proses sidik jari dokumen. Algoritma Winnowing melakukan penghitungan nilai-nilai hash dari setiap k-gram, untuk mencari nilai hash selanjutnya digunakan fungsi rolling hash (pemisah bergulir). b.
Menentukan kemiripan Menentukan kemiripan merupakan sebuah proses yang dilakukan dalam
aplikasi ini untuk menentukan besarnya persentase kemiripan antara teks 1 dengan teks 2.
Output
a.
Persentase kemiripan Persentase kemiripan merupakan hasil keluaran dari proses algoritma
Winnowing dan menentukan kemiripan dalam bentuk angka. 3.2
Perancangan Sistem Untuk merancang aplikasi ini mengunakan pemrograman terstruktur dan
rancangan antar muka. Pemrograman terstruktur yang dibuat adalah diagram alir dari program tersebut. 3.2.1 Diagram Alir Dalam merancang sebuah aplikasi dibutuhkan diagram alir atau alur dari sebuah algoritma. Diagram alir ini dibuat untuk mempermudah perancangan sistem sebuah aplikasi. Dalam aplikasi ini, membuat diagram alir algoritma. Diagram alir algoritma dimulai dengan pengguna memasukkan teks 1 dan teks 2 pada kotak yang telah disediakan. Setelah pengguna memasukkan teks, maka algoritma akan menentukan nilai k-gram dari masing-masing teks. Nilai kgram dibentuk berdasarkan rata-rata jumlah huruf yang ada pada setiap teks.
26
Selanjutnya algoritma Winnowing akan melakukan pembersihan teks, yaitu menghilangkan spasi, tanda baca, karakter, dan menjadikan huruf kapital menjadi lowercase. Winnowing akan membentuk sebuah array k-gram. Pembentukan kgram ini dilakukan berdasarkan nilai k-gram yang telah ditentukan sebelumnya. Setelah menentukan nilai k-gram, maka aka nada sebuah proses rolling hash. Rolling hash adalah sebuah rangkaian proses algoritma yang merubah kata ke dalam bentuk nilai ascii. Hasil dari proses rolling hash akan dilakukan pengelompokkan nilai hash. Sebelum melakukan pengelompokan nilai hash, akan dilakukan penentuan window, dimana window adalah rata-rata jumlah kata yang ada didalam sebuah kalimat teks tersebut. Memilih nilai hash minimum (nilai terkecil) dari pengelompokan nilai window. Pemilihan pernyataan atau decision, perhatikan apakah nilai hash dalam window tersebut terdapat kesamaan atau tidak? Jika ya (ada yang sama), maka akan ada penggabungan nilai hash, dan dalam pemilihan fingerprint nilai hash yang sama hanya ditulis satu kali. Jika tidak ada yang sama, maka bisa di lanjutkan dalam pembuatan fingerprint. Hasil pemilihan beberapa nilai hash minimum dari window dan ditambahkan informasi posisi fingerprint. Langkah terakhir adalah menghitung nilai kemiripan dari proses yang sudah dibuat. Cara menghitung nilai kemiripan dari kedua teks adalah nilai hash yang sama dibagi dengan jumlah nilai hash teks 1 dan teks 2 dikurangi nilai hash yang sama kemudian hasil pembagian tersebut dikali seratus persen. Setelah melakukan penghitungan maka program akan menampilkan hasil persentase kemiripan kedua teks. Ketika program sudah menampilkan hasil persentase maka program ini berakhir. Rangkaian proses algoritma Winnowing bisa dilihat dalam diagram alir dari algoritma Winnowing. Berikut ini diagram alir dari algoritma Winnowing. Lihat Gambar 3.1.
27 Start
Input: -teks 1 -teks 2
Menentukan nilai k-gram
-Pembersihan teks (spasi, tanda baca) -Menjadikan huruf kecil
Pembentukkan rangkaian gram sesuai dengan nilai k-gram yang sudah di tentukan
Rolling hash
Mengelompokkan nilai hash ke dalam ukuran window yang telah ditentukan
Memilih minimum hash dari setiap window
ya Apakah Nilai hash ada yang sama?
tidak
Memilih salah satu dari nilai hash yang sama
Membuat fingerprint
Menghitung nilai kemiripan
Output: Presentase kemiripan
Stop
Gambar 3.1 diagram alir algoritma Winnowing
28
1.
Diagram alir menentukan nilai k-gram. Lihat Gambar 3.2. Start
Input : - teks 1 - teks 2
Melakukan explode
Melakukan Count
Melakukan pembagian
Tidak Succes?
Ya Membulatkan angka hasil dari pembagian
Output: Nilai k-gram teks
Stop
Gambar 3.2 diagram alir menentukan nilai k-gram
Dalam menentukan nilai k-gram pada algoritma Winnowing, langkah pertama yang dilakukan adalah melakukan explode, yaitu memisah string menjadi substring. Langkah kedua adalah melakukan count atau penghitungan teks, count yang dimaksud disini adalah menghitung rata-rata jumlah huruf dalam satu kata pada teks dan menghitung jumlah huruf yang ada pada teks. Selanjutnya, membagi jumlah huruf pada teks dengan rata-rata jumlah huruf yang ada pada teks. Hasil pembagian antara jumlah huruf pada teks dengan rata-rata jumlah
29
huruf yang ada pada teks akan dibulatkan. Misal hasil dari pembagian 5,4 maka akan dibulatkan menjadi 5. Maka program akan menampilkan hasil dari proses menentukan nilai k-gram (dalam bentuk angka). 2.
Diagram alir pembersihan teks. Lihat Gambar 3.3. start
Input : - teks 1 - teks 2
Menentukan nilai k-gram
Menjadikan lowercase (huruf kecil)
Membuang semua yang bukan huruf dan angka
Menghapus spasi
Tidak Succes?
Ya Output: Tidak ada huruf kapital, spasi dan tanda baca dalam teks
Stop
Gambar 3.3 diagram alir pembersihan teks
Dalam proses pembersihan teks langkah pertama yang dilakukan adalah menjadikan semua huruf kapital yang ada pada inputan teks huruf kecil atau lowercase. Kemudian membuang atau menghilangkan semua yang bukan huruf dan angka yang ada pada teks, seperti karakter huruf, tanda baca. Setelah melakukan proses pembuangan karakter, dilanjutkan dengan menghilangkan
30
spasi. Setelah proses seleseai, maka program akan menampilkan teks tanpa karakter, huruf kapital, tanda baca, dan spasi. Contoh: Nama saya: Afni Menjadi: namasayaafni 3.
Diagram alir rolling hash. Lihat Gambar 3.4. Start
Input: -teks 1 -teks 2
Menentukan nilai k-gram
-Pembersihan teks (spasi, tanda baca) -Menjadikan huruf kecil
Pembentukkan rangkaian gram sesuai dengan nilai k-gram yang sudah di tentukan
Menghitung jumlah array rangkaian gram
Menentukan nilai bilangan prima
Mengubah huruf kedalam bentuk nilai ascii
tidak Success? ya Output: Array nilai hash
Stop
Gambar 3.4 diagram alir rolling hash
31
Sebelum melakukan proses rolling hash, hal yang dilakukan adalah pembentukkan rangkaian gram (array) sesuai dengan nilai k-gram yang sudah ditentukan dalam bentuk array. Melakukan penghitungan atas array yang sudah dibentuk pada proses sebelumnya. Menentukan nilai bilangan prima untuk digunakan pada proses selanjutnya, yaitu fungsi rolling hash. Setelah melakukan pembentukkan array rangkaian gram, dilanjutkan dengan mengubah huruf kedalam bentuk nilai ascii. Proses ini dilakukan dengan menggunakan rumus rolling hash, dimana rumus ini adalah mengalikan nilai ascii dengan bilangan prima yang sudah ditentukan yang berpangkat k-gram. Rumus rolling hash yaitu: c1*b(k-1) + c2*b(k-2) + … + c(k-1)*b + ck Fungsi rolling hash untuk mencari nilai hash ke-2 sampai ke-n: H(c2…ck+1) = (H(c1..ck) – c1 * b(k-1) * b + c (k+1) keterangan: c= nilai ascii karakter b= basis (bilangan prima) k= nilai k-gram
Jika sudah melakukan proses dari rolling hash, maka program akan menampilkan sebuah array nilai hash (dalam bentuk angka). Contoh: - Teks - k-gram - array - bentuk ascii
: namasayaafni :4 : nama amas masa asay saya ayaa yaaf aafn afni : 159443 143478 158178 144210 166230 144912 173957 142076 142764
32
4.
Diagram alir menentukan kemiripan Langkah terakhir dalam membuat aplikasi untuk membandingkan kemiripan
dua buah teks adalah menentukan kemiripan. Hal yang harus dilakukan adalah menentukan nilai window. Window adalah rata-rata jumlah kata yang ada pada setiap kalimat. Nilai window digunakan untuk proses selanjutnya, yaitu fingerprint. Di dalam aplikasi ini menggunakan window 4. Kemudian mengelompokkan nilai hash ke dalam ukuran window yang telah ditentukan. Pengelompokkan ini bertujuan untuk memudahkan fingerprint melakukan proses pemilihan nilai hash terkecil. Setelah melakukan proses pengelompokkan, maka selanjutnya adalah melakukan minimum hash yang ada pada setiap window. Memilih salah satu dari nilai hash yang sama. Apabila nilai hash terkecil pada window selanjutnya sama dengan nilai hash terkecil pada window sebelumnya maka nilai hash-nya tidak perlu dituliskan lagi. Setelah proses ini berhasil maka akan langsung dilanjutkan kepada proses fingerprint. Menghitung jumlah fingerprint yang ada pada setiap teks. Menghitung jumlah fingerprint yang sama dalam teks 1 dan teks 2 (NS). Menjumlahkan total fingerprint teks 1 dengan total fingerprint teks 2 (NA+NB). Membagi NS dengan (NA+NB) kemudian dikurangi dengan NS. NS (NA+NB) – NS Setelah mendapatkan nilai dari hasil perhitungan kemiripan, maka hasil tersebut dikalikan dengan 100, untuk mendapatkan nilai persen. Kemudian program akan menampilkan sebuah nilai persentase kemiripan. Proses menghitung atau menentukan nilai kemiripan dapat dilihat pada diagram alir menentukan kemiripan. Lihat Gambar 3.5.
33
Start
Input: -teks 1 -teks 2
Menentukan nilai k-gram
-Pembersihan teks (spasi, tanda baca) -Menjadikan huruf kecil
Pembentukkan rangkaian gram sesuai dengan nilai k-gram yang sudah di tentukan
Rolling hash
Menentukan nilai window
Mengelompokkan nilai hash ke dalam ukuran window yang telah ditentukan
Memilih minimum hash dari setiap window
ya Apakah Nilai hash ada yang sama?
tidak
Membuat fingerprint
Menghitung jumlah fingerprint yang ada pada setiap teks (NA dan NB)
Menghitung jumlah fingerprint yang sama dalam teks 1 dan 2 (NS)
Menjumlahkan fingerprint teks 1 dengan fingerprint teks 2 (NA+NB)
Perhitungan kemiripan
Mengalikan hasil dari pembagian dengan 100
Output: Persentase kemiripan
Stop
Memilih salah satu dari nilai hash yang sama
34
Gambar 3.5 diagram alir persentase kemiripan
3.3
Desain Antarmuka (Interface) Desain aplikasi berbasis web untuk membandingkan kemiripan dua buah
teks dibuat seperti ini dengan tujuan memudahkan pengguna dalam pemakaian. Pengguna hanya tinggal memasukkan dua buah teks pada kotak teks 1 dan kotak teks 2. Kemudian program akan menampilkan nilai gram dan window secara otomatis. Setelah
itu
dilakukan
proses
pengecekkan,
maka
program
akan
menampilkan hasil dari kemiripan kedua buah teks tersebut. Desain aplikasi memasukkan teks dapat dilihat pada Gambar 3.6 sedangkan desain aplikasi yang memunculkan nilai kemiripan dapat dilihat pada Gambar 3.7.
APLIKASI BERBASIS WEB UNTUK MEMBANDINGKAN KEMIRIPAN DUA BUAH TEKS ALGORITMA WINNOWING Afni Fathia Asih - 41511010033
Teks 1
:
Teks 2
:
Gram
:
Window : CEK
Gambar 3.6 desain aplikasi memasukkan teks (input text)
35
APLIKASI BERBASIS WEB UNTUK MEMBANDINGKAN KEMIRIPAN DUA BUAH TEKS ALGORITMA WINNOWING Afni Fathia Asih - 41511010033
Teks 1
:
Teks 2
:
Gram
:
Window : CEK Kesamaan
%
Gambar 3.7 desain aplikasi hasil kemiripan
36
