Algoritma Pencarian String dengan metode String Matching, Boyer Moore, dan KMP.

Algoritma adalah langkah-langkah yang disusun secara tertulis dan berurutan untuk menyelesaikan suatu masalah.  Sedangkan Algoritma Pemrograman adalah langkah-langkah yang ditulis secara berurutan untuk menyelesaikan masalah pemrograman komputer.

Dalam pemrograman yang sederhana, algoritma merupakan langkah pertama yang harus ditulis sebelum menuliskan program. Masalah yang dapat diselesaikan dengan pemrograman komputer adalah masalah-masalah yang berhubungan dengan perhitungan matematik.

Hal yang penting dikuasai dalam pemrograman adalah logika berpikir bagaimana cara memecahkan masalah pemrograman yang akan dibuat. Kadang-kadang ada masalah matematika yang sangat gampang jika diselesaikan secara tertulis, tetapi cukup sulit jika diterjemahkan ke dalam pemrograman. Jika menemukan hal seperti itu, maka algoritma dan logika pemrograman sangat penting untuk memecahkan masalah !!!!!!!

Nahh Kali Ini Saya Akan Berbagi Ilmu Terkait Algoritma Pencarian String Dengan Menggunakan Metode String Matching, Boyer Moore, Dan KMP !!

Selamat Belajar.....

Algoritma pencarian string merupakan salah satu bagian terpenting dalam berbagai proses yang berkaitan dengan data dengan tipe teks. Berbagai perangkat lunak yang digunakan di seluruh dunia saat ini dengan sejumlah sistem operasi berbeda, menggunakan algoritma pencarian string sebagai dasar implementasi. Meskipun terdapat berbagai metode dan bentuk penyimpanan data yang telah dikembangkan hingga saat ini, tetapi tipe data teks masih merupakan bentuk utama pada proses transfer data. Fakta tersebut mendorong perkembangan berbagai algoritma pencarian string yang mangkus sehingga memberikan hasil yang akurat dengan waktu singkat. Hingga saat ini terdapat puluhan algoritma pencarian string yang dapat dikelompokkan berdasarkan jenis pola dan metode pencocokan string yang digunakan, beberapa contoh algoritma pencarian string diantaranya adalah algoritma string matching yang merupakan algoritma paling sederhana, algoritma Knuth-Morris-Pratt (KMP), algoritma Boyer-Moore, algoritma dua jalur, algoritma Raita, algoritma quick search dan algoritma alpha skip.

Kata kunci: algoritma sting matching, boyer moore, dan Knuth-Morris-Pratt(KMP).

Algoritma pencarian string banyak digunakan pada proses pencarian data pada suatu kumpulan data, tidak hanya pada bidang teknologi komputer semata, melainkan juga pada berbagai bidang keilmuan yang membutuhkan penyimpanan data dalam jumlah besar untuk kemudian dilakukan pencarian dan pengubahan data sesuai perubahan situasi dan kondisi. Algoritma pencarian string bekerja dengan menghasilkan satu atau lebih pola suatu string tertentu dalam sebuah tipe data teks sebagai kumpulan string. Dengan demikian, algoritma pencarian string.

membutuhkan minimal dua data masukan, yaitu string yang akan dicari dan data teks atau string yang lebih panjang sebagai lokasi pencarian. Algoritma pencarian string bekerja dengan memanfaatkan konsep automata, yaitu proses dibagi menjadi sejumlah kondisi berbeda sesuai masukan yang telah diproses. Berdasarkan arah pemeriksaan karakter, metode yang digunakan dikelompokkan menjadi :

1. Metode pembacaan berawal dari posisi kiri mengarah ke kanan, salah satu contohnya adalah algoritma Knut-Morris-Pratt. Metode ini tergolong alamiah karena sesuai dengan arah pembacaan biasa dan memiliki karakteristik seperti proses pada automata.

2. Metode pembacaan berawal dari posisi kanan mengarah ke kiri, misalnya algoritma BoyerMoore. Metode ini umumnya menghasilkan algoritma yang sederhana dan dianggap paling mangkus.

3. Metode pencarian dengan aturan tertentu, salah satunya adalah pencarian dua arah yang diawali dengan kemunculan algoritma dua jalur yang dicetuskan oleh Crochemore-Perrin. Metode ini melakukan dua jenis pencarian, yang pertama adalah mencari bagian kanan pola dari kiri ke kanan, dan jika tidak ada ketidakcocokan, pencarian dilanjutkan dengan bagian kiri.

4. Metode yang tidak memiliki suatu pola tertentu, biasanya algoritma ini menggunakan sebagian metode dari algoritma pada tiga kelompok di atas yang dikombinasikan dengan metode lain, contohnya adalah algotima quick search.

Pada kali ini hanya akan membahas tiga algoritma pencarian string, yaitu algoritma string matching, algoritma boyer moore, dan algoritma KnuthMorris-Pratt (KMP). Pembahasan mencakup metode pencocokan yang digunakan dan variasi yang mungkin pada bentuk implementasi algoritma pada bahasa pemrograman C, berikut beberapa penamaan variabel dan fungsi atau prosedur standar yang digunakan :

·    char* input, data teks sebagai sumber pencarian

·    char* tes, pola string yang akan dicari

·    int len_i, variabel jumlah karakter pada input

·    int len_t, variabel jumlah karakter pada tes

·         int getLenStr(char* str), fungsi penghitung jumlah karakter pada sebuah   string

·         void output(int x), prosedur pengembali nilai hasil pencarian

·         int memcmp(char* b1, char* b2, int len), fungsi bawaan dari bahasa C pada  library   “string.h” yang membandingkan byte string b1 dengan byte string b2 dan keduanya diasumsikan memiliki panjang len. Fungsi ini mengembalikan nilai 0 jika keduan string sama, atau nilai perbedaan karakter yang berbeda dalam byte.

1. Algoritma String Matching (Brute Force).

Algoritma pencarian string atau sering disebut juga algoritma pencocokan string yaitu algoritma untuk melakukan pencarian semua kemunculan string  pendek dan dan panjang, untuk string pendek yang disebut pattern dan  string yang lebih panjang yang disebut teks.

String pendek  =

String panjang = 

Jenis algoritma ini merupakan algoritma yang mencocokan sebuah pattern atau kata kunci dalam suatu data yang tersimpan antara indeks 0 sampai indeks n– m untuk mengetahui keberadaan pattern dalam suatu text . Text disini merupakan suatu data yang tersimpan dalam komputer sedangkan pattern merupakan kata kunci yang akan dicari dalam suatu data. Proses pencocokan satu huruf antara pattern dengan text  dari kiri ke kanan dengan ketentuan sebagai berikut :  

1. karakter atau huruf di pattern dan di text yang di bandingkan tidak cocok, maka dilakukan pergeseran sebanyak 1 kali.

2.  Jika semua karakter pattern cocok dengan text, maka tidak ada lagi pergeseran., program akan memberitahukan penemuan  pada posisi ini dan menambahkan nilai suatu variabel sebagai banyaknya pattern yang ditemukan  dalam text.

Contoh :

T

=

A

L

E

X

A

N

D

E

R

T

E

O

L

E

M

B

A

N

G

P

=

T

E

O

Pada contoh diatas terjadi pergeseran sampai Shift = 11, sehingga telah di temukan kata kunci “TEO” yang dicari pada suatu data.

2. Algoritma Boyer Moore.

Boyer-Moore merupakan sebuah cara untuk mencocokan sebuah String dari kanan ke kiri. Sebuah teks dicocokan dengan pattern tertentu untuk menentukan apakah dalam teks yang dicocokan terdapat pattern tersebut.
Perbedaan pencocokan String Boyer-Moore dengan pencocokan String secara Brute Force adalah pada Algoritma Boyer-Moore tidak semua String dicocokan seperti pada cara Brute Force. Ketika Ada text dan pattern yang terjadi Mismatch, maka pattern akan mencocokan text meloncat menurut nilai pada tabel delta atau sebanyak jumlah karakter  yang telah dicocokan. Hal ini tergantung nilai maksimum yang terdapat dari keduanya.

Secara sistematis, langkah-langkah yang dilakukan algoritme Boyer-Moore pada saat mencocokkan string adalah:

1.         Menentukan nilai OH(BMBC) dan MH(BMGS).

2.         Algoritme Boyer-Moore mulai mencocokkan pattern pada awal teks.

3.         Dari kanan ke kiri, algoritme ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:

1.             Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).

2.             Semua karakter di pattern cocok. Kemudian algoritme akan memberitahukan penemuan di posisi ini.

4.         Algoritme kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix(OH) dan penggeseran bad-character(MH), lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

Contoh :

T

=

A

L

E

X

A

N

D

E

R

T

E

O

L

E

M

B

A

N

G

P

=

T

E

O

Menentukan nilai OH(BMBC) dan MH(BMGS).

	T	E	O
0			0
1		1
2	2

Dari tabel di atas dapat dilihat bahwa nilai OH  dan MH :

OH = 2 1 0

MH = 3 3 1 (dimana nilai 3 merupakan jumlah karakter pada pattern, dan nilia 1 merupakan default atau suatu ketetapan).

Algoritme Boyer-Moore mulai mencocokkan pattern Dari kanan ke kiri, algoritme ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, dengan menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix(OH) dan penggeseran bad-character(MH).

1. Pada pergeseran ke 1 karakter “O” pada pattern tidak cocok dengan karakter “E” pada teks, maka pergeseran berdasarkan nilai dari tabel OH, karena Pada tabel OH karakter E bernilai 1, maka pergeseran dilakukan sebanyak 1 kali.

2. pada pergeseran 2-4, karakter pattern berturut-turut O, O, dan O, tidak cocok dengan karakter pada teks berturut-turut X, D, dan SPASI, maka pergeseran di lakukan berdasarkan jumlah karakter pattern, karena karakter X, D, dan spasi tidak mempunyai nilai pada OH.

3. Pada tahap ke 5 tidak dilakukan pergeseran, karena pattern telah ditemukan, dan proses pencarian pattern berhenti dan tidak ada lagi pergeseran ke indeks berikutnya.

3. Algoritma KMP.

Algoritma Knuth Morris Pratt (KMP) dikembangkan oleh D. E. Knuth, bersama dengan J.H. Morris dan V. R.Pratt. Algoritma Knuth Morris Pratt bekerja dengan memanfaatkan pergeseran yang semaksimal mungkin dalam pencocokan string dalam teks. Jenis algoritma ini merupakan proses matching yang dilakukan untuk mengetahui jumlah penggeseran yang dilihat dari kesamaan String antara prefix dan suffix.

Langkah-langkah yang dilakukan algoritma Knuth-Morris-Pratt pada saat mencocokkan string yaitu (modifikasi):

1.            String pattern (kata yang dicari) akan dipecah menjadi array karakter

2.            String text (teks, artikel, dsb) akan dipecah menjadi array karakter

3.            Menentukan lompatan yang akan dilakukan ketika pencarian (funsi  preKMP())

4.            Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks. ()

5.         Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:

6.            Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).

7.            Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.

8.            Algoritma kemudian menggeser pattern berdasarkan tabel next (lompat), lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

Contoh :

T

=

A

L

E

X

A

N

D

E

R

T

E

O

L

E

M

B

A

N

G

P

=

T

E

O

No	Pattern	P	nilai	S
1	T	no perfix	0	no subfix
2	TE	T	0	E
3	TEO	T,TE	0	O, EO

          P(j) = T E O

            B(j) = 0 0 0

Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern, Dari kiri ke kanan.

teks

A

L

E

X

A

N

D

E

R

T

E

O

L

E

M

B

A

N

G

pattern

T

E

O

T

E

O

T

E

O

T

E

O

T

E

O

T

E

O

T

E

O

T

E

O

T

E

O

T

E

O

T

E

O

Sekian Ilmu Yang Bisa Saya Bagi, Semoga Bermanfat !!!!!