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

CARA MENCARI STRING DENGAN METODE STRING MATCHING, BOYER MOORE, DAN KMP

v Pengertian Algoritma Pencarian String (String Matching)

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  = 

Algoritma pencarian string ini dapat juga diklasifikasikan 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 unuk mencari string matching :

Teks : moh fadli

Petter : fadli

1.       String Matching

T =	m	o	h		f	a	d	l	i
P =	f	a	d	l	i

m	o	h		f	a	d	l	i
f	a	d	l	i
	f	a	d	l	i
		f	a	d	l	i
			f	a	d	l	i
				f	a	d	l	i

Pada contoh di atas terjadi pergeseran sebanyak 5 kali, sehingga telah di temuka kata kunci (fadli) yang akan kita cari.

v  Boyer-Moore String Matching

Boyer-Moore String Matching 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.

Contoh :

Diketahui sebuah teks : moh fadli

dan Pattern : fadli

2.    Boyer Moore

	1	2	3	4	5	6	7	8	9
T =	m	o	h		f	a	d	l	i
P =	f	a	d	l	i

Menentukan nilai OH dan MH

	f	a	d	l	i
0					0
1				1
2			2
3		3
4	4

Dari table di atas dapat dilihat bahwa nilai OH dan MH

OH : 4 3 2 1 0

MH : 5 5 5 5 1 (dimana nilai 5 merupakan jumlah karakter pada pettern, dan nilai 1 merupakan ketetapan).

	1	2	3	4	5	6	7	8	9
teks	m	o	h		f	a	d	l	i
	f	a	d	l	i
		f	a	d	l	i
			f	a	d	l	i
				f	a	d	l	i
					f	a	d	l	i

Penjelasan :

1.       Ketika dicocokan pertama kali, Indeks ke-5 pada teks (I) tidak cocok dengan pattern pertama paling kanan (F). Hal ini membuat pattern digeser sejauh nilai maksimal dari tabel delta atau sejumlah pergeseran teks. Dicari nilai maksimal dari nilai delta huruf I yakni 1 (lihat tabel delta) dan pergeseran pattern masih 1 kali. Sehingga pattern digeser sejauh 1 langkah.

2.        pada pergeseran 2-4, karakter pattern berturut-turut I, I, dan I, tidak cocok dengan karakter pada teks berturut-turut A, D, dan L, maka pergeseran di lakukan berdasarkan jumlah karakter pattern.

3.       pencocokan kelima yakni pada indeks ke-9. Setelah dilakukan pengecekan dari kanan ke kiri teks terhadap pattern, ditemukan kecocokan seluruh pattern pada teks. Ketika Seluruh pattern telah berhasil dicocokan, maka algoritma akan berhenti dan mengembalikan status pattern tersebut terdapat pada teks. Algoritma pun selesai

3.    KMP

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.

No	Pattern	P	Nilai	S
1	f	No perfix	0	No subfix
2	fa	f	0	a
3	fad	f,fa	0	d,ad
4	fadl	f,fa,fad	0	i,dl,adl
5	fadli	f,fa,fad,fadl	0	i,li,dli,adli

P(j)      : f a d l i

B(j)      : 0 0 0 0 0

teks	M	O	H		F	A	D	L	I
pattern	F	A	D	L	I
		F	A	D	L	I
			F	A	D	L	I
				F	A	D	L	I
					F	A	D	L	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.

SEKIAN MATERI YANG BISA SAYA BUAT, APA BILA ADA KEKELIRIHAN DAN KESALAHAN DALAM MATERI YANG SAYA BUAT, SAYA MOHON MAAF