Hello kali ini kita akan membahas tentang "String mathcing" apa itu string matching? String matching adalah pencarian
sebuah pattern pada sebuah teks. Algoritma string matching adalah algoritma
yang ditujukan untuk melakukan string matching. Prinsip kerja algoritma string
matching adalah sebagai berikut:
1.
Memindai teks dengan bantuan sebuah
window yang ukurannya sama dengan panjang pattern.
2.
Menempatkan window pada awal teks.
3.
Membandingkan karakter pada window
dengan karakter dari pattern. Setelah pencocokan (baik hasilnya cocok atau
tidak cocok), dilakukan shift ke kanan pada window. Prosedur ini dilakukan
berulang-ulang sampai window berada pada akhir teks. Mekanisme ini disebut
mekanisme sliding-window.
Algoritma string matching mempunyai
tiga komponen, yaitu: pattern, teks dan alfabet dengan asumsi sebagai berikut:
1.
Pattern, deretan karakter yang
dicocokkan dengan teks, dinyatakan dengan x[0..m-1], panjang pattern dinyatakan
dengan m.
2.
Teks, tempat pencocokan pattern
dilakukan, dinyatakan dengan y[0..n-1], panjang teks dinyatakan dengan n.
3.
Alfabet, berisi semua simbol yang
digunakan oleh bahasa pada teks dan pattern, dinyatakan dengan ∑ dengan ukuran
dinyatakan dengan ASIZE.
Algoritma
o Boyer Moore
o Quick Search
o Turbo BM
o Shift-or
Boyer Moore
Algoritma Boyer Moore termasuk
algoritma string matching yang paling efisien dibandingkan algoritma string
matching lainnya. Karena sifatnya yang efisien, banyak dikembangkan algoritma
string matching dengan bertumpu pada konsep algoritma Boyer Moore, beberapa di
antaranya adalah algoritma Turbo BM dan algoritma Quick Search.
Algoritma Boyer Moore menggunakan metode pencocokan string dari kanan ke
kiri, memindai karakter pattern dari kanan ke kiri. Algoritma Boyer Moore
menggunakan dua fungsi shift yaitu good-suffix shift dan bad-character shift untuk mengambil
langkah berikutnya setelah terjadi ketidakcocokan antara karakter pattern dan
karakter teks yang dicocokkan.
Deskripsi kerja algoritma Boyer Moore
Untuk menjelaskan konsep dari good-suffix
shift dan bad-character shift diperlukan
contoh kasus, seperti kasus ketidakcocokan ditengah pencocokan karakter pada
teks dan pattern. Karakter pattern x[i]=a tidak cocok dengan karakter teks y[i+j]=b saat pencocokan pada posisi j. Maka x[i+l .. m-1]= y[i+j+1 .. j+m-1]=u dan x[i] ≠ y[i+j].
Good-suffix shift
Good-suffix shift adalah pergeseran yang dibutuhkan
dari x[i]=a ke karakter lain yang letaknya lebih kiri dari x[i] dan terletak di sebelah kiri segmen u. Kasus ini ditunjukkan pada gambar di
bawah ini.
Y
|
b
|
u
|
||
X
|
a
|
u
|
  Shift |
|
X
|
c
|
u
|
Good-suffix shift, u terjadi lagi didahului karakter c berbeda
dari a.
Jika tidak ada segmen
yang sama dengan u, maka dicari u yang merupakan suffiks terpanjang u.
Kasus ini ditunjukkan pada Gambar berikut
Y
|
b
|
u
|
||
X
|
a
|
u
|
 Shift |
|
X
|
v
|
Good-suffix
shift, hanya suffix dari u yang
terjadi lagi di pattern x.
Bad-character shift
Berdasarkan contoh kasus di atas, bad-character adalah karakter pada teks
yaitu y [i+j] yang tidak cocok
dengan karakter pada pattern. Konsep
dari fungsi bad-character shift adalah
sebagai berikut:
Y
|
b
|
u
|
||
X
|
a
|
u
|
 Shift |
|
X
|
b
|
b tidak ditemukan
|
Bad-character shift, b terdapat di pattern x.
-
Jika
bad-character y[i+j] tidak ada pada pattern sama sekali, maka pattern digeser ke kanan sejauh i. Kasus ini dit tunjukkan pada Gambar
di bawah
Y
|
b
|
u
|
||
X
|
a
|
u
|
 Shift |
|
X
|
b tidak ditemukan
|
Bad-character
shift, b tidak ada di pattern x
-
Jika
bad-character y[i+j] terdapat pada pattern di posisi terkanan k yang lebih
kanan dari x[i] maka pattern seharusnya digeser sejauh i-k yang hasilnya negatif (pattern digeser kembali ke kiri). Maka
bila kasus ini terjadi. akan diabaikan.
Cara kerja algoritma Boyer Moore
·
Menjalankan prosedur preBmBc dan
preBmGs untuk mendapatkan inisialisasi.
- Menjalankan prosedur preBmBc. Fungsi dari prosedur ini adalah untuk menentukan berapa besar pergeseran yang dibutuhkan untuk mencapai karakter tertentu pada pattern dari karakter pattern terakhir/terkanan. Hasil dari prosedur preBmBc disimpan pada tabel BmBc.
- Menjalankan prosedur preBmGs. Sebelum menjalankan isi prosedur ini, prosedur suffix dijalankan terlebih dulu pada pattern. Fungsi dari prosedur suffix adalah memeriksa kecocokan sejumlah karakter yang dimulai dari karakter terakhir/terkanan dengan sejumlah karakter yang dimulai dari setiap karakter yang lebih kiri dari karakter terkanan tadi. Hasil dari prosedur suffix disimpan pada tabel suff. Jadi suff[i] mencatat panjang dari suffix yang cocok dengan segmen dari pattern yang diakhiri karakter ke-i.
- Dengan prosedur preBmGs, dapat diketahui berapa banyak langkah pada pattern dari sebeuah segmen ke segmen lain yang sama yang letaknya lebih kiri dengan karakter di sebelah kiri segmen yang berbeda. Prosedur preBmGs menggunakan tabel suff untuk mengetahui semua pasangan segmen yang sama. Contoh pada Gambar 2.1, yaitu berapa langkah yang dibutuhkan dari au(u = segmen, a = karakter di sebelah kiri u) ke cu yang mempunyai segmen u pada pattern dengan karakter di sebelah kiri segmen yaitu c berbeda dari a dan terletak lebih kiri dari au. Hasil dari prosedur preBmGs disimpan pada tabel BmGs.
·
Dilakukan
proses pencarian string dengan
menggunakan hasil dari prosedur preBmBc dan preBmGs yaitu tabel BmBc dan BmGs.
Prosedur Algoritma Boyer Moore
o
Prosedur PreBmBc
procedure preBmBc(I / O x: string,
m: integer, output BmBc: array of
integer)
{ ASIZE = ukuran ∑ }
i traversal [0..ASIZE - 1]
BmBc[i] ¬ m
i traversal [0..m - 2]
BmBc[x[i] ] ¬ m -
i - 1
o
Prosedur
suffix
procedure suffix
(I / O x: string, m: integer, output suff: array of integer)
suff [m – 1] ¬ m
g ¬ m – 1
i traversal [m – 2..0]
if ( i > g and suff [i + m -1 – f] < i –
g) then
suff [i]
¬ suff [
i + m – 1 – f]
else
if (I < g) then
g ¬ i
f
¬ i
while
(g ³ 0 and x[g] ¬ x[g + m – 1 – f]) do
g
¬ g – 1
f
¬ i
while
(g ³ 0 and x[g] ¬ x[g] + m – 1 – f]) do
g
¬ g – 1
suff[i]
¬ f - g
Quick Search
Quick Search merupakan salah
satu algoritma penyederhanaan dari algoritma Boyer Moore (merupakan varian yang
lebih sederhana) yang dalam prakteknya dianggap paling efisien dan mudah untuk
diimplementasikan.
Deskripsi kerja algoritma Quick
Search
Algoritma Quick Search menggunakan
metode pencocokan string dari kiri ke
kanan. Algoritma ini hanya menggunakan tabel bad-character shift. Ketika dilakukan pencocokan pada teks y[j..
j+m-1] apabila terjadi ketidakcocokan
maka dilakukan shift berdasarkan
karakter teks y[j+m], dimana shift yang dipilih adalah jarak terdekat ke karakter pattern yang sama dengan karakter teks
y[j+m] dihitung dari 1 posisi setelah
pattern terakhir.
Dengan menggunakan tabel QsBc untuk menyimpan bad-character shift. Bad-character shift dari algoritma ini sedikit dimodifikasi untuk karakter
terakhir dari pattern.
Cara kerja algoritma Quick Search
· Menjalankan prosedur preQsBc sebagai
inisialisasi. Fungsi dari prosedur ini adalah untuk mengetahui posisi terkanan
masing-masing jenis karakter yang ada pada pattern.
· Melakukan proses perbandingan
karakter. Jika terjadi ketidakcocokan maka dilakukan pergeseran berdasarkan
tabel QsBc.
Prosedur Algoritma Quick Search
o Prosedur
PreQsBc
procedure preQsBc(I / O x: string, m: integer, output qsBc: array of – integer)
i traversal [0..ASIZE – 1]
qsBc[i] ← m
+ 1
i traversal
[0..m – 1]
qsBc[x [i] ]
← m - i
o Prosedur
Quick Search
procedure QS(I / O x,y: string,
m,n: integer)
preQsBc(x,
m, qsBc)
j
← 0
while
(j ≤ n - m) do
if
(memcmp (x, y + j, m) = 0 ) then
OUTPUT
(j)
j
← j +qsBc[y [j + m] ]
Algoritma Turbo BM
Merupakan
varian dari algoritma Boyer Moore. Algoritma ini membutuhkan preprocessing yang sama tapi membutuhkan
memori sedikit lebih banyak
dibandingkan dengan algoritma Boyer Moore. Algoritma Turbo BM menggunakan metode pencocokan string dari kanan ke kiri.
Deskripsi kerja algoritma Turbo BM
Algoritma Turbo BM menggunakan kedua fungsi shift dari algoritma Boyer Moore
yaitu good-suffix shift dan bad-character
shift. Algoritma ini mengingat segmen dari teks yang cocok dengan suffix
dari pattern selama pencocokan
terakhir (dan hanya jika good-suffix shift dilakukan).
Cara ini mempunyai dua keuntungan:
·
Memungkinkan segmen yang diingat tadi dilewati tanpa
perlu diperiksa.
·
Memungkinkan dilakukannya turbo-shift.
Turbo-shift dapat terjadi bila selama
pencocokan sekarang (yang sedang berlangsung), suffix dari pattern yang cocok dengan teks lebih
pendek daripada suffix yang diingat dari pencocokan terakhir (pencocokan
sebelum pencocokan yang sedang berlangsung). Pada kasus ini, anggap u faktor yang diingat dan v suffix
yang dicocokkan selama pencocokan sekarang sebagaimana uzv adalah suffix
x. Anggap a adalah karakter dari pattern
dan b karakter teks yang tidak
cocok selama pencocokan sekarang. Lalu av adalah suffix x,
begitu juga u karena |v| < |u|. Kedua karakter a dan b terjadi pada jarak p
di teks, dan suffix x dari panjang |uzv| mempunyai periode
panjang p=|zv| karena u adalah perbatasan dari usv, sehingga tidak dapat menutupi kedua kejadian dari dua karakter
berbeda a dan b, pada
jarak p, di teks.
Cara kerja algoritma Turbo BM
·
Inisialisasi,
karena algoritma ini menggunakan good-suffix shift dan bad-character shift dari algoritma Boyer
Moore maka untuk inisialisasi dijalankan prosedur preBmBc dan preBmGs
seperti algoritma Boyer Moore.
·
Melakukan
proses pencocokan karakter pada pattern dengan
karakter pada teks. Jika terjadi ketidakcocokan maka dilakukan pergeseran
terbesar berdasarkan tabel BmBc, tabel BmGs dan turbo shift.
Prosedur Turbo BM
o
Prosedur Turbo BM
procedure TBM(I / O x,y : string ,m,n:integer)
{Preprocessing}
preBmGs(x,m, BmGs)
preBmBc(x,m, BmBc)
{Searching}
j ← 0
u ← 0
 shift ← m |
while (i ≥
0 and x[i] = y[i+j] ) do
i ←
m - 1
while ( i
≥ 0 and x [i] =
y[i+j] ) do
i ←
i - 1
if ( u ≠
0 and i
= m - 1
- shift ) then i
← i - u
if ( i
< 0 ) then
OUTPUT(j)
shift ← BmGs [0]
u ← m - shift
else
v ← m - 1- i
turboShift ← u - v
bcShift ←
BmBc [y [i+j ] - m + 1 + i
shift ←
MAX (turboShift, bcShift)
shift ←
MAX(shift, BmGs[i])
if (shift = BmGs[i])then
u ← MIN (m - shift, v)
else
if (turboShif < bcshift)then
shift ← MAX(shift, u + 1)
u ← 0
j ←
j + shift
|
Algoritma Shift-or
Algoritma Shift-or merupakan salah satu algoritma string matching yang efisien untuk masalah pencocokan string secara tepat dan menggunakan
metode pencocokan string dari kiri ke
kanan. Algoritma Shift-or ini
mempunyai batas ukuran. Ukuran pattern yang
akan dicocokkan tidak boleh melebihi 32 bit.
Deskripsi kerja algoritma Shift-or
Algoritma ini menggunakan sebuah
tabel cancel mask dan sebuah variabel
match register. Maka sebelum
pencocokan dilakukan, tabel cancel mask dan
match register harus dibangun
terlebih dulu. Untuk mengilustrasikan deskripsi dan cara kerja dari algoritma shift-or.
Tabel cancel mask
Tabel cancel mask adalah tabel yang berfungsi untuk mencatat kemunculan
karakter alfabet yang muncul pada pattern.
Pada tabel cancel mask ini, nilai
benar diwakili dengan 0, sedangkan nilai salah diwakili dengan 1.
Cancel Mask Table
|
||||||||
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
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
· Lakukan operasi logika OR terhadap
match register dan tabel cancel mask untuk karakter pertama pada
teks (untuk karakter ke n, tabel cancel
mask-nya adalah seluruh kolom dari
baris karakter n tersebut).
· Simpan hasilnya pada match register (setelah dilakukan shift kiri pada hasil operasi tadi).
Variabel match register baru ini
menjadi match register y ang di-OR-kan dengan cancel mask untuk karakter berikutnya.
· Lakukan proses di atas pada semua
karakter pada teks sampai terdapat 0 pada kolom paling kiri match register hasil operasi logika OR
(yang berarti ditemukan bagian dari teks yang sama dengan pattern ).
Prosedur Algoritma Shift-or
o
Prosedur Shift-or
Pada algoritma ini, terdapat asumsi:
-
Simbol
‘or’ melambangkan or-bitwise.
-
Simbol
‘and’ melambangkan and-bitwise.
-
Simbol
‘~’ melambangkan komplemen untuk bitwise.
i traversal [0..alphabetsize]
cancelmask[i] 1
lim ← 0
j ← 1
i traversal [0..LONG(pattern) - 1]
j ← j <<1
cancelmask[pattern[i]] ← cancelmask[pattern[i]
] and
lim ← lim or j
lim ← ~ (1im >>1)
matchregister ← 1
i traversal [0..LONG(text)]
matchregister ← ((matchregister <<1) or (cancelmask [ text [i] ] )
|
Ya sekian. Jika ada kekurangan mohon maaf.
Cheers!!
Sumber :
- https://en.wikipedia.org/wiki/String_searching_algorithm
- Munir, Rinaldi. 2011. Algoritma & Pemograman Dalam Bahasa Pascal dan C Edisi Revisi. Bandung : Informatika Bandung.
- Munir Rinaldi, Diktat Kuliah Strategi Algoritmik, 193, 2005.
- Anany Levitin, Intro 2 Design&Analysis Algorithms.
EmoticonEmoticon