Cara Membuat Foto Mozaik dengan CorelDRAW X7 Tutorial CorelDraw

Tutorial Corel DRAW; cara memotong gambar dan menganti background

fungsi tool pada kelompok SHAPING pada coreldraw tutorial corelDRAW #part 2

fungsi tool dalam kelompok SHAPING pada coreldraw tutorial corelDRAW

vektor art

olahraga

sepak bola 
ini adalah team SEPAK BOLA yang ada di kampung saya(PENGAWU)kota palu,
pemainnya adalah pemain asal pengawu sendiri yang terdiri dari pemuda pemuda yang kuat akan rasa persaudaraan..
sepak bola adalah bahasa universal.itu yang membuat orang orang tertarik dengan olahraga tersebut.
sepak bola adalah bahan paling umum dalam proses sosialisasi,karena sepak bola bukan sekedar olahraga permainan.lebih dari itu sepak bola adalah pemersatu banyak perbedaan,keseruannya bisa membuat orang lupa dengan latar belakang mereka,,itulah sepak bola bisa membuat banyak perubahan lawan bisa jadi teman..olahraga yang di mainkan dengan waktu 90 menit...

semangat anak muda
olahraga yes
narkoba no

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

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