CARA MENCARI STRING DENGAN METODE
STRING
MATCHING, BOYER MOORE, DAN KMP
A. Pengertian Algoritma Pencarian String
(String Matching)
String
matching adalah
pencarian sebuah pattern pada sebuah teks . String matching digunakan
untuk menemukan suatu string yang disebut dengan pattern dalam string
yang disebut dengan teks,untuk string pendek di sebut pattern dan umtuk string yang lebih panjang di sebut pattern
1. Pattern, yaitu deretan
karakter yang akan dicocokkan dengan teks, dinyatakan dengan 𝑥[0…𝑚−1],
panjang pattern dinyatakan dengan 𝑚.
2. Teks, yaitu tempat pencocokan pattern
dilakukan. Dinyatakan dengan 𝑦[0…𝑛−1], panjang
teks dinyatakan dengan 𝑛.
3. Alfabet, berisi semua simbol yang digunakan oleh bahasa
pada teks dan pattern, dinyatakan dengan Σ dengan ukuran dinyatakan ASIZE.
algoritma pencarian string ini dapat juga di klasifikasikan menjadi 3 bagian menurut arah pencariannya,berikut ini adalah algoritma yang termasuk dalam algoritma ini,
· Dari
arah yang paling alami yaitu dari kiri ke kanan, yang merupakan arah untuk
membaca, algoritma yang termasuk kategori ini adalah:
1. Algoritma
Brute Force. Anda bisa membaca lebih detail tentang algoritma tersebut
pada judul artikel ini "Algoritma Brute Force"
2. Algoritma
dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt
· Kategori
kedua yaitu dari arah kanan ke kiri, arah yang biasanya menghasilkan hasil
terbaik secara praktikal, contohnya adalah:
1. Algoritma
dari Boyer dan Moore, yang kemudian banyak dikembangkan, menjadi Algoritma
turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka.
Berikut contoh untuk mencari string matching :
Teks :a d i r i f a l d i
Pattern :a l d i
Teks
|
A
|
D
|
I
|
R
|
I
|
F
|
A
|
L
|
D
|
I
|
Shift1
|
A
|
L
|
D
|
I
|
||||||
Shift2
|
A
|
L
|
D
|
I
|
||||||
Shift3
|
A
|
L
|
D
|
I
|
||||||
Shift4
|
A
|
L
|
D
|
I
|
||||||
Shift5
|
A
|
L
|
D
|
I
|
||||||
Shift6
|
A
|
L
|
D
|
I
|
||||||
Shift7
|
A
|
L
|
D
|
I
|
di atas berhenti pada langkah ke 7 sudah
menemukan kata yang cocok pada langkah ke 7
B.ALGORITMA
BOYER-MOORE (STRING MATCHING)
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.
Secara
sistematis, langkah-langkah yang dilakukan algoritma Boyer-Moore
pada
saat mencocokkan string adalah :
1.
Algoritma Boyer-Moore mulai mencocokkan pattern pada awal teks.
2.
Dari kanan ke kiri, algoritma ini akan mencocokkan karakter per karakter
pattern dengan karakter di teks
yang bersesuaian, sampai salah satu kondisi
berikut
dipenuhi :
a.
Karakter di pattern dan
di teks yang dibandingkan tidak cocok
(mismatch).
b.
Semua karakter di pattern cocok.
Kemudian algoritma akan
memberitahukan
penemuan di posisi ini.
3.
Algoritma kemudian menggeser pattern dengan memaksimalkan nilai
penggeseran
good-suffix dan penggeseran bad-character, lalu mengulangi
langkah 2 sampai pattern berada di ujung teks.
Berikut contoh untuk algoritma boyer-moore:
TEKS :
A D I R I F A L D I
PATTERN :A
L D I
indeks
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
T
|
A
|
D
|
I
|
R
|
I
|
F
|
A
|
L
|
D
|
I
|
p
|
A
|
L
|
D
|
I
|
||||||
Menentukan nila Occurence Heuristic
(OH) dan Match Heuristic (MH).
posisi
|
1
|
2
|
3
|
4
|
string
|
A
|
L
|
D
|
i
|
OH
|
3
|
2
|
1
|
0
|
MH
|
4
|
4
|
4
|
1
|
Dari tabel di atas dapat di lihat bahwa nilai OH dan MH:
OH=3 2 1 0
MH=4 4 4 1(nilai 4 ialah jumlah karakter pada pattern,dan nilai 1 merupakan
default atau ketetapan)
Algoritma boyer-moore mulai mencocokan pattern dari kanan ke kiri,algoritma
ini akan mencocokan perkarakter karakter di teks yang bersesuian ,dengan
menggeser pattern dengan memaksimalkan pattern
dengan nilai penggeseran good-suffix(OH) dan penggeseran bad-character(MH).
Tahap 1
A
|
D
|
I
|
R
|
I
|
F
|
A
|
L
|
D
|
I
|
A
|
L
|
D
|
I
|
||||||
Karakter ‘R’ tidak cocok dengan ‘I’ tabel OH karakter “R” nilai
pergeseranya=4,tabel MH ketikcocokan pada posisi 4 karakter ‘I’ nilai
pergeserannya 1,sehinggga geser sebesar 4 posisi (nilai maksimal dari kedua
tabel pergeseran)
Tahap 2
A
|
D
|
I
|
R
|
I
|
F
|
A
|
L
|
D
|
I
|
A
|
L
|
D
|
I
|
Karakter “L” tidak cocok dengan “i” tabel OH karakter “L” nilai
pergeserannya 2, tabel MH ketidakcocokan pada posisi 4 karakter “I” nilai
pergeserannya 1
Sehinggga geser sebesar 2 posisi(nilai maksimal dari kedua tabel
pergeseran)
Tahap 3
A
|
D
|
I
|
R
|
I
|
F
|
A
|
L
|
D
|
I
|
A
|
L
|
D
|
I
|
Dari pergeseran sebelumnya maka karakter pattern pada teks cocok,ketika
seluruh pattern berhasil di cocokan,maka algoritma akan berhenti dan
mengembalikan status pattern tersebut pada teks,algoritma pun selesai.
C. Algoritma String
Matching Knuth-Morris-Pratt
Algoritma Knuth-Morris-Pratt
dikembangkan secara terpisah oleh Donald E. Knuth pada tahun 1967 dan James H.
Morris bersama Vaughan R. Pratt pada tahun 1966, namun keduanya
mempublikasikannya secara bersamaan pada tahun 1977.
Algoritma Knuth-Morris-Pratt (KMP)
merupakan algoritma yang digunakan untuk melakukan proses pencocokan string.
Algoritma ini merupakan jenis Exact String Matching Algorithm yang
merupakan pencocokan string secara tepat dengan susunan karakter dalam string
yang dicocokkan memiliki jumlah maupun urutan karakter dalam string yang sama,.
Secara sistematis, langkah-langkah yang dilakukan algoritma
Knuth-Morris-Pratt pada saat mencocokkan string:
1.
String pattern (kata yang dicari) akan dipecah menjadi array karakter.
String text (teks, artikel, dsb) akan dipecah menjadi array karakter
2.
Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks.
3.
Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter
pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut
dipenuhi:
A. Karakter di pattern
dan di teks yang dibandingkan tidak cocok (mismatch).
B. Semua karakter di
pattern cocok. Kemudian algoritma akan memberitahukan
penemuan di posisi ini.
4.
Algoritma kemudian menggeser pattern berdasarkan tabel next, lalu
mengulangi langkah 2 sampai pattern berada di ujung teks.
Contoh algoritma KMP
No
|
pattern
|
P
|
nilai
|
S
|
1
|
A
|
-
|
0
|
-
|
2
|
AL
|
A
|
0
|
L
|
3
|
ALD
|
A,AL
|
0
|
LD,D
|
4
|
ALDI
|
A,AL,ALD
|
0
|
LDI,DI,I
|
P(J) =A L D I
B (j) =0 0 0 0
Algoritma Knuth-Morris-Pratt
mulai mencocokkan pattern, Dari kiri ke kanan.
TEKS
|
a
|
d
|
i
|
r
|
i
|
f
|
a
|
l
|
d
|
i
|
pattern
|
a
|
l
|
d
|
I
|
||||||
a
|
l
|
d
|
I
|
|||||||
a
|
l
|
d
|
I
|
|||||||
a
|
l
|
d
|
I
|
|||||||
a
|
l
|
d
|
I
|
|||||||
a
|
l
|
d
|
I
|
|||||||
a
|
l
|
d
|
i
|
Kelebihan dan Kekurangan
Kelebihan dari algoritma Knuth-Morris-Pratt selain cepat juga sangat baik
digunakan pada file berukuran besar karena pencarian kecocokan tidak perlu
kembali ke belakang pada input teks.
Namun algoritma ini memilki kekurangan yakni efektifitas dari algoritma ini
akan berkurang seiring dengan bertambahnya jumlah jenis karakter dari teks.
Semoga bermanfaat
Mantap
ReplyDeleteIye
ReplyDelete