Source Code Aplikasi Algoritma Boyer Moore

By , August 7, 2017,

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

  1. User, merupakan modul yang digunakan untuk mengelola data  user atau pengguna aplikasi
  2. Filter, merupakan teks atau string yang berguna sebagai string pattern untuk mencari kata yang akan di filter
  3. Teks, teks merupakan dokumen yang akan di cari menggunakan pattern
  4. Chat, chat merupakan fitur tambahan  yang saya tambahkan untuk melakukan chat antara admin dengan pengunjung
  5. 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

  1. Tabel user (idUser,username,password,nama)
  2. Tabel filter (idFilter,filter)
  3. Tabel teks (idTeks,teks)
  4. Tabel chat (idUser,nama,chat)

Pengembangan

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

Demo Aplikasi

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

Postingan berikutnya

  1. cara membuat source code pada algoitma chat
  2. cara membuat source code pada algoritma chat

Leave a Reply

Your email address will not be published. Required fields are marked *