Working With String

TUGAS Pengenalan pola dengan string matching (algoritma string matching) Makalah ini dibuat untuk memenuhi tugas mata kuliah Pengolahan Citra Digital yang dibina oleh Ririen Kusumawati, S.Si, M.Kom

By Abdullah Umar

[05550079]

Khusniy Khusniyatul Asma Asma [05550058 [05550058] 58]

JURUSAN TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI (UIN) MALANG Oktober 2008

KATA PENGANTAR Puji syukur, kami panjatkan kehadirat Allah SWT, karena atas rahmat dan hidayahNya, kami dapat menyelesaikan Tugas Pengolahan Citra Digital. Tanpa Ridha dari- Nya, tentunya kami tidak akan mampu menyelesaikan Tugas Kelompok ini. Dalam Tugas Kelompok ini, kami mengambil materi tentang Pengenalan Pola dengan subbab working with string in matlab and string matching yang telah kami dapat dan kami pelajari sebelumnya. Tujuan kami dalam menyajikan materi ini yaitu sebagai bahan pengetahuan mengenai penyajian informasi berdasarkan pengolahan Citra Digital. Perihal dalam makalah ini seluruhnya membahas mengenai informasi Pengenalan Pola berdasarkan working string matching serta ruang lingkup Pengenalan Pola itu sendiri. Pada kesempatan kali ini kami selaku penulis juga tidak

lupa mengucapkan

terimakasih yang sebesar-besarnya kepada semua pihak yang terkait baik jasa maupun materi dalam penyelesaian Tugas Kelompok ini. Akhir kata, tiada gading yang tak retak, demikian pula dengan makalah ini. Oleh karena itu, kami sangat berharap sudi kirannya para pembaca makalah ini, berkenan memberikan masukan, kritik, dan sarannya. Demi membangun terciptanya kesempurnaan makalah

ini.

Kritik

dan

saran,

anda

dapat

layangkan

[email protected] atau [email protected].

1

ke

email

kami

di

BAB I PENDAHULUAN A. LATAR BELAKANG Pengolahan citra adalah salah satu cabang dari ilmu informatika. Pengolahan citra berkutat pada usaha untuk melakukan transformasi suatu citra/gambar menjadi citra lain dengan menggunakan teknik tertentu. Pentingnya informasi yang terkandung dalam pengolahan citra menyebabkan perlakuan terhadap citra (image) tidak boleh menghilangkan atau mengurangi informasi yang terkandung di dalamnya.

B. TUJUAN Tujuan tugas ini adalah untuk membuat sebuah makalah kemudian dianalisis untuk membuat aplikasi pengolahan citra dan dapat menerapkan konsep - konsep pengolahan citra untuk menghasilkan suatu teknologi berbasis pengolahan citra.

C. BATASAN MASALAH Pada tugas akhir ini beberapa permasalahan yang menjadi batasan-batasan adalah sebagai berikut : 1. Pengolahan citra

kali ini hanya membahas mengenai bab tertentu saja yaitu

pengenalan pola dengan subbab working with string in matlab dan string matching. 2. Mengetahui lingkungan kerja pada Matlab.

2

BAB II KAJIAN TEORI A. PENGOLAHAN CITRA DIGITAL Secara bahasa citra adalah gambar dua dimensi yang dihasilkan dari gambar analog dua dimensi yang kontinu menjadi gambar diskrit melalui proses sampling. Gambar analog dibagi menjadi N baris dan M kolom sehingga menjadi gambar diskrit. Persilangan antara baris dan kolom tertentu disebut dengan piksel. Contohnya adalah gambar/titik diskrit pada baris n dan kolom m disebut dengan piksel [n,m]. Sampling adalah proses untuk menentukan warna pada piksel tertentu pada citra dari sebuah gambar yang kontinu. Pada proses sampling biasanya dicari warna rata-rata dari gambar analog yang kemudian dibulatkan. Proses sampling sering juga disebut proses digitisasi. Pengolahan citra adalah metode yang digunakan untuk memproses gambar dalam bentuk

sinyal

digital

lalu

dikenali

oleh

komputer.

jatim.go.id/news.php?id=14093). Pengolahan citra adalah

(http://www.d-infokom-

pemrosesan citra,

khususnya

dengan menggunakan komputer, menjadi citra yang kualitasnya lebih baik. Sebagai contoh, citra burung nuri pada Gambar 1.2 (a) tampak agak gelap, lalu dengan operasi pengolahan citra kontrasnya diperbaiki sehingga menjadi lebih terang dan tajam (b).

Gambar 1. (a) Citra burung nuri yang agak gelap, (b) Citra burung yang telah diperbaiki kontrasny sehingga terlihat jelas dan tajam Di dalam bidang komputer, sebenarnya ada tiga bidang studi yang berkaitan dengan data citra, namun tujuan ketiganya berbeda, yaitu: 1. Grafika Komputer (computer graphics). 2. Pengolahan Citra (image processing). 3. Pengenalan Pola (pattern recognition/image interpretation).

3

Hubungan antara ketiga bidang (grafika komputer, pengolahan citra, pengenalan pola) ditunjukkan pada Gambar 2.

Gambar 2. Tiga bidang study yang berkaitan dengan citra Grafika Komputer bertujuan menghasilkan citra (lebih tepat disebut grafik atau picture) dengan primitif-primitif geometri seperti garis, lingkaran, dan sebagainya. Primitifprimitif geometri tersebut memerlukan data deskriptif untuk melukis elemen-elemen gambar. Contoh data deskriptif adalah koordinat titik, panjang garis, jari -jari lingkaran, tebal garis, warna, dan sebagainya. Grafika komputer memainkan peranan penting dalam visualisasi dan virtual reality. Contoh grafika komputer misalnya menggambar sebuah ‘rumah’ yang dibentuk oleh garis-garis lurus, dengan data masukan berupa koordinat awal dan koordinat ujung garis (Gambar 3).

Gambar 3. (a) Progran grafika computer untuk membuat gambar rumah (b) Pengolahan Citra bertujuan memperbaiki kualitas citra agar mudah diinterpretasi oleh manusia atau mesin (dalam hal ini komputer).

Teknik-teknik pengolahan citra

mentransformasikan citra menjadi citra lain. Jadi, masukannya adalah citra dan keluarannya juga citra, namun citra keluaran mempunyai kualitas lebih baik daripada citra masukan. Termasuk ke dalam bidang ini juga adalah pemampatan citra (image compression).

Pengubahan kontras citra seperti pada Gambar 1. adalah contoh operasi pengolahan citra. Contoh operasi pengolahan citra lainnya adalah penghilangan derau (noise) pada citra 4

Lena (Gambar 3). Citra Lena yang di sebelah kiri mengandung derau berupa bintik-bintik putih (derau). Dengan operasi penapisan (filtering), derau pada citra masukan ini dapat dikurangi sehingga dihasilkan citra Lena yang kualitasnya lebih baik.

Gambar 4. (a) Citra Lena yang mengandung derau, (b) hasil dari operasi penapisan derau.

Pengenalan pola mengelompokkan data numerik dan simbolik (termasuk citra) secara otomatis oleh mesin (dalam

hal ini komputer). Tujuan pengelompokan adalah untuk

mengenali suatu objek di dalam citra. Manusia bisa mengenali objek yang dilihatnya karena otak manusia telah belajar mengklasifikasi objek-objek di alam sehingga mampu membedakan suatu objek dengan objek lainnya. Kemampuan sistem visual manusia inilah yang dicoba ditiru oleh mesin. Komputer menerima masukan berupa citra objek yang akan diidentifikasi, memproses citra tersebut, dan memberikan keluaran berupa deskripsi objek di dalam citra.

Contoh pengenalan pola misalnya citra pada Gambar 5. adalah tulisan tangan yang digunakan sebagai data masukan untuk mengenali karakter ‘ A’. Dengan menggunakan suatu algoritma pengenalan pola, diharapkan komputer dapat mengenali bahwa karakter tersebut adalah ‘A’.

Gambar 5. Citra karakter ‘A’ yang digunakan sebagai masukan untuk pengenalan huruf.

5

B. PENGENALAN POLA Pengenalan pola (pattern recognition) merupakan konsep yang sangat luas aplikasinya dalam banyak bidang antara lain dalam bidang komputer dan informatika yaitu: Speech recognition, speaker identification, character recognition, signature verification, image segmentation dan artificial intelligence Pengenalan pola adalah disiplin ilmu yang mengklasifikasikan object berdasar image, berat atau parameter-parameter yang telah ditentukan kedalam sejumlah kategori atau kelas. Pengenalan pola meliputi berbagai aplikasi dan implementasi dalam kasus kasus real world. Belanche and Nebot (2002) menggambarkan pengenalan pola secara garis besar sebagai serangkaian kegiatan yang mencakup: kegiatan pengukuran dunia nyata dengan alat ukur yang menggambarkan fenomena yang akan diukur diikuti serangkaian kegiatan: preprosesor, ekstrak feature, klasifikasi atau diskrips i pola (lihat Gambar 1). Kegiatan yang fital dalam pengenalan pola adalah kegiata klasifikasi dari ruang feature yang diperoleh dari kegiatan seleksi dan ekstrak feature.

Gambar 6. Skema Kegiatan dalam Pengenalan Pola (Belanche and Nebot, 2002) Contoh aplikasi yang menerapkan pengenalan pola adalah sebagai berikut: •

Machine Vision Pengenalan pola menjadi dasar dari sistem mesin ini. Mesin ini menangkap sebuah atau sekelompok object dengan kamera dan selanjutnya dianalisa untuk di deskripsikan object atau benda tersebut.

•

Character recognition (OCR) Salah satu area pengenalan pola yang secara umum menangani permasalahan otomatisasi dan informasi. Sistem OCR mempunyai front end device yang terdiri dari pembangkit cahaya, lensa scan, document transport dan sebuah detektor.

•

Computer aided diagnosis Sistem ini membantu dokter dalam mengambil keputusan suatu diagnosa

•

Speech recognition Pengenalan pola suara salah satu aplikasi yang berkembang saat ini. Sistem ini mengijinkan kita untuk berkomunikasi antara manusia dengan memasukkan data ke

6

computer. Meningkatakan efisiensi industri manufaktur, mengontrol mesin dengan berbicara pada mesin itu. •

Face recognition Pengenalan wajah adalah sebuah system yang mengenali image wajah manusia yang digunakan dalam otomatisasi dan security sebuah industri

•

Biometrics Biometric beguna untuk mengenali suatu pola mahluk hidup yang dihubungkan dengan parameter – parameter psikologi maupun tingkah laku

•

Image Data Base retrieval Adalah sebuah system untuk pengembalian imagi data base

•

Data mining Adalah pengelompokan pola objek sejumlah data yang terurut dengan harapan dapat memberikan informasi yang berguna dan diinginkan.

•

Bioinformatics Bioinformatik berhubungan erat dengan disiplin kedokteran, pengenalan pola atau image dari suatu image penyakit atau pola dalam sebuah analisa diagnosa penyakit atau pengenalan pola pola yang berhubungan dengan dunia biologi secara umum. Klasifikasi adalah mengelompokkan suatu Objek berdasar pola pola tertentu dalam

suatu kelas atau kelompok yang tepat.

C. STRING MATCHING Permasalahan string matching atau lebih dikenal dengan pencocokan string merupakan permasalahan yang sangat terkenal dalam dunia informatika. Contoh implementasi dari permasalahan pencocokan string adalah pada pencocokan sebuah string pada Microsoft Word atau editor yaitu fasilitas find, atau dalam kasus yang lebih besar lagi, yaitu pencocokan website dengan memasukkan kata-kata kunci sebagaimana yang telah diimplementasikan pada search engine, seperti Yahoo atau Google. Berbagai cara yang telah diterapkan untuk menyelesaikan permasalahan ini, diantaranya algoritma Staightforward Matching, algoritma Finite Automata, algoritma KnuthMorris-Pratt, algoritma Boyer-Moore, algoritma Karp-Rabin, algoritma Shift Or, algoritma Forward Dawg Matching, algoritma Apostolico-Crochemore, algoritma Not So Naive, algoritma Brute Force dan lain sebagainya. Pencocokan string adalah bagian penting dalam memproses teks. Algoritma pencocokan string merupakan komponen utama dalam implementasi software sistem operasi yang paling dasar. Selain itu, algoritma ini menekankan metoda algoritma yang lain dalam pengetahuan komputer. 7

Dalam makalah yang sederhana ini kami akan mencoba membahas masing-masing cara tersebut. Masalah utama dalam pencarian string adalah untuk mencari sebuah string yang terdiri dari beberapa karakter (yang biasa disebut pattern) dalam sejumlah besar text. Pencarian string juga bias digunakan untuk mencari pola bit dalam sejumlah besar file binary. Dalam menganalisis algoritma-algoritma pencarian string kami akan mengasumsikan bahwa panjang string (pattern) adalah S dan panjang text tempat pattern tersebut dicari dimisalkan dengan T. Berbagai jenis algoritma pencocokan string sederhana sebagai berikut: 1. Algoritma Straightforward Matching Algoritma straightforward matching adalah cara brute-force untuk menyelesaikan permasalahan pencarian string. Jalannya algoritma ini adalah sebagai berikut. Awalnya kita membandingkan karakter pertama dari string dangan karakter pertama dari text. Jika sama maka kita bergerak ke karakter selanjutnya sampai kita telah mencocokan keseluruhan string atau menemukan karakter yang tidak sama Jika kita menemukan karakter yang tidak sama maka kita akan bergerak satu langkah kedepan dan akan memulai lagi mencocokan string dari awal. Kasus terburuk adalah kita sukses dalam setiap perbandingan kecuali pada karakter terakhir string. Dalam kasus ini kita melakukan S*(T-S+1) kali perbandingan. Algoritma ini sangat powerfull, namun akan sangat lama dan tidak efektif bila kita harus mencari sebuah string dalam text yang sangat panjang. Bayangkan bila search engine yang ada sekarang menggunakan algoritma ini, betapa lamanya kita harus menunggu karena informasi yang kita inginkan baru akan muncul setelah search engine membandingkan karakter demi karakter yang ada di seluruh dunia.

2. Algoritma Finite Automata Finite Automata digunakan untuk memutuskan apakah sebuah kata atau string adalah kata yang diterima oleh mesin automata tersebut. Sebuah aoutomata memiliki status dan fungsi transisi yang merubah status berdasarkan status saat ini dan karakter yang dibaca saat ini. Ada yang disebut sebagai status akhir dan status ini mungkin lebih dari satu. Bila string itu dijalankan dan berakhir disalah satu status akhir maka string itu diterima atau termasuk dalam behasa tersebut. Kita bisa membuat finite automata untuk menerima string yang kita cari dan jika kita menemukan sebuah kata yang berakhir di status akhir finite automata yang kita buat maka kita bisa mengetahiu bahwa kita telah menemukan string yang kita cari.

8

Karena kita melihat setiap karakter yang ada pada text, maka sedikitnya kita telah melakukan T perbandingan, namun keistimewaan finite automata kita bisa menentukan status mana yang akan dituju setelah sebuah status menerima sebuah karakter. Hal ini yang kemudian menjadi dasar pemikiran untuk Algoritma KnuthMorris-Pratt.

3. Algoritma Knuth-Morris-Pratt Algoritma dikembangkan oleh D. E. Knuth, bersamasama dengan J. H. Morris dan V. R. Pratt. Dalam Algoritma Knuth-Morris-Pratt (KMP), untuk setiap karakter yang dibandingkan kita bias memutuskan apakah berhasil atau gagal. Algoritma KMP membangun sebuah mesin automata yang status-statusnya adalah status dari string yang sedang kita cari. Dan setiap status memiliki fungsi berhasil dan gagal. Berhasil artinya status akan bergerak lebih mendekat ke status akhir dan gagal artinya status bisa jadi semakin jauh atau tetap terhadap status akhir. Kita akan mendapatkan sebuah karakter dari text saat kita berhasil dalam membandingkan dan akan mereuse karakter bila kita gagal. Contohnya :

Perbandingan yang gagal paling banyak adalah sejumlah S-1 kali. Dan yang membuat algoritma ini lebih baik dari brute-force adalah jumlah perbandingan yang lebih sedikit dari algoritma standar brute force. Kompleksitas brute force adalah O(S * T) , sedangkan algoritma KMP memiliki kompleksitas O (S + T). Kompleksitas waktu algoritma KMP, yaitu: • Menghitung fungsi pinggiran : O(m), • Pencarian string : O(n) • Kompleksitas waktu algoritma KMP adalah O(m+n).

9

4. Algoritma Boyer-Moore Rinaldi (2005: 193) mendefinisikan bahwa Algoritma Boyer- Moore merupakan variasi lain dari pencarian string dengan melompat maju sejauh mungkin. Tetapi, algoritma Boyer Moore (BM) berbeda dengan algoritma Knuth-Morris-Pratt (KMP), dimana algoritma Boyer Moore melakukan perbandingan pattern mulai dari kanan sedangkan algoritma Knuth-Morris-Pratt melakukan perbandingan dari kiri. Jika kita mencocokan dari kanan string atau pattern maka ketidakcocokan mungkin membantu kita untuk menggerakkan pattern tersebut dengan jarak yang lebih jauh yang artinya akan lebih signifikan dalam mengurangi proses perbandingan. Jadi kita bias melompati atau tidak melakukan perbandingan-perbandingan karakter yang diprediksikan akan gagal. Contoh : Text : there they are Pattern : they Dengan satu kali perbandingan karakter ‘r’ dan ‘y’ kita bisa melihat bahwa gerakan dari 4 karakter adalah yang terbaik. Kita juga harus mempertimbangkan karakter-karakter yang telah kita cocokan jadi kita tidak bergeser terlalu sedikit. Algoritma Boyer Moore ini menggunakan gerakan geser (slide) dan lompat (jump). Garakan geser memberikan informasi berapa banyak pattern harus digeser untuk mendapatkan karekter yang cocok. Gerakan Lompat memberikan informasi berapa banyak pattern harus digeser untuk mencocokan karakter terakhir yang cocok dengan kemunculan awalnya dengan pattern. Studi telah menunjukan bahwa dengan text bahasa natural dan dengan sebuah pattern yang terdiri dari enam atau lebih karakter, maka jumlah perbandingan sekita 0,4T. Seiring dengan meningkatnya panjang pattern maka algoritma Boyer Moore ini memiliki perbandingan yang lebih rendah, sekitar 0,25T.

5. Algoritma Karp-Rabin Algoritma Karp-Rabin menggunakan fungsi hash yang menyediakan metode sederhana untuk menghindari kompleksitas waktu O(m2) dalam banyak kasus (Karp, 1987: 249-260). Daripada mengecek posisi setiap pola yang terdapat dalam teks, akan lebih efisien apabila dilakukan pegecekan hanya pada pola yang diinginkan. Pengecekan kesamaan antara dua kata menggunakan fungsi hash. Untuk lebih membantu dalam masalah pencocokan string, fungsi hash harus mempunyai properti-properti sebagai berikut : 10

o Kemampuan komputasi yang efisien. o Diskriminasi yang tinggi terhadap string. o Fungsi hash ( y [ j+1 .. j+m ] ) harus mudah dikomputasi dari: · hash ( y[j .. j+m-1] ) · hash ( y[j+m] ) dalam artian hash (y[j+1 .. j+m]) = rehash ( y[j], y [j+m], hash (y[j .. j+m-1]) ) Untuk sebuah kata w dengan panjang m, hash(w) didefinisikan sebagai berikut: hash(w[0 .. m-1]) = (w[0]*2m-1+ w[1]*2m-2+···+ w[m-1]*20) mod q dimana q adalah bilangan besar.

Gambar 7. Ilustrasi Algoritma Karp-Rabin

Algoritma Karp-Rabin mempunyai ciri-ciri sebagai berikut :
Menggunakan fungsi hash
Fase preproses dalam kompleksitas waktu O(m) dan tempat yang konstan.
Fase pencarian dalam kompleksitas waktu O(mn)
O(n+m) memperkirakan waktu aktif 6. Algoritma Shift Or Algoritma Shift Or menggunakan teknik bitwise, misalkan R sebagai array bit yang berisi ukuran m. Sedangkan vektor Rj adalah nilai dari array R, setelah karakter y[j] telah diproses. Vektor Rj berisi tentang semua pencocokan prefix dari x yang berakhir pada posisi j (Baeza-yates. 1992). Untuk lebih jelas lihat gambar 8.

11

Gambar 8. Ilustrasi vektor Rj

Aturan dalam vektor Rj adalah sebagai berikut :

vektor Rj+1 dapat dikomputasi setelah Rj sebagai berikut untuk setiap Rj[i] = 0 maka

jika Rj+1[m-1] = 0 maka pencocokan string sempurna. Transisi dari Rj ke Rj+1 dapat dikomputasi dengan cepat sebagai berikut : untuk setiap c dalam , misal Sc sebagai bit array yang berisi ukuran m atau dengan batasan i adalah for 0

i < m-1 , Sc[i] = 0 iff x[i] = c

Array Sc menunjukkan posisi dari karakter c dalam pola x. Setiap Sc dapat melakukan fase preproses sebelum melakukan fase pencarian. Dan komputasi dari Rj+1 mengurangi dua operasi yaitu shift dan or. Hal ini dapat dinyatakan dalam persamaan sebagai berikut : R j+1= SHIFT ( R j) OR Sy [ j+1 ] Dengan asumsi bahwa panjang pola tidak lebih panjang dari ukuran memori word suatu mesin, ruang dan kompleksitas waktu dari fase preproses adalah O(m+ ) (Baeza-yates. 1992). Sedangkan untuk kompleksitas waktu dari fase pencarian adalah O(n) tidak bergantung pada ukuran alphabet dan ukuran pola. Algoritma Shift Or merupakan algoritma yang efisien untuk pencocokan string yang tepat dan algoritma ini lebih mudah beradaptasi pada pendekatan pencocokan string (Baeza-yates. 1992). Algoritma Shift Or mempunyai cirri-ciri sebagai berikut :
Menggunakan teknik bitwise
Efisien jika panjang pola tidak lebih panjang dari ukuran memori word suatu mesin.
Fase pre-proses dalam kompleksitas waktu O(m + ) dan kompleksitas ruang.

12


Fase pencarian dalam kompleksitas waktu O(n) (tidak bergantung pada ukuran alphabet dan ukuran pola).
Lebih mudah beradaptasi pada pendekatan pencocokan string. Terdapat 4 (Empat) kategori metode pencocokan string menurut urutan perbandingan antara pola karakter dan teks karakter untuk setiap attempt yaitu · From right to left · From left to right · In specific order · In any order Berdasarkan empat kategori di atas, algoritma Karp-Rabin dan algoritma Shift Or termasuk ke dalam kategori From left to right. Algoritma pencocokan string yang kami jabarkan diatas belum mampu untuk menangani kesalahan yang terjadi berikut ini : 1. Kemungkinan ada karakter teks yang hilang. 2. Kemungkinan ada karakter yang hilang dari string (pattern) 3. Kemungkinan ada karakter didalam string atau teks yang mungkin di tambahkan, diganti, atau dihilangkan.

E. NORMALISASI STRING UNTUK OPTIMASI STRING MATCHING Saat ini sudah banyak ditemukan algoritma pencocokan string berdasarkan kemiripan ucapan (phonetic string matching). Masing-masing algoritma tersebut memiliki pendekatan yang hampir mirip. Namun, kebanyakan algoritma tersebut ditulis berdasarkan pengucapan dalam bahasa Inggris. Selain itu, algoritma-algoritma tersebut masih menghadapi masalah ketidakakuratan, seiring dengan begitu bervariasinya string yang akan dicocokan, terutama dalam mengidentifikasi nama (misal nama orang atau nama tempat). Hambatan ini merupakan faktor utama penyebab ketidakakuratan algoritma-algoritma pencocokan string berdasarkan kemiripan pengucapan, seperti Soundex, Metaphone, dan lainnya. Nama adalah suatu string khusus yang bisa sangat bervariasi. Penulisan dan cara pengucapan nama sangat tergantung kepada bahasa yang digunakan. Beberapa nama yang penulisannya berbeda, memiliki cara pengucapan yang sama. Oleh karena itu, perlu adanya suatu langkah normalisasi sebelum dilakukan langkah pencocokan string. Aturan-aturan yang dipaparkan merupakan aturan yang ditemukan secara empirik dan belum dilandasi oleh alasan ilmiah. Namun, pengamatan empirik tersebut kami rasa masih cukup ideal.

13

1. Ketidakteraturan Nama dalam Bahasa Indonesia Nama dalam bahasa Indonesia sangat dipengaruhi oleh bangsa-bangsa yang pernah berinteraksi dengan bangsa Indonesia. Oleh karena itu, banyak ditemukan nama yang menggunakan cara penulisan dan pengucapan asing, seperti Belanda, Arab, Cina, maupun Inggris. Beberapa penulisan nama merujuk kepada satu cara pengucapan. Nama-nama tersebut merupakan variasi cara penulisan dari nama yang sudah ada. Contoh berikut menunjukkan pernyataan tersebut. Tabel 1: Contoh variasi nama dan pengucapannya dalam bahasa Indonesia Nama

Cara Pengucapan

Rahmat Rahmat

Rachmat Rakhmat Efendhi Efendi

Efendi

Efendy Effendhy Effendi Effendy

Tabel1 menunjukkan bahwa perbedaan nama tersebut bukanlah sebuah kesalahan entri data, namun merupakan variasi umum dari sebuah nama. Damerau (1964: 171-176) menunjukkan setidaknya ada empat kejadian yang mengakibatkan variasi pada nama. Tabel 2: Klasifikasi ‘kesalahan’ menurut Damerau Jenis

Nama Dasar

Variasi

Insertion

Fisher

Fischer

Johnston

Johnson

Catherine

Katherine

Hagler

Halger

(penyisipan) Omission (penghilangan) Substitution (penggantian) Transposition (pertukaran)

14

Walaupun contoh yang diberikan berupa nama-nama asing, namun jenis-jenis variasi yang dipaparkan pun terjadi dalam nama Indonesia. 2. Bentuk Normal dalam Bahasa Indonesia Cara pengucapan yang ditunjukkan pada tabel1 merupakan bentuk paling sederhana yang dapat diucapkan dalam bahasa Indonesia. Dapat dikatakan, bentuk tersebut adalah bentuk normal dari nama-nama tersebut. Untuk

meningkatkan

akurasi algoritma

pencocokan

string,

maka

sebelum

‘dilewatkan’ ke algoritma tersebut, harus dilakukan normalisasi terhadap string tersebut. Proses normalisasi secara garis besar terbagi menjadi beberapa tahap, yaitu: a. Normalisasi q-gram b. Eliminasi duplikasi karakter Tahap yang paling penting dalam proses normalisasi adalah normalisasi q-gram. Q-gram adalah susunan beberapa huruf yang berurutan. Normalisasi q-gram dilakukan dengan mengubah susunan huruf tersebut menjadi q-gram lain yang lebih sederhana. Secara empirik, aturan-aturan tersebut ditunjukkan dalam tabel 3. Tabel 3: 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,

BB,DD,

GH,JH,

GG,JJ,

Ardhi

Arddi

SH,TH, ZH

SS,TT, ZZ

V

F

Saviena

Safiena

KS

XX

Wicaksono

Wicaxxono

OE

UU

Wahyoedi

Wahyuudi

IE

II

Arie

Arii

Y

I

Donny

Donni

15

Tahap eliminasi duplikasi karakter dilakukan dengan menghilangkan karakter-karakter berurutan yang sama. Kebanyakan duplikasi karakter ini muncul setelah langkah normalisasi q-gram.

3. Kendala dalam Proses Normalisasi Walaupun aturan yang ada sudah cukup ideal dan memadai, namun masih terdapat beberapa q-gram yang didefinisikan aturannya. Hal ini disebabkan oleh ambiguitas pengucapan q-gram akibat serapan dari berbagai bahasa asing. Selain itu, ambiguitas juga disebabkan oleh perbedaan ejaan Indonesia lama dan baru. Tabel 4: Contoh ambiguitas q-gram Q-gram

Variasi

Bentuk Normal Translasi

Nurcholis

Nurholis

HH

Christian

Kristian

KK

Chandra

Candra

CC

Joni

Joni



Dajat

Dayat

Y

CH

J

Ambiguitas ini menimbulkan masalah, karena string yang diperoleh tidak dapat dinormalisasi. Salah satu pemecahannya adalah dengan menggunakan pendekatan statistik untuk menghitung sebaran translasi mana yang lebih sering muncul. Namun, untuk melakukan hal ini dibutuhkan sampel nama yang cukup besar dan waktu yang relatif lama.

4. Analisis Efektivitas Untuk menguji hasil normalisasi, kami mencoba menganalisis string dengan menggunakan algoritma Soundex standar. Algoritma Soundex yang digunakan adalah algoritma yang murni (untuk bahasa Inggris) yang ditunjukkan dalam tabel 5. Tabel 5: Analisis efektivitas normalisasi String

Soundex (tanpa

Soundex (dengan

normalisasi)

normalisasi)

Rahmat

R530

R530

Rachmat

R253

Rakhmat

R253

Dzikri

D226

Zikri

Z260

16

Z260

Ginanjar

G552

Ginandjar

G553

G552

Terlihat bahwa string yang memiliki kesamaan ucapan mendapat hasil Soundex yang sama setelah dinormalisasi. Walaupun analisis yang dilakukan masih sederhana,

namun sudah dapat

menggambarkan efektivitas normalisasi yang dilakukan. Namun untuk pembuktian secara ilmiah, tentunya membutuhkan penelitian yang lebih lama dan mendalam. Proses normalisasi menghasilkan string yang sederhana, dengan pengucapan yang sama dalam bahasa Indonesia.

Aturan-aturan normalisasi yang dipaparkan didapatkan

berdasarkan pengamatan empirik. Oleh karena itu, aturan yang didapatkan belum dapat dibuktikan secara ilmiah. Selain itu, aturan-aturan (rules) yang ada pun perlu diperbaiki agar dapat mengakomodasi q-gram yang lebih rumit maupun q-gram yang ambigu. Langkah yang dilakukan misalnya dengan menggunakan pendekatan statistik yang lebih rumit. Bagaimanapun juga, proses normalisasi ini merupakan tahap awal untuk menemukan algoritma pencocokan string dalam bahasa Indonesia. Tentunya algoritma seperti ini akan sangat berguna untuk bidang-bidang lain seperti basis data, data mining, atau bahkan natural language processing.

17

KESIMPULAN

A. SIMPULAN Setelah menganalisa dari berbagai model dan jenis algoritma pencarian string (string matching) maka dapat diambil beberapa kesimpulan, yaitu: 1) Permasalahan pencarian string (string macthing) pada dasarnya adalah permasalahan mencari sebuah string (pattern) pada sebuah teks. 2) Algoritma Knuth-Morris-Pratt, Straightforward matching,

Finite Automata dan

Algoritma Boyer-Moore yang dibahas (analisis) hanya dapat menangani permasalahan string yang bersifat exact string matching sedangkan untuk permasalahan string yang bersifat inexact string matching diperlukan algoritma lain yang lebih advance. 3) Algoritma Karp-Rabin dan algoritma Shift Or dapat diklasifikasikan ke dalam kategori From left to right menurut urutan perbandingan antara pola karakter dan teks karakter untuk setiap attempt. 4) Proses normalisasi menghasilkan string yang sederhana, dengan pengucapan yang sama dalam bahasa Indonesia. 5) Proses normalisasi menghasilkan string yang sederhana, dengan pengucapan yang sama dalam bahasa Indonesia dan merupakan tahap awal untuk menemukan algoritma pencocokan string dalam bahasa Indonesia

B. SARAN 1.

Aturan-aturan (rules) yang ada perlu diperbaiki agar dapat mengakomodasi q-gram yang lebih rumit maupun q-gram yang ambigu. Langkah yang dilakukan misalnya dengan menggunakan pendekatan statistik yang lebih rumit.

2.

Perlu

dilakukan

sebuah

kajian

yang

lebih

mendalam

normalisasiyang didapatkan dapat dibuktikan secara ilmiah.

18

agar

aturan-aturan

DAFTAR PUSTAKA Munir Rinaldi. 2005. Diktat Kuliah Strategi Algoritmik. 193.

Karhendana, Arie, dkk. 2006. Normalisasi String untuk Optimasi Phonetic String Matching dalam Bahasa Indonesia. Sekolah Teknik Elektro & Informatika ITB: Bandung

Gunocipto Hartoyo, Eko, dkk. 2006. Analisis Algoritma Pencarian String (String Matching) Departemen Teknik Informatika ITB: Bandung.

D, Arliadinda, dkk.2006. String Matching Using Karp-Rabin and Shift Or Algorithm. Sekolah Tinggi Teknologi Telkom: Bandung.

Baeza-yates, R.A., Gonnet,G.H. 1992. A New Approach To Text Searching, Communications of the ACM . 35(10) :74-82

F. Damerau, 1964. A Technique for Computer Detection and Correction of Spelling Errors, Communications of the ACM 7, 171-176. Belanche L. and Nebot A., 2002, Intelligent Data Analysis and Data Mining, Wright State University.

Christian.Charras,Thierry.Lecroq.1997.Exact String Matching Algorithms Animation In Java, Introduction. Sumber: http://www-igm.univmlv.fr/~lecroq/string/node2 .html

Karp R.M., RABIN M.O. 1987. Efficient Randomized Pattern-Matching Algorithms. IBM J. Res. Dev. 31(2):249-260.

http://id.wikipedia.org/wiki/Pengolahan_Citra

19