String Matching

String Macthing

Pengertian String Macthing

String macthing adalah pencarian sebuah pattern pada sebuah teks (Corman, T.M. et al. 1994). String macthing digunakan untuk menemukan suatu string yang di sebut dengan pattern dalam string yang di sebut dengan teks(Charras, C. Dan Lecroq. T.1997). Prinsin kerja algoritma string macthing(Effendi, D. Et al. 2013) adalah sebagai berikut:

1.           Memindai teks dengan bantuan sebuah window  yang           ukurannya sama dengan panjang pattern.

2.           Menempampatkan window pada awal teks.

3.           Membandingan karakter pada window dengan karakter dari pattern. Setelah pencocokan dilakukan pergeseran ke kanan pada window. Prosedur ini di lakukan berulang-ulang sampai window berada pada akhir teks. Mekanisme ini di sebut mekanisme sliding window.

Cara kerja Sting Matching

                 Cara yang jelas untuk mencari pattern yang cocok dengan teks adalah dengan mencoba mencari di setiap posisi awal dari teks dan mengabaikan pencarian secepat mungkin jika karakter yang salah di temukan (Knuth, D.E. et al. 1997). Proses pertama adalah menyelaraskan bagian paling kiri dari pattern dengan teks kemudian di bandingkan karakter yangb sesuai dari tks dan pattern setelah seluruhnya cocok maupun tidak cocok dari pattern, window di geser ke kanan sampai posisi (n-m+

                 Dengan sebuah nilai karakter (m < n) yang akan di cari dari teks dalam algoritma pencocokan sting, teks di asumsikan berada di dalam memory, sehingga bila kita mencari string di dalam sebuah arsip, maka semua isi arsip perlu di baca terlebih dahulukemudian di simpan di dalam memory. Jika pattern muncul lebih dari sekali di dalam teks, maka pencarian hanya akan memberikan keluaran berupa lokasi pattern di temukan pertama kali (Wulan. 2011).

  Teknik Algoritma String Matching

Menurut singla, N. Dan Grag, D.(2012), ada dua tekhnik utama dalam algoritma string matching yaitu:

1.                 Exact string matching

Exact string matching merupakan pencocokan string secara tepat dengan susunan karakter dalam string yang dicocokan memiliki jumlah maupun urutan karakter dalam string yang sama. Bagian algoritma ini bermanfaat jiga penggunaan ingin mencari string dalam dokumen yang sama percis dengan string masukan. Beberapa algoritma exact string matching antara lain:

a. Knuth-Morris-Pratt

Metode ini mencari kehadiran sebuah kata dalam teks dengan melakukan observasi awal (preprocessing) dengan cara mengecek ulang kata sebelumnya. Algoritma ini melakukan pencocokan dari kiri ke kanan.

b. Boyer-Moore

Algoritma Boyer-Moore adalah algoritma string matching yang paling efisien dibandingkan algoritma string matching lainnya. Sebelum melakukan pencarian string, algoritma melakukan proses terlebih dahulu pada pattern, bukan pada string pada teks tempat pencarian. Algoritma ini melakukan pencocokan karakter yang dimulai dari kanan ke kiri. Karena sifatnya yang sangat efisien, Boyer-Moore memiliki banyak variasi penyederhanaannya. Salah satunya adalah algoritma Horspool yang akan digunakan dalam penelitian ini dan akan dijelaskan pada poin berikutnya

2.                  Approximate string matching atau Fuzzy string matching.

Fuzzy string matching merupakan pencocokan string secara samar, maksudnya pencocokan string dimana string yang dicocokkan memiliki kemiripan memiliki susunan karakter yang berbeda (mungkin jumlah atau urutannya), tetapi string tersebut memiliki kemiripan baik kemiripan tekstual/penulisan (approximate string matching) atau kemiripan ucapan (phonetic string matching)

   Algoritma Horspool

Algoritma Horspool adalah penyederhanaan dari algoritma Boyer-Moore yang dibuat oleh R. Nigel Horspool. Menurut Horspool, R.N. (1980), masalah dalam pencarian teks ini adalah mencari dalam teks yang besar untuk menemukan pattern pertama. Karena teks yang dicari bisa sangat besar (memungkinkan ratusan ribu karakter) maka penting untuk menggunakan teknik yang lebih efisien. Algoritma Horspool bekerja dengan metode yang hampir sama dengan algoritma Boyer-Moore namun tidak melakukan lompatan berdasarkan karakter pada pattern yang ditemukan tidak cocok pada teks.

Algoritma Horspool mempunyai nilai pergeseran karakter yang paling kanan dari window. Pada tahap observasi awal (preprocessing), nilai shift akan dihitung untuk semua karakter. Pada tahap ini, dibandingkan pattern dari kanan ke kiri hingga kecocokan atau ketidakcocokan pattern terjadi. Karakter yang paling kanan pada window digunakan sebagai indeks dalam melakukan nilai shift. Dalam kasus ketidakcocokan (karakter tidak terdapat pada pattern) terjadi, window digeser oleh panjang dari sebuah pattern. Jika tidak, window digeser menurut karakter yang paling kanan pada pattern (Baeza-Yates, R.A. & Regnier, M. 1992).

Berikut adalah pseudocode algoritma Horspool pada tahap praproses:

Procedure preBmBc (

input P : array[0. . m-1] of char,

input m : integer,

input/output BmBc : array [0 . . n-1] of integer

)

Deklarasi:

i : integer

Algoritma:

for (i := 0 to ASIZE – 1)

BmBc[i] := m;

endfor

for (i := 0 to m-2)

BmBc[P[i]] := m – i – 1;

Endfor

Dan berikut adalah pseudocode algoritma Horspool pada tahap pencarian:

Procedure HorspoolSearch (

input m, n : integer,

input P : array[0 . . m-1] of char,

input T : array[0 . . n-1] of char,

output find : array[0 . . m-1] of boolean

)

Deklarasi:

j : integer

BmBc : array[0 . . n] of integer

c : char

Algoritma:

preBmBc(P, m, BmBc)

j := 0

while (j <= n – m) do

c = T[j + m – 1];

if (P[m – 1] == c && memcmp(P, T + j, m-1) == 0) then

find[j] := true;

endif

j := j + BmBc[c];

endwhile

sumber : 
http://repository.usu.ac.id/