String Matching

String matching adalah pencaraian karakter pada teks. Pencarian tersebut mempunyai algoritma khusus yang dinamakan algoritma string matching. Sebelum ke cara kerja string matching mempunyai 3 komponen yaitu: 

•  Pattern = deretan karakter yang dibandingkan dengan teks, dengan bentuknya x[0..m-1], panjang pattern disimbolkan dengan m.

• Teks, tempat pembandingn pattern dilakukan, dengan bentuknya y[0..n-1], panjang teks disimbolkan dengan n.
•  Alfabet, semua simbol yang digunakan oleh bahasa pada teks dan pattern,bentuknya (∑) dengan ukuran disimbolkan dengan ASIZE.

Cara kerja singkat algoritma ini adalah :

•  Pemindaian teks dengan bantuan window yang ukurannya sama dengan panjang pattern.

•  Menempatkan window pada awal teks

• Membandingkan karakter pada window dengan karakter dari pattern. Lalu lakukan shift ke kanan pada window. lakukan secara berulang sampai window ada di akhir teks. ini disebut mekanisme sliding-window.

Dan algoritma ini terdapat jenis-jenis nya, yaitu:

1. Boyer moore

Algoritma Boyer Moore merupakan metode pencocokan string dari kanan ke kiri, memindai karakter pattern dari kanan ke kiri. Terdapat dua fungsi shift yaitu good­-suffix shift dan bad-character shift digunakan untuk mengambil langkah berikutnya apabila terjadi ketidakcocokan antara karakter pattern dengan karakter teks yang dicocokkan.

Berikut ini adalah cara kerja boyer moore:

• Menjalankan preBmBc dan preBmGs supaya dapat inisialisasi.

preBmBc berfungsi untuk menentukan besar pergeseran yang dibutuhkan untuk mencapai karakter tertentu pada pattern dari karakter pattern terkanan. Lalu hasilnya disimpan pada tabel BmBc.

      

preBmGs. Sebelumnya suffix dijalankan pada pattern. Fungsi suffix adalah memeriksa kecocokan karakter dari terkanan dengan karakter yang lebih kiri dari karakter terkanan. Hasilnya disimpan pada tabel suff.  Sedangkan fungsi preBmGs adalah untuk mengetahui banyak langkah pada pattern.

• lakukan pencarian string dengan hasil dari preBmBc dan preBmGs tadi.

2. Quick Search

Algoritma quick search merupakan metode pencocokan string dari kiri ke kanan kebalikannya dari boyer moore. Pada quick hanya menggunakan bad-character shift.

Cara kerja algoritma Quick Search:

• Menjalankan preQsBc sebagai inisialisasi. berfungsi untuk mengetahui posisi terkanan masing-masing karakter pada pattern.

• Membandingkan karakter. Jika ada ketidakcocokan maka bergeser berdasarkan QsBc.

 

3. Turbo BM

Algoritma yang menggunakan metode pencocokan string dari kanan ke kiri tapi membutuhkan memori lebih banyak dibandingkan dengan algoritma Boyer Moore. Algoritma Turbo BM menggunakan fungsi good-suffix shift dan bad-character shift serta menggunakan turbo shift.

Cara kerja algoritma Turbo BM

•  menjalankan prosedur preBmBc dan preBmGs.

• Melakukan pencocokan karakter pada pattern. Jika ada ketidakcocokan maka terjadi pergeseran terbesar berdasarkan BmBc, tabel BmGs dan turbo shift.     

4. Algoritma Shift-or

Algoritma Shift-or adalah algoritma yang menggunakan metode pencocokan string dari kiri ke kanan. tapi mempunyai batas ukuran yaitu Ukuran pattern dicocokkan tidak boleh lebih 32 bit. Algoritma ini harus menggunakan tabel cancel mask dan variabel match register terlebih dahulu.

Tabel cancel mask berfungsi mencatat kemunculan karakter alfabet yang muncul pada pattern. Berikut tabel cancel mask dan match register. 

Tabel Cancel Mask
	7	6	5	4	3	2	1	0
	g	a	G	a	G	a	c	g
G	0	1	0	1	0	1	1	0
C	1	1	1	1	1	1	0	1
A	1	0	1	0	1	0	1	1
T	1	1	1	1	1	1	1	1

Match Register
G	a	g	a	g	a	c	g
8	7	6	5	4	3	2	1
1	1	1	1	1	1	1	1

Cara kerja algoritma Shift-or

• Gunakan logika OR terhadap match register dan tabel cancel mask untuk karakter pertama pada teks.

• Simpan hasilnya pada match register. Variabel match register baru ini menjadi match register y ang di-OR-kan dengan cancel mask untuk karakter berikutnya.

• Dan langkah di atas lakukan pada semua karakter pada teks sampai terdapat 0 pada kolom paling kiri match register.

Sumber: http://analisis-algoritma12.blogspot.co.id/2016/10/string-matching.html