Majalah Ilmiah UNIKOM

Vol.11 No. 2

266

H a l a m a n

Diana Effendi, Tono Hartono, Andri Kurnaedi

di suatu program, maka nama file judulnya

(header file) harus dilibatkan dalam

program yang menggunakannya dengan

preprocessor directive berupa #include.

String matching adalah pencarian

pattern

L. Rivest dkk. 1994). Prinsip kerja algoritma

string matching adalah sebagai berikut:

1. Memindai teks dengan bantuan sebuah

window yang ukurannya sama dengan

pattern

2. Menempatkan window pada awal teks.

3. Membandingkan karakter pada window

pattern

pencocokan (baik hasilnya cocok atau

tidak cocok), dilakukan shft ke kanan

pada window. Prosedur ini dilakukan

berulang-ulang sampai window berada

pada akhir teks. Mekanisme ini disebut

mekanisme sliding-window.

Algoritma

string

matching

mempunyai tiga komponen utama, yaitu:

Pattern

akan

dicocokkan

dengan

teks,

dinyatakan dengan x[0..m-1], panjang

pattern

pattern

dilakukan, dinyatakan dengan y[0..n-1],

panjang teks dinyatakan dengan n.

3. Alfabet, yang berisi semua simbol yang

digunakan oleh bahasa pada teks dan

pattern

ukuran dinyatakan dengan ASIZE.

Algoritma Boyer-Moore termasuk

algoritma string matching yang paling

efisien dibandingkan algoritma-algoritma

string matching lainnya (Ronald L. Rivest

dkk. 1994). Karena sifatnya yang efisien,

banyak dikembangkan algoritma string

matching dengan bertumpu pada konsep

algoritma

Boyer-Moore,

beberapa

di

antaranya adalah algoritma Turbo BM dan

algoritma Quick Search.

Algoritma Boyer-Moore menggunakan

metode pencocokan string dari kanan ke kiri

pattern

ke kiri dimulai dari karakter paling kanan.

Algoritma Boyer-Moore menggunakan dua

fungsi shift yaitu good-suffix shift dan bad-

character shift untuk mengambil langkah

berikutnya setelah terjadi ketidakcocokan

pattern

yang dicocokkan.

Stack adalah suatu bentuk khusus

dari linear list (suatu struktur data yang

merupakan himpunan terurut yang dapat

berkurang atau bertambah setiap saat) di

mana operasi penyisipan dan penghapusan

atas elemen-elemennya hanya dapat

dilakukan pada satu sisi saja yang disebut

sebagai “TOP”. Ada empat operasi dasar

yang didefinisikan pada stack, yaitu:

1. Create, operator ini berfungsi untuk

membuat sebuah stack kosong.

2. IsEmpty, operator ini berfungsi untuk

menentukan apakah suatu stack adalah

stack kosong.

3. Push, operator ini berfungsi untuk

menambahkan satu elemen ke dalam

stack.

4. Pop, operator ini berfungsi untuk

mengeluarkan satu elemen dari dalam

stack.

Dalam

penggunaannya,

untuk

menempatkan stack biasanya digunakan

sebuah array. Tetapi perlu diingat di sini

bahwa stack dan array adalah dua hal yang

berbeda. Selain itu penggunaan stack

dengan array dirasakan kurang tepat.

Penggunaan stack pada pembangunan

Translator ini menggunakan record sebagai

implementasi stack.

Tree

yang tidak linear/non linear yang digunakan

terutama

untuk

merepresentasikan

hubungan data yang bersifat hierarkis

antara

elemen-elemennya.

Kumpulan

elemen yang salah satu elemennya disebut

root

node/vertex

yang terpecah menjadi sejumlah himpunan

yang tidak saling berhubungan satu sama

subtree

Sebuah pohon biner T dapat

didefinisikan sebagai sekumpulan terbatas

dari elemen-elemen yang disebut nodes/

simpul dimana :

tree

empty tree

kosong)