JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6

1

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

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, palato-

alveolar, 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

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: siti@its-sby.edu

P

JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6

2

Tabel 2. Aturan Translasi Q-Gram

Q-Gram Contoh

Awal Translasi Awal Translasi

KH HH Rakhmat Rahhmat

DJ JJ Endjang Enjjang

TJ CC Itjang Iccang

CQ, CK KK Erick Erikk

PH FF Philip Ffilip

DZ ZZ Dzikri Zzikri

SJ SY Sjahrir Syahrir

SY SS Syifa Ssifa

BH, DH, GH,

JH, SH, TH, ZH

BB, DD, GG,

JJ, SS, TT, ZZ

Ardhi Arddi

V F Saviena Safiena

KS XX Wicaksono Wicaxxono

OE UU Wahyoedi Wahyuudi

IE II Arie Arii

Y I Donny Donni

6. Menulis empat posisi pertama yang mengikuti pola:

<uppercase letter><digit><digit><digit>. 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

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 bagian-

bagian 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].

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.

Ekstraksi

kumpulan

kata

Optical Character

Recognition (OCR)

Aplikasi Verifikasi

Pencocokan

kumpulan kata

nama mahasiswa

SI Beasiswa Aplikasi Verifikasi Berkas

Mahasiswa Administrator

SI Beasiswa

Web Service

Berkas

Persyaratan

Beasiswa

Pendeteksian kata

kunci berkas

Gambar 1. Diagram Arsitektur Sistem

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.

Mulai

Berkas

gambar

Pengurangan

noise

dengan

teknik resize,

gray-scale

dan contrast

Berkas

gambar

dengan

noise

yang

diminim

alisir

Proses

ekstraksi

berkas

gambar

Kumpul

an kata

Pencarian baris kumpulan

kata yang mengandung

nama mahasiswa

Baris string

ada yang

mengandung

nama

mahasiswa?

Simpan dalam

variabel nama

mahasiswa

SelesaiYa

Tidak

Gambar 2. Diagram Alir Proses Ekstraksi Berkas Gambar

Mulai

Variabel nama

mahasiswa yang

dibandingkan

Proses

pengkodean

string nama

mahasiswa

menggunakan

algoritma

Soundex

Kode fonetis

nama yang

dibandingkan

Proses

perbandingan

kode fonetis

nama yang

dibandingkan

Kode fonetis

mempunyai

kemiripan?

Simpan dalam variabel

nama mahasiswaSelesai

Ya

Tidak

Gambar 3. Diagram Alir Proses Pencocokan Kumpulan Kata Menggunakan

Algoritma Soundex

JURNAL TEKNIK POMITS Vol. 1, No. 1, (2014) 1-6

4

Mulai

Variabel nama

mahasiswa

yang

dibandingkan

Proses pencarian perbedaan

karakter string nama mahasiswa

menggunakan algoritma

Levenshtein Distance

Jumlah

perbedaan

karakter yang

dibandingkan

sangat rendah?

Simpan dalam

variabel nama

mahasiswa

Selesai

Ya

Tidak

Gambar 4. Diagram Alir Proses Pencocokan Kumpulan Kata Menggunakan

Algoritma Levenshtein Distance

Mulai

Variabel nama

mahasiswa

yang

dibandingkan

Proses pencarian rangkaian karakter

terpanjang dari string nama

mahasiswa menggunakan algoritma

Longest Common Subsequences

Rangkaian

karakter yang

didapat sangat

sedikit

Simpan dalam

variabel nama

mahasiswa

Selesai

Tidak

Ya

Gambar 5. Diagram Alir Proses Pencocokan Kumpulan Kata Menggunakan

Algoritma Longest Common Subsequence

3. 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.

4. 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

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

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

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

5

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] Gambar 7. Pseudocode Fungsi LevenshteinDistance

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.

Tabel 3. Daftar Berkas Gambar Untuk Data Uji

Nama Berkas Gambar

Persentase Kualitas Berkas

Kata Kunci Berkas

Nama Dari Berkas

Nama Yang Dibandingkan

Validitas Berkas

Berkas1 > 80% Ditemukan Slamet Syamsudiman

Slamet Syamsudiman

Valid

Berkas2 < 60% Ditemukan Nengah Widiada

Nengah Widiada

Valid

Berkas3 > 80% Ditemukan Maryono

Maryono

Valid

Berkas4 < 40% Ditemukan Nengah Widiada

Nengah Widiada

Valid

Berkas5 > 70% Ditemukan Machmud

Machmud

Valid

Tabel 4. Daftar Precision dan Recall dari Hasil Pengujian Pencarian Kata

Kunci Berkas

Data Uji Retrieve Relevant Relevant Retrieve

Precision Recall

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 Retrieve

Precision Recall

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

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.

DAFTAR PUSTAKA

[1] Creativyst, Inc.”Understanding Classic Soundex Algorithms”.

[Online]. Tersedia:

http://www.creativyst.com/Doc/Articles/SoundEx1/SoundEx1.htm.

[Diakses pada 8 Februari 2014].

[2] Karhendana, Arie. Normalisasi String untuk Optimasi Phonetic

String Matching dalam Bahasa Indonesia. STEI, ITB, 2004.

[3] 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].

[4] 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

[5] “Vladimir I. Levenshtein biography”. [Online]. Tersedia:

http://www.ieeeghn.org/wiki/index.php/Vladimir_I._Levenshtein. [Diakses pada 8 Februari 2014].

[6] Pinzon, Yoan. Algorithms for Approximate String Matching. Universidad Nacional de Colombia, 2006.

[7] “Optical Character Recognition”. [Online]. Tersedia: http://searchcontentmanagement.techtarget.com/definition/OCR-

optical-character-recognition. [Diakses pada 23 Januari 2014]

[8] W3C, “Web Services Tutorial”. [Online]. Tersedia: http://www.w3schools.com/webservices/default.asp. [Diakses pada

23 Januari 2014].

[9] P. Raghavan, C. D. Manning and H. Schutze, "Evaluation in Information Retrieval," in Introduction to Information Retrieval,

Cambridge University Press, 2008.