PENCOCOKAN STRING
Algoritma Knuth-Morris-Pratt
Dalam Algoritma Knuth-Morris-Pratt (KMP), untuk setiap karakter yang dibandingkan kita bisa memutuskan apakah berhasil atau gagal. Algoritma KMP membangun sebuah mesin automata yang status-statusnya adalah status dari string yang sedang kita cari. Dan setiap status memiliki fungsi berhasil dan gagal. Berhasil artinya status akan bergerak lebih mendekat ke status akhir dan gagal artinya status bisa jadi semakin jauh atau tetap terhadap status akhir. Kita akan mendapatkan sebuah karakter dari text saat kita berhasil dalam membandingkan dan akan mereuse karakter bila kita gagal. Contohnya : Perbandingan yang gagal paling banyak adalah sejumlah S-1 kali. Dan yang membuat algoritma ini lebih baik dari brute-force adalah jumlah perbandingan yang lebih sedikit dari algoritma standar brute force. Kompleksitas brute force adalah O(S * T) , sedangkan algoritma KMP memiliki kompleksitas O(S + T).
Contoh proses :
. String pattern (kata yang dicari) akan dipecah menjadi array karakter
. String text (teks, artikel, dsb) akan dipecah menjadi array karakter
. Menentukan lompatan yang akan dilakukan ketika pencarian (funsi preKMP())
. Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks. ()
. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
. Algortima kemudian menggeser pattern berdasarkan tabel next (lompat), lalu mengulangi lngkah 2 sampai pattern berada di ujung teks
. String pattern (kata yang dicari) akan dipecah menjadi array karakter
. String text (teks, artikel, dsb) akan dipecah menjadi array karakter
. Menentukan lompatan yang akan dilakukan ketika pencarian (funsi preKMP())
. Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks. ()
. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
. Algortima kemudian menggeser pattern berdasarkan tabel next (lompat), lalu mengulangi lngkah 2 sampai pattern berada di ujung teks
Algoritma Brute Force
Brute Force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan. Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way).
Secara sistematis, langkah-langkah yang dilakukan algoritma brute force pada saat mencocokkan string adalah:
- Algoritma brute force mulai mencocokkan pattern pada awal teks.
- Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
- . Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
- Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
- Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks.
Berikut adalah Algoritma brute force yang sedang bekerja mencari string:
Pseudocode algoritma brute force ini:
procedure BruteForceSearch(
input m, n : integer,
input P : array[0..n-1] of char,
input T : array[0..m-1] of char,
output ketemu : array[0..m-1] of boolean
)
Deklarasi:
i, j: integer
Algoritma:
for (i:=0 to m-n) do
j:=0
while (j < n and T[i+j] = P[j]) do
j:=j+1
endwhile
if(j >= n) then
ketemu[i]:=true;
endif
endfor
Kelemahan pencarian string
1. Kemungkinan ada karakter teks yang hilang.
2. Kemungkinan ada karakter yang hilang dari string (pattern).
3. Kemungkinan ada karakter didalam string atau teks yang mungkin di tambahkan, diganti, atau dihilangkan.Referensi