BAB II LANDASAN TEORI
Pada bab ini akan dijelaskan lebih lanjut mengenai hal-hal yang diperlukan untuk pembuatan aplikasi ini. Komponen-komponen tersebut meliputi penjelasan mengenai konsep dasar approximate string matching, algoritma SoundEx, algoritma JaroWinkler, dan metodologi rekayasa perangkat lunak yang akan digunakan.
2.1 PENCOCOKAN STRING (STRING MATCHING)
2.1.1 Pengertian pencocokan string
String menurut Dictionary of Algorithms and Data Structures adalah susunan dari karakter-karakter
(angka,
alfabet
atau
karakter
yang
lain)
dan
biasanya
direpresentasikan sebagai struktur data array. String dapat berupa kata, frase, atau kalimat (National Institute of Standards and Technology n.d.). Sedangkan pencocokan string (string matching) diartikan sebagai sebuah permasalahan untuk menemukan pola susunan karakter string di dalam string lain atau bagian dari isi teks.
10
11
2.1.2 Klasifikasi pencocokan string
Pencocokan string (string matching) secara garis besar dapat dibedakan menjadi dua (Binstock and Rex 1995) yaitu: 1. Exact string matching, merupakan pencocokan string secara tepat dengan susunan karakter dalam string yang dicocokkan memiliki jumlah maupun urutan karakter dalam string yang sama. Contoh: kata ahmad akan menunjukkan kecocokan hanya dengan kata ahmad. 2. Approximate string matching, merupakan pencocokan string berdasarkan kemiripannya. Sebuah string bisa jadi memiliki susunan karakter yang berbeda (mungkin jumlah atau urutannya) dengan string lain namun memiliki kemiripan, misalnya: kemiripan secara penulisan, atau kemiripan bunyi pengucapan.
2.1.3 Phonetic string matching
Phonetic adalah ilmu yang menyelidiki bunyi bahasa tanpa melihat fungsi bunyi itu sebagai pembeda makna dalam suatu bahasa (Syaroni dan Munir 2005). Klasifikasi konsonan memegang peranan penting dalam phonetic string matching. Misalnya, konsonan ‘b’ dan ‘p’ dianggap mirip karena keduanya diartikulasi oleh dua bibir. Kemiripan bunyi pengucapan dua buah teks dapat diukur berdasarkan penggunaan konsonan yang terdapat pada teks tersebut. Kedua buah teks tersebut selanjutnya akan diubah menjadi dua buah kode fonetis (phonetic code), yaitu kode yang dihasilkan dari
12
klasifikasi konsonan berdasarkan cara pengucapannya. Kedua kode fonetis tersebut selanjutnya akan dibandingkan. Jika kode fonetis sama, maka dua teks tersebut dianggap mirip, dan jika berbeda, maka dua teks tersebut dianggap tidak mirip.
2.1.4 Approximate string matching
Kemiripan penulisan dua buah teks dapat diukur berdasarkan sejumlah operasi dasar yang dilakukan terhadap salah satu teks agar kedua teks tersebut menjadi cocok (match). Banyaknya operasi dasar yang dilakukan agar kedua teks tersebut menjadi cocok disebut sebagai jarak edit (edit distance) antara teks dan pola teks yang dicari. Operasi-operasi dasar terhadap teks yang umumnya dipakai untuk membuat sebuah teks menjadi cocok dengan teks lain (Cormen, et al. 2001) adalah:
Penyisipan (insertion), yaitu melakukan penambahan huruf pada suatu kata agar kata tersebut menjadi sama dengan teks pembanding, misalnya mengubah kata saya menjadi satya dengan cara menyisipkan huruf ‘t’ di tengah kata saya;
Penghapusan (deletion), yaitu melakukan penghapusan huruf pada suatu kata agar kata tersebut menjadi sama dengan teks pembanding, misalnya mengubah kata satya menjadi saya dengan cara menghapus huruf ‘t’ pada kata satya;
Penggantian (substitution), yaitu melakukan penggantian sebuah huruf pada suatu kata dengan huruf lain agar kata tersebut menjadi sama dengan teks
13
pembanding, misalnya mengubah kata saya menjadi sama dengan cara mengganti huruf ‘y’ pada kata saya dengan huruf ‘m’. Operasi-operasi dasar terhadap teks tersebut di atas dalam teknik komputer sebenarnya dapat diubah menjadi hanya satu jenis operasi saja, yaitu operasi penggantian (substitution) seperti berikut:
Kata saya menjadi satya; adalah mengganti ‘NULL’ dengan huruf ‘t’;
Kata satya menjadi saya; adalah mengganti huruf ‘t’ dengan ‘NULL’;
Operasi lain yang juga sering digunakan pada beberapa algoritma pencocokan string adalah transposisi, yaitu penukaran tempat antara dua huruf yang terdapat dalam teks, misalnya mengubah kata saya menjadi asya dengan cara menukar posisi huruf pertama dan huruf kedua. Jarak edit antara sebuah teks dengan teks pembanding menentukan seberapa mirip kedua teks tersebut. Semakin kecil jarak edit, semakin mirip kedua teks tersebut. Misalnya, kata saya akan dianggap lebih mirip dengan kata sama, dibandingkan dengan kata satwa, karena untuk mengubah kata saya menjadi kata satwa diperlukan operasi dasar teks yang lebih banyak daripada yang dilakukan terhadap kata sama. Jika tidak diperlukan operasi dasar teks apapun untuk membuat sebuah teks menjadi sama dengan teks pembanding, berarti teks tersebut adalah sama (match) dengan teks pembanding.
14
2.2 ALGORITMA SOUNDEX
Algoritma SoundEx pertama kali dipatenkan oleh Robert C. Russell pada tahun 1918 (Russell 1918). Algoritma SoundEx menghasilkan kode fonetis dengan panjang empat karakter untuk semua panjang string masukan. Pencocokan dua buah string dilakukan dengan cara menghitung kode fonetis dari kedua buah string tersebut. Jika menghasilkan kode fonetis yang sama, maka dua buah string tersebut dianggap sebagai cocok atau mirip.
2.2.1 Aturan kode fonetis
Aturan pemberian kode fonetis dalam algoritma SoundEx dapat dilihat pada tabel berikut (Repici 2007): Tabel 2.1 Aturan pemberian kode pada algoritma SoundEx Huruf-huruf Kode ‘A’, ‘E’, ‘H’, ‘I’, ‘O’, ‘U’, ‘W’, ‘Y’ ‘0’ ‘B’, ‘F’, ‘P’, ‘V’ ‘1’ ‘C’, ‘G’, ‘J’, ‘K’, ‘Q’, ‘S’, ‘X’, ‘Z’ ‘2’ ‘D’, ‘T’ ‘3’ ‘L’ ‘4’ ‘M’, ‘N’ ‘5’ ‘R’ ‘6’
Prinsip dasar algoritma SoundEx di atas berdasarkan klasifikasi konsonan menurut alat bicara yang menghasilkannya dan cara artikulasinya. Penjelasan cara pemberian kode angka terhadap huruf-huruf dalam kata dilihat dari segi fonetik bahasa Inggris adalah (Syaroni dan Munir 2005):
15
1. Kode ‘0’ untuk huruf-huruf ‘a’, ‘e’, ‘h’, ‘i’, ‘o’, ‘u’, ‘w’, ‘y’ disebabkan hurufhuruf tersebut diperlakukan sebagai bunyi vokal; 2. Huruf-huruf ‘b’, ‘f’, ‘p’, ‘v’ dikelompokkan menjadi satu dengan kode ‘1’ karena terdapat dalam satu kelompok konsonan yaitu konsonan labial (diartikulasi oleh bunyi bibir); 3. Huruf-huruf ‘c’, ‘g’, ‘j’, ‘k’, ‘q’, ‘s’, ‘x’, ‘z’ dikelompokkan menjadi satu dengan kode ‘2’ karena pengucapan huruf-huruf tersebut mirip; 4. Huruf-huruf ‘d’, ‘t’ dikelompokkan menjadi satu dengan kode ‘3’ karena terdapat dalam satu kelompok konsonan yaitu plosive alveolar (diartikulasi oleh ujung lidah dengan langit-langit mulut kemudian dilepaskan secara tibatiba); 5. Huruf ‘l’ dikelompokkan tersendiri menjadi satu dengan kode ‘4’ karena merupakan konsonan lateral (sampingan); 6. Huruf-huruf ‘m’, ‘n’ dikelompokkan menjadi satu dengan kode ‘5’ karena huruf ‘m’ dan ‘n’ keduanya merupakan konsonan nasal (sengau); 7. Huruf ‘r’ pada kedua algoritma SoundEx di atas dikelompokkan tersendiri menjadi satu kelompok dan diberi kode ‘6’ karena huruf ‘r’ dalam pengucapan bahasa Inggris berbeda dengan konsonan lain dan sangat beragam karena dapat menjadi konsonan flapped (kuat), rolled (bergetar), maupun menjadi konsonan fricative (geseran).
16
2.2.2 Penghitungan kode fonetis
Dalam algoritma SoundEx, sebuah teks yang akan dibandingkan diproses terlebih dahulu untuk mendapatkan kode fonetisnya. Berikut adalah langkah penghitungan kode fonetis dari sebuah teks (Repici 2007): 1. Ubah semua huruf alphabet pada teks menjadi huruf kapital; 2. Ubah semua karakter non-alphabet menjadi karakter spasi; 3. Hapus semua karakter spasi di depan (leading spaces) dan di belakang teks (trailing spaces); 4. Simpan huruf pertama dan sisihkan dari langkah-langkah selanjutnya 5. Ubah karakter spasi menjadi karakter ‘0’; 6. Ubah setiap huruf menjadi kode angka sesuai dengan aturan seperti tertera pada tabel 2.1; 7. Hapus salah satu dari kode angka sama yang berderet; 8. Hapus semua angka ‘0’; 9. Ambil tiga angka pertama dari deretan angka tersisa. Jika panjangnya kurang dari tiga angka, maka tambahkan angka ‘0’ di belakang hingga tersusun menjadi tiga angka; 10. Kode fonetis dari teks telah kita dapatkan dengan cara menyusun huruf pertama yang tadi kita simpan, dengan tiga angka yang dihasilkan pada poin 9, sehingga membentuk susunan:
.
17
2.3 ALGORITMA JARO-WINKLER
Algoritma Jaro-Winkler adalah sebuah metode pengukuran kemiripan antara dua buah teks yang dikembangkan oleh William E. Winkler (Winkler 1999) berdasarkan algoritma Jaro yang lebih dahulu dikembangkan oleh Matthew A. Jaro (Jaro 1989). Algoritma Jaro-Winkler menitikberatkan pencocokan string berdasarkan kemungkinan perbedaan penulisan ejaan (spelling deviation) dan didesain khusus untuk pencocokan teks pendek seperti nama orang. Sebagai alat ukur kemiripan teks, algoritma Jaro-Winkler menghasilkan sebuah angka antara 0 hingga 1. 0 berarti kedua buah teks tersebut sangat tidak mirip, dan 1 berarti kedua buah teks tersebut sama (match).
2.4 METODE PERANCANGAN
Pengembangan aplikasi untuk perbandingan pencocokan nama ini akan dilakukan menggunakan metode prototyping. Metode ini dipilih karena beberapa alasan, antara lain:
Aplikasi yang akan dibuat bukanlah aplikasi dengan fitur komplit yang langsung dapat dimanfaatkan untuk keperluan tertentu, melainkan sebatas proof of requirement atau proof of concept saja;
Mempercepat waktu pengembangan dan segera bisa terlihat hasilnya;
18
Pengembang juga bertindak sebagai user sehingga keterlibatan user sangat tinggi terhadap proses pengembangan.
Metode prototyping diawali dengan penentuan kebutuhan oleh user. Pengembang akan mengumpulkan informasi-informasi mengenai kebutuhan user tersebut dan kemudian membuat sebuah prototype dari perangkat lunak yang akan dikembangkan. Berikut adalah tahapan yang dilakukan dalam prototyping (DSDM Consortium n.d.): 1. Analisis kebutuhan user, pengembang dan pengguna atau pemilik sistem melakukan diskusi untuk mengetahui kebutuhan sistem yang diinginkan; 2. Perencanaan prototype, pengembang mendiskusikan dengan pengguna atau pemilik sistem tentang rencana waktu penyelesaian dan bagaimana prototype dikembangkan; 3. Membuat prototype, pengembang membuat prototype dari sistem yang telah dijelaskan oleh pengguna atau pemilik sistem; 4. Meninjau prototype, memeriksa prototype yang telah dihasilkan, apakah sesuai atau tidak dengan kebutuhan sistem yang diinginkan. Hal ini dapat dilakukan melalui end-user testing dengan menggunakan contoh data asli untuk mendapatkan umpan balik dari pengguna;
2.5 UNIFIED MODELLING LANGUAGE
Unified Modelling Language (UML) adalah sebuah standar yang dapat membantu untuk memvisualisasikan, membangun, dan mendokumentasikan sistem perangkat lunak (Object Management Group 2009). UML menawarkan sebuah standar untuk
19
merancang model sebuah sistem. Dengan mempelajari UML, maka setiap orang dapat memahami suatu gambaran dokumentasi model yang sebelumnya hanya dipahami orang tertentu.
2.5.1 Komponen uml
UML memiliki banyak komponen diagram agar dapat memodelkan sistem secara lebih akurat. Diagram-diagram tersebut digunakan dalam pembuatan suatu sistem untuk mengakomodasi kepentingan pihak-pihak tertentu (stakeholder) pada aspekaspek yang berlainan dari sistem. Dengan demikian, maka pihak-pihak yang terlibat dapat memahami informasi yang ingin disampaikan dari satu pihak menuju pihak lainnya. UML terdefinisi dalam tiga belas macam diagram yang terbagi dalam tiga kategori (Object Management Group 2009), yaitu: 1. Structure Diagrams untuk memodelkan struktur statis aplikasi. Yang termasuk dalam diagram ini adalah: a. Class Diagram; b. Object Diagram; c. Component Diagram; d. Composite Structure Diagram; e. Package Diagram; dan f. Deployment Diagram.
20
2. Behaviour Diagrams untuk memodelkan perilaku umum sistem. Yang termasuk dalam diagram ini adalah: a. Use Case Diagram; b. Activity Diagram; dan c. State Machine Diagram; 3. Interaction Diagrams untuk memodelkan interaksi dari aspek-aspek yang berbeda. Yang termasuk dalam diagram ini adalah: a. Sequence Diagram; b. Communication Diagram; c. Timing Diagram; dan d. Interaction Overview Diagram. Meskipun UML mempunyai banyak diagram, tetapi tidak semua diagram harus digunakan dalam pembuatan suatu sistem. Dalam pengerjaan Tugas Akhir ini, hanya akan digunakan 2 (dua) diagram yaitu Use Case Diagram dan Activity Diagram untuk mendukung desain dari sistem.
2.5.2 Use case diagram
Use case diagram digunakan untuk memodelkan bisnis proses berdasarkan perspektif pengguna sistem. Yang ditekankan adalah ”apa” yang diperbuat sistem, dan bukan ”bagaimana” (Dharwiyanti dan Wahono 2003). Sebuah use case merepresentasikan sebuah interaksi antara aktor dengan sistem. Aktor menggambarkan
21
orang, sistem atau entitas eksternal / stakeholder yang menyediakan atau menerima informasi dari sistem. Sebuah use case dapat meng-include fungsionalitas use case lain sebagai bagian dari proses dalam dirinya. Secara umum diasumsikan bahwa use case yang di-include akan dipanggil setiap kali use case yang meng-include dieksekusi secara normal. Sebuah use case dapat di-include oleh lebih dari satu use case lain, sehingga duplikasi fungsionalitas dapat dihindari dengan cara menarik keluar fungsionalitas yang umum. Sebuah use case juga dapat meng-extend use case lain dengan behaviour-nya sendiri. Sementara hubungan generalisasi antar use case menunjukkan bahwa use case yang satu merupakan spesialisasi dari yang lain. Gambar berikut menunjukkan contoh use case diagram:
22
Gambar 2.1 Contoh use case diagram (Dharwiyanti dan Wahono 2003)
2.5.3 Activity diagram
Activity diagram menggambarkan berbagai alir aktivitas dalam sistem yang sedang dirancang, bagaimana masing-masing alir berawal, decision yang mungkin terjadi, dan bagaimana mereka berakhir (Dharwiyanti dan Wahono 2003). Activity diagram juga dapat menggambarkan proses paralel yang mungkin terjadi pada beberapa eksekusi. Activity diagram dibuat berdasarkan sebuah atau beberapa use case pada use case diagram.
23
Activity diagram merupakan state diagram khusus, di mana sebagian besar state adalah action dan sebagian besar transisi di-trigger oleh selesainya state sebelumnya (internal processing). Oleh karena itu activity diagram tidak menggambarkan behaviour internal sebuah sistem (dan interaksi antar subsistem) secara eksak, tetapi lebih menggambarkan proses-proses dan jalur-jalur aktivitas dari level atas secara umum. Activity diagram menggunakan notasi UML segiempat dengan sudut membulat untuk menggambarkan aktivitas. Decision digunakan untuk menggambarkan behaviour pada kondisi tertentu. Untuk mengilustrasikan proses-proses paralel (fork dan join) digunakan titik sinkronisasi yang dapat berupa titik, garis horizontal atau vertikal. Activity diagram dapat dibagi menjadi beberapa object swimlane untuk menggambarkan objek mana yang bertanggung jawab untuk aktivitas tertentu. Berikut ini adalah contoh activity diagram:
24
Gambar 2.2 Contoh activity diagram (Dharwiyanti dan Wahono 2003)
2.6 BASIS DATA
Basis data adalah sekumpulan data yang tersimpan secara sistematis dan terstruktur pada suatu tempat penyimpanan (storage) dan dapat digunakan untuk memenuhi kebutuhan informasi sejumlah pemakai (Connoly and Begg 2002). Data pada sistem basis data disimpan dalam sebuah objek yang disebut tabel. Tabel adalah sekumpulan data yang berhubungan dan tersimpan dalam bentuk baris
25
dan kolom (W3 Schools n.d.). Sebuah basis data umumnya berisi sekumpulan tabel, stored procedure, function, dan objek-objek lain yang digunakan untuk mewakili, menyimpan, dan mengakses data.
2.6.1 Structured query language
Untuk dapat mengakses dan memanipulasi basis data oleh pemakai ataupun dari aplikasi, dilakukan menggunakan bahasa standar yang disebut SQL (Structured Query Language). Perintah-perintah SQL yang digunakan untuk memanipulasi basis data antara lain:
Perintah Create Table Perintah ini digunakan untuk membuat suatu tabel dalam basis data. Bentuk umum perintah create table adalah sebagai berikut:
CREATE TABLE [nama_tabel]( nama_field1 tipe_data [, nama_field2 tipe_data, ...] [CONSTRAINT nama_field constraints] )
Perintah Select Perintah ini digunakan untuk menampilkan data dari suatu tabel. Bentuk umum perintah select adalah sebagai berikut:
SELECT nama_field1 [, nama_field2, ...] FROM nama_tabel1 [WHERE kondisi] [ORDER BY nama_field1 [ASC|DESC]
Perintah Insert
26
Perintah ini digunakan untuk menambah data ke dalam tabel. Bentuk umum perintah insert adalah sebagai berikut: INSERT INTO nama_tabel [(nama_field1 [, nama_field2, …])] VALUES (nilai1 [,nilai2, …])
Perintah Update Perintah ini digunakan untuk mengubah data dalam tabel. Bentuk umum perintah update adalah sebagai berikut:
UPDATE nama_tabel SET nama_field1=nilai1 [, nama_field2=nilai2, …] WHERE [kondisi]
Perintah Delete Perintah ini digunakan untuk menghapus data dalam tabel. Bentuk umum perintah delete adalah sebagai berikut:
DELETE FROM nama_tabel WHERE [kondisi]
2.6.2 Microsoft sql server
Microsoft SQL Server adalah basis data relasional yang dirancang untuk mendukung aplikasi dengan arsitektur client-server, dimana basis data terdapat pada komputer pusat yang disebut server dan informasi digunakan bersama oleh beberapa user yang menjalankan aplikasi pada komputer lokalnya disebut client (Djuandi 2002). Bahasa query utamanya adalah Transact-SQL, yaitu pengembangan dari SQL yang dipublikasi oleh International Organization for Standardization (ISO) dan American National Standards Institute (ANSI).
27
2.6.3 Fungsi (user defined function)
User Defined Function (UDF) adalah kumpulan rutin perintah-perintah SQL yang digunakan untuk membungkus (encapsulate) logika program (Novick 2004). UDF dapat menerima parameter atau argumen serta dapat mengembalikan sebuah nilai (value). Dengan UDF, developer dapat membagi logika program yang kompleks menjadi lebih pendek sehingga memudahkan penulisan dan pemeliharaan kode program. UDF dapat dipanggil melalui perintah SQL. Sejak SQL Server 2000, Microsoft telah menyediakan konsep UDF yang dapat dipakai oleh developer untuk membuat fungsi untuk keperluannya sendiri. Dalam SQL Server, terdapat tiga jenis nilai yang dapat dikembalikan oleh UDF (Novick 2004), yakni:
Scalar (nilai tunggal) UDF scalar mengembalikan sebuah tipe data skalar, misalnya Int, atau Varchar. Tipe data Text, Timestamp, dan Image tidak dapat dipakai sebagai nilai kembalian. Berikut ini adalah contoh UDF jenis scalar:
CREATE FUNCTION udf_Area (@Length float, @Width float) RETURNS float AS BEGIN RETURN @Length * @Width END
Inline table UDF ini mengembalikan hasil select dalam bentuk table. UDF jenis ini hanya dapat menyimpan satu perintah SQL select, namun memiliki keuntungan
28
karena dapat menerima parameter. Berikut ini adalah contoh UDF jenis inline table: CREATE FUNCTION dbo.udf_AuthorsByLetter (@Letter CHAR(1)) RETURNS TABLE AS RETURN SELECT * FROM pubs.Authors WHERE LEFT(au_lname, 1) = @Letter
Multistatement table UDF ini mengembalikan sebuah table yang didefinisikan di dalamnya dan dapat berisi lebih dari satu perintah SQL. Berikut ini adalah contoh UDF jenis scalar:
CREATE FUNCTION dbo.udf_FactorialsTAB (@N int ) RETURNS @Factorials TABLE (Number INT, Factorial INT) AS BEGIN DECLARE @I INT, @F INT SELECT @I = 1, @F = 1 WHILE @I < = @N BEGIN SET @F = @I * @F INSERT INTO @Factorials VALUES (@I, @F) SET @I = @I + 1 END -- WHILE RETURN END
2.6.4 Borland delphi
Borland Delphi merupakan suatu bahasa pemrograman yang memberikan berbagai fasilitas pembuatan aplikasi visual. Keunggulan bahasa pemrograman ini terletak pada produktivitas, kualitas, pengembangan perangkat lunak, kecepatan kompilasi, pola desain yang menarik serta diperkuat dengan pemrogramannya yang terstruktur. Keunggulan lain dari Delphi adalah dapat digunakan untuk merancang
29
program aplikasi yang memiliki tampilan seperti program aplikasi lain yang berbasis Windows. Khusus untuk pemrograman dengan basis data, Borland Delphi menyediakan fasilitas objek yang kuat dan lengkap yang memudahkan programmer dalam membuat program.
