BAB II TINJAUAN PUSTAKA 2.1. Regular Expression Regular expression atau yang sering disebut sebagai Regex adalah sebuah formula untuk pencarian pola suatu kalimat/string (Kuchling,2002). Sering kali orang beranggapan bahwa regex susah dan membingungkan. Namun sebenarnya regex sangatlah membantu dalam menemukan pola-pola kalimat. Sehingga percobaan terhadap semua kemungkinan pola kalimat tidak perlu dilakukan. Regular expression umumnya digunakan oleh banyak pengolah kata/text editor dan peralatan lainnya untuk mencari dan memanipulasi kalimat dengan berdasrkan kepada suatu pola tertentu. Banyak bahasa pemrograman yang mendukung regular expression seperti misalnya PHP, perl, VB dan Tcl. Sebuah alasan yang sangat bagus untuk menggunakan regex adalah karena regex sangatlah cepat dan akurat. Dimana regex menggunakan teknik finite automata yang memeriksa setiap karakter pada string berdasarkan pola yang sudah di rancang sebelumnya. Pada level rendah regex dapat mencari sebuah penggalan kata. Pada level tinggi regex mampu melakukan kontrol terhadap data. Baik mencari, menghapus dan merubah data string (Kuchling, 2002). Sedangkan bagaimana cara untuk mencari sebuah teks dalam html. Seringkali digunakan karakter “?” dan “*”. Penggunaan karakter “?” mengandung arti bahwa sedang dicari sebuah sebuah string yang mengandung sebuah karakter tertentu dan karakter “*” mengandung arti sedang dicari nol atau lebih karakter. Sebagai contoh : pencarian dengan menggunakan pola “blackberry ?” akan menghasilkan beberapa contoh sebagai berikut : • blackberry strom • blackberry 9800 • blackberry 3G Menggunakan karakter “*” akan menghasilkan lebih banyak hasil pencarian. “blackberry *” akan menghasilkan : • blackberry strom 4
5
• blackberry 9800 Kedua contoh di atas adalah salah satu penggunaan regular expression. Bayangkan saja jika pencarian string hanya menggunakan metode nama barang tanpa menyertakan regular expression. Tentunya saat proses pencarian menggunakan pola “blackberry *” hasilnya adalah harus “blackberry *”. Proses pencarian blackberry * tersebut menyebabkan regex menjadi cepat dan akurat. Dengan menggunakan sebuah pola “*” didapatkan hasil yang luas. Beberapa pola yang umum digunakan dalam regex tampak pada tabel 2.1. (Muliantara, 2009). Tabel 2.1. pola umum pada regex Pola ?
^
Penjelasan cocok dengan nol atau satu karakter sebelumnya. misal: pattern "died?" cocok dengan string "die" dan "died". cocok dengan satu atau lebih karakter sebelumnya. misal: "yu+k" cocok dengan "yuk", "yuuk", "yuuuk", dan seterusnya. cocok dengan nol atau lebih karakter sebelumnya. misal: pattern "hu*p" cocok dengan string "hp", "hup", "huup" dan seterusnya. jika diletakkan di depan pattern, maka berarti "bukan". misal pattern "!a.u" cocok dengan string apa saja kecuali string "alu", "anu", "abu", "asu", "aiu", dan seterusnya jika diletakkan di depan pattern, akan cocok dengan awal sebuah string.
$
jika diletakkan di belakang pattern, akan cocok dengan akhir sebuah string
()
gruping. digunakan untuk mengelompokkan karakter-karakter menjadi single unit. string yang cocok dalan pattern yang berada dalam tanda kurung dapat digunakan pada operasi berikutnya. semacam variable. escape character. mengembalikan fungsi metacharacter menjadi karakter biasa. pada beberapa system dapat berarti sebaliknya, yaitu metacharacter menggunakan escape character didepannya . (titik) yang akan cocok dengan satu karakter apa pun. … berarti string apa pun boleh asal memiliki tiga karakter.
+ * !
\
.
Selama pencocokan, kelakuan mesin regex dapat diubah dengan modifier. Ada beberapa modifier yang dikenal dalam regex Perl-compatible. Yang pertama adalah i (Ignore_Case). Jika kita memberikan modifier ini, maka mesin regex tidak akan membedakan huruf besar dan kecil. Artinya, [A-Z] dalam mode i
6
akan sama dengan [A-Za-z]. Modifier i dapat bermanfaat untuk memperpendek pola, jika kita menginginkan pencocokan yang tidak membedakan huruf besar kecil. Modifier lain adalah s (Single_Line). Ingat karakter meta . (titik)? Menurut definisi, titik cocok dengan semua karakter. Tapi secara default mesin regex tidak akan mencocokkan titik dengan newline atau Enter. Jadi pola Selamat.+ akan cocok dengan string “Selamat datang” tapi tidak akan cocok dengan “Selamat\ndatang” (Selamat yang diikuti datang di baris berikutnya). Karena tanpa mode s, setiap akhir baris dianggap sebagai akhir string. Subpola .+ tidak kebagian karakter karena setelah Selamat tidak ada karakter lagi di baris pertama string. Namun dengan modifier s, .+ akan menelan semua sisa hingga akhir string (\ndatang) karena titik di mode s akan cocok dengan newline. Jadi, dengan kata lain, dalam mode s keseluruhan string dianggap terdiri dari satu baris. Modifier m (Multi_Line) berfungsi untuk mengubah kelakuan karakter meta jangkar. Tanpa mode m, pola ^datang tidak akan cocok dengan string “Selamat datang” karena jangkar ^ harus dicocokkan dengan awal string. Dalam hal ini awal string adalah Selamat. Namun dengan modifier m, pola tersebut akan cocok karena tiap awal dan akhir baris dianggap sebagai ujung yang bisa cocok dengan jangkar. Contoh lain, Selamat$ akan cocok di mode m tapi tidak tanpa m. Dengan kata lain, dalam mode m setiap baris dalam string akan dianggap masingmasin memiliki ujung. Modifier g (Global_Match) terutama hanya berguna di Perl. Dengan modifier ini, pencocokan berikutnya akan dilanjutkan dari posisi terakhir, tidak diulang dari posisi awal string. Terutama berguna jika ingin mengiterasi string dari awal hingga akhir. 2.2. Similarity Definisi dari similarity adalah ukuran kesamaan atau kemiripan terhadap sesuatu yang penting dan merupakan konsep yang digunakan secara umum. Pada penelitian ini kosep similarity berkaitan dengan kosep data mining yang mencari
7
kesamaan arti dari data barang yang jumlahnya sangat banyak agar tidak terjadi penduplikasian data barang. Similarity mempunyai beberapa pendekatan, yaitu: a. Perkiraan 1: kesamaan antara A dan B adalah berhubungan dengan kesamaannya secara umum. Semakin banyak kesamaan umum yang dibagikan, semakin banyak pula kesamaan mereka. b. Perkiraan 2: kesamaan antara A dan B adalah berhubungan dengan perbedaan-perbedaan yang dimilikinya. Semakin banyak perbedaan yang dimiliki, semakin kecil tingkat kemiripannya. c. Perkiraan 3: kesamaan maksimum antara A dan B akan tercapai ketika A dan B adalah serupa atau identik, berapa banyak kesamaan umum yang mereka bagikan tidak berpengaruh. Similarity juga memiliki beberapa masalah. Masalah ini antara lain tidak adanya asumsi yang tegas mengenai suatu sifat kesamaan. Tanpa adanya asusmsi yang jelas dan tegas tentunya akan sangat sulit untuk menentukan secara teoritis suatu sifat kesamaan dalam similarity tersebut (Aribowo dkk, 2009).
2.3. Metode Levenshtein Distance Levenshtein distance merupakan metode yang dikembangkan oleh Vladimir Levenshtein pada tahun 1965. Dalam teori informasi,
levenshtein
distance dua string adalah jumlah minimal operasi yang dibutuhkan untuk mengubah suatu string ke string yang lain, di mana operasi-operasi tersebut adalah operasi penyisipan, penghapusan, atau penyubstitusian sebuah karakter. Perbedaan yang diukur adalah jumlah minimal operasi penambahan (insert), penghapusan (delete) dan penggantian karakter (substitute) yang dibutuhkan untuk meniadakan perbedaan diantara keduanya (Adiwidya, 2009). Pendekatan tersebut menjadi bahan analisis untuk pengaplikasiannya dalam aplikasi yang nyata, seperti untuk mesin pencari, pengecek ejaan, pendeteksian suatu rantai dalam DNA, pendeteksi pemalsuan, dan lain-lain Ada tiga buah operasi string yang digunakan yaitu operasi penghapusan, penyisipan, dan penggantian. Jumlah operasi minimal dari ketiga operasi tersebut terhadap dua buah string disebut dengan levenshtein distance atau edit distance.
8
Untuk menghitung jaraknya tanpa menggunakan proses rekursif, digunakan matriks (n + 1) × (m + 1) di mana n adalah panjang string s1 dan m adalah panjang string s2. Berikut adalah Algoritma dari Levenshstein Distace : Langkah 1: Inisialisasi a) Set n untuk menjadi panjang s, m ditetapkan menjadi panjang t. b) Buatlah matriks yang berisi baris 0 .. m dan kolom 0 .. n. c) Menginisialisasi baris pertama ke 0 .. n, d) Inisialisasi kolom pertama untuk 0 .. m. Step2: Pengolahan a) Periksa s (i dari 1 sampai n). b) Periksa t (j dari 1 sampai m). c) Jika s [i] sama [j] t, biaya adalah 0. d) Jika s [i] tidak t sebesar [j], biaya adalah 1. e) Mengatur sel d [i, j] dari matriks sama dengan minimum: i) Sel tepat di atas 1 ditambah: d [i-1, j] + 1. ii). Sel segera ke kiri ditambah 1: d [i, j-1] + 1. iii Sel diagonal atas dan ke kiri ditambah biaya: d [i-1, j-1] + biaya. Langkah 3: Hasil Langkah 2 diulang sampai d [n, m] nilai ditemukan (Ardiyanto,2008) Sebagai contoh berikut adalah implementasi dari algoritma levenshtein distance dalam string : X=abcxdefghi Y=abcdefgh Setelah melalui proses pada algoritma ini maka hasil akhirnya dapat digambarkan pada gambar 2.1. Dari gambar 2.1 dapat dilihat bahwa angka yang bergaris bawah merupakan diagonal utama dari string yang hit antara kedua string tersebut. a
b
c
x
d
e
f
g
h
i
a
0
1
2
3
4
5
6
7
8
9
b
1
0
1
2
3
4
5
6
7
8
c
2
1
0
1
2
3
4
5
6
7
d
3
2
1
1
1
2
3
4
5
6
9
e
4
3
2
2
2
1
2
3
4
5
f
5
4
3
3
3
2
1
2
3
4
g
6
5
4
4
4
3
2
1
2
3
h
7
6
5
5
5
4
3
2
1
2
Gambar 2.1. Array dari dinamic programming untuk string X dan Y Elemen terakhir (kanan bawah) adalah elemen yang nilainya menyatakan jarak kedua string yang dibandingkan. Jadi nilai perbedaan karakter dari string X dan Y adalah 2 karakter.
