JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6
1
Rancang Bangun Aplikasi Sistem Verifikasi Data Berkas Beasiswa Artha Pradyta, Siti Rochimah, dan Umi Laili Yuhana Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia E-mail:
[email protected] Abstrak—Pada tulisan ini dibuat sebuah sistem yang dapat melakukan verifikasi berkas persyaratan beasiswa. Sistem verifikasi berkas otomatis ini diperlukan untuk menangani lamanya proses verifikasi berkas yang dilakukan oleh manusia. Proses verifikasi berkas yang lama ini disebabkan karena banyaknya jenis berkas beasiswa yang harus diverifikasi, sehingga menyebabkan bertambah lamanya proses seleksi pemberian beasiswa karena harus menunggu manusia untuk melakukan verifikasi berkas. Proses verifikasi yang dilakukan adalah dengan cara mendeteksi kata kunci dan karakter nama pemilik berkas yang tertera pada berkas gambar yang diunggah dan dibandingkan dengan karakter nama yang akan dibandingkan. Guna mendeteksi kata kunci berkas dan karakter nama pemilik berkas gambar, diperlukan proses ekstraksi gambar menjadi kumpulan kata (string) dengan menggunakan teknologi Optical Character Recognition. Dari kumpulan kata tersebut, dicari baris kumpulan kata yang mengandung nama dan kata kunci berkas. Setelah kumpulan kata nama didapat, diperlukan teknik-teknik pencocokan kumpulan kata (string matching) seperti algoritma Soundex, algoritma Levenshtein Distance, dan juga algoritma Longest Common Subsequence. Berdasarkan hasil pengujian yang dilakukan, sistem mempunyai rata-rata nilai precision sebesar 1 dalam pendeteksian kata kunci dan karakter nama pemilik berkas. Di samping itu, sistem mempunyai rata-rata nilai recall dalam pencarian kata kunci berkas sebesar 0.494 dan nilai recall dalam pencarian karakter nama pemilik berkas sebesar 0.77. Nilai recall yang rendah ini menunjukkan jika sistem tidak bisa secara utuh mendapatkan seluruh informasi yang tertera pada berkas gambar yang diekstraksi. Hal ini disebabkan karena adanya noise pada berkas-berkas yang akan diverifikasi sehingga kualitas gambar dari berkas akan mempengaruhi keberhasilan dari verifikasi yang dilakukan oleh sistem verifikasi berkas. Kata Kunci—Levenshtein Distance, Longest Common Subsequence, Optical Character Recognition, Soundex, String Matching.
I. PENDAHULUAN
P
ROGRAM pemberian beasiswa merupakan salah satu program tahunan yang diselenggarakan oleh setiap Perguruan Tinggi. Untuk mengikuti seleksi beasiswa, mahasiswa melakukan pengunggahan berkas-berkas persyaratan beasiswa berupa berkas gambar ke dalam sistem beasiswa sebuah Perguruan Tinggi. Akan tetapi terdapat masalah ketika sistem beasiswa tersebut tidak bisa melakukan verifikasi jenis berkas dan nama pemilik berkas secara otomatis dimana terdapat banyak sekali jenis berkas persyaratan beasiswa yang harus diverifikasi. Hal ini menyebabkan bertambah lamanya proses seleksi pemberian beasiswa karena harus menunggu manusia untuk melakukan verifikasi berkas, padahal hasil seleksi yang dilakukan harus diberikan kepada pihak pemberi beasiswa secepatnya. Saat ini, untuk proses verifikasi berkas persyaratan beasiswa memang masih ditangani oleh manusia meskipun
proses pengumpulan berkas tersebut sudah ditangani oleh sistem. Pemeriksaan oleh manusia ini tentunya membutuhkan waktu yang lama jika berkas yang diverifikasi cukup banyak dan beragam, serta tidak menjamin terbebas dari human error saat verifikasi. Dalam artikel ini akan dibuat sistem yang dapat melakukan verifikasi berkas persyaratan beasiswa dengan cara mendeteksi jenis berkas serta siapa pemilik sah dari berkas yang diunggah. Sistem ini akan membantu mengurangi lamanya proses seleksi pemberian beasiswa. II. TINJAUAN PUSTAKA A. Algoritma Soundex dan Normalisasi Kumpulan Kata Algoritma Soundex mengambil masukan berupa sebuah kumpulan kata yang mengidentifikasi apakah sepasang kata tersebut mirip secara fonetik. Kumpulan kata ini disebut dengan kode fonetis. Fonetik sendiri merupakan ilmu yang menyelidiki bunyi bahasa tanpa melihat fungsi bunyi itu sebagai pembeda makna dalam suatu bahasa. Pencocokan kumpulan kata fonetik adalah suatu teknik pencocokan kumpulan kata yang membandingkan suatu kumpulan kata dengan kumpulan kata yang lain berdasarkan kode fonetis masing-masing [1]. Sebuah kumpulan kata yang berbeda namun mempunyai cara pengucapan yang sama, akan memiliki kode fonetis yang sama. Contohnya adalah “Djono” dan “Jono”. Metode yang digunakan algoritma Soundex berdasarkan pada klasifikasi fonetis dari suara cara berbicara manusia (human speech sound) yaitu labial, dental, alveolar, palatoalveolar, palatal, velar, dan glottal [2]. Aturan pemberian kode fonetis per huruf pada algoritma Soundex [3] dapat dilihat pada Tabel 1. Berikut ini merupakan langkah-langkah algoritma Soundex dalam menghasilkan kode fonetis dari sebuah kumpulan kata masukan. 1. Mengubah semua huruf menjadi huruf kapital, dan hilangkan tanda baca. 2. Mempertahankan huruf pertama pada kata tersebut. 3. Mengubah huruf lainnya menjadi kode fonetis berdasarkan aturan yang berlaku. 4. Menghapus semua pasangan dari kode fonetis yang berurutan. 5. Menghapus semua kode fonetis yang bernilai 0. Tabel 1. Aturan Pemberian Kode Fonetis Pada Algoritma Soundex Huruf Kode Klasifikasi Fonetis A,E,H,I,O,U,W,Y 0 Diperlukan sebagai bunyi vokal B,F,P,V 1 Labial dan labio-dental C,G,J,K,Q,S,X,Z 2 Glottal D,T 3 Dental-mute L 4 Palatal fricative M,N 5 Labio-nasal dan dental R 6 Dental fricative
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6
Q-Gram Awal KH DJ TJ CQ, CK PH DZ SJ SY BH, DH, GH, JH, SH, TH, ZH V KS OE IE Y
Tabel 2. Aturan Translasi Q-Gram Contoh Translasi Awal HH Rakhmat JJ Endjang CC Itjang KK Erick FF Philip ZZ Dzikri SY Sjahrir SS Syifa BB, DD, GG, Ardhi JJ, SS, TT, ZZ F Saviena XX Wicaksono UU Wahyoedi II Arie I Donny
Translasi Rahhmat Enjjang Iccang Erikk Ffilip Zzikri Syahrir Ssifa Arddi Safiena Wicaxxono Wahyuudi Arii Donni
6. Menulis empat posisi pertama yang mengikuti pola:
. Ini merupakan keluaran dari kode fonetis. Jika kode fonetis tidak sampai empat karakter, maka ditambahkan angka 0 sampai menjadi empat karakter. Algoritma Soundex dibuat berdasarkan pengucapan dalam bahasa Inggris. Untuk mendukung pencocokan kumpulan kata berdasarkan bahasa Indonesia, sekaligus melakukan optimasi terhadap algoritma tersebut, diperlukan suatu proses normalisasi. Salah satu cara untuk proses normalisasi adalah dengan menggunakan aturan translasi q-gram [4]. Aturan translasi q-gram dijelaskan pada Tabel 2. Setelah proses normalisasi selesai, biasanya akan muncul karakter yang terduplikasi sehingga diperlukan eliminasi karakter-karakter berurutan yang sama. B. Algoritma Levenshtein Distance Levenshtein Distance adalah jumlah minimal operasi yang dibutuhkan untuk mengubah suatu kumpulan kata ke kumpulan kata yang lain. Dengan algoritma ini, dapat diketahui tingkat perbedaan dua buah kumpulan kata dalam representasi angka. Berikut ini operasi yang dilakukan dalam algoritma Levenshtein Distance [5]. 1. Penyisipan (Insertion) Merupakan proses penyisipan sebuah karakter ke dalam sebuah kumpulan kata tertentu. 2. Penghapusan (Deletion) Merupakan proses penghapusan sebuah karakter dari sebuah kumpulan kata tertentu. 3. Penggantian (Substitution) Merupakan proses penggantian sebuah karakter dari sebuah kumpulan kata dengan karakter lain. C. Algoritma Longest Common Subsequence Subsequence adalah sebuah rangkaian yang dapat diperoleh dari rangkaian lain dengan cara menghapus beberapa elemen tertentu tanpa mengubah urutan dari elemen lain yang tersisa [6]. Misalkan ada rangkaian X dan Y, rangkaian S dikatakan sebuah common subsequence dari X dan Y apabila S adalah subsequence dari keduanya. Longest Common Subsequence (LCS) merupakan common subsequence terpanjang dari seluruh common subsequence. Contohnya adalah sebagai berikut. X = {M,A,K,A,N}. Y = {M,A,L,A,M}. Contoh common subsequence dari X dan Y adalah S = {M,A,A} dan T = {M,A}. Karena S merupakan subsequence
2 yang lebih panjang, maka longest common subsequence dari X dan Y adalah S. D. Optical Character Recognition Optical Character Recognition (OCR) merupakan sebuah teknologi konversi dari gambar ke bentuk teks. Teknologi ini biasanya digunakan untuk mengambil data dari berkas-berkas berbentuk gambar seperti dokumen paspor, faktur, laporan bank, kartu nama, dan sebagainya. Dalam pemrosesan OCR, gambar dianalisis pada daerah terang dan gelap dalam rangka mengidentifikasi setiap huruf abjad maupun angka numerik [7]. Ketika karakter sudah diketahui, maka setiap kata tersebut dirubah ke dalam bentuk ASCII. Dalam hal ini mesin komputer merubah kode ASCII tersebut menjadi berupa karakter maupun angka. Karena kemampuannya dalam hal ekstraksi data dari gambar inilah, maka teknologi ini digunakan untuk mengambil data-data dari berkas persyaratan mahasiswa yang telah diunggah ke sistem. Berikut ini merupakan langkah-langkah alur kerja sistem OCR secara umum. 1. Pengambilan Data (Data Capture) Merupakan proses konversi suatu dokumen menjadi suatu berkas gambar bitmap. 2. Pra Pemrosesan (Preprocessing) Merupakan suatu proses untuk menghilangkan bagianbagian yang tidak diperlukan pada masukan untuk proses selanjutnya. Beberapa contoh pra pemrosesan adalah noise filtering. 3. Segmentasi (Segmentation) Merupakan proses pemisahan area pengamatan pada setiap karakter yang dideteksi. 4. Normalisasi (Normalization) Merupakan proses pengubahan dimensi area pengamatan setiap karakter dan ketebalan karakter. Dalam OCR algoritma yang digunakan dalam proses ini adalah algoritma penskalaan (scaling) dan penghalusan (thinning). 5. Ekstraksi Fitur (Feature Extraction) Merupakan proses untuk mengambil ciri-ciri tertentu dari karakter yang diamati. 6. Pengenalan (Recognition) Merupakan proses untuk mengenali karakter yang diamati dengan cara membandingkan ciri-ciri yang diperoleh dengan ciri-ciri karakter yang ada pada basis data. 7. Pasca Pemrosesan (Postprocessing) Merupakan proses koreksi ejaan. E. Web Service Menurut W3C [8] Web Service adalah suatu sistem perangkat lunak yang dirancang untuk mendukung interaksi mesin ke mesin pada suatu jaringan. Perangkat lunak aplikasi yang ditulis dalam berbagai bahasa pemrograman dan berjalan pada berbagai platform dapat menggunakan Web Service untuk pertukaran data pada jaringan. Dalam hal ini Web Service digunakan sebagai perantara pertukaran data berkas antara SI Beasiswa dengan aplikasi verifikasi berkas beasiswa. F. Precision dan Recall Untuk menghitung tingkat performansi suatu sistem yang memiliki kemampuan untuk mendapatkan kembali informasi-informasi tertentu dapat menggunakan perhitungan precision dan recall. Precision adalah tingkat ketepatan antara informasi yang diminta oleh pengguna dengan
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6
3
jawaban yang diberikan oleh sistem. Sedangkan recall adalah tingkat keberhasilan sistem dalam menemukan kembali sebuah informasi. Secara matematis, rumus untuk menghitung presisi dan recall dapat dilihat pada Persamaan 1 dan Persamaan 2. 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = 𝑟𝑒𝑐𝑎𝑙𝑙 =
𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑡𝑒𝑚𝑠 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 𝑖𝑡𝑒𝑚𝑠
𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑡𝑒𝑚𝑠 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑡𝑒𝑚𝑠
(1)
(2)
Recall merupakan ukuran sensitivitas suatu information retriever dalam menemukan informasi-informasi yang sebenarnya relevan dengan permintaan[9].
B. Perancangan Proses Beberapa proses yang digunakan dalam merancang aplikasi verifikasi berkas ini adalah proses ekstraksi berkas gambar menggunakan Optical Character Recognition, proses pengenalan jenis berkas, proses pencarian nama pemilik berkas, proses pencocokan kumpulan kata menggunakan algoritma Soundex, proses pencocokan kumpulan kata menggunakan algoritma Levenshtein Distance, dan proses pencocokan kata menggunakan algoritma Longest Common Subsequences. 1.
Proses Ekstraksi Berkas Gambar Menggunakan Optical Character Recognition Proses ekstraksi berkas berupa berkas gambar merupakan tahap awal yang harus dilakukan untuk mendapatkan semua informasi data yang terdapat pada berkas gambar. Keseluruhan proses ini digambarkan pada Gambar 2.
2.
Proses Pengenalan Jenis Berkas Proses ini berfungsi untuk mengenali jenis berkas yang diunggah oleh pengguna. Proses utama yang dilakukan yaitu mencari kumpulan kata kunci berkas dari basis data, lalu membandingkannya dengan kumpulan kata yang didapat dari hasil ekstraksi.
III. ANALISIS DAN PERANCANGAN A. Deskripsi Umum Sistem Sistem yang dibuat yaitu berupa aplikasi situs web dengan bahasa pemrograman ASP .NET. Aplikasi ini dapat melakukan verifikasi jenis dan kepemilikan berkas beasiswa berupa berkas gambar yang diunggah oleh mahasiswa. Beberapa jenis berkas gambar yang bisa diverifikasi menggunakan aplikasi ini adalah berkas yang mempunyai ekstensi JPEG, JPG, TIF, GIF dan PNG. Untuk dapat melakukan proses verifikasi data pada berkas gambar, terlebih dahulu diperlukan proses ekstraksi data dari berkas gambar ke dalam bentuk kumpulan kata menggunakan teknologi Optical Character Recognition. Setelah kumpulan data dari ekstraksi berkas gambar didapat, dilakukan verifikasi jenis berkas yaitu dengan pendeteksian sekumpulan kata kunci berkas pada kumpulan data yang didapat. Jika satu atau lebih kata kunci ditemukan pada kumpulan data, maka jenis berkas yang diunggah dianggap valid dan masuk proses verifikasi selanjutnya. Proses verifikasi yang kedua yaitu verifikasi kepemilikan berkas yang dilakukan dengan cara membandingkan nama yang didapat dari hasil analisa teknologi Optical Character Recognition dengan nama yang ingin dibandingkan. Proses perbandingan kedua nama tersebut menggunakan beberapa algoritma pencocokan kumpulan kata diantaranya adalah algoritma Soundex, Levenshtein Distance, dan Longest Common Subsequences. Dari perbandingan tersebut, aplikasi akan menentukan hasil valid atau tidaknya nama yang tertera pada berkas gambar. Aplikasi situs web ini juga mempunyai fitur layanan Web Service sehingga memungkinkan sistem ini bisa diakses oleh sistem lain untuk keperluan verifikasi berkas lain. Dengan adanya aplikasi ini, pengecekan berkas oleh manusia dapat dikurangi sehingga dapat mempercepat proses seleksi pemberian beasiswa. Diagram arsitektur dari sistem digambarkan pada Gambar 1. Administrator
Mahasiswa
Pencocokan kumpulan kata Pendeteksian kata kunci berkas nama mahasiswa
Mulai
Berkas gambar
Kumpul an kata
Pencarian baris kumpulan kata yang mengandung nama mahasiswa
Berkas gambar dengan noise yang diminim alisir
Proses ekstraksi berkas gambar
Pengurangan noise dengan teknik resize, gray-scale dan contrast
Baris string ada yang mengandung nama mahasiswa? Ya
Tidak
Simpan dalam variabel nama mahasiswa
Selesai
Gambar 2. Diagram Alir Proses Ekstraksi Berkas Gambar Mulai Variabel nama mahasiswa yang dibandingkan
Proses perbandingan kode fonetis nama yang dibandingkan
Kode fonetis nama yang dibandingkan
Kode fonetis mempunyai kemiripan?
Proses pengkodean string nama mahasiswa menggunakan algoritma Soundex
Tidak
Ya
Aplikasi Verifikasi
SI Beasiswa Web Service Berkas Persyaratan Beasiswa SI Beasiswa
Ekstraksi kumpulan kata
Optical Character Recognition (OCR) Aplikasi Verifikasi Berkas
Gambar 1. Diagram Arsitektur Sistem
Simpan dalam variabel nama mahasiswa
Selesai
Gambar 3. Diagram Alir Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Soundex
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6 Mulai
Proses pencarian perbedaan karakter string nama mahasiswa menggunakan algoritma Levenshtein Distance
Jumlah perbedaan karakter yang dibandingkan sangat rendah?
Variabel nama mahasiswa yang dibandingkan
Tidak
Proses pencocokan kumpulan kata dengan menggunakan algoritma Longest Common Subsequence ini mempunyai tugas untuk membandingkan kumpulan kata nama yang didapat dari proses ekstraksi dengan kumpulan kata nama yang ingin dibandingkan berdasarkan jumlah rangkaian karakter terpanjang. Keseluruhan proses ini digambarkan pada Gambar 5. IV. IMPLEMENTASI A. Implementasi Proses Ekstraksi Berkas Gambar Menggunakan Optical Character Recognition
Ya
Simpan dalam variabel nama mahasiswa
4
Selesai
Gambar 4. Diagram Alir Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Levenshtein Distance Mulai
Fungsi Process dari objek TesseractEngine merupakan implementasi dari proses ekstraksi informasi dari sebuah berkas gambar. Parameter fungsi ini adalah sebuah Bitmap berkas gambar yang akan diverifikasi. Tipe nilai kembalian dari fungsi ini adalah String. B. Implementasi Proses Pengenalan Jenis Berkas
Proses pencarian rangkaian karakter terpanjang dari string nama mahasiswa menggunakan algoritma Longest Common Subsequences
Rangkaian karakter yang didapat sangat sedikit
Variabel nama mahasiswa yang dibandingkan
Ya
Tidak Simpan dalam variabel nama mahasiswa
Selesai
Gambar 5. Diagram Alir Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Longest Common Subsequence
3.
4.
Proses Pencarian Nama Pemilik Berkas Proses ini berfungsi untuk mengenali nama pemilik berkas yang diunggah oleh pengguna. Proses utama yang dilakukan yaitu mencari kumpulan kata yang mengandung kata “Nama”, “Nama Lengkap”, dan lain sebagainya dari kumpulan kata yang didapat dari hasil ekstraksi. Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Soundex Proses pencocokan kumpulan kata dengan menggunakan algoritma Soundex ini mempunyai tugas untuk membandingkan kumpulan kata nama yang didapat dari proses ekstraksi dengan kumpulan kata nama yang ingin dibandingkan berdasarkan nada pengucapan (fonetis) yang dimiliki oleh manusia. Keseluruhan proses ini digambarkan pada Gambar 3.
5.
Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Levenshtein Distance Proses pencocokan kumpulan kata dengan menggunakan algoritma Levenshtein Distance ini mempunyai tugas untuk membandingkan kumpulan kata nama yang didapat dari proses ekstraksi dengan kumpulan kata nama yang ingin dibandingkan berdasarkan perbedaan karakter di antara keduanya. Keseluruhan proses ini digambarkan pada Gambar 4.
6.
Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Longest Common Subsequence
Fungsi ReadDocumentType merupakan implementasi dari proses pengenalan jenis berkas yang diverifikasi. Parameter fungsi ini adalah sebuah String hasil ekstraksi berkas gambar. Tipe nilai kembalian dari fungsi ini adalah Boolean yang menyatakan benar atau tidaknya jenis berkas yang diverifikasi. C. Implementasi Proses Pencarian Nama Pemilik Berkas Fungsi ReadDocumentAuthor merupakan implementasi dari proses pendeteksian karakter nama pemilik berkas yang diverifikasi. Parameter fungsi ini adalah sebuah String hasil ekstraksi berkas gambar. Tipe nilai kembalian dari fungsi ini adalah String karakter nama pemilik berkas. D. Implementasi Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Soundex Fungsi Soundex merupakan implementasi dari algoritma Soundex. Parameter fungsi ini adalah sebuah String yang akan dicari kode fonetisnya. Tipe nilai kembalian dari fungsi ini adalah String. Implementasi fungsi ini dapat dilihat pada Gambar 6. E. Implementasi Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Levenshtein Distance Fungsi LevenshteinDistance merupakan implementasi dari algoritma Levenshtein Distance. Parameter fungsi ini adalah dua String yang akan dihitung jumlah perbedaan karakter di antara String tersebut. Tipe nilai kembalian dari fungsi ini adalah Integer. Implementasi fungsi ini dapat dilihat pada Gambar 7. function Soundex (x[1..m]) CurrCode ← empty PrevCode ← empty Result ← empty Normalization ← empty if x != 0 normalization ← IndonesianNormalization (x[i]) for i ← 0 to m result ← ToUpper (normalization) CurrCode ← Encode (normalization) if CurrCode != PrevCode result ← CurrCode if result == 4 break if CurrCode != empty PrevCode ← CurrCode return result
Gambar 6. Pseudocode Fungsi Soundex
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6 function LevenshteinDistance(s1[1..m], s2[1..n]) levDist <- array (0..m, 0..n) for i ← 0 to m for j ← 0 to n if i = 0 levDist[i,j] ← j else if j = 0 levDist[i,j] ← i else if (s1[i] = s2[j]) levDist[i,j] ← levDist [i-1,j-1] else levDist[i,j] ← 1 + minimum (levDist[i-1,j-1], levDist[i-1,j], levDist[i-1][j-1]) return levDist[i,j]
5
Nama Berkas Gambar Berkas1
Berkas2
Gambar 7. Pseudocode Fungsi LevenshteinDistance Berkas3 function LCS (x[1..m], y[1..n]) lcs ← array (0..m, 0..n) for i ← 0 to m for j ← 0 to n if i = 0 or j = 0 lcs[i,j] ← 0 else if x[i] = y[j] lcs[i,j] ← lcs[i-1,j-1] + 1 else lcs[i,j] ← max (lcs[i,j-1], lcs[i-1,j]) return lcs[m,n]
Gambar 8. Pseudocode Fungsi LCS
F. Implementasi Proses Pencocokan Kumpulan Kata Menggunakan Algoritma Longest Common Subsequence Fungsi LCS merupakan implementasi dari algoritma Longest Common Subsequence. Parameter fungsi ini adalah dua String yang akan diperiksa apakah salah satu String merupakan LCS dari String yang lain. Tipe nilai kembalian dari fungsi ini adalah String. Implementasi fungsi ini dapat dilihat pada Gambar 8. V. PENGUJIAN DAN EVALUASI Pengujian fitur verifikasi berkas persyaratan beasiswa dilakukan dengan menggunakan beberapa data uji. Data uji tersebut berupa lima buah berkas gambar yang diverifikasi secara manual oleh manusia. Data berkas gambar yang digunakan dalam pengujian dapat dilihat pada Tabel 3. Persentase kualitas berkas yang terdapat pada tabel merupakan tingkat kejelasan data pada berkas gambar saat dilakukan pembesaran gambar pada komputer dilihat dari sudut pandang mata manusia. Sedangkan kata kunci berkas dan nama dari berkas yang terdapat pada tabel merupakan data kata kunci dan nama pemilik berkas yang didapatkan dari berkas gambar yang diverifikasi dengan menggunakan mata manusia. Untuk mengukur performa dari sistem perlu dilakukan perhitungan tingkat precision dan recall. Precision dihitung dari jumlah informasi relevan yang berhasil dideteksi melalui pengecekan manual oleh manusia dibandingkan dengan seluruh hasil deteksi yang dilakukan oleh sistem. Sedangkan recall didapatkan dari perbandingan jumlah informasi relevan yang berhasil dideteksi oleh sistem dengan jumlah kata kunci atau nama pemilik berkas pada berkas yang diverifikasi berdasarkan informasi dari pengecekan secara manual oleh manusia. Hasil perhitungan tingkat precision dan recall dari sistem dalam pencarian kata kunci berkas pada berkas yang diverifikasi dapat dilihat pada Tabel 4, sedangkan pencarian karakter dari kumpulan kata nama pemilik berkas yang tertera pada berkas yang diverifikasi dapat dilihat pada Tabel 5.
Berkas4 Berkas5
Tabel 3. Daftar Berkas Gambar Untuk Data Uji Persent Kata Kunci Nama Nama ase Berkas Dari Yang Kualitas Berkas Dibandi Berkas ngkan > 80% Ditemukan Slamet Slamet Syamsud Syamsud iman iman < 60% Ditemukan Nengah Nengah Widiada Widiada > 80% Ditemukan Maryon Maryon o o < 40% Ditemukan Nengah Nengah Widiada Widiada > 70% Ditemukan Machmu Machmu d d
Validit as Berkas Valid
Valid Valid Valid Valid
Tabel 4. Daftar Precision dan Recall dari Hasil Pengujian Pencarian Kata Kunci Berkas Data Uji Retrieve Relevant Relevant Precision Recall Retrieve Berkas1 1 1 1 1 1 Berkas2 0 2 0 1 0 Berkas3 4 5 4 1 0.8 Berkas4 0 6 0 1 0 Berkas5 2 3 2 1 0.67 Average 1 0.494 Tabel 5. Daftar Precision dan Recall dari Hasil Pengujian Pencarian Karakter Nama Pemilik Berkas Data Uji Retrieve Relevant Relevant Precision Recall Retrieve Berkas1 18 18 18 1 1 Berkas2 17 20 17 1 0.85 Berkas3 7 7 7 1 1 Berkas4 0 14 0 1 0 Berkas5 7 7 7 1 1 Average 1 0.77
Hasil uji coba pada Berkas1 dalam pencarian kata kunci pada berkas yang diverifikasi menunjukkan nilai precision sebesar 1 dan recall sebesar 1. Di samping itu, hasil uji coba pada Berkas1 dalam pencarian karakter nama pemilik berkas pada berkas yang diverifikasi menunjukkan nilai precision sebesar 1 dan recall sebesar 1. Kedua data tersebut menunjukkan jika data kata kunci berkas serta nama pemilik berkas dapat dideteksi oleh sistem dan semua hasil deteksi relevan. Hasil uji coba pada Berkas3 dan Berkas5 juga menunjukkan keberhasilan verifikasi berkas seperti pada uji coba Berkas1. Hasil uji coba pada Berkas2 dalam pencarian kata kunci pada berkas yang diverifikasi menunjukkan nilai precision sebesar 1 dan recall sebesar 0. Nilai recall tersebut menunjukkan jika sistem gagal mendeteksi adanya kata kunci pada berkas. Hal ini disebabkan karena berkas yang diverifikasi mempunyai kualitas gambar yang lumayan buruk. Kualitas buruk dari berkas gambar disebabkan banyaknya gangguan seperti bayangan dan bercak hitam disekitar huruf yang akan diekstraksi oleh Optical Character Recognition. Gangguan-gangguan tersebut menyebabkan kumpulan kata hasil dari proses ekstraksi tidak dapat secara utuh didapatkan sehingga sistem tidak dapat mendeteksi kata kunci berkas. Sebaliknya, hasil uji coba pada Berkas2 dalam pencarian karakter nama pemilik berkas pada berkas yang diverifikasi menunjukkan nilai precision sebesar 1 dan recall sebesar 0.85. Meskipun kumpulan kata hasil ekstraksi dari uji coba kedua ini tidak didapatkan secara utuh, sistem tetap dapat mendeteksi nama pemilik berkas. Hal ini disebabkan
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6 karena gangguan pada kalimat yang mengandung nama pemilik berkas tidak separah gangguan pada bagian-bagian lain dari berkas yang diverifikasi. Untuk uji coba keempat dilakukan pengujian verifikasi terhadap berkas yang mempunyai kualitas lebih buruk dari berkas gambar uji coba kedua. Hasilnya didapatkan nilai precision sebesar 1 dan recall sebesar 0 dalam pencarian kata kunci maupun nama pemilik berkas pada berkas yang diverifikasi. Data tersebut menunjukkan gagalnya verifikasi yang dilakukan terhadap berkas uji coba keempat ini. Alasan gagalnya verifikasi ini sama seperti pada uji coba kedua yaitu disebabkan karena adanya gangguan. Dari lima kali uji coba yang dilakukan, hasil pengujian pencarian kata kunci berkas menunjukkan rata-rata nilai precision sebesar 1 dan nilai recall sebesar 0.494. Di samping itu, hasil pengujian pencarian karakter nama pemilik berkas menunjukkan rata-rata nilai precision sebesar 1 dan nilai recall sebesar 0.77. Nilai precision sebesar 1 menunjukkan jika data yang didapatkan oleh sistem sudah relevan dengan kata kunci dan karakter nama pemilik berkas yang didapat secara manual dari sudut pandang mata manusia. Nilai recall sebesar 0.494 dan 0.77 menunjukkan jika sistem tidak bisa mendapatkan kata kunci dan karakter nama pemilik berkas secara utuh. Hal ini disebabkan karena adanya gangguan pada berkas yang diverifikasi. VI. KESIMPULAN DAN SARAN Dari hasil pengamatan selama perancangan, implementasi, dan proses pengujian yang dilakukan, kesimpulan yang dapat diambil berdasarkan rumusan masalah yang ada adalah sebagai berikut ini: 1. Sistem dapat melakukan verifikasi data berkas persyaratan beasiswa dengan cara mendeteksi kata kunci berkas dan nama pemilik berkas memanfaatkan teknologi Optical Character Recognition dengan menggunakan layanan Web Service. 2. Sistem berhasil mendeteksi karakter nama pemilik berkas beserta kata kunci berkas dari hasil ekstraksi Optical Character Recognition. Keberhasilan dalam proses pendeteksian ini tergantung dengan kualitas gambar yang diverifikasi. Semakin rendah kualitas gambar, maka kumpulan kata yang didapat dari hasil ekstraksi akan tidak utuh sehingga data kata kunci berkas dan nama pemilik berkas tidak dapat ditemukan. Hal ini ditunjukkan dengan rata-rata nilai recall dari sistem sebesar 0.494 pada pendeteksian kata kunci berkas dan 0.77 pada pendeteksian karakter nama pemilik berkas. 3. Sistem berhasil melakukan verifikasi karakter nama pemilik berkas dengan karakter nama yang dibandingkan menggunakan kombinasi algoritma Soundex, algoritma Levenshtein Distance, dan algoritma Longest Common Subsequence. Pada kesempatan pengembangan aplikasi selanjutnya, penulis menyarankan untuk mengembangkan proses pengurangan gangguan pada berkas gambar yang diverifikasi guna menambah tingkat keutuhan data yang diperoleh dari hasil ekstraksi Optical Character Recognition. Di samping itu juga perlu untuk mengembangkan proses optimasi verifikasi berkas guna menambah tingkat kecepatan dan ketepatan verifikasi serta pendeteksian berkas gambar palsu yang dimanipulasi datanya.
6 DAFTAR PUSTAKA [1]
[2] [3]
[4]
[5] [6] [7] [8] [9]
Creativyst, Inc.”Understanding Classic Soundex Algorithms”. [Online]. Tersedia: http://www.creativyst.com/Doc/Articles/SoundEx1/SoundEx1.htm. [Diakses pada 8 Februari 2014]. Karhendana, Arie. Normalisasi String untuk Optimasi Phonetic String Matching dalam Bahasa Indonesia. STEI, ITB, 2004. GenealogyInTime Magazine, “Soundex Coding Rules”.[Online]. Tersedia: http://www.genealogyintime.com/GenealogyResources/Articles/wha t_is_soundex_and_how_does_soundex_work_page2.html. [Diakses pada 8 Februari 2014]. Karhendana, Arie, Wizanajani, Dicky, dan Yuliawan, Fajar. 2004. Normalisasi String untuk Optimasi Phonetic String Matching dalam Bahasa Indonesia. Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung “Vladimir I. Levenshtein biography”. [Online]. Tersedia: http://www.ieeeghn.org/wiki/index.php/Vladimir_I._Levenshtein. [Diakses pada 8 Februari 2014]. Pinzon, Yoan. Algorithms for Approximate String Matching. Universidad Nacional de Colombia, 2006. “Optical Character Recognition”. [Online]. Tersedia: http://searchcontentmanagement.techtarget.com/definition/OCRoptical-character-recognition. [Diakses pada 23 Januari 2014] W3C, “Web Services Tutorial”. [Online]. Tersedia: http://www.w3schools.com/webservices/default.asp. [Diakses pada 23 Januari 2014]. P. Raghavan, C. D. Manning and H. Schutze, "Evaluation in Information Retrieval," in Introduction to Information Retrieval, Cambridge University Press, 2008.
