PROPOSAL TUGAS AKHIR

Penerapan Levenshtein Distance untuk

Pengoreksian Kesalahan OCR pada

Dokumen Teks Bahasa Indonesia

Disusun Oleh:

Sekar Rini Abidin

NIM. M0511045

JURUSAN INFORMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

2014

UNIVERSITAS SEBELAS MARET JURUSAN INFORMATIKA

PROPOSAL TUGAS AKHIR Nama : Sekar Rini Abidin No. Mhs : M0511045

PERSETUJUAN PEMBIMBING

Proposal Tugas Akhir ini telah disetujui oleh :

Sari Widya Sihwi, S.Kom, MTI

NIP. 198304122009122003

1. JUDUL/ TOPIK

Penerapan Levenshtein Distance untuk Pengoreksian Kesalahan OCR pada Dokumen Teks

Bahasa Indonesia.

2. PENDAHULUAN

2.1 Latar Belakang

Bahasa Indonesia adalah bahasa resmi dan bahasa persatuan Republik

Indonesia (Pasal 36 UUD 1945) (Katubi, 2008). Bahasa Indonesia digunakan luas

di perguruan-perguruan, media massa, sastra, surat menyurat resmi dan dinas,

bisnis, dan berbagai forum publik lainnya (Rahayu, 2007) (Sudarsa dkk 1991).

Sehingga dapat dikatakan bahwa Bahasa Indonesia dapat digunakan oleh semua

warga Indonesia (Katubi, 2008).

Penggunaan Bahasa Indonesia dengan ejaan yang baik dan benar dapat

diartikan pemakaian ragam bahasa yang serasi dan mengikuti kaidah bahasa. Pada

kondisi tertentu, yaitu pada kondisi formal baik lisan maupun tulisan, ejaan Bahasa

Indonesia menjadi prioritas utama (Kartini, 2013). Bahasa Indonesia wajib

digunakan dalam komunikasi resmi di lingkungan kerja pemerintah dan swasta

(Pasal 33 ayat 1 UU RI No.24 tahun 2009), juga wajib digunakan dalam laporan

setiap lembaga atau perseorangan kepada instansi pemerintahan (Pasal 34 UU RI

No. 24 tahun 2009).

Dalam dunia komputer, pengecekkan ejaan merupakan proses dari deteksi.

Terkadang komputer memberikan saran ejaan pada ejaan kata yang salah pada teks.

Pada dasarnya, pengecekkan ejaan merupakan program komputer yang

menggunakan kamus (Bassil dan Alwani, 2012a). Semakin besar kamusnya,

ketelitian pendeteksian kesalahannya semakin tinggi. Fakta yang terjadi banyak

ditemukan masalah ketika pada proses pengecekkan terbatas pada koleksi kata

yang sedikit (Budhi dkk, 2006) (Bassil dan Alwani, 2012a). Hasilnya, kualitas

pendeteksian kesalahan rendah dan hal ini sering terjadi pada dokumen teks, bukan

dokumen gambar, suara, maupun video (Bassil dan Alwani, 2012a).

KBBI (Kamus Besar Bahasa Indonesia) adalah kamus ekabahasa resmi

Bahasa Indonesia yang disusun oleh tim penyusun Kamus Pusat Bahasa (Pusat

Bahasa, 2008). Kamus ini menjadi acuan tertinggi Bahasa Indonesia yang baku

(Kusmayadi, 2006), karena kamus ini merupakan kamus Bahasa Indonesia

terlengkap dan yang paling akurat yang pernah diterbitkan oleh penerbit yang

memiliki hak paten dari pemerintah Republik Indonesia (Widada dan Prayogi,

2010). Hingga saat ini KBBI adalah edisi keempat yang cetakan pertamanya

diterbitkan pada tahun 2008, memuat lebih dari 90.000 lema, yakni memuat

kosakata umum dan istilah (Pusat Bahasa, 2008). Oleh karena itu KBBI dapat

diandalkan membuat performa kamus kata yang bagus untuk pengoreksian

kesalahan kata (Widada dan Prayogi, 2006) (Pusat Bahasa, 2008).

OCR (Optical Character Recognition) adalah proses mentransformasikan

citra tulisan tangan atau dokumen ketikan yang masih berbentuk gambar menjadi

teks digital (Bassil dan Alwani, 2012b), teks yang dapat diedit menggunakan

komputer (Singh, 2013). Citra gambar tersebut didapatkan dari hasil scanner atau

kamera (Bassil dan Alwani, 2012c).

OCR mempunyai enam tahapan (Singh, 2013) (Bassil dan Alwani, 2012b).

Pertama, akuisisi gambar, dokumen pada kertas discan menggunakan scanner atau

difoto. Kedua, pre-processing, gambar hasil scan atau foto diproses dan

dimodifikasi menggunakan algoritma image processing seperti mengurangi noise,

menormalisasi data, dan kompresi data. Ketiga, segmentasi, yaitu dokumen dibagi

menjadi komponen-komponen lebih kecil, yang disebut objek gambar. Keempat,

ekstraksi gambar, mendekomposisikan beberapa gambar untuk memfasilitasi

pengenalan karakter dan kata. Kelima, klasifikasi gambar, semua gambar yang

sudah diekstrak diklasifikasikan ke kelas dan kategori yang independen. Keenam,

post-processing, tahapan terakhir dari sistem OCR yang bertujuan untuk

mendeteksi dan mengoreksi kesalahan ejaan pada teks keluaran (Bassil dan

Alwani, 2012b). Proses mengoreksi ini adalah proses yang sangat penting untuk

menghasilkan kesalahan mendekati nol (Singh, 2013).

Ada dua tipe kesalahan OCR, yaitu kesalahan kata (real-word) dan

kesalahan bukan kata (non-word) (Bassil dan Alwani, 2012c). Kesalahan kata yaitu

kesalahan mengeja kata yang tidak sesuai dengan konteks kalimat meskipun kata

tersebut ada. Sedangkan kesalahan bukan kata yaitu kesalahan mengeja kata dan

kata tersebut tidak ada (Bassil dan Alwani, 2012b).

Post-processing terdiri dari tiga macam, yaitu manual, semi otomatis, dan

otomatis (Singh, 2013). Semi otomatis dilakukan oleh manusia dengan cara

mengoreksi kesalahan. Sedangkan otomatis dilakukan dengan cara mendeteksi dan

mengoreksi kesalahan oleh sistem. Karena semi otomatis dan manual memakan

waktu dan tenaga, maka diperlukan otomatis (Sigh, 2013) (Narender dan Rao,

2012).

Sistem OCR masih salah dan tidak akurat dalam menghasilkan teks dan

banyak terjadi kesalahan pengejaan, terlebih jika kualitas dokumen rendah (Bassil

dan Alwani, 2012b) (Singh, 2013) (Bassil dan Alwani, 2012c). Penelitian yang

dilakukan oleh Yousses Bassil dan Mohammad Alwani menghasilkan bahwa

tingkat keerorran OCR lebih tinggi dibandingkan dengan metode yang

diusulkannya (Bassil dan Alwani, 2012b). Dokumen yang digunakan adalah

dokumen Bahasa Inggris dan Perancis. Metode yang digunakan pada penelitian

tersebut (Bassil dan Alwani, 2012b) adalah pendeteksian kesalahan OCR, generator

untuk memberikan kandidat kata yang salah, dan pengoreksian kesalahan OCR.

Penelitian lain yang tentang koreksi kata pada teks artikel Bahasa Indonesia

menggunakan empat tahapan (Budhi dkk, 2006) yaitu pemilihan lexeme atau

bentuk tulisan, penentuan jenis token, pemeriksaan kata, dan output kata-kata yang

salah juga kata-kata pengganti yang disarankan untuk setiap kata yang salah.

Lavenshtein distance adalah algoritma yang berguna untuk memeriksa

kemiripan dari dua buah string yang umumnya ditemukan pada aplikasi

pengecekkan suatu ejaan (Adiwidya, 2009). Lavenshtein melibatkan operasi

insertion (penambahan), deletion (penghapusan), dan atau substitution

(penggantian) (Adiwidya, 2009) (Atmajaya, 2012). Algoritma ini terbukti menjadi

algoritma yang dinamis dengan kompleksitas O( ) (Adiwidya, 2009).

Pada penelitian ini akan menggabungkan metode dari penelitian-penelitian

sebelumnya tentang koreksi kata untuk digunakan pada post-processing OCR.

Metode yang akan digunakan ada tiga tahap, yaitu deteksi kesalahan OCR,

penyaranan kandidate kata, dan pengoreksian kesalahan OCR. Pada tahap deteksi

kesalahan OCR terdiri dari dua tahap, yaitu pemilihan lexeme dan penentuan jenis

token (tokenize). Pada tahap penyaranan kandidate kata menggunakan algoritma

Lavenshtein distance.

2.2 Rumusan Masalah

Seberapa besar tingkat error dan efektivitas metode yang diusulkan apabila

KBBI dan Levenshtein Distance diterapkan pada pengoreksian kesalahan Optical

Character Recognition pada dokumen teks Bahasa Indonesia?

2.3 Batasan Masalah

Pembatasan masalah pada penelitian ini adalah sebagai berikut.

1. Sistem OCR yang digunakan adalah OmniPage.

2. Dokumen teks yang digunakan dari dokumen teks ketikan, bukan tulisan

tangan.

3. Bahasa Indonesia yang diterapkan adalah Bahasa Indonesia baku, bukan

yang tidak baku.

3. Pengoreksian hanya sebatas kata, bukan tata bahasa.

2.4 Tujuan Penelitian

Menerapkan KBBI dan Levenshtein Distance untuk pengoreksian kesalahan

Optical Character Recognition post-processing pada dokumen teks Bahasa

Indonesia, sehingga dapat diketahui nilai error dan efektivitasnya.

2.5 Manfaat Penelitian

Manfaat dari penelitian ini diharapkan dapat membantu mengoreksi

kesalahan pada Optical Character Recognition dan mengurangi kesalahan pada

teks yang dihasilkan.

3. PENELITIAN TERKAIT

Penelitian yang digunakan sebagai acuan adalah penelitian yang dilakukan

oleh Youssef Bassil dan Mohammad Alwani dengan judul OCR Context Sensitive

Error Correction Based on Google Web 1T 5-Gram Data Set (Bassil dan Alwani,

2012b). Masalah yang dibahas adalah OCR post-processing belum sempurna

karena masih banyak kesalahan dan tidak akurat dalam mengeja kata pada teks

yang dihasilkan, terlebih jika gambar hasil scan berkualitas rendah. Metode yang

diusulkan terdiri dari tiga algoritma yaitu, OCR error detection, candidate

spelling generation, dan OCR error correction. Data set yang digunakan adalah

google web 1T 5-gram karena mempunyai kosa kata yang luas. Dokumen yang

digunakan sebagai bahan adalah dokumen teks Bahasa Inggris dan dokumen teks

Bahasa Perancis. Hasilnya menunjukkan peningkatan drastis dalam mendeteksi

dan mengoreksi kesalahan OCR, yaitu 5 kali lipat (504%) pada dokumen teks

Bahasa Inggris dan 4 kali lipat (405) pada dokumen teks Bahasa Perancis.

Penelitian lain yang mendukung adalah penelitian yang juga dilakukan oleh

Youssef Bassil dan Mohammad Alwani dengan judul Context-sensitive Spelling

Correction Using Google Web 1T 5-gram Information (Bassil dan Alwani,

2012a). Masalah yang dibahas masih seputar pengoreksian kesalahan kata dan

ejaan pada dokumen teks yang disebabkan minimnya kosa-kata pada kamus di

dalam program computer. Penelitian yang dilakukan ini terlepas dari OCR.

Metode yang diusulkan untuk mengoreksi kesalahan ejaan non-word dan real-

word, yaitu error detection, candidate spelling generation, dan error correction.

Data set yang digunakan google web 1T 5-gram. Dokumen yang digunakan

sebagai contributor adalah 300 artikel dari berbagai domain, yaitu keuangan,

bisnis, IT, politik, kesehatan, olahraga, dan sebagainya. Semua artikel tersebut

ditotal terdiri dari 200.000 kata, termasuk kata, nama, domain, terminologi,

akronim, dan jargon. Hasilnya membuktikan bahwa metode yang diusulkan untuk

mendeteksi dan mengoreksi kesalahan jauh lebih efektif. Jika menggunakan GNU

Aspell, total error 49%, non word error 38%, real-word error 92%. Jika

menggunakan Ghotic test result, total error 38%, non word error 30%, real-word

error 71%. Ketika menggunaka metode yang diusulkan, total error menjadi 7%,

non word error 1%, dan real word error 30%.

Kedua penelitian yang dilakukan Youssef Bassil dan Mohammad Alwani

tersebut metode yang digunakan secara prinsip sama, hanya saja yang satu

diterapkan pada OCR dan yang satu dari dokumen teks biasa.

Terdapat penelitian mengenai spelling checker pada teks artikel Bahasa

Indonesia yang dilakukan oleh Gregorius S. Budi, Irwan Kristianto, dan Elvi

Suhartono (Budi dkk, 2006). Masalah yang dibahas adalah bahwa seperti bahasa-

bahasa lainnya, Bahasa Indonesia juga memiliki struktur yang membentuk bahasa

tersebut sehingga banyak orang dapat memahaminya. Tetapi pada penerapannya

dalam tulisan, banyak orang yang masih salah saat menulis kata Bahasa

Indonesia. Dari hal tersebut muncul ide pembuatan aplikasi untuk memeriksa kata

dalam Bahasa Indonesia yang benar dari sebuah inputan teks. Metode yang

digunakan terdiri dari empat tahap, yaitu pemilihan lexeme (bentuk tulisan),

penetuan jenis token (tokenize), pemeriksaan kata, dan output kata-kata yang

salah juga kata-kata pengganti yang disarankan untuk setiap kata yang salah.

Hasilnya dapat disimpulkan bahwa program aplikasi ini dapat digunakan untuk

memeriksa kebenaran kata Bahasa Indonesia.

Penelitian yang mendukung penggunaan Levenshtein distance adalah

penelitian yang dilakukan oleh Bernadino Madaharsa Dito Adiwidya dengan

judul Algoritma Levenshtein Dalam Pendekatan Approximate String Matching

(Adiwidya, 2009). Masalah yang dibahas adalah banyaknya mesin pencari yang

tersedia di internet. Ketika kita ingin mencari suatu kata kunci yang terletak

dalam suatu halaman web yang berisi berita, artikel, atau informasi lainnya,

seringkali dalam kata yang kita masukkan tidak sesuai dengan tata Bahasa

Indonesia yang benar. Benar disini dalam artian ejaan yang baku, memiliki suatu

imbuhan yang komponen katanya berbeda, ataupun salah ketik. Oleh karena itu

diperlukan suatu metode pendekatan pencarian string yang dapat memenuhi

keinginan tersebut. Algoritma yang digunakan adalah levenshtein distance dengan

pendekatan approximate string matching, yang meliputi operasi penghapusan,

penyisipan, dan penggantian. Hasilnya membuktikan bahwa pencarian jumlah

operasi string dalam approximate string matching yang diperlukan untuk

mentransformasikan suatu string menjadi string lain memerlukan algoritma yang

mangkus seperti algoritma Levenshtein Algoritma ini merupakan program

dinamis dengan kompleksitas O( ).

4. DASAR TEORI

4.1 Optical Character Recognition

Optical Character Recognition (OCR) adalah proses mengubah dari

tulisan tangan atau dokumen ketikan ke dalam teks yang editable pada

komputer (Cheriet, Kharma, Liu, dan Suen, 2007). Citra gambar tersebut

didapatkan dari hasil scanner atau kamera (Basil dan Alwani, 2012a).

OCR mempunyai enam tahapan (Basil dan Alwani, 2012b), yaitu:

1. Akuisisi gambar, dimana dokumen pada kertas discan menggunakan

scanner atau difoto menggunakan kamera digital. Gambar yang dihasilkan

disimpan di komputer dalam mode gambar grayscale atau hitam putih untuk

memudahkan tahapan selanjutnya dalam mengenali karakter.

2. Pre-processing, yaitu gambar hasil scan atau kamera digital diproses

dan dimodifikasi menggunakan image processing algorithm seperti

mengurangi noise, menormalisasi data, dan kompresi data.

3. Segmentasi yaitu dokumen dibagi menjadi komponen-komponen lebih

kecil, yang disebut objek gambar. Ada dua tipe segmentasi, yaitu segmentasi

eksternal yang membagi dokumen menjadi paragraf, kalimat, dan kata; dan

segmentasi internal yang membagi sebuah dokumen menjadi karakter, huruf,

dan angka, disebut glyphs (blok dasar yang merepresentasikan satu atau lebih

karakter).

4. Ekstraksi gambar yaitu mendekomposisikan beberapa gambar untuk

memfasilitasi pengenalan karakter dan kata. Setiap karakter pada alphabet

mempunyai gambar unik yang dapat membedakan dengan karakter lainnya.

Namun ada karakter yang mirip sehingga membuat sulit. Maka dalam proses

ini setiap karakter akan diekstrak lebar, tinggi, bentuk, panjang, sudut, dan

lekukannya.

5. Post-processing, yaitu tahapan terakhir dari sistem OCR yang

bertujuan untuk mendeteksi dan mengoreksi kesalahan ejaan pada teks

keluaran. Proses mengoreksi ini adalah proses yang sangat penting untuk

menghasilkan kesalahan mendekati nol. Ada dua jenis kesalahan ejaan, yaitu

non-word error yang merupakan kesalahan ejaan yang menghasilkan kata

tersebut tidak valid. Yang kedua yaitu real-word error, kesalahan mengeja

kata yang menghasilkan kata yang valid, namun secara grammatical atau

semantic tidak sesuai konteks.

4.2 Kamus Besar Bahasa Indonesia

Kamus Besar Bahasa Indonesia (KBBI) adalah kamus ekabahasa resmi

Bahasa Indonesia yang disusun oleh tim penyusun Kamus Pusat Bahasa (Pusat

Bahasa, 2008). Kamus ini menjadi acuan tertinggi bahasa Indonesia yang baku

(Kusmayadi, 2006), karena kamus ini merupakan kamus bahasa Indonesia

terlengkap dan yang paling akurat yang pernah diterbitkan oleh penerbit yang

memiliki hak paten dari pemerintah Republik Indonesia (Widada dan Prayogi,

2010). Hingga saat ini sejak KBBI terbit pertama kali pada tahun 1988 sudah

mengalami tiga kali revisi. Edisi pertama (1988) adalah hasil pengembangan

dari Kamus Bahasa Indonesia yang terbit pada tahun 1983. Kamus ini baru

memuat 62.100 lema. Edisi kedua (1991) adalah revisi pertama KBBI dan

memuat 72.000 lema. Edisi ketiga (2005), memuat 78.000 lema. Menurut Dr.

Dendy Sugono, Kepala Pusat Bahasa, kamus ketiga ini masih terasa banyak

sekali kosakata yang belum masuk. Tetapi harap diingat bahwa KBBI adalah

Kamus Umum berisi kosakata umum, sehingga dalam kamus tidak termasuk

berbagai istilah. Untuk penggunaan kamus bidang ilmu tertentu Pusat Bahasa

juga memiliki kamus Istilah. Edisi keempat (2008) memuat lebih dari 90.000

lema. Pada edisi ini KBBI diperkaya kosakata yang berasal dari kamus istilah,

pada edisi ini kamus disusun berdasarkan paradigm. Edisi kelima,

kemungkinan besar akan dirilis pada tahun 2013, dengan perkiraan

penambahan kata sekitar 2.000 kata (Pusat Bahasa, 2008).

4.3 Levenshtein Distance

Algoritma Levenshtein merupakan algoritma yang berguna untuk

memeriksa kemiripan dari dua buah string yang umumnya ditemukan pada

aplikasi pengecekkan suatu ejaan (Adiwidya, 2009). Lavenshtein melibatkan

operasi insertion (penambahan), deletion (penghapusan), dan atau substitution

(penggantian) (Adiwidya, 2009) (Atmajaya, 2012). Dengan algoritma ini, tidak

perlu dilakukan seluruh percobaan kemungkinan penghapusan, penyisipan,

atau penggantian terhadap string. Oleh karena itu, algoritma ini dapat

digolongkan sebagai program dinamis. Nilai edit distance dapat diperoleh

hanya dengan menyediakan matriks cost yang ukurannya tergantung panjang

kedua string (Adikara, 2011).

Algoritma Levenshtein, atau sering disebut dengan Levenshtein Distance

atau Edit Distance merupakan algoritma pencarian jumlah perbedaan string

yang ditemukan oleh Vladimir Levenshtein, seorang ilmuwan Rusia, pada

tahun 1965. Algoritma ini digunakan secara luas dalam berbagai bidang,

misalnya mesin pencari, pengecek ejaan (spell checking), pengenal

pembicaraan (speech recognition), pengucapan dialek, analisis DNA,

pendeteksi pemalsuan, dan lain-lain (Adiwidya, 2006).

Langkah-langkah Algoritma

Pada dasarnya, algoritma ini menghitung jumlah minimum

pentransformasian suatu string menjadi string lain yang meliputi penggantian,

penghapusan, dan penyisipan. Algoritma ini digunakan untuk mengoptimalkan

pencarian tersebut karena sangat tidak efisien jika dilakukan pencarian setiap

kombinasi operasioperasi string tersebut. Oleh karena itu, algoritma ini

tergolong program dinamis dalam pencarian nilai minimal tersebut.

Dalam algoritma ini, dilakukan penyeleksian panjang kedua string

terlebih dahulu. Jika salah satu atau kedua string merupakan string kosong,

jalannya algoritma ini berhenti dan memberikan hasil edit distance yang

bernilai nol atau panjang string yang tidak kosong. Jika panjang string

keduanya tidak nol, setiap string memiliki sebuah karakter terakhir, misalnya

c1 dan c2. Misalnya bagian string pertama tanpa c1 adalah s1 dan bagian string

kedua tanpa c2 adalah s2, dapat dikatakan penghitungan yang dilakukan adalah

cara mentransformasikan s1+c1 menjadi s2+c2. Jika c1 sama dengan c2, dapat

diberikan nilai cost 0 dan nilai edit distance-nya adalah nilai edit distance dari

pentransformasian s1 menjadi s2. Jika c1 berbeda dengan c2, dibutuhkan

pengubahan c1 menjadi c2 sehingga nilai cost-nya 1. Akibanya, nilai edit

distance-nya adalah nilai edit distance dari pentransformasian s1 menjadi s2

ditambah 1. Kemungkinan lain adalah dengan menghapus c1 dan mengedit s1

menjadi s2+c2 sehingga nilai edit distance-nya dari pentransformasian s1

menjadi s2+c2 ditambah 1. Begitu pula dengan penghapusan c2 dan mengedit

s1+c1 menjadi s2. Dari kemungkinan-kemungkinan tersebut, dicarilah nilai

minimal sebagai nilai edit distance.

Untuk lebih jelasnya, dapat dilihat pada pseudocode berikut ini. Di

bawah ini digunakan s sebagai string sumber dan t sebagai string target.

Pseudocode ini berupa suatu fungsi yang nilai kembaliannya adalah nilai edit

distance.

n <- length(s)

m <- length(t)

if n = 0 then return m

else if m = 0 then return n

else

for i = 0 to n do

cost[0][i] <- i

for i = 0 to m do

cost[i][0] <- i

for i = 1 to n do

for j = 1 to m do

if (s[i-1]=t[j-1]) then

cost[j][i] <- 0

else cost[j][i] <- 1

a1 <- cost[j][i-1]+1

a2 <- cost[j-1][i]+1

a3 <- cost[j-1][i-1]+cost[j][i]

cost[j][i] <- min(t1,t2,t3)

return cost[m][n]

Berdasarkan pseudocode di atas, dapat ditunjukkan kompleksitas

algoritmanya adalah O(|s|*|t|) atau dapat dianggap O( ) (Adiwidya, 2009).

Misalkan s = malamram dan t = aram. Di bawah ini merupakan sebagian

dari operasi transformasi s ke t dengan berpatokan pada kesamaan string

berurutan “am” pada keduanya.

1. s: m a l a m r a m

t: - a r a m - - -

String s ditransformasikan menjadi t dengan melakukan 4

penghapusan dan 1 penggantian. Jumlah perubahannya adalah 5.

2. s: m a l a m r a m

t: - - - - a r a m

String s ditransformasikan menjadi t dengan 4 penghapusan dan 1

penggantian. Jumlah perubahannya adalah 5.

3. s: m a l a m r a m

t: - a - - - r a m

String s ditransformasikan menjadi t dengan melakukan 4

penghapusan. Jumlah perubahannya adalah 4.

4. s: m a l a m r a m

t: - - - a - r a m

String s ditransformasikan menjadi t dengan melakukan 4

penghapusan. Jumlah perubahannya adalah 4.

5. METODOLOGI

Pada penelitian ini, data set yang digunakan adalah data set KBBI (Kamus

Besar Bahasa Indonesia), bisa didapat dari Pusat Bahasa, Departemen Pendidikan

Nasional. Sedangkan indikator (indicators) yang diobservasi adalah dokumen

teks Bahasa Indonesia hasil OCR.

Metode yang diusulkan (proposed method) terdiri dari tiga tahap yaitu:

1. Deteksi kesalahan OCR

Kata yang dianggap salah adalah kata yang tidak sesuai dengan kaidah

penggunaan pengejaan Bahasa Indonesia, termasuk imbuhan dan akhiran.

Proses ini terdiri dari dua langkah:

a. Pemilihan Lexeme (bentuk kata)

Pada proses pemilihan ini, inputan teks akan dipilah-pilahkan berdasarkan

kriteria tertentu, yaitu:

- Kumpulan angka. Misalnya: “1”, “23, “435”, dan sebagainya.

- Kumpulan huruf. Misalnya: “abc”, “pisang”, “mereka”, dan sebagainya.

- Gabungan angka dan tanda, seperti tanda “.”, “/” , “,”. Misalnya: “45.000”,

“3/4” , 20,7”, dan sebagainya.

- Gabungan huruf dan angka. Misalnya: “sepuluh2” ,” B403”, “sinema21”, dan

sebagainya.

- Tanda baca. Tanda baca tersebut adalah yang berlaku menurut tata Bahasa

Indonesia, yaitu spasi (“ “), tanda titik (“.”), tanda koma (“,”), tanda seru (“!”),

tanda Tanya (“?”), tanda titik dua (“:”), tanda hubung (“-“), tanda petik dua (“””),

dan tanda garis miring (“/”).

INDICATORS PROPOSED METHOD

Error a = nilai error jika menggunakan metode yang

diusulkan

Error b = nilai error jika

menggunakan OmniPage

MEASUREMENT OBJECTIVES

Dokumen

Teks

Bahasa

Indonesia

hasil OCR

x 100%

Tingkat

error

KBBI (Pusat Bahasa,

2008)

Deteksi Kesalahan OCR

Penyaranan kata

Koreksi kesalahan

OCR

Efektivitas x 100%

Pemilihan

lexeme Token

ize

Levenshtein

distance

b. Tokenize (penentuan jenis token)

Token terdiri dari:

- Separator, yang terdiri dari tanda baca. Masing-masing tanda baca dianggap

sebagai token.

- Kata, token ini masih dibedakan lagi ke dalam jenis-jenis kata yang terdapat

format-format lexeme.

Angka (numeralia), yang terdiri dari angka romawi (VII, IX, M, dan

sebagainya) dan angka arab (1, 2, 43, 645, dan sebagainya).

Tanggal

Nama (pronomia)

Identifier, yaitu lexeme-lexeme yang tidak termasuk ke dalam jenis

token lainnya.

Apabila pada proses pemilihan lexeme dan tokenize tetap tidak ditemukan

kata dasar, maka akan dianggap kata yang salah. Langkah berikutnya adalah

penyaranan kata.

2. Penyaranan kata

Pada proses penyaranan kata menggunakan Levenshtence distance. Kata

yang disarankan sebanyak 5, yakni yang mempunyai kemiripan, didapatkan dari

data set KBBI. Hasil dari proses penyaranan kata ini akan digunakan untuk

menentukan proses berikutnya, yaitu koreksi kesalahan OCR.

3. Koreksi kesalahan OCR

Pada proses pengoreksian kesalahan OCR ini yang diambil adalah memilih

1 kata yang mempunyai kemiripan tertinggi kemudian menggantikan kata yang

salah tersebut.

Tujuan (objectives) pada penelitian ini adalah adanya penurunan nilai error

dan peningkatan efektivitas pada pengoreksian kesalahan OCR, dimana

pengukuran akan menggunakan rumus yang ada pada measurement.

Hasil dari penelitian adalah tingkat error dan efektifitas yang dihitung

menggunakan rumus pada measurement.

6. JADWAL

No

Aktivitas Waktu

Maret

2014

April

2014

Mei

2014

Juni

2014

Juli

2014

Agustus

2014

Minggu Minggu Minggu Minggu Minggu Minggu

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

1 Pengajuan

Judul

2 Penyusuna

n Pra

Proposal

3 Bmbingan

/

konsultasi

4 Penyusuna

n Proposal

5 Pengumpu

lan

proposal

Seminar

proposal

6 Penulisan

Bab I

7 Penulisan

Bab II

8 Pengumpu

lan data

9 Penulisan

Bab III

10 Analisa

Sistem

11 Perancang

an Sistem

12 Penulsan

Bab IV

13 Implement

asi

14 Pengujian

Sistem

15 Penulisan

Bab V

16 Seminar

Hasil

17 Revisi

18 Sidang TA

DAFTAR PUSTAKA

Adikara, Putra Pandu, “Rekomendasi Kata Berbahasa Alay ke Bahasa Indonesia

Menggunakan Algoritma Fonetik dan Levenshtein Distance”, Universitas

Brawijaya, 2011.

Adiwidya, Bernardino, “Algoritma Levenshtein Dalam Pendekatan Approximate

String Matching”, Strategi Algoritma Teknik Informatika Institut Teknologi

Bandung, 2009.

Atmajaya, Gede, “Pembuatan Spelling Checker untuk Bahasa Indonesia dengan

Java 2 Stanard Edition”, Teknik Informatika Universitas Gunadarma, 2012.

Bassil, Y., Alwani, M., “Context-sensitive Spelling Correction Using Google Web

1T 5-Gram Information”, Computer and Information Science, Volume 5, No. 3,

Mei 2012.

Bassil, Y., Alwani, M., “OCR Context-Sensitive Error Correction Based on

Google Web 1T 5-Gram Data Set”, American Journal of Scientific Research, ISSN

1450-223X, Issue 50, Februari 2012.

Bassil, Y., Alwani, M., “OCR Post-Processing Error Correction Algorithm Using

Google’s Online Speliing Suggestion”, Journal of Emerging Trends in Computing

and Information Sciences, ISSN 2079-8407, Volume 3, No. 1, Januari 2012.

Budhi, Gregorius, dkk. ,”Aplikasi Pemeriksan Kebenaran Kata (Spelling Checker)

Bahasa Indonesia Pada Teks Artikel Berbahasa Indonesia”, Teknik Informatika UK

Petra Surabaya, 2006.

Cheriet, Kharma, Liu, Suen, “Character Recognition Systems: A Guide for

Students and Practitioners”, Wiley-Interscience Publication, 2007.

Kartini, Ari, “Sikap Bahasa Dan Kemampuan Berbahasa Masyarakat Dwi

Bahasawan”, Universitas Pendidikan Indonesia, 2013.

Katubi, “Bahasa dan Nasionalisme di Indonesia”, Lembaga Ilmu Pengetahuan

Indonesia, ISSN 0125-9989, Jilid XXXIV, Nomer 2, 2008.

Kusmayadi, Ismail, dkk, “Be Smart Bahasa Indonesia”, PT Grafindo Media

Pratama, 2006.

Narender, G dan Rao, Meda Sriniva, “Parallel OCR Error Correction”,

International Journal of Computer Science and Information Technologies, Volume

3, No. 6, 2012.

Pasal 33 ayat 1 UU RI No. 24 tahun 2009 tentang BBLNLK.

Pasal 34 UU RI No. 24 tahun 2009 tentang BBLNLK.

Pasal 36 UUD 1945 tentang Bahasa Negara.

Pusat Bahasa, “Kamus Besar Bahasa Indonesia”, Gramedia Pustaka Utama, 2008.

Rahayu, Minto, “Bahasa Indonesia di Perguruan Tinggi”, Grasindo, 2007.

Singh, Sukhpreet, “Optical Character Recognition Techniques: A Survey”, Journal

of Emerging Trends in Computing and Information Sciences, ISSN 2079-8407,

Volume 4, No. 6, Juni 2013.

Sudarsa, Caca dkk, “Surat menyurat dalam Bahasa Indonesia Seri Penyuluhan 2”,

Pusat Pembinaan dan Pengembangan Bahasa, 1981.

Widada, R dan Prayogi, Icuk, “Kamus Saku Bahasa Indonesia”, Bentang Pustaka,

2010.