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 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:
- Algoritma Brute Force.
- 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:
- Algoritma dari Boyer dan Moore, yang kemudian
banyak dikembangkan, menjadi Algoritma turbo Boyer-Moore, Algoritma tuned
Boyer-Moore, dan Algoritma Zhu-Takaoka;
- Dan kategori terakhir yaitu adalah dari arah yang
ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan
hasil terbaik secara teoritis, algoritma yang termasuk kategori ini
adalah:
- Algoritma Colussi
- Algoritma Crochemore-Perrin
Persoalan
Pencarian String
Diberikan:
- teks (text), yaitu (long) string yang panjangnya
n karakter
- pattern, yaitu string dengan panjang m karakter
(m < n) yang akan dicari di dalam teks.
Carilah (find atau locate) lokasi pertama di dalam
teks yang bersesuaian dengan pattern.untuk bisa memahami persoalan diatas maka
akan saya berikan contoh dibawah ini.
Contoh 1:
Pattern: hari
Teks: kami
pulang hari kamis
^ target
Contoh 2:
Pattern: not
Teks: nobody noticed
him
^ target
Contoh 3:
Pattern: apa
Teks: Siapa
yang menjemput Papa dari kota Balikpapan?
Contoh
Pencarian String (String Matching) Dengan Algoritma Brute Force
Contoh 4:
Teks : nobody noticed him
Pattern : not
nobody noticed him
s=0 not
s=1 not
s=2 not
s=3 not
s=4 not
s=5 not
s=6 not
s=7 not
Pada contoh di atas berhenti pada langkah ke 7 karena
sudah menemukan kata yang cocok pada langkah ke 7
Contoh 5:
Teks: 10010101001011110101010001
Pattern: 001011
10010101001011110101010001
s=0 001011
s=1 001011
s=2 001011
s=3 001011
s=4 001011
s=5 001011
s=6 001011
s=7 001011
s=8 001011
Pada contoh di atas berhenti pada langkah ke 8 karena
sudah menemukan kata yang cocok pada langkah ke 8.
Ø Algoritma
Brute Force
Algoritma
brute force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan
peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktik, namun
berguna dalam studi pembanding dan studi-studi lainnya.
Cara kerja
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
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
Ø Algoritma
Knuth-Morris-Pratt
Algoritma
Knuth-Morris-Pratt adalah salah satu algoritma pencarian string,
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.
Jika kita melihat algoritma brute force lebih
mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang
dilakukan sebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan.
Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan
kecepatan pencarian.
Cara kerja
Perhitungan penggeseran pada
algoritma ini adalah sebagai berikut, bila terjadi ketidakcocokan pada saat
pattern sejajar dengan teks[i..i + n – 1], kita bisa menganggap
ketidakcocokan pertama terjadi di antara teks[I + j] dan pattern [j],dengan
0 < j < n.berarti, teks [i..i + j – 1] = pattern
[0..j – 1] dan a = teks [I + j]tidak sama dengan b
= pattern[j].Ketika kita menggeser, sangat beralasan bila ada sebuah
awalan udari pattern akan sama dengan sebagian akhiran udari
sebagian teks. Sehingga kita bisa menggeser pattern agar awalan utersebut
sejajar dengan akhiran dari u.dengan kata lain, pencocokan string
akan berjalan secara efesien bial kita mempunyai table yang menentukan berapa
panjang kita seharusnya menggeser seandainya terdeteksi ketidakcocokan di
karakter ke- jdari pattern. Tabel itu harus memuat next[j]yang
merupakan posisi karakter pattern[j]
setelah digeser, sehingga kita bisa menggeser pattern
sebesar j –next[j]relative terhadap teks.
Secara sistematis, langkah-langkah yang dilakukan
algoritma Knuth-Morris-Pratt pada saat mencocokkan string:
- Algoritma Knuth-Morris-Pratt muali
mencocokkan pattern pada awal teks.
- Dari kiri ke kanan, algoritma ini akan
mencocokkan karakter per-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 menggeser pattern berdasarkan
tabel next, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.
Pseudocode
Berikut adalah pseudocode algoritma KMP
pada fase pra-pencarian:
procedure preKMP(
input P :
array[0..n-1] of char,
input n :
integer,
input/output
kmpNext : array[0..n] of integer
)
Deklarasi:
i,j: integer
Algoritma
i := 0;
j :=
kmpNext[0] := -1;
while (i <
n) {
while (j
> -1 and not(P[i] = P[j]))
j :=
kmpNext[j];
i:= i+1;
j:= j+1;
if (P[i] =
P[j])
kmpNext[i] := kmpNext[j];
else
kmpNext[i] := j;
endif
endwhile
Dan berikut adalah pseudocode algoritma
KMP pada fase pencarian:
procedure KMPSearch(
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,next: integer
kmpNext : array[0..n] of interger
Algoritma:
preKMP(n, P, kmpNext)
i:=0
while (i<= 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
next:= j -
kmpNext[j]
i:= i+next
endwhile
Ø
Tidak ada komentar:
Posting Komentar