Thursday, July 5, 2018

Algoritma Pemrograman pencarian String menggunakan metode String Matching, Boyer Moore, dan KMP



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


 Naive String Matching Algorithm



Algoritma boyer moore




Knuth–Morris–Pratt algorithm





2 comments: