Source Code Aplikasi Algoritma Boyer Moore

Algoritma

Source Code Aplikasi Algoritma Boyer Moore. Untuk pseudo code algoritma boyer moore di bagi menjadi dua tahapan dalam penyelesaiannya:

1. Pencocokan

Pencocokan merupaan penyesuaian antara pattern dengan dokumen yang akan di cari. Dalam kasus ini biasanya berupa string. Dalam istilah algoritma ini, tahap pencocokan di kenal dengan istilah pra-pencarian atau proses yang dilakukan sebelum pencarian dilakukan.

procedure preBmBc(
input P : array[0..n-1] of char,
input n : integer,
input/output bmBc : array[0..n-1] of integer
)
Deklarasi:
i: integer

Algoritma:
for (i := 0 to ASIZE-1)
bmBc[i] := m;
endfor
for (i := 0 to m – 2)
bmBc[P[i]] := m – i – 1;
endfor

////////////////////////

procedure preSuffixes(
input P : array[0..n-1] of char,
input n : integer,
input/output suff : array[0..n-1] of integer
)

Deklarasi:
f, g, i: integer

Algoritme:
suff[n – 1] := n;
g := n – 1;
for (i := n – 2 downto 0) {
if (i > g and (suff[i + n – 1 – f] < i – g))
suff[i] := suff[i + n – 1 – f];
else
if (i < g)
g := i;
endif
f := i;
while (g >= 0 and P[g] = P[g + n – 1 – f])
–g;
endwhile
suff[i] = f – g;
endif
endfor

////////////////////////

procedure preBmGs(
input P : array[0..n-1] of char,
input n : integer,
input/output bmBc : array[0..n-1] of integer
)
Deklarasi:
i, j: integer
suff: array [0..RuangAlpabet] of integer

preSuffixes(x, n, suff);

for (i := 0 to m-1)
bmGs[i] := n
endfor
j := 0
for (i := n – 1 downto 0)
if (suff[i] = i + 1)
for (j:=j to n – 2 – i)
if (bmGs[j] = n)
bmGs[j] := n – 1 – i
endif
endfor
endif
endfor
for (i = 0 to n – 2)
bmGs[n – 1 – suff[i]] := n – 1 – i;
endfor

2. Pencarian

Setelah string dari pattern cocok atau sesuai dengan dokumen maka pencarian mulai dilakukan dan disesuaikan dengan patternya di cari, dan beriku pseudocode dari pencariannya:

procedure BoyerMooreSearch(
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, shift, bmBcShift, bmGsShift: integer
BmBc : array[0..255] of interger
BmGs : array[0..n-1] of interger

Algoritma:
preBmBc(n, P, BmBc)
preBmGs(n, P, BmGs)
i:=0
while (i<= m-n) do
j:=n-1
while (j >=0 n and T[i+j] = P[j]) do
j:=j-1
endwhile
if(j < 0) then
ketemu[i]:=true;
endif
bmBcShift:= BmBc[chartoint(T[i+j])]-n+j+1
bmGsShift:= BmGs[j]
shift:= max(bmBcShift, bmGsShift)
i:= i+shift

Aplikasi

Berikut ini aplikasi yang saya kembangkan pada aplikasi filtering pada sebuah dokumen teks. Yang mana patter dan dokumen di simpan pada tabel database mysql.

Modul Aplikasi

User, merupakan modul yang digunakan untuk mengelola data user atau pengguna aplikasi
Filter, merupakan teks atau string yang berguna sebagai string pattern untuk mencari kata yang akan di filter
Teks, teks merupakan dokumen yang akan di cari menggunakan pattern
Chat, chat merupakan fitur tambahan yang saya tambahkan untuk melakukan chat antara admin dengan pengunjung
Laporan, merupakan modul yang berguna untuk mencetak laporan teks, filter

Struktur database

Berikut ini tabel beserta field-field yang ada pada setiap masing-masing tabelnya

Tabel user (idUser,username,password,nama)
Tabel filter (idFilter,filter)
Tabel teks (idTeks,teks)
Tabel chat (idUser,nama,chat)

Pengembangan

Program: PHP 5.+
Database: Mysql
Server: Testing di apache
Pengembangan yang tersedia (yii, laravel, ci / codeigniter)
Template Bootstrap

Demo Aplikasi

sumber: https://id.wikipedia.org/wiki/Algoritma_Boyer-Moore