String matching atau pencocokan string sering disebut juga algoritma pencarian string dapat didefinisikan sebagai algoritma untuk melakukan pencarian semua kemunculan string pendek (character) maupun string yang lebih panjang (teks). Jenis Algoritma String Matching diantaranya :
1.
Algoritma Brute Force
Adalah
algoritma pencocokan string yang memulai pencocokan pattern dari arah kiri ke
kanan. Algoritma brute force ini jarang di pakai dalam praktik karena algoritma
ini tidak memikirkan peforma.
Algoritma Brute_Force_Search;
DEKLARASI
:
i,
j, m, n : integer;
P
: array[0..n-1] of char;
T
: array[0..m-1] of char;
ketemu
: array[0..m-1] of boolean;
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
Adalah
algoritma pencocokan string yang memulai pencocokan pattern dari arah kanan
sehingga lebih banyak informasi yang didapat. Algoritma Boyer and Moore ini dianggap
paling efisien pada aplikasinya.
Algoritma Turbo_Boyer_and_Moore;
DEKLARASI
:
P := array[0..n-1] of
char;
T := array[0..m-1] of
char;
i, j, v1, v2, shift,
bnBcshift, bmGsShift, turboShift, m, n := integer;
ketemu:= array [0..m-1]
of boolean;
bmBc := array [0..255]
of integer;
BmBs := array [0..n-1]
of integer;
ALGORITMA :
preBmBc
(n,P, BmBc);
preBmGs
(n,P, BmGs);
i:=
v1 := 0;
shift
:= n;
while
I <= m-n do
j:=
n-1;
while
j >= 0 and T[i+j] = P[j] do
j:=
j-1
if
not v1 = 0 and I = m-1-shift
j:=
j-v1;
endwhile
if
j < 0 then
ketemu
[i] :=true;
shift:=bmGs[0];
v1:=
n-shift;
else
v2:=
n-1-j;
turboShift
:= v1-v2;
bmBcShift:=
BmBc[chartoint(T[i+j])] –n+j+1;
bmGsShift:=
bmGs[j];
shift
:= max(bmBcShift, BmGsShift);
shift
:= max(shift, turboShift)
if
shift = bmGs[i] then
v1:=
min(m-shift,v2)
else
if
turboShift<bmBcShift
shift:=
max(shift,v1+1)
endif
v1:=0;
endif
endif
i:=
i+shift;
endwhile
3.
Algoritma Collusi ( Livio Collusi 1994 )
Adalah
algoritma pencocokan string yang polanya membagi menjadi dua bagian/sub
himpunan yang di sebut lobang dan non-lubang. Algoritma ini membagi pencocokan
pada dua fase. Pada fase pertama mencocokan karakter-karakter non-lubang dari
kiri ke kanan dan pada fase kedua mencocokan karakter-karakter lubang dari
kanan ke kiri.
Algoritma Collusi;
DEKLARASI
:
i, j, m, n, nd, last :
interger;
P := array[0..n-1] of
char;
T := array[0..m-1] of
char;
ketemu :array[0..n-1]
of boolean;
h:= array[0..n] of
integer;
next:= array[0..n] of
integer;
shift:= array[0..n] of
integer;
ALGORITMA :
nd
:= preColussi (n, p,h, next, shift)
i
: = j : = 0;
last:=
-1;
while
(i<= m-n) do
while
(j < n and last , i+h[j] and T [i+h[j]] = P[h[j]]) do
j:
=j+1
endwhile
if
(j>nd) then
last
: = i+m-1
endif
i
: = i+shift[j]
j
: =next [j]
endwhile
Tidak ada komentar:
Posting Komentar