ANALISIS PENERAPAN STRING MATCHING DALAM KOMPARASI DATA KEPESERTAAN JAMINAN KESEHATAN MASYARAKAT (JAMKESMAS)
Skripsi Diajukan untuk Memenuhi Persyaratan Memperoleh Gelar Sarjana Komputer (S.Kom)
Oleh: SRI WULAN NIM : 206091004077
PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2011
i
ANALISIS PENERAPAN STRING MATCHING DALAM KOMPARASI DATA KEPESERTAAN JAMINAN KESEHATAN MASYARAKAT (JAMKESMAS)
Skripsi Sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Komputer Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta
Oleh : SRI WULAN NIM. 206091004077
PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2011
ii
iii
iv
PERNYATAAN
DENGAN INI SAYA MENYATAKAN BAHWA SKRIPSI INI BENARBENAR HASIL KARYA SENDIRI YANG BELUM PERNAH DIAJUKAN SEBAGAI SKRIPSI ATAU KARYA ILMIAH PADA PERGURUAN TINGGI ATAU LEMBAGA MANAPUN.
Jakarta, Maret 2011
Sri Wulan L (206091004077)
v
LEMBAR PERSEMBAHAN
Tugas akhir (Skripsi) ini sengaja penulis persembahkan teruntuk : 1. Otak, pikiran, jiwa dan organ-organ yang ada dalam tubuh dan diri ini. Selamat atas kerja kerasnya. Ingatlah bahwa tak akan berhenti kita hingga kita melangkah ke jannah-Nya karna hidup ini bukan untuk hidup, hidup juga bukan untuk mati, tapi hidup untuk yang Maha Hidup. 2. Kedua orang tua (Bapak dan Mama). Terima kasih atas kasih sayang, perhatian, kecemasan serta berbagai hal yang tak terhitung hingga yang tak pantas untuk dihitung. Hanya jannah-Nya lah balasan yang layak untuk keduanya. Amieen.
vi
KATA PENGANTAR Alhamdulillahirabbil’alamin. Segala puji bagi Allah SWT atas segala rahmat dan karunia-Nya dalam memberikan jalan dan kemudahan kepada penulis hingga tugas akhir ini dapat terselesaikan dengan baik. Shalawat dan salam memang pantas tercurah kepada Nabi Muhammad SAW, keluarga, serta para sahabatsahabatnya yang menjadi panutan dan inspirasi bagi penulis.
Dalam hal ini, penulis mencoba untuk melakukan suatu penelitian dengan topik judul ”Analisis Penerapan String Matching dalam Komparasi Data Kepesertaan Jaminan Kesehatan (JAMKESMAS)”. Topik ini merupakan tugas akhir yang diambil penulis guna memenuhi syarat untuk memperoleh gelar Sarjana Komputer (S.Kom) Teknik Informatika Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta.
Adapun dalam penyelesaian tugas akhir ini, penulis ingin menyampaikan terima kasih sebesar-besarnya kepada pihak-pihak yang telah membantu dalam penyelesaian pembuatan aplikasi dan penyusunan tugas akhir, antara lain kepada yang terhormat : 1. Bapak DR. Syopiansyah Jaya Putra, M.Sis selaku Dekan Fakultas Sains dan Teknologi yang telah memberikan suatu komitmen, dorongan, dan program pendidikan sesuai kebutuhan mahasiswanya. 2. Bapak Yusuf Durachman, M.sc selaku Ketua Jurusan yang telah memberikan peran sesuai dengan fungsinya dalam membimbing serta memberikan ruang ilmu bagi penulis.
vii
3. Ibu Fitri Mintarsih, M.Kom selaku Dosen Pembimbing 1 dan Ibu Khodijah Hulliyah, M.Si selaku Dosen Pembimbing 2 yang telah memberikan bimbingan dan dukungan baik secara moril maupun teknis. 4. Bapak Swasetyo Yulianto selaku Dosen Pembimbing Lapangan yang telah memberikan bimbingan, masukan, serta berbagi ilmu pengetahuan dalam penyusunan sehingga penulis dapat menyelesaikan tugas akhir ini. 5. Seluruh anggota keluarga tercinta yang senantiasa mendoakan dan memberikan dukungan selama menjalankan masa perkuliahan. 6. Rekan-rekan seperjuangan, teman–teman Software Enginering dan seluruh kawan-kawan jurusan Teknik Informatika yang memberikan motivasi serta informasi kepada penulis. Mari kita sukses bersama. 7. Seluruh pihak yang telah membantu dan namanya tidak dapat disebutkan satu persatu. Terima kasih atas doa dan bimbingannya, Semoga Allah SWT membalas segala kebaikan yang telah diberikan kepada penulis.
Akhir kata, penulis memohon maaf atas berbagai hal keliru yang diperbuat selama masa penyelesaian tugas akhir ini, kritik dan saran yang membangun sangat diharapkan demi menambah pengetahuan dalam kepenulisan dan semoga tugas akhir ini dapat bermanfaat bagi pengembangan selanjutnya. Amiin
Jakarta, Maret 2011
Sri Wulan
viii
ABSTRAK
SRI WULAN. Analisis Penerapan String Matching dalam Komparasi Data Kepesertaan JAMKESMAS Dibimbing oleh : FITRI MINTARSIH, M.Kom dan KHODIJAH HULLIYAH, M.Si
Dalam pencocokan string (string matching), penggunaan algoritma yang tepat dapat memberikan hasil penelusuran yang tepat pula dan sesuai keinginan pengguna. Dalam tugas akhir ini, penulis akan menganalisa penerapan algoritma string matching yang terdiri atas inexact string matching (fuzzy string macthing) menggunakan approximate string matching (dilihat dari segi penulisan) dan exact string matching menggunakan brute force string matching pada data nama orang (peserta) jamkesmas. Data yang digunakan dalam pencocokan string dalam menerapkan algoritma string matching merupakan data yang akan dikomparasikan untuk mendapatkan kecocokan data yang berasal dari dua database. Hasil analisa fuzzy string matching dalam komparasi data kepesertaan ini akan diaplikasikan menggunakan PHP dan MySQL, dengan menggunakan fase pengembangan sistem RAD (Rapid Application Deveplopment). Hasil penerapan string matching dalam tugas akhir ini menunjukkan bahwa penerapan fuzzy string matching mampu menangani bentuk nama orang (peserta) yang bervariasi bentuk penulisannya dan exact string matching tidak mampu mencocokan data nama yang variatif bentuk kepenulisannya. Pengujian fuzzy string matching dalam komparasi data kepesertaan ini menghasilkan persentasi kecocokan data peserta yang sama besar dengan exact string matching.
Kata kunci : String Matching, Fuzzy String Matching (Approximate), Exact String Matching (Brute Force), komparasi data, dan RAD.
ix
DAFTAR ISI
Halaman HALAMAN LUAR .......................................................................................... i HALAMAN DALAM ...................................................................................... ii LEMBAR PENGESAHAN PEMBIMBING ................................................. iii LEMBAR PENGESAHAN UJIAN ................................................................ iv LEMBAR PERNYATAAN ............................................................................. v LEMBAR PERSEMBAHAN .......................................................................... vi KATA PENGANTAR ...................................................................................... vii ABSTRAK ....................................................................................................... viii DAFTAR ISI .................................................................................................... ix DAFTAR GAMBAR ......................................................................................... xiii DAFTAR TABEL ............................................................................................ xv DAFTAR ISTILAH ......................................................................................... xvi BAB I PENDAHULUAN 1.1 Latar Belakang Masalah ................................................................................. 1 1.2 Rumusan Masalah .......................................................................................... 4 1.3 Batasan Masalah ............................................................................................. 4 1.4 Metode Penelitian ........................................................................................... 5 1.5 Tujuan dan Manfaat Penelitian ...................................................................... 6 1.6 Sistematika Penulisan .................................................................................... 7
x
BAB II LANDASAN TEORI 2.1 Konsep Algoritma ........................................................................................ 9 2.1.1 Definisi Algoritma ............................................................................. 9 2.1.2 Ciri-ciri dan Sifat Algoritma .............................................................. 10 2.2 Logika Fuzzy ................................................................................................ 14 2.3 String Matching ............................................................................................ 15 2.3.1 Definisi String Matching .................................................................... 15 2.2.2 Kerangka Kerja String Matching ....................................................... 16 2.3.3 Kerangka Pikir String Matching ........................................................ 16 2.3.3 Macam Algoritma String Matching ................................................... 18 2.4 Exact String Matching .................................................................................. 18 2.5 Inexact String Matching (Fuzzy String Matching) ...................................... 25 2.6 Karakteristik Nama ...................................................................................... 28 2.7 Normalisasi Nama ........................................................................................ 29 2.8 Sistem Basis Data ......................................................................................... 32 2.9 SQL .............................................................................................................. 33 2.10 MySQL ....................................................................................................... 34 2.11 Fungsi String MySQL ................................................................................ 35 2.12 Aplikasi ...................................................................................................... 35 2.13 Metode Pengembangan Sistem .................................................................. 34 2.13.1. Definisi Pengembangan Sistem ...................................................... 34 2.13.2. Macam-macam Metode Pengembangan Sistem ............................. 34 2.14 Unit Testing ................................................................................................ 39
xi
2.15 Studi Sejenis ............................................................................................... 40
BAB III METODE PENELITIAN 3.1 Metode Pengumpulan Data .......................................................................... 44 3.2 Metode Komparatif ...................................................................................... 45 3.3 Metode Pengembangan Sistem .................................................................... 46 3.4 Alasan Penggunaan RAD ............................................................................. 48 3.5 Keunggulan dan Kelemahan RAD ............................................................... 49 BAB IV PENGEMBANGAN SISTEM 4.1 Metode Komparatif ...................................................................................... 50 4.1.1 Analisis String Matching ................................................................... 50 4.1.1.1 Exact String Matching .......................................................... 51 4.1.1.2 Normalisasi String ................................................................ 55 4.1.1.3 Inexact String Matching ........................................................ 63 4.2 Fase Perencanaan Syarat-syarat ................................................................... 68 4.2.1 Tujuan Informasi ................................................................................ 53 4.2.2 Syarat Kebutuhan/Informasi .............................................................. 53 4.3 Perancangan Sistem ..................................................................................... 67 4.3.1 Perancangan Proses ............................................................................ 67 4.3.1.1 Algoritma Exact String Matching ......................................... 67 4.3.1.2 Proses Kecocokan ................................................................. 68 4.3.1.2 Algoritma Inexact String Matching ...................................... 69 4.3.1.2 Proses Normalisasi (Fuzzy String Matching) ....................... 70
xii
4.3.2 Perancangan Database ....................................................................... 71 4.3.3 Rancangan Interface Sistem ............................................................... 86 4.4 Fase Konstruksi ............................................................................................ 87 4.5 Implementasi ................................................................................................ 90 4.4.1 Pengenalan Sistem ............................................................................. 90 4.4.1 Pengujian Sistem ................................................................................ 91 BAB IV PENUTUP 5.1 Kesimpulan ……………………………………………………………….. 104 5.2 Saran …..………………………………………………………………….. 106 DAFTAR PUSTAKA ………………………………………………………. 107 LAMPIRAN
xiii
DAFTAR GAMBAR Halaman Gambar 2.1 Model Sekuensial Linier ............................................................... 39 Gambar 4.1 Proses Similarity Function ............................................................. 59 Gambar 4.2 Flowchart Exact String Matching ................................................. 66 Gambar 4.3 Flowchart Kecocokan .................................................................... 67 Gambar 4.4 Flowchart Fuzzy String Matching ................................................. 68 Gambar 4.5 Flowchart Normalisasi String Nama ............................................. 69 Gambar 4.6 Rancangan Tampilan Exact String Matching ................................ 85 Gambar 4.7 Rancangan Tampilan Inexact String Matching ............................. 86 Gambar 4.8 Form Masukan Exact .................................................................... 88 Gambar 4.9 Form Masukan Inexact .................................................................. 89 Gambar 4.10 Tampilan Output Kecocokan ...................................................... 89 Gambar 4.11 Uji 1 ............................................................................................. 90 Gambar 4.12 Hasil Uji 1 ................................................................................... 91 Gambar 4.13 Uji 2 ............................................................................................. 91 Gambar 4.14 Hasil Uji 2 ................................................................................... 92 Gambar 4.15 Uji 3 ............................................................................................. 92 Gambar 4.16 Hasil Uji 3 ................................................................................... 93 Gambar 4.17 Uji 4 ............................................................................................. 93 Gambar 4.18 Hasil Uji 4 ................................................................................... 94 Gambar 4.19 Uji 5 ............................................................................................. 94 Gambar 4.20 Hasil Uji 5 ................................................................................... 95
xiv
Gambar 4.21 Uji 6 ............................................................................................. 95 Gambar 4.22 Hasil Uji 6 ................................................................................... 96 Gambar 4.23 Uji 7 ............................................................................................. 96 Gambar 4.24 Hasil Uji 7 ................................................................................... 97 Gambar 4.25 Uji 8 ............................................................................................. 97 Gambar 4.26 Hasil Uji 8 ................................................................................... 98 Gambar 4.27 Uji 9 ............................................................................................. 98 Gambar 4.28 Hasil Uji 9 .................................................................................... 99 Gambar 4.29 Uji 10 ........................................................................................... 99 Gambar 4.30 Hasil Uji 10 ................................................................................. 100 Gambar 4.31 Uji 11 ........................................................................................... 100 Gambar 4.32 Hasil Uji 11 ................................................................................. 101 Gambar 4.33 Uji 12 ........................................................................................... 101 Gambar 4.34 Hasil Uji 12 ................................................................................. 102
xv
DAFTAR TABEL
Halaman Table 2.1 Simbol-simbol Flowchart ................................................................... 14 Table 2.2 Damerau Variasi Nama ...................................................................... 30 Table 4.2 Contoh Variasi Penamaan .................................................................. 53 Table 4.3 Translasi Q-gram ................................................................................ 59 Table 4.4 Struktur File BPS ............................................................................... 71 Table 4.5 Struktur File Translasi Db1 ................................................................ 73 Table 4.6 Struktur File Normalisasi Db1 ........................................................... 75 Table 4.7 Struktur File Peserta Askes ................................................................ 76 Table 4.8 Struktur File Translasi Db2 ................................................................ 80 Table 4.9 Struktur File Normalisasi Db2 ........................................................... 85 Table 4.10 Kecocokan Field Kedua Database ................................................... 85 Table 4.11 Hasil Uji String Matching ................................................................ 104
xvi
DAFTAR ISTILAH
Istilah
Arti
String
Suatu kumpulan karakter
Pattern
Sekumpulan string yang dicari pada teks.
Database
Suatu kumpulan data atau informasi yang kompleks dimana
data
tersebut
disusun
menjadi
beberapa
kelompok dengan tipe data yang sejenis, dimana setiap datanya saling berhubungan satu sama lain atau dapat berdiri sendiri, sehingga mudah diakses. Boolean
Segala hal dapat diekspresikan dalam istilah binary (0 atau 1, hitam atau putih, ya atau tidak),
Fuzzy Logic
Pendekatan yang membantu dalam menjelaskan ketidakpastian batas antara satu kriteria dengan kriteria lainnya, yang disebabkan oleh adanya penilaian manusia terhadap sesuatu secara kumulatif.
xvii
BAB I PENDAHULUAN
1.1.
Latar Belakang Masalah Dewasa ini kemajuan yang sangat pesat di bidang teknologi, terutama teknologi informasi komputer, mendorong munculnya inovasi baru dalam penyajian informasi untuk memenuhi kebutuhan informasi. Penyajian data atau informasi baik berupa subjek maupun objek dalam suatu perusahaan atau lembaga memerlukan adanya suatu database. Database adalah suatu kumpulan
data atau informasi yang kompleks dimana, data tersebut disusun menjadi beberapa kelompok dengan tipe data yang sejenis, dimana setiap datanya saling berhubungan satu sama lain atau dapat berdiri sendiri, sehingga mudah diakses. Penggunan database kini banyak dimanfaatkan oleh berbagai lembaga untuk berbagai kepentingan. Salah satunya yakni penggunaan dalam menangani database penduduk dalam penjaminan kesehatan bagi masyarakat miskin yang diselenggarakan sekretariat pengelola JAMKESMAS Kementrian Kesehatan. Adapun data yang dimiliki oleh pengelola JAMKESMAS kementrian kesehatan ini berasal dari database dua instansi hasil SK Bupati/Walikota berjumlah sekitar 72 juta record warga miskin dan data dari lembaga sensus penduduk (BPS) sekitar 68 juta record warga miskin. Data penduduk miskin dari ke dua instansi ini berasal dari pengambilan data penduduk pada wilayah yang sama namun memiliki masing-masing jumlah 1
2
data yang berbeda. Perbedaan ini tentunya didasarkan karena perbedaan metode, teknik, serta perbedaan waktu pengambilan data maupun berbagai masalah teknis dilapangan yang dihadapi oleh masing-masing instansi. Perbedaan jumlah data dari dua instansi ini merupakan permasalahan bagi pengelola jamkesmas dalam menggunakan database penduduk miskin untuk penjaminan kesehatan secara menyeluruh dikarenakan akan berdampak pada keakurasian data penduduk miskin dilapangan serta mengakibatkan adanya sejumlah warga miskin yang tidak terdata maupun terdata lebih dari satu. Maka dari itu diperlukan suatu metode pencocokan untuk mencari kecocokan data diantara kedua database tersebut, yang mana tiap penduduknya memiliki data identitas yang bervariatif, sehingga tujuan dari penjaminan kesehatan dapat memadai atau terpenuhi. Metode pencocokan string (string matching) yang merupakan bagian dalam proses pencarian string memegang peranan penting untuk mendapatkan dokumen yang sesuai dengan kebutuhan informasi. Pencocokan string (string matching) secara garis besar dapat dibedakan menjadi dua yaitu pencocokan string secara eksak/sama persis (exact string matching) dan pencocokan string berdasarkan kemiripan (inexact string matching/fuzzy string matching). Fuzzy string matching (inexact string matching) merupakan pencocokan string yang melakukan pencarian terhadap string yang sama dan juga string yang mendekati dengan string lain yang terkumpul dalam sebuah penampung atau kamus. Pencocokan string berdasarkan kemiripan masih dapat dibedakan menjadi dua yaitu berdasarkan kemiripan penulisan (approximate string
3
matching) dan berdasarkan kemiripan ucapan (phonetic string matching). Dalam permasalahan ini penulis menggunakan fuzzy string matching proses pendekatan secara kemiripan penulisan (approximate) serta brute force yang mewakili algoritma exact string matching. Adapun dalam pencocokan ini, penulis lebih berpusat terhadap analisa string nama peserta, dikarenakan nama orang (peserta) merupakan string yang memiliki aneka ragam bentuk penulisan dalam satu pengucapan nama orang dalam pemasukan data peserta. Misalnya dalam permasalahan ini suatu string nama orang memiliki suatu bentuk pola huruf penulisan yang variatif tapi memiliki cara pengucapan yang sama dalam satu nama orang, sehingga diperlukan suatu aturan serta analisa yang tepat untuk menganalisa permasalahan mengenai pencocokan data string nama orang. Berdasarkan uraian permasalahan tersebut, maka penulis mengambil suatu judul “Analisis Penerapan String Matching dalam Komparasi Data Kepesertaan Jaminan Kesehatan Masyarakat (JAMKESMAS) ” pada tugas akhir (skripsi) ini.
1.2.
Rumusan Masalah Berpijak dari uraian yang telah dikemukakan pada latar belakang masalah, dapat dirumuskan masalah yang akan diteliti dalam hal ini adalah : a. Bagaimana menyelesaikan permasalahan dalam mencocokan perbedaan database yang ada pada dua instansi.
4
b. Bagaimana penerapan inexact string matching dan exact string matching dalam pencocokan data nama orang (peserta). c. Bagaimana jumlah kesesuaian (kecocokan) data antar kedua database dalam penerapan string matching.
1.3.
Batasan Masalah Adapun yang diteliti dalam hal tugas akhir ini mencakup : 1. Analisis dan penerapan algoritma string matching (Brute Force dan Approximate) dalam penyelesaian pencocokan database dalam komparasi data kepesertaan. 2. Menggunakan sample data BPS dan ASKES yang diambil pada wilayah Bangka Belitung . 3. Mengaplikasikan algoritma string matching menggunakan PHP sebagai bahasa pemrograman dan MySQL sebagai database server.
1.4.
Metode Penelitian Untuk mendapat data dan fakta yang sebenarnya dalam menguraikan masalah pada penelitian ini, maka penulis merumuskan cara yang tepat dalam memecah permasalahan yang ada dengan : 1. Metode Pengumpulan data Untuk mendapatkan informasi serta kebutuhan guna menyelesaikan penerapan algoritma string matching dalam komparasi data kepesertaan ini, penulis melakukan salah satu metode pengumpulan data yaitu metode
5
dokumentasi. Metode dokumentasi adalah tehnik pengumpulan data yang dilakukan dengan membaca dan mempelajari buku, dokumen, jurnal serta literatur yang berkaitan dengan objek penelitian (Arikunto, 2006 : 231). Pengumpulan data ini penulis lakukan dengan cara mengunjungi perpustakaan maupun melalui artikel-artikel web online. 2. Metode Pengembangan Sistem Metodologi yang digunakan pada pengembangan sistem penerapan algoritma string matching dalam komparasi data penamaan ini adalah metodologi pengembangan sistem RAD (Rapid Aplication Development) Kendall & Kendall, yang meliputi: a. Fase perencanaan syarat-syarat : melakukan identifikasi terhadap kebutuhan
informasi
untuk
memecahkan
permasalahan
dan
menganalisa metode yang tepat guna memberikan solusi untuk mencapai tujuan dan syarat-syarat informasi. b. Fase design : merancang proses-proses yang terjadi pada sistem program, database, maupun antarmuka (interface) aplikasi yang hendak dibangun. c. Fase konstruksi : membangun aplikasi yang dibuat dengan cara pengkodean program. d. Fase implementasi : fase dimana aplikasi sistem yang dibangun pada fase sebelumnya diimplementasikan. Dalam fase ini juga diuji kehandalan penerapan metode string matching yang digunakan dalam sistem komparasi data kepesertaan.
6
1.5.
Tujuan dan Manfaat Penelitian Tujuan dari penelitian ini yakni : a. Mendapatkan kecocokan data peserta antar kedua database. b. Menganalisis pencocokan string (string matching) nama orang dalam komparasi data kepesertaan. c. Agar dapat diaplikasikan dalam berbagai permasalahan pencocokan komparasi data nama orang (peserta). Penelitian ini diharapkan dapat bermanfaat : a. Bagi Pengguna : Menyelesaikan permasalahan perbedaan data rujukan kepesertaan jamkesmas yang akurat dengan lebih cepat, efisien, dan murah. b. Bagi Penulis : Memberikan pengetahuan tentang penerapan algoritma string matching dalam analisis bentuk penulisan nama orang (peserta) dan komparasi data peserta. c. Bagi
Universitas
:
Sebagai
wahana
dalam
mengembangkan
kemampuan mahasiswa/i dalam penyusunan tugas akhir.
1.6.
Sistematika Penulisan Secara garis besar, tugas akhir ini terbagi menjadi 5 bab, yaitu : BAB I :
PENDAHULUAN Dalam bab ini penulis mencoba menerangkan tentang hal umum terhadap permasalahan dasar yang hendak diteliti yaitu mencakupi latar belakang masalah, perumusan
7
masalah, batasan masalah, tujuan, manfaat serta metodologi penelitian dan sistematika penulisan dalam tugas akhir ini. BAB II :
LANDASAN TEORI Dalam bab ini penulis akan menjelaskan secara detail teoriteori relevan yang digunakan dan mendasari dalam analisa penelitian ini. Bab ini terdiri atas teori pendukung, pengertian serta penjabaran yang dapat dijadikan sebagai suatu landasan teori analisa dari penelitian terhadap penerapan
string
matching
dalam
komparasi
data
kepesertaan. BAB III :
METODOLOGI PENELITIAN Dalam bab ini penulis mencoba memaparkan mengenai metodologi yang digunakan selama menganalisa tentang penerapan fuzzy string matching dan exact string matching, pengembangan sistem yang digunakan, langkah (fase) kerja pengembangan sistem .
BAB IV :
PENGEMBANGAN SISTEM Dalam bab ini penulis akan membahas mengenai hasil dari analisa metode algoritma string matching yang diterapkan dan metodologi penelitian terhadap penerapan algoritma string matching dalam komparasi data kepesertaan.
8
BAB V :
PENUTUP Dalam bab ini penulis memberikan kesimpulan yang memaparkan mengenai hal-hal yang didapatkan dari hasil pengujian sistem dalam penerapan algoritma string matching komparasi data kepesertaan, yang kemudian berisi saran-saran perbaikan yang berhubungan dengan masalah yang dibahas untuk pengembangan selajutnya.
BAB II LANDASAN TEORI
Dalam proses menyelesaikan penelitian ini penulis mendapatkan berbagai teori, konsep, serta berbagai uraian-uraian yang relevan terhadap objek penelitian dari berbagai referensi sehingga dapat dijadikan acuan pendukung penulis dalam pelaksanaan penelitian ini. Dalam bagian ini penulis mencoba menjelaskan
teori-teori
yang
mendukung
menerapkan
algoritma
string
matching
dalam dalam
menganalisa penyelesaian
serta kasus
permasalahan komparasi data kepesertaan.
2.1.
Konsep Algoritma
2.1.1. Definisi Algoritma Menurut, Munir (2001:4) Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis, sedangkan menurut Kamus Besar Bahasa Indonesia (1976:30) algoritma adalah urutan logis pengambilan putusan untuk pemecahan masalah.
Adapun definisi algoritma meliputi (Suarga, 2004 : 1) : 1. Teknik penyusunan langkah-langkah penyelesaian masalah dalam bentuk kalimat dengan jumlah kata terbatas, tetapi tersusun secara logis dan sistematis. 2. Suatu prosedur yang jelas untuk menyelesaikan suatu persoalan dengan menggunakan langkah-langkah tertentu dan terbatas jumlahnya 9
10
Kata algoritma sendiri diadaptasi dari nama ilmuwan muslim Abu Ja’far Muhammad
ibn
Musa
Al-Khawarizmi
(780-847
M)
yang
banyak
menghasilkan karya dalam bidang matematika, disamping karya-karyanya dalam bidang lainnya seperti geografi dan musik (Wahid, 2004 : 1).
2.1.2. Ciri – ciri dan Sifat Algoritma Donald E. Knuth (1973), menyatakan bahwa ada beberapa ciri-ciri algoritma, yaitu : a. Algoritma mempunyai awal dan akhir. Suatu algoritma harus berhenti setelah mengerjakan serangkaian tugas atau dengan kata lain suatu algoritma harus memiliki langkah yang terbatas. b. Setiap langkah harus didefinisikan dengan tepat sehingga tidak memiliki arti ganda. c. Memiliki masukan atau kondisi awal. d. Memiliki keluaran atau kondisi akhir. e. Algoritma harus efektif; bila dikuti dengan benar-benar akan menyelesaikan persoalan.
Berdasarkan ciri algoritma dapat disimpulkan sifat utama suatu algoritma, yaitu (Suarga, 2004 : 2):
11
a. Input : suatu algoritma memiliki input atau kondisi awal sebelum algoritma dilaksanakan dan bisa berupa nilai-nilai pengubah yang diambil dari himpunan khusus. b. Output : suatu algoritma akan menghasilkan output setelah dilaksanakan, atau algoritma akan mengubah kondisi awal menjadi kondisi akhir, dimana nilai output diperoleh dari nilai input yang telah diproses melalui algoritma. c. Definiteness : langkah-langkah yang dituliskan dalam algoritma terdefinisi dengan jelas sehingga mudah dilaksanakan oleh pengguna algoritma. d. Finiteness : suatu algoritma harus memberi kondisi akhir atau output setelah melakukan sejumlah langkah yang terbatas jumlahnya untuk setiap kondisi awal atau input yang diberikan. e. Effectiveness : setiap langkah dalam algoritma bisa dilaksanakan dalam suatu selang waktu tertentu sehingga pada akhirnya member solusi sesuai yang diharapkan. f. Generality : langkah-langkah algoritma berlaku untuk setiap himpunan input yang sesuai dengan persoalan yang akan diberikan, tidak hanya untuk himpunan tertentu.
Algoritma sebagai langkah-langkah pemecahan masalah dapat dituliskan dengan berbagai cara , yaitu (Wahid, 2004 : 9) : 1. Uraian deskriptif
12
Penulisan algoritma dengan uraian deskriptif menggunakan bahasa yang biasa digunakan sehari-hari. 2. Algoritma pseudecode adalah algoritma yang dituliskan dalam kodekode yang disepakati dan mempunyai urutan-urutan tertentu. Kodekode ini dapat dikembangkan sendiri asalkan arti dari setiap kode disepakati bersama. 3. Bagan alir (flowchart) Flowchart (bagan alir dokumen) adalah penggambaran secara grafik dari langkah-langkah dan urutan-urutan prosedur dari suatu program ( Jogiyanto Hartono : 1989).
Berikut ini adalah simbol-simbol yang digunakan dalam bagan alir dokumen menurut Marshall B. Romney ( 2004 ; 198 ) : Tabel 2.1 Simbol-simbol Flowchart Simbol
Keterangan Dokumen atau laporan : dokumen tersebut dapat dipersiapkan dengan tulisan tangan, atau di cetak
Dokumen
dengan komputer. Fungsi input atau output apa pun di dalam bagan alir program. Juga dipergunakan untuk mewakili
Input/output
jurnal dan buku besar dalam bagan alir dokumen. Menghubungkan
arus
pemrosesan
di
satu
halaman yang sama, penggunaan konektor ini
13
On-page
akan menghindari garis-garis yang saling silang
connector
di satu halaman. Suatu penanda masuk dari, atau keluar ke, halaman lain.
Off-page connector Pelaksanaan pemrosesan yang dilaksanakan secara manual. Proses manual Komentar deskriptif tambahan atau catatan penjelasan untuk klarifikasi. Anotasi File dokumen secara manual disimpan dan
File
ditarik
kembali; huruf yang ditulis di dalam
simbol
menunjukkan urutan pengaturan file
secara N = numeris, A = alfabetis, D = berdasar tanggal. Fungsi pemrosesan yang dilaksanakan dengan komputer, biasanya menghasilkan perubahan
Pemrosesan dengan Komputer
atas data atau informasi.
14
Langkah pengambilan keputusan; dipergunakan dalam sebuah program komputer bagan alir Keputusan
untuk memperlihatkan pembuatan cabang ke jalan alternative. Arah pemrosesan atau arus dokumen; arus yang
Arus
dokumen
normal berada dibawah dan mengarah ke kanan.
atau proses Titik awal, akhir, atau pemberhentian dalam suatu proses atau program; juga dipergunakan Terminal
untuk menunjukkan adanya pihak eksternal. Data disimpan secara permanen di dalam disk magnetis, dipergunakan untuk file utama (
Disk Magnetic
master file ) dan database.
Sumber : Mulyadi, Sistem Akuntansi, 2001
2.2.
Logika Fuzzy Logika Fuzzy adalah peningkatan logika boolean yang berhadapan dengan konsep kebenaran sebagian. Di mana logika klasik menyatakan bahwa segala hal dapat diekspresikan dalam istilah binary (0 atau 1, hitam atau putih, ya atau tidak), logika fuzzy menggantikan kebenaran boolean dengan tingkat kebenaran (Kusumadewi, 2004). Metode fuzzy adalah salah satu perkembangan dari teori himpunan fuzzy dan logika fuzzy, dengan berbasiskan aturan yang menerapkan pemetaan non linear
antara
masukan
dan
keluarannya
(Dadone,
2001).
Menurut
15
Kusumadewi dan Purnomo (2004), pendekatan metode fuzzy dapat membantu dalam menjelaskan ketidakpastian batas antara satu kriteria dengan kriteria lainnya, yang disebabkan oleh adanya penilaian manusia terhadap sesuatu secara kumulatif. Teori ini dapat digunakan untuk membantu menyelesaikan permasalahan dalam ketidakpastian penulisan nama orang.
2.3.
Pencocokan String (String Matching)
2.3.1. Definisi String Matching Menurut Black (dalam Syaroni dan Munir, 2004:1) string adalah susunan dari karakter-karakter (angka, alphabet, atau karakter yang lain) dan biasanya direpresentasikan sebagai struktu data array. String dapat berupa kata, frase, atau kalimat. Sedangkan string matching menurut Black (dalam syaroni dan munir, 2004:1) diartikan sebagai sebuah permasalahan untuk menemukan pola susunan karakter string didalam string lain atau bagian dari isi teks. String matching dalam bahasa Indonesia dikenal dengan istilah pencocokan string (Munir dalam Hadiati, 2007:1).
Pencarian string yang juga bisa disebut pencocokan string (String Matching) merupakan
algoritma untuk
melakukan pencarian
semua
kemunculan string pendek pattern [ 0….n-1] yang disebut pattern di string yang lebih panjang teks [0…m-1] yang disebut teks (Charras, 1997 : 11).
16
2.3.2. Kerangka Kerja String Matching Persoalan pencarian string dirumuskan sebagai berikut (Munir, 2004 : 1) Diberikan : 1. Sebuah teks (text), yaitu sebuah (long) stringyang panjangnya n karakter. 2. Pattern, yaitu sebuah string dengan panjang m. Dengan sebuah nilai karakter (m < n) yang akan dicari dalam teks. Dalam algoritma pencocokan string, teks diasumsikan berada di dalam memori, sehingga bila kita mencari string di dalam sebuah arsip, maka semua isi arsip perlu dibaca terlebih dahulu kemudian disimpan di dalam memori. Jika pattern muncul lebih dari sekali di dalam teks, maka pencarian hanya akan memberikan keluaran berupa lokasi pattern ditemukan pertama kali.
2.3.3. Kerangka Pikir String Matching Algoritma string matching dapat diklasifikasikan menjadi 3 bagian menurut arah pencariannya, yakni (Charras, 1997 : 12). 1. From left to right Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk membaca. Algoritma yang termasuk kategori ini adalah algoritma brute force, algoritma knuth moris Pratt. 2. From right to left
17
Dari arah kanan ke kiri, arah yang bisanya menghasilkan hasil terbaik secara partikal. Algoritma yang termasuk kategori ini adalah algoritma boyer-moore. 3. In a specific order Dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis. Algoritma yang termasuk kategori ini adalah algoritma colossi dan algoritma crochemore-perrin.
Beberapa konsep string matching antara lain: 1. Approximate string matching, yaitu sebuah pencarian terhadap pola-pola string (mengandung beberapa proses yaitu mengitung jumlah karakter yang berbeda, penyisipan dan penghapusan karakter) sehingga mendekati pola atau pattern dari string yang dicari. Dari wikipedia didefinisikan sebagai sebuah teknik untuk mencari sebuah pola yang mendekati string dari sebuah kumpulan teks. 2. Algoritma pencarian string adalah sebuah proses pencarian tempat dari suatu atau beberapa string yang ditemukan dalam sebuah kumpulan string atau teks. Jalan paling sederhana adalah dengan cara membaca karakter satu persatu dan melakukan perhitungan kesalahan posisi yang ada dari string yang dicari.
18
2.3.4. Macam Algoritma String Matching Secara garis besar string matching dibedakan menjadi dua (Binstock & Rex dalam Syaroni & Munir, 2004 : 2), yaitu: 1. Exact string matching 2. Inexact string matching atau Fuzzy string matching.
2.4.
Exact String Matching Exact string matching, merupakan pencocokan string secara tepat dengan susunan karakter dalam string yang dicocokkan memiliki jumlah maupun urutan karakter dalam string yang sama. Bagian algoritma ini bermanfaat jika pengguna ingin mencari string dalam dokumen yang sama persis dengan string masukan. Beberapa algoritma exact string matching yang mengemuka antara lain : 1. Brute Force Analisis dengan metoda Brute Force adalah membandingkan karakter per karakter sampai ditemukannya pola yang dicari dari awal string sampai dengan akhir string (Sagita, 2006 :1 ). Dengan asumsi bahwa teks berada di dalam array T[1..n] dan pattern berada di dalam arrayP[1..m], maka algoritma brute force pencocokan string adalah sebagai berikut: a. Mula-mula pattern P dicocokkan pada awal teks T. b. Dengan bergerak dari kiri ke kanan, bandingkan setiap karakter di dalam pattern P dengan karakter yang bersesuaian di dalam teks T
19
sampai:semua karakter yang dibandingkan cocok atau sama (pencarian berhasil), atau dijumpai sebuah ketidakcocokan karakter (pencarian belum berhasil). c. Bila pattern P belum ditemukan kecocokannya dan teks T belum habis, geser pattern P satu karakter ke kanan dan ulangi langkah 2.
Kekuatan dan Kelemahan Metode Brute Force. (Munir, 2004:6) a. Kekuatan: 1) Metode brute force dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability). 2) Metode brute force sederhana dan mudah dimengerti. 3) Metode brute force menghasilkan algoritma yang layak untuk
beberapa
masalah
penting
seperti
pencarian,
pengurutan, pencocokan string, perkalian matriks. 4) Metode (standard)
brute
force
untuk
menghasilkan tugas-tugas
algoritma
komputasi
baku seperti
penjumlahan/perkalian n buah bilangan, menentukan elemen minimum atau maksimum di dalam tabel (list). b. Kelemahan: 1) Metode brute force jarang menghasilkan algoritma yang mangkus. 2) Beberapa algoritma brute force lambat sehingga tidak dapat diterima.
20
3) Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya. Berikut ini adalah pseudecode dari algoritma brute force : procedure PencocokanString(input P : string, T : string, n, m : integer,output idx : integer) { Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasika sebagai string (array of character) Keluaran: lokasi awal kecocokan (idx) } Deklarasi i : integer ketemu : boolean Algoritma: i 0 ketemu false while (i n-m) and (not ketemu) do j 1 while (j m) and (Pj = Ti+j ) do j j+1 endwhile { j > m or Pj Ti+j } if j = m then{ kecocokan string ditemukan } ketemu true else i i+1 {geser pattern satu karakter ke kanan teks } endif endfor { i > n – m or ketemu } if ketemu then idx i+1 else idx -1 endif
2. Knuth Morris Pratt Algoritma KMP dikembangkan oleh D. E. Knuth, bersama-sama dengan J. H. Morris dan V. R. Pratt. (Munir, 2004 : 8) Dengan algoritma KMP
21
waktu pencarian dalam pencocokan pattern dan teks dapat berkurang dikarenakan algoritma ini melakukan sejumlah pergeseran lebih jauh sesuai dengan informasi ketidakcocokan string antara teks dan pattern.
Dalam Algoritma Knuth-Morris-Pratt (KMP), untuk setiap karakter yang dibandingkan kita bisa 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 me-reuse karakter bila kita gagal (Sagita : 3). Berikut ini adalah pseudecode dari algoritma brute force : procedure KMPsearch(input m, n : integer, input P : array[1..m] ofchar, input T : array[1..n] ofchar, output idx : integer) { Mencari kecocokan pattern P di dalam teks T dengan algoritma Knuth-Morris-Pratt. Jika ditemukan P di dalam T, lokasi awal kecocokan disimpan di dalam peubah idx. Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasika sebagai string (array of character) Keluaran: posisi awal kecocokan (idx). Jika P tidak ditemukan, idx = -1. } Deklarasi i, j : integer ketemu : boolean b : array[1..m] ofinteger procedure HitungPinggiran(input m : integer, P : array[1..m] ofchar, output b : array[1..m] ofinteger) { Menghitung nilai b[1..m] untuk pattern P[1..m] }
22
Algoritma: HitungPinggiran(m, P, b) j 0 i 1 ketemu false while (i n and not ketemu) do while((j > 0) and (P[j+1] T[i])) do j b[j] endwhile if P[j+1]=T[i] then j j+1 endif if j = m then ketemu true else i i+1 endif endwhile if ketemu then idx i-m+1 { catatan: jika indeks array dimulai dari 0, maka idx m} else idx -1 endif
i-
3. Algoritma Boyer Moore Algoritma boyer-moore adalah algoritma yang mempertimbangkan string matching dengan efisiensi tinggi dari aplikasi. Algoritma ini melakukan pencocokan karakter yang dimulai dari kanan ke kiri (Purwanto, 2008).
Algoritma Boyer-Moore dipublikasikan oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977. Tidak seperti dua algoritma sebelumnya, algoritma Boyer-Moore memulai mencocokkan karakter dari sebelah kanan pattern. Ide dibalik algoritma ini adalah bahwa dengan memulai
23
pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat (Boyer). Jadi kita bisa melompati atau tidak melakukan perbandingan-perbandingan karakter yang diprediksikan akan gagal. Karakter paling kanan pada pola merupakan karakter pertama yang akan dicocokkan dengan teks. Sehingga prinsip dasar dari algoritma Boyer-Moore ini yakni : 1. Pembacaan karakter dari kanan ke kiri. 2. Preprocessing dimana terdapat kondisi bad karakter preprocessing dan good suffix preprocessing.
2.5.
Inexact string matching (fuzzy String Matching) Fuzzy string matching merupakan pencocokan string secara samar,
maksudnya pencocokan string dimana string yang dicocokkan memiliki kemiripan dimana keduanya memiliki susunan karakter yang berbeda (mungkin jumlah atau urutannya) tetapi string-string tersebut memiliki kemiripan baik kemiripan tekstual/penulisan (approximate string matching) atau kemiripan ucapan (phonetic string matching). Metoda fuzzy string matching diarahkan untuk mencari nilai dari beberapa string yang mendekati dan tidak hanya mengasilkan cocok atau tidak cocok (Syaroni dan Munir, 2004 : 2). Konsep Fuzzy String Matching. (Dewanto : 2007) 1. Fuzzy String Matching adalah salah satu metode pencarian string yang menggunakan proses pendekatan terhadap pola dari string yang dicari.
24
2. Melakukan pencarian terhadap string yang sama dan juga string yang mendekati dengan string lain yang terkumpul dalam sebuah penampung atau kamus. 3. Kunci dari konsep pencarian ini adalah bagaimana memutuskan bahwa sebuah string yang dicari memiliki kesamaan dengan string tertampung di kamus, meskipun tidak sama persis dalam susunan karakternya. Untuk memutuskan ‘kesamaan’ ini dipergunakan sebuah fungsi yang diistilahkan sebagai similarity function. Fungsi ini akan bertugas memutuskan string hasil pencarian jika ditemukan string hasil pendekatan (aproksimasi).
Inexact string matching masih dibagi menjadi dua yaitu : (Binstock & Rex dalam Syaroni & Munir, 2004 : 2) 1. Approximate string matching Approximate string matching adalah pencocokan string berdasarkan kemiripan
penulisan
(jumlah
karakter,susunan
karakter
dalam
dokumen). Tingkat kemiripan ditentukan dengan jauh tidaknya beda penulisan dua buah string yang dibandingkan tersebut dan nilai tingkat kemiripan ini ditentukan oleh pemrogram (programmer). Contoh :c mpuler dengan compiler, memiliki jumlah karakter yang sama tetapi ada dua karakter yang berbeda. Jika perbedaan dua karakter ini dapat ditoleransi sebagai sebuah kesalahan penulisan maka dua string tersebut dikatakan cocok.
25
2. Phonetic String Matching Phonetic String Matching adalah pencocokan string dengan dasar kemiripan dari segi pengucapannya meskipun ada perbedaan penulisan dua string yang dibandingkan tersebut. Contoh step dengan steb dari tulisan berbeda tetapi dalam pengucapannya mirip sehingga dua string tersebut dianggap cocok. Contoh yang lain adalah step, dengan steppe, sttep, stepp, stepe. Dalam pembagiannya beberapa algoritma phonetic string matching antara lain : soundex, metaphone, caverphone, phonex, NYSIIS, Jaro-Winkler, dan lain-lain. (Syaroni dan Munir, 2004)
Dalam penerapan kedua algoritma tersebut, sebenarnya phonetic string matching dapat dimanfaatkan untuk approximate string matching dengan batasan dua string yang dicocokkan masih memiliki kemiripan ucapan. Phonetic string matching sering juga dimanfaatkan untuk approximate string matching karena phonetic string matching lebih mudah diimplementasikan. Phonetic string matching banyak digunakan dalam bahasa Inggris karena dalam bahasa Inggris terdapat perbedaan antara penulisan dan pengucapan. Hal itupun terjadi pada bentuk penamaan Indonesia.
2.6.
Karakteristik Nama Nama adalah sebutan atau label yang diberikan kepada benda, manusia, tempat, produk (misalnya merek produk) dan bahkan gagasan atau konsep, yang biasanya digunakan untuk membedakan satu sama lain. Nama dapat
26
dipakai untuk mengenali sekelompok atau hanya sebuah benda dalam konteks yang unik maupun yang diberikan. Nama manusia umumnya terbagi kepada nama depan dan nama keluarga (marga), contohnya Ali Wijaya, di mana Ali adalah nama depan sedangkan Wijaya adalah marganya. Meskipun begitu, ada pula budaya-budaya yang tidak mengenal konsep tersebut. Ada pula nama panggilan yang merupakan nama khusus yang digunakan dalam bersosialisasi.
Ada banyak cara untuk menyusun suatu nama, tergantung dari budaya setempat dan bahasa setempat dan biasanya merupakan kombinasi dari 1. nama pemberian/nama depan (unik untuk setiap anak). 2. nama keluarga (unik untuk setiap keturunan dari garis laki-laki 3. nama tengah (untuk membedakan nama pemberian yang sama dari satu keluarga) 4. nama akhir (nama pemberian yang diletakkan setelah nama depan) 5. nama ayah 6. nama ibu 7. nama gadis (nama keluarga ibu sebelum menikah) 8. nama keluarga kakek dari ayah (=nama keluarga) 9. nama keluarga nenek dari ayah (=nama gadis nenek dari ayah) 10. nama keluarga kakek dari ibu (=nama gadis ibu) 11. nama keluarga nenek dari ibu (=nama gadis nenek dari ibu) 12. nama baptis 13. nama kota (biasanya di Eropa/Amerika)
27
14. nama pekerjaan (biasanya di Eropa/Amerika) 15. nama warna (biasanya di Eropa/Amerika) Daftar ini hanya sebagian kecil dari variasi yang mungkin terbentuk.
2.7.
Normalisasi nama Sebuah nama dapat memiliki banyak variasi dalam berbagai bahasa, biasanya untuk membuat suatu nama menjadi unik, orang juga membuat variasi mereka sendiri terhadap suatu nama yang telah ada. Nama-nama yang umum dipakai biasanya diturunkan dari nama orang-orang terkenal pada zaman dahulu, atau nama yang memiliki makna khusus (kata-kata yang indah, profesi orangtua, nama bunga, dan lain-lain). Dengan demikian, Penulisan dan cara pengucapan nama sangat tergantung kepada bahasa yang digunakan. Damerau (1964 : 171-176) menunjukkan setidaknya ada empat kejadian yang mengakibatkan variasi pada nama.
Tabel 2.2 Damerau Variasi Nama Jenis
Nama Dasar
Variasi
Insertion (Penyisipan)
Fisher
Fishcer
Omission (Penghilangan)
Johnston
Johnson
Subtitution (Penggantian)
Chatherine
Katherine
Transpotition (Pertukaran)
Hagler
Halger
28
Variasi pada nama tersebut, secara umum juga terjadi pada penamaan Indonesia. Sehingga dapat disimpulkan bahwa sifat bentuk penulisan dan pengucapan penamaan orang, adalah: 1. Memiliki bentuk cara penulisan yang bervariasi dalam satu nama orang. 2. Tidak memiliki standar penulisan nama yang baku. 3. Ketidakpastian (kekaburan) dalam bentuk penulisan. 4. Beberapa nama yang penulisannya berbeda, memiliki cara pengucapan yang sama.
Oleh karena itu, berdasarkan referensi studi yang dilakukan oleh Karhendana dalam studinya normalisasi string untuk optimasi phonetic string matching dalam menangani data nama orang didapatkan bahwa perlu adanya suatu langkah normalisasi sebelum dilakukan langkah pencocokan string dalam penamaan Bahasa Indonesia. Hal ini dilakukan untuk mendapatkan bentuk normal dari suatu bentuk penamaan Indonesia untuk meningkatkan akurasi algoritma pencocokan string dalam string nama orang. Adapun secara umum normalisasi bertujuan, yaitu : 1. Untuk menghilangkan kerangkapan data. 2. Untuk mengurangi kompleksitas. 3. Untuk mempermudah pemodifikasian data Proses normalisasi secara garis besar terbagi menjadi beberapa tahap, yaitu : (Karhendana : 2002) 1. Normalisasi Q-gram
29
2. Eliminasi duplikasi karakter Tahap yang paling penting dalam proses normalisasi adalah translasi Qgram. Q-gram adalah susunan beberapa huruf yang berurutan. translasi q-gram dilakukan dengan mengubah susunan huruf tersebut menjadi q-gram lain yang lebih sederhana. Tahap eliminasi duplikasi karakter dilakukan dengan menghilangkan karakter-karakter berurutan yang sama. Kebanyakan duplikasi karakter ini muncul setelah langkah normalisasi Q-gram. (Karhendana : 2002)
2.8.
Sistem Basis Data Database adalah kumpulan informasi yang disimpan di dalam komputer secara sistematik dan terstruktur sehingga dapat diperiksa menggunakan suatu program komputer untuk memperoleh informasi dari basis data tersebut.
Menurut Fathansyah (1999 : 2), basis data dapat diartikan sebagai suatu himpunan kelompok data (arsip) yang saling berhubung, diorganisasi sedemikian rupa agar kelak dapat dimanfaatkan kembali dengan cepat dan mudah. A. Alasan Perlunya Database 1. Basis data merupakan salah satu komponen penting dalam system informasi, karena merupakan dasar dalam menyediakan informasi. 2. Basis data menentukan kualitas informasi : akurat, tepat pada waktunya dan relevan. Informasi dapat dikatakan bernilai bila manfaatnya lebih efektif dibandingkan dengan biaya mendapatkannya.
30
3. Basis data mengurangi duplikasi data (data redudancy). 4. Dengan
mengaplikasikan
basis
data
hubungan
data
dapat
ditingkatkan. 5. Basis data dapat mengurangi pemborosan tempat simpanan luar.
B. Bahasa Basis Data Bahasa basis data terdiri atas : 1. Data Definition Language (DDL), merujuk pada kumpulan perintah yang dapat digunakan untuk mendefinisikan objek – objek basis data, seperti membuat sebuah tabel basis data atau indeks primer atau sekunder. 2. Data Manipulation Language (DML), mengacu pada kumpulan perintah yang dapat digunakan untuk melakukan manipulasi data, seperti penyimpanan data ke suatu tabel, kemudian mengubahnya dan menghapusnya atau hanya sekedar menampilkannya kembali.
C. Manfaat Basis Data Secara lebih lengkap, pemanfaatan basis data dilakukan untuk memenuhi sejumlah tujuan (objektif) seperti berikut a. Kecepatan dan kemudahan (Speed) b. Efisiensi ruang penyimpanan (Space) c. Keakuratan (Accuracy) d. Ketersediaan (Avaibility)
31
e. Kelengkapan (Completeness) f. Keamanan (Security) g. Kebersamaan pemakaian (Share sability)
2.9.
SQL (Structured Query Language) SQL adalah bahasa yang digunakan untuk berkomunikasi dengan database. Menurut ANSI (American National Standards Institute), bahasa ini merupakan standar untuk relational database management systems (RDBMS). Bahasa SQL memiliki struktur yang mudah dipahami karena perintah – perintahnya pada dasarnya dibuat dari bahasa Inggris. Sehingga kita dapat melakukan perintah – perintah SQL ke dalam database, yaitu : a. Memasukkan atau menambah record baru ke dalam database. b. Mengeksekusi query database c. Mengambil data dari database d. Mengubah record pada database e. Menghapus record pada database
Perintah SQL dapat diketik dengan huruf besar atau kecil (non case sensitive). Setelah selesai mengetik perintah di MySQL harus diakhiri dengan tanda titik koma sebagai penanda akhir dari perintah MySQL. Hampir semua software database mengimplementasikan bahasa SQL sebagai komponen utama dari produknya, salah satunya MySQL.
32
2.10.
MySQL MySQL adalah sebuah server database buatan T.c.X Data Konsultan AB
SQL multiuser dan multi-threaded. Beberapa keistimewaan MySQL: 1. API Languange (Application Programming Interface). Aplikasi database MySQL dapat ditulis dengan bahasa pemrograman C, Perl, PHP, dan lain-lain. 2. Large Tabel. MySQL menyimpan masing-masing tabel dalam database seperti file, terpisah dalam directori database. 3. Speed and Durability. MySQL lebih cepat 3-4 kali dari database komersial lain. 4. MySQL mudah untuk dikendalikan dan tidak membutuhkan database administrator proffesional untuk menginstall MySql. 5. MySQL adalah database relasional yang bersifat open source dan gratis. 6. Tersedia dibanyak platform (tersedia berbagai versi untuk berbagai sistem operasi). 7. Memiliki sistem sekuriti yang cukup baik dengan verifikasi host. 8. Mendukung ODBC untuk sistem operasi Microsoft Windows. 9. Tidak membutuhkan ruang harddisk yang besar untuk aplikasinya, dan mudah digunakan pada database server. 10. Mendukung record yang memiliki kolom dengan panjang tetap atau panjang bervariasi.
33
2.11.
Fungsi String MySQL Fungsi atau function adalah kata atau teks SQL yang mempunyai
kegunaan khusus untuk mengolah suatu data, sedangkan string adalah rangkaian karakter, angka, dan symbol-simbol lainnya. Banyak fungsi string yang disediakan MySQL untuk memanipulasi data string sehingga memudahkan pengolahan data.
2.12.
Aplikasi Menurut Daryanto (2004:347), aplikasi adalah Software atau perangkat
lunak yang dibuatuntuk menyelesaikan masalah-masalah khusus. Sedangkan menurut Jogiyanto (2004 : 4), aplikasi merupakan program yang berisikan perintah-perintah untuk melakukan pengolahan data. Jadi aplikasi secara umum adalah suatu proses dari cara manual yang ditransformasikan ke komputer dengan membuat sistem atau program agar data diolah lebih berdaya guna secara optimal, sedangkan menurut Kristanto (2004 : 1), software adalah instruksi (program komputer) yang ketika dijalankan menyediakan fungsi dan tampilan yang diinginkan, struktur data yang memberikan kesempatan program untuk memanipulasi informasi dan dokumen yang mendeskripsikan operasi dan pengaturan program. Sehingga dapat disimpulkan aplikasi adalah perangkat lunak yang berisi perintah-perintah untuk menyelesaikan masalah-masalah pengolahan data.
34
Didalam sebuah program aplikasi terbagi menjadi 2 bagian: ( Santosa, 2004) 1. Bagian Antarmuka –> Berupa tampilan untuk pemasukan data (input) dan untuk keluaran data (Output) 2. Bagian Aplikasi –> bagian yang berfungsi untuk menghasilkan informasi berdasar olahan data yang sudah dimasukkan oleh pengguna lewat algoritma yang diisyaratkan oleh aplikasi tersebut. Adapun dalam analisa penerapan fuzzy string matching ini aplikasi yang dibuat termasuk kedalam kategori bagian aplikasi.
2.13.
Metode Pengembangan Sistem
2.13.1. Definisi Pengembangan Sistem Menurut Govindaraju (2006:2) pengembangan sistem adalah aktifitas untuk menghasilkan sistem informasi berbasis komputer untuk menyelesaikan persoalan organisasi untuk memanfaatkan kesempatan yang timbul, sehingga sesuai dengan kasus permasalahan. 2.13.2. Macam-macam Metode Pengembangan Sistem 1. Model Siklus Kehidupan Klasik Model Sekuensial Linier merupakan paradigma rekayasa perangkat lunak yang paling tua dan paling banyak dipakai. Model ini mengusulkan sebuah pendekatan perkembangan perangkat lunak yang sistematik dan sekuensial dimulai pada tingkat dan kemajuan sistem pada seluruh analisis, desain, kode,
35
pengujian, dan pemeliharaan (Pressman : 1977). Model ini juga sering disebut dengan model air terjun. Tahapan-tahapan Model Sekuensial Linier : 1. Rekayasa dan Pemodelan Sistem/Informasi Karena perangkat lunak merupakan bagian dari suatu sistem maka langkah pertama dimulai dengan membangun syarat semua elemen sistem dan mengalokasikan ke perangkat lunak dengan memperhatikan hubungannya dengan manusia, perangkat keras dan database. 2. Analisis Kebutuhan Perangkat Lunak Proses menganalisis dan pengumpulan kebutuhan sistem yang sesuai dengan domain informasi tingkah laku, unjuk kerja, dan antar muka (interface) yang diperlukan. 3. Desain Proses desain akan menerjemahkan syarat kebutuhan ke sebuah perancangan perangkat lunak yang dapat diperkirakan sebelum dibuat coding. 4. Pengkodean (Coding) Pengkodean merupakan proses menerjemahkan desain ke dalam suatu bahasa yang bisa dimengerti oleh komputer. 5. Pengujian Proses pengujian dilakukan pada logika internal untuk memastikan semua pernyataan sudah diuji. Pengujian eksternal fungsional untuk menemukan kesalahan-kesalahan dan memastikan bahwa input akan memberikan hasil yang aktual sesuai yang dibutuhkan.
36
6. Pemeliharaan Perangkat lunak yang sudah disampaikan kepada pelanggan pasti akan mengalami perubahan.
Gambar 2.1 Model Sekuensial Linier 2. Prototyping. Prototyping adalah proses iterative dalam pengembangan sistem dimana requirement diubah ke dalam sistem yang bekerja (working system). (Al-Fatta, 2007 : 37). Secara ideal prototipe (dalam Pressman, 2002 : 39) berfungsi sebagai sebuah mekanisme untuk mengidentifikasi kebutuhan software. Tahapan-tahapan dalam Prototyping adalah sebagai berikut: 1. Pengumpulan kebutuhan Pelanggan dan pengembang bersama-sama mendefinisikan format seluruh perangkat lunak, mengidentifikasikan semua kebutuhan, dan garis besar sistem yang akan dibuat. 2. Membangun prototyping Membangun prototyping dengan membuat perancangan sementara (misalnya dengan membuat input dan format output).
37
3. Evaluasi protoptyping Evaluasi ini dilakukan oleh pelanggan apakah prototyping yang sudah dibangun sudah sesuai dengan keinginann pelanggan. Jika sudah sesuai maka langkah 4 akan diambil. Jika tidak prototyping direvisi dengan mengulangi langkah 1, 2 , dan 3. 4. Mengkodekan sistem Dalam tahap ini prototyping yang sudah di sepakati diterjemahkan ke dalam bahasa pemrograman yang sesuai 5. Menguji sistem Pengujian ini dilakukan dengan White Box, Black Box, Basis Path, pengujian arsitektur dan lain-lain 6. Evaluasi Sistem Pelanggan mengevaluasi apakah sistem yang sudah jadi sudah sesuai dengan yang diharapkan .Juka ya, langkah 7 dilakukan; jika tidak, ulangi langkah 4 dan 5. 7.
Menggunakan sistem
Perangkat lunak yang telah diuji dan diterima pelanggan siap untuk digunakan.
3. Rapid Application Development (RAD). Menurut Martin (dalam Pressman, 2002 : 42) Rapid application development (RAD) adalah sebuah model proses pengembangan perangkat lunak sekuensial linier yang menekankan pada siklus perkembangan cepat dengan
38
menggunakan pendekatan konstruksi berbasis komponen. Sehingga apabila kebutuhan dipahami dengan baik, maka system fungsional yang utuh dapat diselesaikan dalam waktu kira-kira 60-90 hari.
Menurut Martin (dalam Kendall & Kendall, 2007 ; 237) Pendekatan RAD meliputi fase-fase: 1. Fase Perencanaan Kebutuhan (Requirement Planning). Fase dimana pengguna tingkat tinggi memutuskan fungsi apa saja yang harus difiturkan oleh aplikasi tersebut. 2. Desain (Design Workshop) Fase dimana pengguna diminta membahas aspek-aspek desain non teknis dari sistem, dengan bimbingan penganalisis.Karena tingginya sifat interaktif, fase ini sering digabungkan dengan fase konstruksi pada workshop desain RAD. 3. Fase Konstruksi Pada fase ini setiap desain yang diciptakan dalam fase sebelumnya selanjutnya ditingkatkan untuk dilakukan pengkodean system.Kemudian setelah tahap ini selesai dilakukan uji kemampuan untuk mendapatkan komentar, dan revisi dari pengguna tingkat tinggi. 4. Fase Implementasi Tahap terakhir adalah dimana aplikasi baru diuji coba dan pengenalan terhadap aplikasi.
39
4. Object Oriented Analysis Design (OOAD) OOAD adalah metode pengembangan sistem yang lebih menekankan pada objek dibandingkan dengan data atau proses. Ada beberapa ciri khas dari pendekatan ini yaitu object, Inheritance dan object class. Objek adalah abstraksi dari benda nyata dimana data dan proses diletakkan bersama untuk memodelkan struktur dan perilaku dari objek dunia nyata. Objek class adalah sekumpulan objek yang berbagi struktur yang sama dan perilaku yang sama. Inheritance adalah properti yang muncul ketika tipe entitas atau objek class disusun secara hirarki dan setiap tipe entitas atau objek class menerima atau mewarisi atribut dan metode dari pendahulunya (Al Fatta, 2007: 38).
2.14.
Unit Testing Pengujian sistem perangkat lunak atau (software testing) adalah bagian
dari suatu siklus yang melibatkan verifikasi apakah suatu unit yang dikembangkan telah memenuhi kebutuhan sistem (syarat-syarat informasi) yang didefinisikan pada tahapan sebelumnya. Unit testing terdiri dari : 1. Pengujian Black Box Black box testing adalah pengujian fungsional yang merupakan pendekatan pengujian yang ujinya diturunkan dari spesifikasi program atau komponen. Sistem merupakan kotak hitam yang perilakunya hanya dapat ditentukan dengan mempelajari input dan output yang berkaitan. Pada black box testing, cara pengujian hanya dilakukan dengan menjalankan atau mengeksekusi unit atau modul, kemudian diamati pakah
40
hasil dari unit itu sesuai dengan proses bisnis yang diinginkan. Jika ada unit yang tidak sesuai outputnya maka untuk meneyelesaikannya, diteruskan pada pengujian white box (Al Fatta, 2007 : 172). 2. Pengujian White Box Pengujian white box (structural testing) merupakan pengujian yang diturunkan dari pengetahuan struktur dan implementasi perangkat lunak. Pengujian structural biasanya diterapkan untuk unit program yang relative kecil seperti subrutin atau operasi yang terkait dengan suatu objek. Sebagaimana ditunjukan oleh namanya, penguji dapat menganalisis kode dan menggunakan pengetahuan mengenai struktur komponen untuk menurunkan data uji. Pengetahuan mengenai algoritma yang digunakan untuk implementasi beberapa fungsi dapat dipakai untuk mengidentifikasi partisi ekuivalensi lebih lanjut (Sommerville, 2003: 91).
2.15.
Studi Sejenis Untuk penelitian skripsi yang dilakukan, berikut ini adalah referensi
tinjauan penelitian algoritma string matching dari dua buah skripsi dan jurnaljurnal yang digunakan sebagai studi literature penulis diantaranya adalah : Supardi (2009). Analisis penerapan string matching pada aplikasi pencarian berkas di komputer. Tujuan penelitian yang dibahas dalam skripsi ini merupakan penerapan algoritma exact string matching pada aplikasi pencarian berkas di komputer dengan menggunakan framework.NET dan bahasa C# melalui tahap model pengembangan sistem RAD . Hasil yang
41
didapatkan pada penelitian ini yakni algoritma boyer-moore memerlukan waktu yang lebih cepat dalam pencocokan dibandingkan knuth morris-pratt dan brute force tetapi boyer- moore tidak dapat melakukan pencocokan string untuk karakter ASCII data yang ada pada berkas komputer. Endang Hastriana (2010). Perbandingan algoritma string matching knuth morris-pratt dengan boyer moore horspool pada simulasi pengenalan sidik jari. Teknik Informatika Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah, Jakarta. Tujuan penelitian yang dibahas dalam tugas akhir ini merupakan penelitian yang dilakukan terhadap perbandingan algoritma knuth morris-pratt dan boyer moore pada suatu simulasi pengenalan sidik jari dengan menggunakan Borland Delphi melalui tahap model pengembangan sistem RAD. Hasil dari penelitian ini didapatkan bahwa boyer moore-horspool menghasilkan pencocokan yang lebih cepat dibanding knuth morris-pratt karena boyer moore horspool melakukan pergeseran yang lebih jauh daripada knuth morris-pratt. Mokhamad Syaroni dan Rinaldi Munir (2004). Pencocokan string berdasarkan kemiripan ucapan (phonetic string matching) dalam Bahasa Inggris. Tujuan penelitian yang dibahas dalam topik penelitian ini merupakan pembahasan dan analisis kemampuan tiga algoritma phonetic string matching yaitu algoritma soundex, metaphone, dan caverphone dari segi fonetik Bahasa Inggris. Hasil analasis kemampuan phonetic string matching algoritma soundex, metaphone, dan caverphone, menunjukkan bahwa kemampuan phonetic string matching yang baik ditunjukkan oleh algoritma caverphone.
42
Bernardino Madaharsa Dito Adiwidya (2009). Algoritma levensthein dalam pendekatan approximate string matching. Tujuan penelitian yang dibahas dalam topik penelitian ini merupakan pencarian jumlah operasi string dalam
approximate
string
matching
yang
diperlukan
untuk
mentransformasikan suatu string menjadi string lain menggunakan pendekatan algoritma levenshtein. Hasil yang didapatkan pada penelitian ini disimpulkan bahwa levenshtein merupakan algoritma yang diperlukan untuk mencari perbedaan- perbedaan string yang ada pada operasi approximate dengan kompleksitas O(n2). Anggy Sagita., dkk (2006). Analisa algoritma pencocokan string. Tujuan penelitian yang dibahas dalam topik penelitian ini merupakan suatu analisis algoritma staightforward matching dengan menggunakan brute force, knuthmorris-pratt, dan boyer-moore pada pencarian string dalam sekumpulan teks. Hasil yang didapatkan yakni bahwa algoritma yang dianalisis pada penelitian ini hanya dapat menangani permasalahan string yang bersifat exact. Dewanto R.A Aradea (2007). Aplikasi SMS Gateway dengan koreksi kesalahan menggunakan fuzzy string matching. Teknik Informatika Fakultas Teknik Universitas Siliwangi Tasikmalaya. Tujuan penelitian yang dibahas dalam topik penelitian ini adalah menggunakan konsep fuzzy string matching untuk mengoreksi kesalahan yang ada pada pengelolaan informasi via sms yang bernama SMS Gateway menggunakan logika Fuzzy dan Clusterring. Hasil yang didapatkan pada penelitian ini yakni Fuzzy String Matching (FSM) mampu menekan kesalahan kode yang masuk ke SMS Gateway. Namun
43
beberapa kekurangan masih muncul jika data yang dikirimkan bukan kode yang ada pada kamus sistem. Berdasarkan penelitian yang dijabarkan diatas, maka penulis menjadikan penelitian-penelitian sebelumnya sebagai referensi studi sejenis untuk proses penelitian pada tugas akhir ini. Adapun penelitian-penelitian sebelumnya belumlah melakukan suatu penelitian analisis penerapan string matching menggunakan inexact string matching secara approximate string matching dan exact string matching secara brute force string matching pada suatu pencocokan string data nama orang yang dikomparasi. Penelitian yang penulis lakukan merupakan suatu analisis penerapan string matching dalam suatu komparasi data kepesertaan JAMKESMAS menggunakan PHP sebagai bahasa pemrograman dan MySQL sebagai database server untuk mendapatkan kecocokan data string antara dua database.
BAB III METODOLOGI PENELITIAN
Untuk mendapat data dan fakta yang sebenarnya dalam menguraikan masalah pada komparasi data untuk mendapatkan kecocokan data ini, maka penulis merumuskan cara yang tepat dalam memecahkan permasalahan yang terangkum dalam suatu rangkaian metodologi penelitian mengacu pada penelitian sebelumnya maupun referensi teori yang mendasari.
3.1.
Metode Pengumpulan Data Berkaitan dengan hal tersebut, penulis melakukan metode pengumpulan data. Pengumpulan data adalah prosedur yang sistematis dan standar untuk perolehan data yang diperlukan. Data yang dikumpulkan merupakan teoriteori yang telah berkembang dalam bidang ilmu yang berhubungan, dan teknik-teknik yang digunakan oleh peneliti sebelumnya. Metode pengumpulan data yang digunakan dalam hal ini adalah : 1. Metode Dokumentasi Metode Dokumentasi adalah teknik pengumpulan data yang dilakukan dengan membaca dan mempelajari buku, dokumen, jurnal serta literatur yang berkaitan dengan objek penelitian. Pengumpulan data ini penulis lakukan dengan cara mengunjungi perpustakaan maupun memanfaatkan media internet .
44
45
2. Wawancara
Wawancara adalah teknik pengumpulan data yang dilakukan dengan Bapak Swasetyo Yulianto pada Desember 2010 di Badan Pengkajian dan Penelitian Teknologi guna mendapatkan informasi permasalahan yang dihadapi dalam pengelolaan data kepesertaan JAMKESMAS.
3.2.
Metode Komparatif Studi kausal-komparatif merupakan informasi yang sangat berguna mengenai sifat-sifat gejala yang dipersoalkan dalam kondisi, perurutan dan cara yang dilakukan dalam mengkomparasi. Untuk mendapatkan gambaran mengenai algoritma string matching dalam menguraikan masalah pada komparasi data ini, maka penulis merumuskan cara dalam memecahkan permasalahan yang terangkum dalam suatu rangkaian analisis algoritma pada penerapan string matching komparasi data kepesertaan. Adapun dalam hal ini penulis menggunakan dua macam algoritma string matching yakni pendekatan algoritma brute-force yang mewakili jenis algoritma exact string matching serta algoritma approximate string matching yang mewakili algoritma fuzzy string matching. Penggunaan algoritma exact string matching dalam komparasi data penamaan ini sengaja penulis lakukan guna menjadikan parameter ukuran serta memperkuat alasan penulis untuk menggunakan fuzzy string matching sebagai solusi dalam permasalahan ini.
46
3.3.
Metode Pengembangan Sistem Dalam pengembangan sistem yang dilaksanakan pada penerapan algoritma string matching dalam komparasi data kepesertaan ini penulis menggunakan model pengembangan RAD yang meliputi : (Kendall & Kendall, 2007:237) 1. Fase Perencanaan Syarat-syarat. Dalam tahapan ini penulis merencanakan tujuan dan berbagai syarat-syarat dalam memenuhi kebutuhan sistem (aplikasi) dalam penyelesaian permasalahan kecocokan data kepesertaan ini. Menetukan syarat-syarat informasi salah satunya adalah menetukan data-data yang diperlukan dan menganalisa metode yang tepat guna memberikan solusi untuk mencapai tujuan, yakni dengan cara : a. Mendefinisikan Masalah, adalah tahap untuk menentukan masalah apa yang harus diselesaikan dengan menggunakan sistem aplikasi yang akan dibangun. Hal ini dilakukan guna menentukan syarat-syarat informasi. b. Menentukan permasalahan
kebutuhan dan
syarat
menganalisa
informasi metode
untuk yang
memecahkan tepat.
Dalam
menyelesaikan permasalahan komparasi data untuk mendapatkan kecocokan string data kepesertaan ini, penulis melakukan penyelesaian dengan menggunakan dua macam algoritma string matching yakni : 1. Exact String Matching Dalam hal ini penulis menggunakan algoritma brute force sebagai salah satu algoritma yang mewakili exact string matching untuk
47
membuktikan dan menguji kehandalan algoritma ini dalam menyelesaikan permasalahan yang ada. 2. Fuzzy String Matching Dalam hal ini penulis menggunakan algoritma approximate string matching untuk membuktikan serta menguji kehandalan algoritma ini dalam meyelesaikan permasalahan yang ada. Analisis algoritma string matching dalam komparasi data penamaan ini akan dijelaskan pada sub bab. 2. Fase Perancangan. Dalam fase ini penulis melakukan perancangan terhadap pengaplikasian metode exact string matching dan fuzzy string matching, serta merancang aplikasi yang hendak dibuat atau dibangun guna menguji keefektifan metode algoritma dalam menyelesaikan permasalahan yang ada. Kegiatan yang dilakukan dalam tahap perancangan atau desain ini meliputi (Ladjamudin, 2005: 39): a. Desain proses, meliputi desain tentang proses-proses apa saja yang dibutuhkan oleh sistem. b. Desain basis data, merupakan desain tabel-tabel yang dibutuhkan dalam pengolahan data. Table-tabel ini akan diimplementasikan kedalam bentuk database, yang menggunakan program MySQL. c. Desain antarmuka, merupakan desain untuk menentukan masukan dan keluaran yang akan digunakan untuk mengoperasikan sistem.
48
3. Fase Konstruksi. Dalam fase ini penulis melakukan konstruksi aplikasi setelah melakukan fase perancangan aplikasi dengan cara pengkodean. Tools program yang digunakan dalam sistem penerapan algoritma string matching ini menggunakan PHP sebagai bahasa pemrograman dan MySQL sebagai database server. 4. Fase Implementasi. Dalam fase ini penulis melakukan implementasi terhadap aplikasi yang dibangun guna menguji seberapa besar kemampuan metode fuzzy string matching dan exact string matching yang digunakan dalam menyelesaikan permasalahan yang ada. Pengujian ini berguna agar penulis dapat mengetahui secara keseluruhan mengenai kesesuaian, efektifitas dan efisiensi penerapan algoritma string matching terhadap tujuan yang ingin dicapai, yang mana hal ini sangat berguna sebagai bahan kesimpulan dalam menilai akurasi kecocokan dalam menyelesaikan permasalahan pencocokan string komprasi data kepesertaan. Metode pengujian yang digunakan dalam pengujian sistem adalah metode pengujian white box pada pengujian sistem aplikasi yang dibangun.
3.4.
Alasan Penggunaan RAD Adapun dalam penelitian ini penulis memilih menggunakan metode pengembangan sistem Rapid Aplication Development dengan berbagai alasan berikut :
49
1. Prinsip model pengembangan RAD yang waktunya cepat dan singkat dalam tiap langkah metode pengerjaannya . 2. Memudahkan dalam tiap-tiap langkah kerja karena adanya modularisasi pengerjaan. 3. Aplikasi yang dirancang dan dibangun hanya dipergunakan untuk mengimplementasikan metode algoritma yang dipilih guna menguji keefektifan algoritma dalam menyelesaikan permasalahan yang ada ssehingga tidak memerlukan tahap pemeliharaan. 4. Sangat cocok diterapkan pada aplikasi berskala kecil. Hal ini sesuai dengan aplikasi yang dibuat dalam penerapan metode algoritma string matching.
3.5.
Keunggulan dan Kelemahan RAD a. Keunggulan: 1. Waktu pengembangan yang lebih singkat dan cepat jika kebutuhan dan batasan proyek diketahui. 2. Biaya yang relatif lebih murah atau rendah. b. Kelemahan: 1. Tidak cocok untuk proyek skala besar. 2. Hanya baik digunakan pada proyek penelitian yang dapat dimodularisasi. 3. Membutuhkan suatu tim yang cukup untuk mengerjakan bagianbagian yang dimodularisasi.
BAB IV ANALISIS DAN PEMBAHASAN Dalam melaksanakan penerapan string matching dalam komparasi data kepesertaan, penulis telah melalui berbagai tahap-tahapan metode penelitian hingga mencapai hasil dari tujuan yang hendak dicapai. Dalam bab ini penulis menjabarkan hal-hal yang dilakukan penulis selama penyelesaian penelitian ini, sesuai dengan metodologi penelitian yang dirujuk penulis.
4.1.
Metode Komparatif Dalam tahap komparatif ini penulis melakukan suatu proses analisis dalam penerapan string matching untuk komparasi data kepesertaan JAMKESMAS yang dilakukan dalam membandingkan dua data yang terdapat pada dua instansi yakni BPS dan ASKES. Data yang dibandingkan dalam komparasi data untuk mendapatkan kecocokan data ini merupakan data yang berasal dari wilayah Propinsi Bangka Belitung.
4.1.1. Analisis Algoritma String Matching Analisis penerapan fuzzy string matching dalam komparasi data kepesertaan merupakan analisis terhadap penerapan algoritma fuzzy string matching dalam membandingkan kecocokan data string nama sebagai tolak ukur kesamaan data yang terdapat pada dua database. Pemilihan nama sebagai informasi peserta yang patut dianalisa dalam algoritma fuzzy string matching komparasi data ini didasari karena data string nama orang merupakan data string yang tidak memiliki bentuk penulisan baku dan bermacam-macam 50
51
bentuk penulisan dalam satu nama orang, hal ini menunjukan bahwa string nama orang adalah hal yang bersifat kabur atau samar yang mana sesuai dengan prinsip logika fuzzy. Untuk menguatkan alasan dan sebagai parameter (ukuran) dalam pemilihan algoritma tersebut maka penulis kemudian juga menggunakan algoritma exact string matching.
4.1.1.1 Exact String Matching Berdasarkan studi literatur yang dilakukan maka penulis memilih menggunakan algoritma brute force untuk diterapkan dalam komparasi data kepesertaan. Exact string matching merupakan algoritma yang digunakan penulis untuk menjadikan parameter (ukuran) dalam penggunaan algoritma inexact string matching.
Teknik Pencocokan pada Algoritma brute force : 1. Menyamakan teks dengan menghitung jumlah karakter teks pada masingmasing database. Setiap string yang memiliki jumlah karakter yang sama maka string tersebut akan dikumpulkan dan kemudian akan dibandingkan untuk dicocokan.
52
1
1
2 3 4 5 6
2 3 4 5 6
Database B
Database A
1
…
…
…
…
6
1
…
…
…
…
6
R
A
H
M
A
T
E
F
E
N
D
Y
R
I
Y
A
D
I
J
U
N
I
A
R
E
F
E
N
D
I
H
A
R
T
I
N
R
A
T
I
N
A
H
U
S
N
A
H
S
U
M
I
N
A
R
E
N
A
T
A
Y
U
N
I
A
R
53
2. Mencocokan kesamaan teks dengan membaca karakter sebelah kiri string yang berindeks-1 pada masing-masing database.
1
…
…
…
…
6
R
A
H
M
A
T
R
E
N
I
T
A
T
U
M
I
N
I
R
I
Y
A
D
I
S
U
M
I
N
A
1
…
…
…
…
6
T
U
M
I
N
I
J
U
N
I
A
R
H
A
R
T
I
N
H
U
S
N
A
H
R
E
L
I
T
A
Y
U
N
I
A
R
a. Bila karakter pada record masing-masing database memiliki kesamaan, maka pencocokan string akan berpindah kearah kanan karakter string selanjutnya, hingga akhir dari string tersebut. b. Sedangkan bila karakter yang dicocokan tidak memiliki kesamaan antar karakter pada masing-masing database maka string tersebut tidak kembali dicocokan (dinyatakan tidak cocok).
54
1
…
…
…
…
6
1
…
…
…
…
6
R
E
N
I
T
A
E
F
E
N
D
Y
E
F
E
N
D
I
R
E
L
I
T
A
1
…
…
…
…
E
F
E
N
D
1
…
…
…
…
6
E
F
E
N
D
I
1
…
…
…
…
6
E
F
E
N
D
1 I
…
E F
…
…
…
6
E
N
D
Y
1
…
…
…
…
6
E
F
E
N
D
Y
1
…
…
…
…
6
E
F
E
N
D
Y
I
55
Karena tidak adanya karakter yang sama saat pembacaan pada karakter ke 5 antara kedua string pada masing-masing database maka pencocokan pada kedua database tidak dilanjutkan (berhenti) atau dinyatakan kedua database yang dibandingkan tidak memiliki kecocokan. Dengan contoh perumpamaan diatas dapat disimpulkan bahwa menggunakan algoritma brute force string matching (Exact String Matching) dalam pencocokan string data nama orang merupakan metode pencocokan string yang hanya mengambil string nama yang sama persis dengan string masukan atau string yang dibandingkan. Sehingga algoritma ini belum mampu untuk menangani, seperti: 1. Adanya kemungkinan perbedaan ejaan dalam input data nama. 2. Bentuk penaaman orang (peserta) yang variatif.
4.1.1.2 Normalisasi String Sebelum melangkah kedalam algoritma string matching diperlukan suatu proses normalisasi string nama untuk mencapai keakuratan fuzzy string matching. Normalisasi string dalam data nama peserta adalah suatu proses untuk mendapatkan similarty function pada algoritma fuzzy string matching. Similarity function adalah suatu fungsi yang menentukan kesamaan data string yang dicocokan. Similarity function didapatkan dari normalisasi string penamaan sesuai dengan aturan translasi Q-gram maupun eliminasi duplikasi karakter setelah dilakukannya translasi Q-gram. Proses normalisasi ini dilakukan guna membentuk suatu nama orang (peserta) yang memiliki keteraturan bentuk penamaan sehingga dapat mengurangi variasi bentuk penamaan.
56
Proses normalisasi secara garis besar terbagi menjadi beberapa tahap, yaitu: 1. Translasi q-gram. 2. Eliminasi duplikasi karakter Dalam menormalisasikan string, penulis melakukan translasi q-gram yang bertujuan untuk mendapatkan aturan tetap dari bentuk suatu karakter yang ada dalam data nama orang. Oleh karena itu dalam melakukan translasi q-gram, penulis melakukan pengambilan sampel data nama peserta untuk mendapatkan sebaran nama yang tetap terhadap bentuk karakter penamaan orang dan melakukan pendekatan statistic untuk memperkecil ambiguitas dari pemakaian bentuk string penamaan orang agar mangetahui translasi karakter yang sering muncul. Adapun aturan yang didapatkan dalam translasi q-gram ini : Tabel 4.1 Translasi Q-gram Awal
Translasi Q-Gram
CQ,CK
KK
DJ
JJ
DZ
ZZ
IE
II
KH
HH
KS
XX
OE
UU
PH
FF
57
V
F
SJ
SY
SY
SS
TJ
CC
DY
DI
BH,CH,DH,GH,JH,SH,TH,ZH BB,CC,DD,GG,JJ,SS,TT,ZZ AA,BB, CC, DD, EE, FF, GG, A, B, C, D, E, F, G, H, I, J, HH, II, JJ, KK, LL, MM, NN, K, L, M, N, O, P, Q, R, T, OO, PP, QQ, RR, SS, TT, UU, U, V, W, X, Y, Z VV, WW, XX, YY, ZZ
Pengambilan q-gram (urutan karakter) pada aturan translasi ini ditetapkan dengan asumsi keunikan dan tingginya tingkat kemunculan q-gram pada suatu string nama orang. Berdasarkan hal diatas, melangkah pada tahap selanjutnya yakni melakukan eliminasi duplikasi karakter. Hal ini dilakukan terhadap suatu karakter yang berulang pada translasi q-gram. Sehingga didapatkan bentuk normal dari suatu karakter penamaan dalam data string nama orang. Dalam penerapan normalisasi untuk mendapatkan similarity function maka dilakukan suatu penghitungan perbedaan jumlah karakter dari data string pada masing-masing database dengan cara melakukan operasi-operasi seperti operasi penghapusan, penyisipan, maupun penggantian pada data string
58
hingga didapatkan kecocokan string yang sama, ataupun mendekati kesamaan sesuai dengan similarity function.
Gambar 4.1 Proses Similarity Function
1. Operasi penghapusan Operasi penghapusan dilakukan bila suatu string yang akan dicocokan memiliki q-gram yang harus mengikuti aturan translasi q-gram. Contoh :
1
2
3
4
5
6
7
E
F
E
N
D
H
I
Karena DH merupakan q-gram (urutan karakter) yang terdapat pada aturan tranlasi q-gram maka dilakukan suatu operasi penghapusan pada karakter H sesuai dengan aturan translasi Q-gram yang mana string tersebut menjadi :
59
1
2
3
4
5
6
7
E
F
E
N
D
D
I
Setelah melalui proses translasi q-gram maka karakter yang berdekatan dan mengalami pengulangan pada suatu string akan dieliminasi (eliminasi duplikasi karakter) sehingga string menjadi : 1
2
3
4
5
6
E
F
E
N
D
I
Sehingga dapat disimpulkan bahwa nama string normal dari nama EFENDHI dadalah EFENDI atau EFENDHI = EFENDI
2. Operasi penggantian Operasi penggantian dilakukan bila suatu string yang akan dicocokan memiliki q-gram yang harus mengikuti aturan translasi q-gram. Contoh : 1
2
3
4
5
6
E
F
E
N
D
Y
Maka pada data string diatas akan dilakukan suatu operasi penggantian pada karakter Y sesuai dengan aturan translasi Q-gram yang mana string tersebut akan menjadi :
60
1
2
3
4
5
6
E
F
E
N
D
I
Setelah data sesuai dengan aturan translasi Q-gram maka akan dilakukan eliminasi duplikasi karakter pada suatu karakter yang berulang, karena pada data string tidak memiliki pengulangan karakter yang berdekatan maka string tersebut tidak melakukan eliminasi duplikasi karakter sehingga dapat disimpulkan bahwa bentuk normal dari nama EFENDY adalah EFENDI atau EFENDY = EFENDI
3. Operasi Penyisipan Operasi penggantian dilakukan bila suatu string yang akan dicocokan memiliki q-gram yang harus mengikuti aturan translasi q-gram.
1
2
3
4
5
R
A
M
A
T
Dalam hal ini maka akan dilakukan operasi penyisipan pada string diatas sehingga dapat sesuai dengan bentuk normal dari string tersebut.
1
2
3
4
5
6
R
A
H
M
A
T
61
Bentuk string diatas merupakan bentuk string normal dari nama tersebut sesuai dengan similarity function. Sehingga dapat disimpulkan bahwa bentuk normal penulisan RAMAT adalah RAHMAT atau RAMAT = RAHMAT.
Dengan demikian dari proses normalisasi q-gram data nama inilah yang kemudian menjadi suatu acuan dalam pembentukan suatu nama yang baku atau normal. Adapun langkah-langkah penerapan proses normalisasi string pada data nama orang (peserta) yaitu : 1. Mengambil data nama orang (peserta). 2. Membaca karakter data nama orang (peserta) yang dimulai dari sebelah kiri string. 3. Untuk 2 urutan karakter (q-gram) yang dibaca. a. Jika q-gram 2 karakter sama dengan q-gram pada tabel q-gram maka translasikan (ubah) 2 karakter yang dibaca sesuai dengan translasi qgram pada tabel q-gram. b. Jika q-gram 2 karakter tidak sama dengan q-gram pada table q-gram maka urutan karakter (q-gram) yang dibaca tidak berubah. 4. Lakukan pembacaan urutan karakter selanjutnya hingga karakter terakhir pada data string nama orang.
62
4.1.1.3 Inexact String Matching (Fuzzy String Matching) Metode inexact string matching atau fuzzy string matching adalah metode pencocokan yang digunakan untuk mencari string yang memiliki kesamaan dengan string tertampung di kamus, meskipun tidak sama persis dalam susunan karakternya. Untuk mendapatkan kesamaan ini dibutuhkan suatu fungsi yang sering disebut dengan similarity function, similarty function adalah Fungsi yang akan bertugas memutuskan string hasil pencarian jika ditemukan string hasil pendekatan (aproksimasi). Similarity function pada data string nama orang didahului dengan normalisasi string penamaan sesuai dengan aturan translasi Q-gram maupun eliminasi duplikasi karakter setelah dilakukannya translasi Q-gram. Q-gram adalah susunan beberapa huruf yang berurutan. Sedangkan eliminasi duplikasi karakter adalah menghilangkan karakter yang memiliki pengulangan pada suatu string. Algoritma (langkah-langkah) Fuzzy String Matching dalam Komparasi data kepesertaan : 1. Menormalisasikan karakter suatu data string nama peserta yang dibaca pada masing-masing database. a. Bila karakter yang dibaca pada string yang dibandingkan memiliki qgram (urutan karakter) yang ada pada suatu tabel aturan q-gram maka q-gram pada string tersebut akan ditranslasikan kedalam bentuk normal karakter tersebut, proses translasi q-gram ini akan dilakukan pada suatu data string yang dibaca selama ditemui adanya suatu urutan karakter yang terdapat pada tabel aturan q-gram, bila kemudian
63
terdapat karakter berdekatan yang berulang maka salah satu karakter tersebut akan dieliminasi.
1
2
3
4
5
6
7
1
2
3
4
5
6
7
E
F
E
N
D
H
Y
E
F
F
E
N
D
Y
1
2
3
4
5
6
7
1
2
3
4
5
6
E
F
E
N
D
D
Y
E
F
E
N
D
Y
1
2
3
4
5
6
1
2
3
4
5
6
E
F
E
N
D
Y
E
F
E
N
D
I
1
2
3
4
5
6
E
F
E
N
D
I
b. Bila karakter yang dibaca pada string yang dibandingkan memiliki qgram (urutan karakter) yang tidak terdapat pada suatu tabel aturan qgram maka dapat disimpulkan string tersebut telah memiliki bentuk normal urutan karakter yang tidak perlu ditranslasikan.
1
2
3
4
5
W
U
L
A
N
64
Dikarenakan WU-UL-LA-AN merupakan uruten karakter yang tidak terdapat pada tabel q-gram maka urutan-urutan karakter yang terdapat pada string tersebut tidak perlu ditranslasikan.
2. Penghitungan jumlah karakter dari data string yang dicocokan pada masing-masing database. 1
2
3
4
5
6
1
2
3
4
5
6
S
T
R
I
N
G
S
T
R
I
N
G
Database A
Database B
3. Bila bentuk suatu string yang dibaca telah memiliki bentuk normal dari string tersebut maka proses membandingkan kecocokan data string dapat dilakukan dengan memeriksa kecocokan tiap-tiap karakter pada data string yang dibandingkan. a. Bila karakter yang dibandingkan memiliki kecocokan atau persamaan karakter maka proses pemeriksaan kecocokan karakter akan berlanjut hingga pada karakter terakhir jumlah string tersebut. b. Bila kemudian ditemui ketidakcocokan karakter pada string yang dibandingkan maka dapat disimpulkan kedua string yang dibandingkan tidak memiliki kecocokan sehingga proses pencocokan pun tidak berlanjut (dinyatakan string yang dibandingkan tidak cocok).
65
Database B
Database A
1
…
…
…
…
J
A
M
I
L
S
U
P
R
Y
U
L
M I S
A
7
1
…
…
…
…
A
H
S
A
M
P
R
I
N
I
A
N
J
A
M
I
L
A
H
I
A
N
A
H
A
R
T
I
R
N
A
T
I
M
P
R
I
N
7
N
4. Mencocokan kesamaan teks dengan membaca karakter sebelah kiri string yang berindeks-1 pada masing-masing database.
1
…
…
…
…
J
A
M
I
L
A
H
S
U
P
R
I
A
N
S
A
M
P
R
I
N
7
1
…
…
…
…
S
A
M
P
R
I
N
J
A
M
I
L
A
H
7
66
a. Bila karakter pada record masing-masing database memiliki kesamaan, maka pencocokan string akan berpindah kearah kanan karakter string selanjutnya, hingga akhir dari string tersebut. b. Sedangkan bila karakter yang dicocokan tidak memiliki kesamaan antar karakter pada masing-masing database maka string tersebut tidak kembali dicocokan (dinyatakan tidak cocok).
1
…
…
…
…
J
A
M
I
L
1
…
…
…
…
S
A
M
P
R
1
…
…
…
…
J
A
M
I
L
A
I
A
7
1
…
…
…
…
H
J
A
M
I
L
7
1
…
…
…
…
N
J
A
M
I
L
7
1
…
…
…
…
H
J
A
M
I
L
7 A
H
7 A
H
7 A
H
67
1
…
…
…
…
J
A
M
I
L
1
…
…
…
…
J
A
M
I
L
1
…
…
…
…
J
A
M
I
L
1
…
…
…
…
J
A
M
I
L
A
A
A
A
7
1
…
…
…
…
H
J
A
M
I
L
7
1
…
…
…
…
H
J
A
M
I
L
7
1
…
…
…
…
H
J
A
M
I
L
7
1
…
…
…
…
H
J
A
M
I
L
7 A
H
7 A
H
7 A
H
7 A
H
68
Karena adanya karakter yang sama hingga pembacaan pada karakter terakhir antara kedua string pada masing-masing database maka dapat disimpulkan data yang dibandingkan memiliki kecocokan. Dengan demikian hasil dari analisis penerapan string matching dalam komparasi data nama peserta inilah yang kemudian menjadi tahapan-tahapan metode (algoritma) yang digunakan dalam mencocokan data antar kedua database sebagai gambaran dalam menangani data nama peserta maupun data string peserta lainnya.
4.2.
Fase Perencanaan Syarat-syarat Dalam tahap perencanaan penerapan string matching komparasi data kepesertaan, terdapat berbagai cara yang dilakukan untuk memenuhi syaratsyarat yang dibutuhkan dalam pembuatan sistem, diantaranya:
4.2.1. Tujuan Informasi Analisis dan penerapan algoritma string matching dalam komparasi data kepesertaan JAMKESMAS ini bertujuan untuk mencari suatu kecocokan data antara kedua database instansi yang menjadi rujukan data kepesertaan jamkemas. Hal ini diperlukan guna memecahkan permasalahan perbedaan data yang terdapat pada kedua instansi yang mengambil data pada wilayah yang sama namun memiliki jumlah data yang berbeda. Sehingga dari perbedaan tersebut diperlukan suatu perbandingan data untuk mencari kecocokan atau kesamaan yang terdapat antar kedua database. Untuk mendapatkan kecocokan data antar kedua database maka diperlukan
69
suatu metode pencocokan string, yang akan digunakan untuk mencari kecocokan string antar kedua database. Algoritma string matching yang digunakan dalam komparasi data untuk mendapatkan kecocokan string ini yakni algoritma brute force yang mewakili algoritma exact string matching, serta approximate string matching yang mewakili algoritma fuzzy string matching. 4.2.2. Syarat Kebutuhan/Informasi Tahapan ini merupakan tahapan untuk menetukan syarat-syarat informasi apa saja yang digunakan. Diantara perangkat-perangkat yang ada untuk menentukan syarat-syarat infromasi salah satunya adalah menentukan datadata yang diperlukan dan metode yang akan dipakai. Adapun dalam mengaplikasikan string matching komparasi data kepesertaan ini penulis menggunakan perangkat keras dan perangkat lunak sebagai berikut: 1. RAM 2 GB. 2. Pentium IV. 3. Windows XP SP3. 4. Telah terinstall Web Browser, Apache web server, PHP, dan MySQL.
70
4.3.
Perancangan Sistem
4.3.1. Perancangan Proses 4.3.1.1 Algoritma Exact String Matching
Start
Ambil Nama
Tb. Peserta 1
Db Utama
Db1 [Nama];
Memeriksa kecocokan
Tidak Apakah cocok
Ya Tampilkan kecocokan data Akhir
Gambar 4.2 Flowchart Exact String Matching
71
4.3.1.2 Proses Kecocokan
Memeriksa kecocokan
Ambil Nama
Tb. Peserta 2
Db1[nama]; Db2[nama];
If (Db1[nama]= Db2[nama])
Keluar
Gambar 4.3 Flowchart Proses Kecocokan
Db 2
72
4.3.1.3 Algoritma Inexact String Matching (Fuzzy String Matching)
Start
Tb. Normalisasi
Normalisasi nama
Ambil nama
Db1[nama];
Memeriksa kecocokan
Tidak Apakah Cocok Ya Tampilkan kecocokan
Akhir
Gambar 4.4 Flowchart Fuzzy String Matching
73
4.3.1.4 Proses Normalisasi (Fuzzy String Matching) Mulai
Ambil Nama
For ( i=0;i<stringNama ;i++)
Tb. Peserta 1&2
Replace (substr, pengganti, Stringnama)
Ambil 2 karakter String Nama Substr(nama, i, 2) Ya
Translasi
Ambil karakter translasi (Select karakter from Transalasi)
If substr(karakter= karakter translasi)
Tidak
Selesai
Gambar 4.5 Flowchart Normalisasi String Nama
74
4.3.2. Perancangan Database Spesifikasi file table database pada sistem penerapan algoritma string matching memiliki rancangan sebagai berikut: 1. Rancangan Database BPS a. Pada rancangan table berikut merupakan data file (field—field) yang berasal langsung dari database asli badan pengkajian statistik (BPS). Nama File
: peserta 1
Akronim
: db1 Tabel 4.2 Struktur File BPS
No.
Nama Field Tipe Data
Panjang
Keterangan
11.
ID
Varchar
11
3
Nomor identitas
42.
Kdprop
Varchar
2
5
Kode propinsi
63.
Nmprop
Varchar
50
7
Nama propinsi
84.
Kdkabu
Varchar
2
9
Kode kabupaten
10 5.
Nmkabu
Varchar
50
11
Nama kabupaten
12 6.
Kdkeca
Varchar
3
13
Kode kecamatan
14 7.
Nmkeca
Varchar
50
15
Nama kecamatan
16 8.
Kdkelr
Varchar
3
17
Kode kelurahan
18 9.
Nmkelr
Varchar
50
19
Nama desa
20 10.
Alamat
Varchar
50
Alamat
21 11.
Noart
Varchar
2
Nomor anggota rumah tangga
22 12.
Nokip2
Varchar
2
Nomor urut
2
75
23 13.
Namaart
Varchar
50
Nama anggota rumah tangga
24 14.
Jnskel
Varchar
1
Jenis kelamin
25 15.
Umur
Varchar
2
Umur
26 16.
Blnlahir
Varchar
2
Bulan lahir
27 17.
Thnlahir
Varchar
2
Tahun lahir
28 18.
Jmlkel
Double
Jumlah keluarga
29 19.
Jmlart
Double
Jumlah anggota keluarga
b. File translasi merupakan table file yang akan digunakan dalam fungsi normalisasi nama. File translasi berasal dari suatu proses transalsi Qgram maupun eliminasi duplikasi karakter yang merupakan lingkup dari proses nomalisasi string nama. Nama File
: Translasi
Akronim
: Translasi Tabel 4.3 Struktur File Translasi Db 1
No.
Nama Field
Tipe Data
Panjang
Keterangan
1.
Karakter
Varchar
2
Urutan Karakter
2.
Perubahan
Varchar
2
Hasil Translasi Q-gram
c. Tabel normalisasi merupakan tabel rancangan yang didapatkan dari pembentukan fungsi nama yang telah dinormalisasi pada proses normalisasi string. Tabel ini akan berfungsi dalam penerapan algoritma
76
fuzzy string matching (Inexact String Matching) pada komparasi data untuk mendapatkan kecocokan data kepesertaan. Nama File
: tabel normalisasi 1
Akronim
: dbs_norm Tabel 4.4 Struktur File Normalisasi Db1
No.
Nama Field
Tipe Data
Panjang
Keterangan
301.
ID
Varchar
11
32
Nomor identitas
332.
Kdprop
Varchar
2
34
Kode propinsi
353.
Nmprop
Varchar
50
36
Nama propinsi
374.
Kdkabu
Varchar
2
38
Kode kabupaten
395.
Nmkabu
Varchar
50
40
Nama kabupaten
416.
Kdkeca
Varchar
3
42
Kode kecamatan
437.
Nmkeca
Varchar
50
44
Nama kecamatan
458.
Kdkelr
Varchar
3
46
Kode kelurahan
479.
Nmkelr
Varchar
50
48
Nama desa
4910. Alamat
Varchar
50
Alamat
5011. Noart
Varchar
2
Nomor anggota rumah tangga
5112. Nokip2
Varchar
2
Nomor urut
5213. Namaart
Varchar
50
Nama anggota rumah tangga
5314. Jnskel
Varchar
1
Jenis kelamin
5415. Umur
Varchar
2
Umur
31
77
5516. Blnlahir
Varchar
2
Bulan lahir
5617. Thnlahir
Varchar
2
Tahun lahir
5718. Jmlkel
Double
Jumlah keluarga
5819. Jmlart
Double
Jumlah anggota keluarga
2. Rancangan Database ASKES a. Pada rancangan tabel berikut merupakan data file (field—field) yang berasal langsung dari database asli Asuransi Kesehatan (ASKES). Nama File
: peserta 2
Akronim
: db2 Tabel 4.5 Struktur File Peserta Askes
No.
Nama Field
Tipe Data
Panjang
1.
Dpsnoka
Varchar
13
Nomor kartu data peserta
2.
Nokk
Varchar
30
Nomor kartu keluarga
Nopen
Varchar
25
Nomor kependudukan
4.
Nosin
Varchar
25
Nomor induk peserta
5.
Pendaftar
Varchar
30
Nomor surat keluar
6.
Kdjnskpst
Varchar
2
Kode jenis kepesertaan
7.
Kdjnsnip
Varchar
1
Kode jenis nomor induk
8.
Kddesa
Varchar
5
Kode desa
9.
Kdkc
Varchar
4
Kode kecamatan
10. Kdkantor
Varchar
12
Kode kantor
11. Dpskddati2
Varchar
4
Kode dati 2 peserta
3.
Keterangan
78
12. Dpskdkec
Varchar
4
Kode kecamatan peserta
13. Dpsnm
Varchar
50
Nama peserta
14. Umur
Varchar
50
Tempat lahir peserta
15. Dpstlglhr
Varchar
1
Tanggal lahir peserta
16. Dpsjk
Varchar
12
Jenis kelamin peserta
17. Dpsstskwn
Varchar
3
Status kawin
18. Dpsgol
Varchar
9
Golongan peserta
19. Dpsgaji
Varchar
9
Gaji peserta
20. Dpsiuran
Double
50
Iuran peserta
21. Dpsjln
Double
7
Alamat peserta
22. Dpskdpos
Varchar
5
Kode pos alamat peserta
23. Dpsnotlp
Varchar
12
Nomor telepon peserta
24. Dpsjmlis
Varchar
1
Jumlah istri peserta
25. Dpsjmla
Varchar
1
Jumlah anak peserta
26. Dpskdmut
Varchar
2
Tanggal mutasi peserta
27. Dpsstskrm
Bit
1
Status kirim peserta
28. Dpstglctk
Datetime
Tanggal cetak kartu
29. Dpstglver
Datetime
Tangal verifikasi peserta
30. Dpsveroleh
Varchar
50
Nama verifikator
31. Dpsnipveroleh
Varchar
11
Nomor induk verifikator
32. Dpsentryoleh
Varchar
50
Nama petugas entry data
33. Dpsmsblaku
Datetime
Masa berlaku kepesertaan
34. Dpstgltrm
Datetime
Tanggal terima peserta
35. Dpsstatus
Varchar
1
Status peserta
36. Dpsgolis
Varchar
3
Golongan istri peserta
37. Dpsaktif
Bit
1
Keaktifan peserta
79
38. Kdtangungan
Varchar
3
Kode tangungan
39. Sws_id
Integer
11
Nomor id urut
b. File translasi merupakan table file yang akan digunakan dalam fungsi normalisasi nama. File transalasi berasal dari suatu proses transalsi Qgram maupun eliminasi duplikasi karakter yang merupakan lingkup dari proses nomalisasi string nama. Nama File
: Translasi
Akronim
: Translasi Tabel 4.6 Struktur File Translasi Db2
No.
Nama Field
Tipe Data
Panjang
Keterangan
1.
Karakter
Varchar
2
Urutan Karakter
2.
Perubahan
Varchar
2
Hasil Translasi Q-gram
c. Tabel normalisasi merupakan tabel rancangan yang didapatkan dari pembentukan fungsi nama yang telah dinormalisasi pada proses normalisasi string. Tabel ini akan berfungsi dalam penerapan algoritma fuzzy string matching (Inexact String Matching) pada komparasi data untuk mendapatkan kecocokan data kepesertaan. Nama File
: table normalisasi 2
Akronim
: db2_norm
80
Tabel 4.7 Struktur File Normalisasi Db2 No.
Nama Field
Tipe Data Panjang
1.
Dpsnoka
Varchar
13
Nomor kartu data peserta
2.
Nokk
Varchar
30
Nomor kartu keluarga
Nopen
Varchar
25
Nomor kependudukan
4.
Nosin
Varchar
25
Nomor induk peserta
5.
Pendaftar
Varchar
30
Nomor surat keluar
6.
Kdjnskpst
Varchar
2
Kode jenis kepesertaan
7.
Kdjnsnip
Varchar
1
Kode jenis nomor induk
8.
Kddesa
Varchar
5
Kode desa
9.
Kdkc
Varchar
4
Kode kecamatan
10. Kdkantor
Varchar
12
Kode kantor
11. Dpskddati2
Varchar
4
Kode dati 2 peserta
12. Dpskdkec
Varchar
4
Kode kecamatan peserta
13. Dpsnm
Varchar
50
Nama peserta
14. Umur
Varchar
50
Tempat lahir peserta
15. Dpstlglhr
Varchar
1
Tanggal lahir peserta
16. Dpsjk
Varchar
12
Jenis kelamin peserta
17. Dpsstskwn
Varchar
3
Status kawin
18. Dpsgol
Varchar
9
Golongan peserta
19. Dpsgaji
Varchar
9
Gaji peserta
20. Dpsiuran
Double
50
Iuran peserta
21. Dpsjln
Double
7
Alamat peserta
22. Dpskdpos
Varchar
5
Kode pos alamat peserta
23. Dpsnotlp
Varchar
12
Nomor telepon peserta
3.
Keterangan
81
24. Dpsjmlis
Varchar
1
Jumlah istri peserta
25. Dpsjmla
Varchar
1
Jumlah anak peserta
26. Dpskdmut
Varchar
2
Tanggal mutasi peserta
27. Dpsstskrm
Bit
1
Status kirim peserta
28. Dpstglctk
Datetime
Tanggal cetak kartu
29. Dpstglver
Datetime
Tangal verifikasi peserta
30. Dpsveroleh
Varchar
50
Nama verifikator
31. Dpsnipveroleh
Varchar
11
Nomor induk verifikator
32. Dpsentryoleh
Varchar
50
Nama petugas entry data
33. Dpsmsblaku
Datetime
Masa berlaku kepesertaan
34. Dpstgltrm
Datetime
Tanggal terima peserta
35. Dpsstatus
Varchar
1
Status peserta
36. Dpsgolis
Varchar
3
Golongan istri peserta
37. Dpsaktif
Bit
1
Keaktifan peserta
38. Kdtangungan
Varchar
3
Kode tangungan
39. Sws_id
Integer
11
Nomor id urut
Dari gambaran struktur data antar kedua database diatas maka dapat dibandingkan bahwa kedua database tersebut memiliki suatu struktur data nama field dan jumlah isi field yang berbeda. Sehingga diperlukan suatu ketetapan untuk menentukan kesamaan isi field dengan melihat kesamaan arti field pada nama field yang berbeda yang dimiliki kedua database sehingga memudahkan dalam pencarian kecocokan string antar kedua database.
82
Kecocokan isi field antar kedua database : Table 4.8 Kecocokan Field Kedua Database Pernyataan
Nama Jenis Kelamin
Definisi Database BPS
Database Askes
Nama Peserta
Nama Peserta
1. Laki-laki (1)
L = laki-laki P = Perempuan
2. Perempuan (2) Umur
Umur
Umur
Alamat
Nama kecamatan
Alamat
Kabupaten
Bangka,Bangka
0108 (Bangka, Bangka
tengah,Bangka
tengah,
Barat, dan Belitung
dan 0109 (Belitung)
Bangka
barat)
Kecocokan isi field database inipun yang kemudian dapat dimanfaatkan sebagai suatu field-field yang menyatukan kesamaan pencarian untuk mendapatkan kecocokan data antar kedua database. Dengan adanya nama sebagai salah satu field yang memiliki kecocokan pada masing-masing database, maka kemudian nama peserta dijadikan hal yang utama dalam
83
analisis dan penerapan pencocokan string dalam komparasi data kepesertaan ini. Hal ini dikarenakan field nama sebagai suatu identitas peserta merupakan field yang perlu dianalisa tingkat variasinya.
4.3.3. Rancangan Interface Sistem Berikut merupakan rancangan antarmuka dari system penarapan algoritma string matching dalam komparasi data kepesertaan.
Database Utama
Database 1
Jenis Kelamin
Umur Alamat Kabupaten Exact
Gambar 4.6 Rancangan Tampilan Exact String Matching
84
Database Utama
Database 1
Jenis Kelamin
Umur Alamat Kabupaten Fuzzy
Gambar 4.7 Rancangan Tampilan Inexact String Matching 4.4.
Fase Konstruksi Hal yang dilakukan dalam fase konstruksi ini yakni membangun suatu aplikasi yang mampu menyelesaikan permasalahan sesuai dengan metode string matching yang diacu maupun sesuai dengan rancangan yang telah disusun dalam fase sebelumnya dengan cara pengkodean. Adapun dalam mengontruksi aplikasi yang hendak dibuat penulis manggunakan integrasi antara bahasa pemrograman PHP dan MySQL (database program). Sesuai dengan rancangan tampilan form terdapat item objek yang digunakan dalam sistem penerapan algoritma string matching:
85
1. Checkbox Kotak cek merupakan item komponen form yang berguna untuk melakukan pemilihan pada satu atau lebih pernyataan dari beberapa pernyataan yang disediakan. Pernyataan-pernyataan yang disediakan pada sistem ini merupakan field-field table pada masing-masing database yang teridentifikasi dapat dijadikan sebagai suatu acuan atau parameter tambahan untuk
mendapatkan kecocokan
dalam komparasi
data
kepesertaan (Table 4.7 Kecocokan Field Kedua Database). 2. Combo box Kotak kombo (drop-down) atau daftar pilihan merupakan objek form yang dimanfaatkan untuk menampilkan daftar pilihan. Pilihan (combo box) pada sistem ini merupakan pilihan yang disediakan untuk memilih item database yang digunakan untuk memilih database utama sebagai referensi pencocokan, yang mana terdapat pilihan database 1 sebagai database yang berasal dari BPS dan Database 2 sebagai database yang berasal dari ASKES. 3. Submit Button Tombol submit merupakan tombol yang berguna untuk mengirimkan semua variable data pada komponen-komponen form yang ada. Variablevariabel data pada komponen form yang dikirimkan merupakan variable yang didapatkan dari nilai komponen-komponen combo box maupun check box.
86
Hal awal yang dilakukan dalam mengonstruksi system guna menerapkan algoritma fuzzy string matching ini yakni membuat suatu table hasil normalisasi pada masing-masing database dari bentuk string data nama orang sesuai dengan fungsi normalisasi berikut : function normalisasi (Stringnama){ $anama_asli= Stringnama; for($i =0; $i < panjangStringnama-1; $i++) {bagian = substr(Stringnama,$i,2); bagian= addslashes(bagian); dum = mysql_query("mengambil bagian database yang sesuai dengan urutan karakter pada table translasi'"); if ( dum != 0) { Char = ArrayChar; Stringnama =str_replace(bagian,Char,Stringnama); } bagian= stripslashes(bagian); } return strtoupper(Stringnama); } Hasil dari fungsi normalisasi inilah yang kemudian akan menjadi suatu tabel nama yang telah memiliki bentuk normal dari suatu nama orang dan
87
digunakan sebagai acuan data nama untuk perbandingan data guna mencari kecocokan data antar kedua database dalam fuzzy string matching.
4.5.
Implementasi
4.5.1. Pengenalan System 1. Tampilan Form Exact
Gambar 4.8 Form Masukan Exact 2. Tampilan Form Inexact (Fuzzy)
Gambar 4.9 Form Masukan Inexact
88
3. Tampilan Output Hasil Kecocokan
Gambar 4.10 Tampilan Output Kecocokan
4.5.2. Pengujian Sistem Pengujian sistem merupakan proses mengesekusi sistem perangkat lunak untuk menentukan apakah sistem perangkat lunak tersebut cocok dengan spesifikasi sistem dan berjalan sesuai dengan lingkungan yang diinginkan. Dalam menguji sistem penerapan algoritma string matching ini penulis mengunakan metode pengujian black box untuk menguji seberapa jauh sistem ini telah memenuhi berbagai hal yang telah dilalui dalam proses tahap pengembangan sistem sebelumnya. Pengujian yang dilakukan dalam sistem penerapan algoritma string matching komparasi data kepesertaan merupakan pengujian terhadap database 1 (database BPS) yang memiliki jumlah record sebesar 45.572 data peserta dan database 2 (database ASKES) yang memiliki jumlah record sebesar 45.957 data peserta.
89
Tahap awal dalam menguji sistem dilakukan dengan memilih database 1 sebagai database utama dan memilih field jenis kelamin, dan umur sebagai parameter kecocokan data.
Gambar 4.11 Uji 1 Dari form inputan gambar 4.11 uji 1 dihasilkan form table output sebagai berikut :
Gambar 4.12 Hasil Uji 1
90
Pengujian ke-2 dilakukan dengan memilih database 1 sebagai database utama dan memilih field jenis kelamin, umur, dan alamat sebagai parameter kecocokan data.
Gambar 4.13 Uji 2 Dari form inputan gambar 4.13 Uji 2 dihasilkan form table output sebagai berikut :
Gambar 4.14 Hasil Uji 2
91
Pengujian ke-3 dilakukan dengan memilih database 1 sebagai database utama dan memilih field jenis kelamin, umur, alamat, dan kebupaten sebagai parameter kecocokan data.
Gambar 4.15 Uji 3 Dari form inputan gambar 4.15 uji 3 dihasilkan form table output sebagai berikut :
Gambar 4.16 Hasil Uji 3
92
Pengujian ke-4 dilakukan dengan memilih database 1 sebagai database utama dan memilih field jenis kelamin dan umur sebagai parameter kecocokan data.
Gambar 4.17 Uji 4 Dari form inputan gambar 4.17 uji 4 dihasilkan form table output sebagai berikut :
Gambar 4.18 Uji 4
93
Pengujian ke-5 dilakukan dengan memilih database 1 sebagai database utama dan memilih field jenis kelamin, umur, dan alamat sebagai parameter kecocokan data.
Gambar 4.19 Uji 5 Dari form inputan gambar 4.19 uji 5 dihasilkan form table output sebagai berikut :
Gambar 4.20 Hasil Uji 5
94
Pengujian ke-6 dilakukan dengan memilih database 1 sebagai database utama dan memilih field jenis kelamin, umur, alamat, dan kebupaten sebagai parameter kecocokan data.
Gambar 4.21 Uji 6 Dari form inputan gambar 4.21 uji 6 dihasilkan form table output sebagai berikut :
Gambar 4.22 Hasil Uji 6
95
Pengujian ke-7 dilakukan dengan memilih database 2 sebagai database utama dan memilih field jenis kelamin, dan umur sebagai parameter kecocokan data.
Gambar 4.23 Uji 7 Dari form inputan gambar 4.23 uji 7 dihasilkan form table output sebagai berikut :
Gambar 4.24 Hasil Uji 7
96
Pengujian ke-8 dilakukan dengan memilih database 2 sebagai database utama dan memilih field jenis kelamin, umur, dan alamat sebagai parameter kecocokan data.
Gambar 4.25 Uji 8 Dari form inputan gambar 4.25 uji 8 dihasilkan form table output sebagai berikut :
Gambar 4.26 Hasil Uji 8
97
Pengujian ke-9 dilakukan dengan memilih database 2 sebagai database utama dan memilih field jenis kelamin, umur, alamat, dan kebupaten sebagai parameter kecocokan data.
Gambar 4.27 Uji 9 Dari form inputan gambar 4.27 uji 9 dihasilkan form table output sebagai berikut :
Gambar 4.28 Hasil Uji 9
98
Pengujian ke-10 dilakukan dengan memilih database 2 sebagai database utama dan memilih field jenis kelamin, dan umur sebagai parameter kecocokan data.
Gambar 4.29 Uji 10 Dari form inputan gambar 4.29 uji 10 dihasilkan form table output sebagai berikut :
Gambar 4.30 Hasil Uji 10
99
Pengujian ke-11 dilakukan dengan memilih database 2 sebagai database utama dan memilih field jenis kelamin, umur, dan alamat sebagai parameter kecocokan data.
Gambar 4.31 Uji 11 Dari form inputan gambar 4.31 uji 11 dihasilkan form table output sebagai berikut :
Gambar 4.32 Hasil Uji 11
100
Pengujian ke-12 dilakukan dengan memilih database 2 sebagai database utama dan memilih field jenis kelamin, umur, alamat, dan kebupaten sebagai parameter kecocokan data.
Gambar 4.33 Uji 12 Dari form inputan gambar 4.33 uji 12 dihasilkan form table output sebagai berikut :
Gambar 4.34 Hasil Uji 12
101
Waktu yang dihasilkan sistem dalam hasil penerapan string matching yang tertera pada hasil output sistem merupakan hasil penghitungan fungsi waktu yang mana fungsi ini akan diletakkan pada awal maupun akhir dari kode pencocokan, dengan rumusan fungsi sebagai berikut: list($usec, $sec)=explode(' ',microtime()); $awal=((int)$usec+ (int) $sec);
Dengan demikian pengujian pada sistem penerapan algoritma string matching komprasi data kepesertaan menghasilkan akurasi kecocokan data antar kedua database dengan rumusan sebagai berikut : Jumlah Kecocokan Data Presentasi Kecocokan =
X 100% Jumlah Record Database Utama
Adapun berikut ini adalah dua belas hasil pengujian yang didapatkan dari sistem penerapan string matching komparasi data kepesertaan untuk mendapatkan nilai kecocokan data :
102
Table 4.9 Hasil Uji String Matching Parameter Kecocokan
Database 45.572 record
1
Databas e
2
45.957 record
Jenis Kelamin
√
√
√
√
√
√
Umur
√
√
√
√
√
√
Alamat
√
√
√
√
Kabupaten
√
√
Exact
Waktu(m)
3939.20
3669.5
3512.00
2385.91
2283.86
1988.69
Matching
Kecocokan
6
28
3903
8
8
3903
Akurasi (%)
0.013
0.061
8.56
0.017
0.017
8.49
Fuzzy
Waktu (m)
3452.02
3445.98
3413.69
2407.00
2430.35
2221.23
Matching
Kecocokan
6
28
4073
8
8
4072
Akurasi (%)
0.013
0.061
8.93
0.017
0.017
8.86
Dari table hasil pengujian terlihat bahwa penerapan exact string matching dan fuzzy string matching mendapatkan jumlah kecocokan data yang tidak sama besar pada pemilihan data field jenis kelamin dan umur namun sama besar saat menambah alamat dan kabupaten sebagai field yang dipilih sebagai
103
ukuran kecocokan dalam komparasi data peserta. Ukuran kecocokan field merupakan suatu hal yang mempengaruhi nilai keakuratan kecocokan data peserta, sehingga dalam penerapan string matching yang dilakukan menunjukan bahwa semakin banyaknya ukuran kecocokan yang dipilih maka jumlah kecocokan yang dimiliki antar kedua database semakin rendah dan semakin lama waktu yang dibutuhkan dalam pencocokan. Namun dengan sedikitnya ukuran kecocokan yang dipilih maka jumlah kecocokan yang dimiliki antar kedua database semakin tinggi dan semakin cepat waktu yang dibutuhkan dalam pencocokan.
BAB V KESIMPULAN
Pada bagian ini penulis ingin menjelaskan mengenai kesimpulan yang didapatkan selama pengerjaan tugas akhir ini. Selain itu, penulis juga memberikan saran-saran yang mungkin dapat diterapkan dalam penelitian selanjutnya yang tentu saja berkaitan dengan topik yang penulis lakukan.
5.1.
Kesimpulan Berdasarkan hasil pengujian serta penjelasan pada bab-bab sebelumnya, maka dapat disimpulkan bahwa : 1. Dalam penerapan algoritma string matching komparasi data kepesertaan dihasilkan bahwa dalam mencocokan perbedaan-perbedaan yang terdapat pada kedua database ini maka diperlukan field-field kecocokan yang ada pada masing-masing database sebagai suatu ukuran kecocokan data peserta. Field-field tersebut adalah jenis kelamin, umur, alamat serta kabupaten. 2. Dalam penerapan algoritma string matching analisis data penamaan didapatkan : a. Exact string matching Berdasarkan penerapan algoritma exact string matching pada pencocokan string data kepesertaan ini dapat disimpulkan bahwa
104
105
algoritma ini hanya mencocokan nama yang sama persis dengan nama yang dikomparasikan algoritma ini belum mampu untuk menangani: 1. Adanya bentuk variasi dari suatu nama. 2. Adanya kemungkinan variasi bentuk penulisan nama dari satu nama orang. 3. Kemungkinan ada karakter didalam string atau teks yang mungkin di tambahkan, diganti, atau dihilangkan. b. Fuzzy string matching Dengan menggunakan algoritma fuzzy string matching (approximate string matching) maka dapat disimpulkan algoritma ini mampu mencocokan bentuk nama peserta yang sama persis maupun mirip dengan nama yang dikomparasikan, dengan cara mencari bentuk normal dari nama orang (peserta) melalui proses normalisasi q-gram. 3. Hasil pengujian untuk jumlah kesesuain (kecocokan) data menunjukkan bahwa semakin banyaknya ukuran kecocokan yang dipilih maka jumlah kecocokan yang dimiliki antar kedua database semakin rendah dan semakin lama waktu yang dibutuhkan dalam pencocokan. Namun dengan sedikitnya ukuran kecocokan yang dipilih maka jumlah kecocokan yang dimiliki antar kedua database semakin tinggi dan semakin cepat waktu yang dibutuhkan dalam pencocokan. Ukuran kecocokan field merupakan suatu nilai keakuratan kecocokan data peserta.
106
5.2.
Saran Berikut adalah beberapa saran yang dimaksudkan dengan tujuan agar penerapan algoritma string matching komparasi data kepesertaan ini nantinya
bisa menjadi lebih baik lagi, yaitu: 1. Perlu adanya suatu analisa sebaran nama yang besar dan mendalam terkait bentuk penulisan nama orang yang bervariasi serta urutan karakter (Qgram)
sehingga
berpengaruh
terhadap
proses
normalisasi
untuk
menghasilkan bentuk penamaan orang (peserta) yang normal dalam penerapan approximate string matching. 2. Memperluas analisa penerapan fuzzy string matching menggunakan phonetic string matching.
DAFTAR PUSTAKA
Al-Fatta, Hanif. 2007. Analisis dan Perancangan Sistem Informasi untuk Keunggulan Bersaing Perusahaan dan Organisasi Modern. Yogyakarta: ANDI. Bernardino Madaharsa Dito Adiwidya (2009). Algoritma levensthein dalam pendekatan approximate string matching. Bandung : Teknik Informatika-Institut Teknologi Bandung (ITB). Charras, Christian., et al. 1997. Handbook of Exact String Matching Algorithms. Oxford University Press. Dadone, Paolo. 2001. Design Optimazation of Fuzzy Logic Systems. Virginia : Virginia Polytehnic Institute and State University. Damerau. 1964. A Technique for Computer Detection and Correction of Spelling Errors. Communications of the ACM 7 Dewanto R A, Aradea. Aplikasi SMS Gateway dengan Koreksi Kesalahan Menggunakan Fuzzy String Matching. Tasikmalaya : Universitas Siliwangi. Endang Hastriana (2010). Perbandingan algoritma string matching knuth morris-pratt dengan boyer moore horspool pada simulasi pengenalan sidik jari. , Jakarta : Teknik Informatika-Universitas Islam Negeri Syarif Hidayatullah.
107
108
Govindaraju, Rajesri. 2006. Pengembangan Sistem Informasi. Diakses pada 3 Desember 2010 dari http://www.ti.itb.ac.id/MSI .ppt Jogiyanto.HM. 2001. Analisis dan Desain. Yogyakarta : ANDI. Karhendana, Arie., dkk. 2002. Normalisasi String untuk Optimasi Phonetic String Matching dalam Bahasa Indonesia. Bandung : Institut Teknologi Bandung. Kendall K.E, dan Kendall, J.E. 2007. Analisis dan Perancangan Sistem. Klaten : Indeks. Knuth, Donald.E., et al. 1977. Fast Pattern Matching in Strings. (IAN) Journal on Computing. Knuth, Donald.E, et al. 1973. Fundamental of Algorithms, Volume 1 of The Art of Computer Programming. Addison-Wesley. Kusumadewi, dan Purnomo Hari. 2004. Aplikasi Logika Fuzzy untuk Pendukung Keputusan. Yogyakarta : Graha Ilmu. Ladjamudin, Al Bahra. 2005. Analisis dan Desain Sistem Informasi. Yogyakarta : Graha Ilmu. Mulyadi. 2001. Sistem Akuntansi. Jakarta : Salemba Empat. Nazir , Mohammmad. 2003. Metode Penelitian. Jakarta : ghalia Indonesia Pressman, Roger S., et all. 1997. Software Engineering (A Practitional Approach). McGraw-Hill.
109
Purwanindita, Alin Kurniawan., et all. String Matching Algorithm. Bandung : STT Telkom. Purwanto, Eko budi. 2008. Perancangan dan Analisis Algoritma. Yogyakarta : Graha Ilmu. Sagita, Anggy., dkk. 2006. Analisa Algoritma Pencocokan String. Bandung : Sekolah Tinggi Teknologi Telkom. Santosa, P. Insap. Ir. 2004. Interaksi Manusia dan Komputer. Jakarta : Andi Offset. Sedgewick, Robert. 1984. Algorithms. USA : Addison-Wesley. Sommerville, ian, 2003, Software Engineering edisi ke-6 jilid 2. Jakarta : Erlangga. Suarga. 2004. Algoritma Pemrograman. Yogyakarta : ANDI. Supardi (2009). Analisis penerapan string matching pada aplikasi pencarian berkas di komputer. Jakarta : Teknik InformatikaUniversitas Islam Negeri Syarif Hidayatullah. Syaroni, Mokhamad, dan Munir, Rinaldi. 2004. Pencocokan String Berdasarkan Kemiripan Ucapan (Phonetic String Matching) dalam Bahasa Inggris. Bandung : Institut Teknologi Bandung (ITB). Wahid. 2004. Dasar- dasar Algoritma dan Pemrograman. Yogyakarta : ANDI.
ANALISIS PENERAPAN STRING MATCHING DALAM KOMPARASI DATA KEPESERTAAN JAMINAN KESEHATAN MASYARAKAT (JAMKESMAS)
Skripsi Diajukan untuk Memenuhi Persyaratan Memperoleh Gelar Sarjana Komputer (S.Kom)
Oleh: SRI WULAN NIM : 206091004077
PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2011
i
ANALISIS PENERAPAN STRING MATCHING DALAM KOMPARASI DATA KEPESERTAAN JAMINAN KESEHATAN MASYARAKAT (JAMKESMAS)
Skripsi Sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Komputer Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta
Oleh : SRI WULAN NIM. 206091004077
Menyetujui, Pembimbing I,
Pembimbing II,
Fitri Mintarsih, M.Kom
Khodijah Hulliyah, M.Si
NIP. 197312092005011002
NIP. 197304022001122001
Mengetahui, Ketua Program Studi Teknik Informatika
Yusuf Durachman, M.Sc NIP.197105222006041002
ii
ANALISIS PENERAPAN STRING MATCHING DALAM KOMPARASI DATA KEPESERTAAN JAMINAN KESEHATAN MASYARAKAT (JAMKESMAS)
Skripsi Sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Komputer Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta
Oleh : SRI WULAN NIM. 206091004077
PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2011
iii
PERNYATAAN
DENGAN INI SAYA MENYATAKAN BAHWA SKRIPSI INI BENARBENAR HASIL KARYA SENDIRI YANG BELUM PERNAH DIAJUKAN SEBAGAI SKRIPSI ATAU KARYA ILMIAH PADA PERGURUAN TINGGI ATAU LEMBAGA MANAPUN.
Jakarta, Maret 2011
Sri Wulan L (206091004077)
iv
LEMBAR PERSEMBAHAN
Tugas akhir (Skripsi) ini sengaja penulis persembahkan teruntuk : 1. Otak, pikiran, jiwa dan organ-organ yang ada dalam tubuh dan diri ini. Selamat atas kerja kerasnya. Ingatlah bahwa tak akan berhenti kita hingga kita melangkah ke jannah-Nya karna hidup ini bukan untuk hidup, hidup juga bukan untuk mati, tapi hidup untuk yang Maha Hidup. 2. Kedua orang tua (Bapak dan Mama). Terima kasih atas kasih sayang, perhatian, kecemasan serta berbagai hal yang tak terhitung hingga yang tak pantas untuk dihitung. Hanya jannah-Nya lah balasan yang layak untuk keduanya. Amieen.
v
KATA PENGANTAR Alhamdulillahirabbil’alamin. Segala puji bagi Allah SWT atas segala rahmat dan karunia-Nya dalam memberikan jalan dan kemudahan kepada penulis hingga tugas akhir ini dapat terselesaikan dengan baik. Shalawat dan salam memang pantas tercurah kepada Nabi Muhammad SAW, keluarga, serta para sahabatsahabatnya yang menjadi panutan dan inspirasi bagi penulis.
Dalam hal ini, penulis mencoba untuk melakukan suatu penelitian dengan topik judul ”Analisis Penerapan String Matching dalam Komparasi Data Kepesertaan Jaminan Kesehatan (JAMKESMAS)”. Topik ini merupakan tugas akhir yang diambil penulis guna memenuhi syarat untuk memperoleh gelar Sarjana Komputer (S.Kom) Teknik Informatika Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta.
Adapun dalam penyelesaian tugas akhir ini, penulis ingin menyampaikan terima kasih sebesar-besarnya kepada pihak-pihak yang telah membantu dalam penyelesaian pembuatan aplikasi dan penyusunan tugas akhir, antara lain kepada yang terhormat : 1. Bapak DR. Syopiansyah Jaya Putra, M.Sis selaku Dekan Fakultas Sains dan Teknologi yang telah memberikan suatu komitmen, dorongan, dan program pendidikan sesuai kebutuhan mahasiswanya. 2. Bapak Yusuf Durachman, M.sc selaku Ketua Jurusan yang telah memberikan peran sesuai dengan fungsinya dalam membimbing serta memberikan ruang ilmu bagi penulis.
vi
3. Ibu Fitri Mintarsih, M.Kom selaku Dosen Pembimbing 1 dan Ibu Khodijah Hulliyah, M.Si selaku Dosen Pembimbing 2 yang telah memberikan bimbingan dan dukungan baik secara moril maupun teknis. 4. Bapak Swasetyo Yulianto selaku Dosen Pembimbing Lapangan yang telah memberikan bimbingan, masukan, serta berbagi ilmu pengetahuan dalam penyusunan sehingga penulis dapat menyelesaikan tugas akhir ini. 5. Seluruh anggota keluarga tercinta yang senantiasa mendoakan dan memberikan dukungan selama menjalankan masa perkuliahan. 6. Rekan-rekan seperjuangan, teman–teman Software Enginering dan seluruh kawan-kawan jurusan Teknik Informatika yang memberikan motivasi serta informasi kepada penulis. Mari kita sukses bersama. 7. Seluruh pihak yang telah membantu dan namanya tidak dapat disebutkan satu persatu. Terima kasih atas doa dan bimbingannya, Semoga Allah SWT membalas segala kebaikan yang telah diberikan kepada penulis.
Akhir kata, penulis memohon maaf atas berbagai hal keliru yang diperbuat selama masa penyelesaian tugas akhir ini, kritik dan saran yang membangun sangat diharapkan demi menambah pengetahuan dalam kepenulisan dan semoga tugas akhir ini dapat bermanfaat bagi pengembangan selanjutnya. Amiin
Jakarta, Maret 2011
Sri Wulan
vii
ABSTRAK
SRI WULAN. Analisis Penerapan String Matching dalam Komparasi Data Kepesertaan JAMKESMAS Dibimbing oleh : FITRI MINTARSIH, M.Kom dan KHODIJAH HULLIYAH, M.Si
Dalam pencocokan string (string matching), penggunaan algoritma yang tepat dapat memberikan hasil penelusuran yang tepat pula dan sesuai keinginan pengguna. Dalam tugas akhir ini, penulis akan menganalisa penerapan algoritma string matching yang terdiri atas inexact string matching (fuzzy string macthing) menggunakan approximate string matching (dilihat dari segi penulisan) dan exact string matching menggunakan brute force string matching pada data nama orang (peserta) jamkesmas. Data yang digunakan dalam pencocokan string dalam menerapkan algoritma string matching merupakan data yang akan dikomparasikan untuk mendapatkan kecocokan data yang berasal dari dua database. Hasil analisa fuzzy string matching dalam komparasi data kepesertaan ini akan diaplikasikan menggunakan PHP dan MySQL, dengan menggunakan fase pengembangan sistem RAD (Rapid Application Deveplopment). Hasil penerapan string matching dalam tugas akhir ini menunjukkan bahwa penerapan fuzzy string matching mampu menangani bentuk nama orang (peserta) yang bervariasi bentuk penulisannya dan exact string matching tidak mampu mencocokan data nama yang variatif bentuk kepenulisannya. Pengujian fuzzy string matching dalam komparasi data kepesertaan ini menghasilkan persentasi kecocokan data peserta yang sama besar dengan exact string matching.
Kata kunci : String Matching, Fuzzy String Matching (Approximate), Exact String Matching (Brute Force), komparasi data, dan RAD.
viii
DAFTAR ISI
Halaman HALAMAN LUAR .......................................................................................... i HALAMAN DALAM ...................................................................................... ii LEMBAR PENGESAHAN PEMBIMBING ................................................. iii LEMBAR PENGESAHAN UJIAN ................................................................ iv LEMBAR PERNYATAAN ............................................................................. v LEMBAR PERSEMBAHAN .......................................................................... vi KATA PENGANTAR ...................................................................................... vii ABSTRAK ....................................................................................................... viii DAFTAR ISI .................................................................................................... ix DAFTAR GAMBAR ......................................................................................... xiii DAFTAR TABEL ............................................................................................ xv DAFTAR ISTILAH ......................................................................................... xvi BAB I PENDAHULUAN 1.1 Latar Belakang Masalah ................................................................................. 1 1.2 Rumusan Masalah .......................................................................................... 4 1.3 Batasan Masalah ............................................................................................. 4 1.4 Metode Penelitian ........................................................................................... 5 1.5 Tujuan dan Manfaat Penelitian ...................................................................... 6 1.6 Sistematika Penulisan .................................................................................... 7
ix
BAB II LANDASAN TEORI 2.1 Konsep Algoritma ........................................................................................ 9 2.1.1 Definisi Algoritma ............................................................................. 9 2.1.2 Ciri-ciri dan Sifat Algoritma .............................................................. 10 2.2 Logika Fuzzy ................................................................................................ 14 2.3 String Matching ............................................................................................ 15 2.3.1 Definisi String Matching .................................................................... 15 2.2.2 Kerangka Kerja String Matching ....................................................... 16 2.3.3 Kerangka Pikir String Matching ........................................................ 16 2.3.3 Macam Algoritma String Matching ................................................... 18 2.4 Exact String Matching .................................................................................. 18 2.5 Inexact String Matching (Fuzzy String Matching) ...................................... 25 2.6 Karakteristik Nama ...................................................................................... 28 2.7 Normalisasi Nama ........................................................................................ 29 2.8 Sistem Basis Data ......................................................................................... 32 2.9 SQL .............................................................................................................. 33 2.10 MySQL ....................................................................................................... 34 2.11 Fungsi String MySQL ................................................................................ 35 2.12 Aplikasi ...................................................................................................... 35 2.13 Metode Pengembangan Sistem .................................................................. 34 2.13.1. Definisi Pengembangan Sistem ...................................................... 34 2.13.2. Macam-macam Metode Pengembangan Sistem ............................. 34 2.14 Unit Testing ................................................................................................ 39
x
2.15 Studi Sejenis ............................................................................................... 40
BAB III METODE PENELITIAN 3.1 Metode Pengumpulan Data .......................................................................... 44 3.2 Metode Komparatif ...................................................................................... 45 3.3 Metode Pengembangan Sistem .................................................................... 46 3.4 Alasan Penggunaan RAD ............................................................................. 48 3.5 Keunggulan dan Kelemahan RAD ............................................................... 49 BAB IV PENGEMBANGAN SISTEM 4.1 Metode Komparatif ...................................................................................... 50 4.1.1 Analisis String Matching ................................................................... 50 4.1.1.1 Exact String Matching .......................................................... 51 4.1.1.2 Normalisasi String ................................................................ 55 4.1.1.3 Inexact String Matching ........................................................ 63 4.2 Fase Perencanaan Syarat-syarat ................................................................... 68 4.2.1 Tujuan Informasi ................................................................................ 53 4.2.2 Syarat Kebutuhan/Informasi .............................................................. 53 4.3 Perancangan Sistem ..................................................................................... 67 4.3.1 Perancangan Proses ............................................................................ 67 4.3.1.1 Algoritma Exact String Matching ......................................... 67 4.3.1.2 Proses Kecocokan ................................................................. 68 4.3.1.2 Algoritma Inexact String Matching ...................................... 69 4.3.1.2 Proses Normalisasi (Fuzzy String Matching) ....................... 70
xi
4.3.2 Perancangan Database ....................................................................... 71 4.3.3 Rancangan Interface Sistem ............................................................... 86 4.4 Fase Konstruksi ............................................................................................ 87 4.5 Implementasi ................................................................................................ 90 4.4.1 Pengenalan Sistem ............................................................................. 90 4.4.1 Pengujian Sistem ................................................................................ 91 BAB IV PENUTUP 5.1 Kesimpulan ……………………………………………………………….. 104 5.2 Saran …..………………………………………………………………….. 106 DAFTAR PUSTAKA ………………………………………………………. 107 LAMPIRAN
xii
DAFTAR GAMBAR Halaman Gambar 2.1 Model Sekuensial Linier ............................................................... 39 Gambar 4.1 Proses Similarity Function ............................................................. 59 Gambar 4.2 Flowchart Exact String Matching ................................................. 66 Gambar 4.3 Flowchart Kecocokan .................................................................... 67 Gambar 4.4 Flowchart Fuzzy String Matching ................................................. 68 Gambar 4.5 Flowchart Normalisasi String Nama ............................................. 69 Gambar 4.6 Rancangan Tampilan Exact String Matching ................................ 85 Gambar 4.7 Rancangan Tampilan Inexact String Matching ............................. 86 Gambar 4.8 Form Masukan Exact .................................................................... 88 Gambar 4.9 Form Masukan Inexact .................................................................. 89 Gambar 4.10 Tampilan Output Kecocokan ...................................................... 89 Gambar 4.11 Uji 1 ............................................................................................. 90 Gambar 4.12 Hasil Uji 1 ................................................................................... 91 Gambar 4.13 Uji 2 ............................................................................................. 91 Gambar 4.14 Hasil Uji 2 ................................................................................... 92 Gambar 4.15 Uji 3 ............................................................................................. 92 Gambar 4.16 Hasil Uji 3 ................................................................................... 93 Gambar 4.17 Uji 4 ............................................................................................. 93 Gambar 4.18 Hasil Uji 4 ................................................................................... 94 Gambar 4.19 Uji 5 ............................................................................................. 94 Gambar 4.20 Hasil Uji 5 ................................................................................... 95
xiii
Gambar 4.21 Uji 6 ............................................................................................. 95 Gambar 4.22 Hasil Uji 6 ................................................................................... 96 Gambar 4.23 Uji 7 ............................................................................................. 96 Gambar 4.24 Hasil Uji 7 ................................................................................... 97 Gambar 4.25 Uji 8 ............................................................................................. 97 Gambar 4.26 Hasil Uji 8 ................................................................................... 98 Gambar 4.27 Uji 9 ............................................................................................. 98 Gambar 4.28 Hasil Uji 9 .................................................................................... 99 Gambar 4.29 Uji 10 ........................................................................................... 99 Gambar 4.30 Hasil Uji 10 ................................................................................. 100 Gambar 4.31 Uji 11 ........................................................................................... 100 Gambar 4.32 Hasil Uji 11 ................................................................................. 101 Gambar 4.33 Uji 12 ........................................................................................... 101 Gambar 4.34 Hasil Uji 12 ................................................................................. 102
xiv
DAFTAR TABEL
Halaman Table 2.1 Simbol-simbol Flowchart ................................................................... 14 Table 2.2 Damerau Variasi Nama ...................................................................... 30 Table 4.2 Contoh Variasi Penamaan .................................................................. 53 Table 4.3 Translasi Q-gram ................................................................................ 59 Table 4.4 Struktur File BPS ............................................................................... 71 Table 4.5 Struktur File Translasi Db1 ................................................................ 73 Table 4.6 Struktur File Normalisasi Db1 ........................................................... 75 Table 4.7 Struktur File Peserta Askes ................................................................ 76 Table 4.8 Struktur File Translasi Db2 ................................................................ 80 Table 4.9 Struktur File Normalisasi Db2 ........................................................... 85 Table 4.10 Kecocokan Field Kedua Database ................................................... 85 Table 4.11 Hasil Uji String Matching ................................................................ 104
DAFTAR ISTILAH
Istilah
Arti
xv
String
Suatu kumpulan karakter
Pattern
Sekumpulan string yang dicari pada teks.
Database
Suatu kumpulan data atau informasi yang kompleks dimana
data
tersebut
disusun
menjadi
beberapa
kelompok dengan tipe data yang sejenis, dimana setiap datanya saling berhubungan satu sama lain atau dapat berdiri sendiri, sehingga mudah diakses. Boolean
Segala hal dapat diekspresikan dalam istilah binary (0 atau 1, hitam atau putih, ya atau tidak),
Fuzzy Logic
Pendekatan yang membantu dalam menjelaskan ketidakpastian batas antara satu kriteria dengan kriteria lainnya, yang disebabkan oleh adanya penilaian manusia terhadap sesuatu secara kumulatif.
xvi
