Pengembangan Algoritma Boyer Moore pada Translator Bahasa Pemrograman

Pengembangan Algoritma Boyer Moore pada Translator Bahasa Pemrograman Diana Effendi1) danAndri Kurnaedi2) Prodi Sistem Informasi, Fakultas Teknik dan Ilmu Komputer UniversitasKomputer Indonesia (UNIKOM), Bandung email :[email protected]) , [email protected])

Abstract Translator is an automatic solution for translating process of programmatic source code from a source language to a target language. Translator source language totarget language runs to do parsing source code, then it applies the rule of translating. In addition, it presents the result of the target translation. The intoducing and translating function can be created accurately. To gain the rule of translating needs to be compared the syntactic rule from target language and source language. The grammmar elements that must be explored are the structure of programme, the customs declarations(variable, type, constancy, etc), an expression, a statement, the regulation of the object naming of programme, etc. Using algorithm with fitting string, Boyer-Moore algorithm becomes an important option in translating process. Compounding the value of translator that is connected to the mastery improvement of the base programming knowledge, Hopefully it can be created a translator application with the superiority of academic point of view. Keywords :Translator, Boyer-Moore

I.Pendahuluan Seperti diketahui, proses alih kode perangkat lunak dari satu bahasa ke bahasa lain seringkali menjadi kendala dikalangan programmer. Ada berbagai alasan yang melatarbelakangi hal ini, contohnya ketidakcukupan penguasaan terhadap bahasa target, waktu, referensi, dan lain-lain. Keperluan alih kode bahasa pun dapat terjadi dengan alasan perubahan proses bisnis, integrasi, regulasi perusahaan, adaptasi dengan teknologi baru, hardware, maupun hal lainnya. Proses alih kode tidaklah mudah, terlebih jika kode sumber aplikasi yang diterjemahkan kompleks dan memiliki ukuran yang besar. Proses alih kode akan membutuhkan banyak waktu dan tenaga, serta rentan terhadap kesalahan. Maka diperlukan suatu solusi untuk melakukan proses alih kode secara otomatis dengan bantuan sebuah alat. Alat yang dimaksud adalah program yang dapat menterjemahkan kode sumber ke bahasa lain yang dikehendaki. Alat tersebut di kenal sebagai Translator. Translator adalah program yang menterjemahkan suatu huruf dengan himpunan terkecil hingga terbesar dari bahasa asal ke bahasa target. Untuk tujuan tersebut digunakan algoritma string matching yang mempunyai konsep pencarian sebuah pattern pada sebuah teks. Algoritma BoyerMoore termasuk algoritma string matching yang paling efisien dibandingkan algoritma-algoritma string matching lainnya. Karena sifatnya yang efisien, banyak dikembangkan algoritma string matching dengan bertumpu pada konsep algoritma

13

Jurnal Informatika, Vol 8, No 1, Juni 2012: 13 - 21

Boyer-Moore, beberapa di antaranya adalah algoritma Turbo BM dan algoritma Quick Search. II.LandasanTeori II.1 Algoritma String Matching String matching adalah pencarian sebuah pattern pada sebuah teks (Ronald L. Rivest dkk. 1994). Prinsip kerja algoritma string matching adalah sebagai berikut: 1. Memindai teks dengan bantuan sebuah window yang ukurannya sama dengan panjang pattern. 2. Menempatkan window pada awal teks. 3. Membandingkan karakter pada window dengan karakter dari pattern. Setelah 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 slidingwindow. Algoritma string matching mempunyai tiga komponen utama, yaitu: 1. Pattern, yaitu deretan karakter yang akan dicocokkan dengan teks, dinyatakan dengan x[0..m-1], panjang pattern dinyatakan dengan m. 2. Teks, yaitu tempat pencocokan 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, dinyatakan dengan ∑ dengan ukuran dinyatakan dengan ASIZE. II.2Algoritma Boyer-Moore Algoritma Boyer-Moore adalah salah satu algoritma pencarian string, dipublikasikan oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977. Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum.Tidak seperti algoritma pencarian string yang ditemukan sebelumnya, algoritma Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide dibalik algoritma ini adalah bahwa dengan memulai pencocokkan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat. Dimisalkan ada sebuah usaha pencocokan yang terjadi pada teks[i..i + n − 1], dan anggap ketidakcocokan pertama terjadi di antara teks[i + j] dan pattern[j], dengan 0 < j < n. Berarti, teks[i + j + 1..i + n − 1] = pattern[j + 1..n − 1] dan a = teks[i + j] tidak sama dengan b = pattern[j]. Jika u adalah akhiran dari pattern sebelum b dan v adalah sebuah awalan dari pattern, maka penggeseran-penggeseran yang mungkin adalah : 1. Penggeseran good-suffix yang terdiri dari mensejajarkan potongan teks[i + j + 1..i + n − 1] = pattern[j + 1..n − 1] dengan kemunculannya paling kanan di pattern yang didahului oleh karakter yang berbeda dengan pattern[j]. Jika tidak ada potongan seperti itu, maka algoritma akan mensejajarkan

14

Pengembangan Algoritma Boyer Moore pada Translator Bahasa Pemrograman (Diana Effendi , Andri Kurnaedi)

2.

akhiran v dari teks[i + j + 1..i + n − 1] dengan awalan dari pattern yang sama. Penggeseran bad-character yang terdiri dari mensejajarkan teks[i + j] dengan kemunculan paling kanan karakter tersebut di pattern. Bila karakter tersebut tidak ada di pattern, maka pattern akan disejajarkan dengan teks[i + n + 1].

Secara sistematis, langkah-langkah yang dilakukan algoritma Boyer-Moore pada saat mencocokkan string adalah : 1. Algoritma Boyer-Moore mulai mencocokkan pattern pada awal teks. 2. Dari kanan ke kiri, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi : a. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch). b. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini. 3. Algoritma kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix dan penggeseran bad-character, lalu mengulangi langkah 2 sampai pattern berada di ujung teks. III. Implementasi Algoritma Boyer-Moore pada Translator Fungsi utama pada Translator terhadap teks yang dibentuk menjadipernyataan atau serangkaian pernyataan bahasaasal yang akanditerjemahkan adalah pencocokan suatu pattern tertentu yang diasumsikan sebagai pemisah rangkaian pembentuk pernyataan bahasaasal. Pencocokan ini dilakukan untuk memenggal teks berdasarkan posisi pattern terhadap teks, sehingga teks dapat dikenali sebagai pernyataan bahasaasal dan diterjemahkan ke pernyataan bahasatujuan. Kaidah pertama dari algoritma Boyer-Moore ini adalah masing-masing karakter dari pattern pencocokan harus mempunyai kode ASCII yang sama terhadap target karakter yang ada pada teks serta karakter-karakter antara pattern dan target harus terurut sama persis. Kaidah yang kedua adalah hasil penerjemahan teks berdasarkan pencocokan pattern akan bernilai benar secara utuh jika teks telah sukses melalui proses compile pada bahasaasal. Walaupun demikian, Translator menerapkan fungsi-fungsi yang dapat memastikan kebenaran sintaksis pernyataan berdasarkan perolehan posisi pattern terhadap teks dan mengabaikan beberapa kesalahan sederhana pada sintaksis sehingga dapat diterjemahkan ke bentuk bahasatujuan. Dengan kata lain, suatu teks memungkinkan diterjemahkan secara utuh, sebagian, atau tidak sama sekali. Untuk itu, dibutuhkan suatu basis pengetahuan dalam pencocokan posisi dan pemenggalan pattern terhadap teks. III. 1 Pengembangan Cara Kerja Umum Algoritma Boyer-Moore

15


Secara umum, langkah-langkah dari teknik penerapan Boyer-Moore pada pencocokan pattern pada teks dapat direpresentasikan sebagai berikut : 1. Menjalankan prosedur preBmBc dan preBmGs untuk mendapatkan nilai perbandingan pergeseran. a. Menjalankan prosedur preBmBc. Fungsi dari prosedur ini adalah untuk menentukan berapa besar pergeseran yang dibutuhkan untuk mencapai karakter tertentu pada pattern dari karakter pattern terakhir/terkanan. Hasil dari prosedur preBmBc disimpan pada stack bmBc. b. Menjalankan prosedur preBmGs. Sebelum menjalankan isi prosedur ini, prosedur suffixdijalankan terlebih dulu pada pattern. Fungsi dari prosedur suffixadalah memenggal sejumlah karakter yang dimulai dari karakter terakhir/terkanan dengan sejumlah karakter yang dimulai dari setiap karakter yang lebih kiri. Hasil dari prosedur suffixdisimpan pada stack suff. Dengan demikian suff[i] mencatat panjang dari suffix yang cocok dengan segmen dari pattern yang di akhiri karakter ke-i. c. Dengan prosedur preBmGs, dapat diketahui berapa banyak langkah pada pattern dari sebuah segmen ke segmen lain yang sama, dimana letaknya lebih kiri dengan karakter di sebelah kiri segmen yang berbeda. Prosedur preBmGs menggunakan stack suff untuk mengetahui semua pasangan segmen yang sama. 2. Menjalankan prosedur BM, proses pencocokan pattern dengan menggunakan hasil dari prosedur preBmBc dan preBmGs yaitu stack bmBc dan bmGs sebagai landasan keputusan pergeseran. III.1.1 Prosedur preBmBc Prosedur preBmBc memiliki tiga nilai penting, diantaranya : 1. Pattern, sebagai subjek pencocokan terhadap teks. 2. Karakter, sebagai karakter-karakter yang terdapat pada pattern. 3. Occurence Heuristic (OH), sebagai nilai pergeseran yang diperoleh ketika menemukan ketidakcocokan karakter. 4. Pergeseran, sebagai nilai yang dicapai ketika melakukan pergeseran dari kanan ke kiri pattern. Contoh kasus : Pattern : MANAMAN Penyelesaian : Pada gambar 1, terlihat bahwa karakter yang ditunjuk akan ditambahkan ke dalam stack BmBc jika tidak ditemukan pada stack BmBc dengan nilai OH yang berkesesuaian dengan nilai pergeseran.

Pattern Pergeseran

16

M

A

N

A

M

↓ A 1

N

Stack BmBc Karakter A Nilai OH

M

N


Pattern Pergeseran

M

A

N

A

↓ M 2

A

N

Pattern Pergeseran

M

A

N

↓ A 3

M

A

N

A

M

A

N

↓ Pattern

M

A

M

↓ A 5

N

A

M

A

N

↓ M 6

A

N

A

M

A

N

M

A

N

A

M

A

↓ N 7

Pergeseran Pattern Pergeseran Pattern Pergeseran Pattern Pergeseran

N 4

Stack BmBc Karakter A Nilai OH 1 Stack BmBc Karakter A Nilai OH 1 Stack BmBc Karakter A Nilai OH 1 Stack BmBc Karakter A Nilai OH 1 Stack BmBc Karakter A Nilai OH 1 Stack BmBc Karakter A Nilai OH 1

M

N

M 2

N

M

N

2 M 2

N 4

M 2

N 4

M 2

N 4

Gambar 1 Penyelesaian contoh kasus Prosedur preBmBc III.1.2 Prosedur preBmGs Prosedur preBmGs memiliki enam nilai penting, diantaranya: 1. Pattern, sebagai subjek pencocokan terhadap teks. 2. Match Heuristic (MH), sebagai nilai pergeseran yang diperoleh ketika menemukan kecocokan suffix. 3. Compare, sebagai akhiran atau sejumlah karakter sebelah kanan dari sebuah karakter pattern yang diperoleh dari pergeseran kanan ke kiri. 4. Prefix, sebagai awalan atau karakter pattern yang diperoleh dari pergeseran dari kiri ke kanan. 5. Suffix, sebagai akhiran sebelah kanan prefix. 6. Pergeseran, sebagai nilai yang dicapai ketika melakukan pergeseran dari compare. Contoh kasus, Pattern : MANAMAN Penyelesaian : Tabel 1 Daftar pencacahan prefix dan suffix dari pattern Suffix (kanan-kiri) Prefix Suffix (kiri-kanan) Null M ANAMAN M A NAMAN MA N AMAN MAN A MAN MANA M AN MANAM A N

17


MANAMA

N

Null

Dari tabel 1, diasumsikan bahwa telah terjadi pemotongan pada kedua sisi suffix terhadap prefix pada pattern. Terlihat bahwa masing-masing suffix dipersatukan oleh prefix hingga menjadi satu kesatuan pattern utuh. Sedangkan null diartikan kosong, yakni semua kondisi pencocokan akan bernilai benar jika dilakukannya perbandingan terhadap karakter tersebut.Pada gambar 2 terlihat pergeseran pada comparememiliki peran utama dalam penentuan nilai MH. Berbeda dengan nilai OH, nilai MH selalu diberikan pada karakter-karakter yang ada pada pattern. Penyusunan stack BmGs pun berdasarkan urutan indeks posisi karakter pada pattern.

Compare Pergeseran

Stack compare MANAM MANA 2 3

MANAMA 1

↓ Pattern

M

A

N

A

M

A

N

Stack BmGs Karakter M Nilai MH

MAN 4

A -

MA 5

N -

A -

M 6

M -

Null 7

A -

N 1

OH selalu bernilai 1 ↓ Pattern

M

A

N

A

M

Cocok ada:

A

M

A

N

A

Cocok pada:

M

Null Null

A

A -

M

A

N

A

Prefix Cocok pada:

Suffix

N -

A -

M -

N 1

Pergeseran Suffix comparator ke 7

N -

A 4

M 7

A 7

N 1

M

A : Prefix Null Pergeseran Suffix MAN : Compare MAN comparator ke 4 ..... Stack BmGs Karakter M A N A M A N A N Nilai 4 4 4 4 7 7 1 MH

M (ANA) AN

: :

Prefix Compare

Null MAN

Pergeseran Compare ke 4

Gambar 2 Penyelesaian contoh kasus Prosedur preBmGs

18

A 7

Prefix Suffix

↓ Pattern

A : Prefix N : Compare ..... Stack BmGs Karakter M N Nilai MH

A -

Prefix Suffix

↓ Pattern

N

Stack BmGs Karakter M Nilai MH


III.1.3 Prosedur preBmGs Prosedur BM memiliki empat nilai penting, diantaranya : 1. Pattern, merupakan subjek pencocokan terhadap teks. 2. Teks, sebagai objek pencocokan. 3. Stack BmBc, sebagai pembanding ketika ditemukan ketidak cocokan. 4. Stack BmGs, sebagai pembanding ketika ditemukan kecocokan. Contoh kasus, Pattern : MANAMAN Teks : NAMANANAMMANAMAN Penyelesaian : Stack BmBc Karakter A Nilai OH 1

M 2

Stack BmGs Karakter M Nilai MH 4

N 4

A 4

N 4

A 4

M 7

A 7

N 1

Indeks

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Teks

N

A

M

A

N

A

N

A

M

M

A

N

A

M

A

N

Pattern

M

A

N

A

M

A

N M

A

N

A

M

A

N

2-0 banding 1, shift → 2

M

A

N

A

M

A

N

Pattern Pattern

4-2 banding 7, shift → 7

Gambar 3Penyelesaian contoh kasus Prosedur BM Pada gambar 3 terlihat bahwa pergeseran pada pattern selalu mengikuti keputusan dari hasil perbandingan OH dan MH. Pada umumnya, pencocokan standar akan mencocokan karakter per karakter, ketika ditemukan ketidakcocokan maka pattern akan digeser satu langkah ke arah selanjutnya. Namun tidak demikian pada algoritma Boyer-Moore. Penambahan proses pada algoritma Boyer-Moore yang dikembangkan, yaitu cek kualifikasi pattern dan database, serta terdapat proses kualifikasi pencocokan. Proses pengambilan nilai BmBc dan BmGs pada database dimaksudkan agar proses perhitungan nilai keputusan pergeseran oleh prosedur BmBc dan BmGs dapat menjadi lebih optimal, karena nilai keputusan telah tersimpan untuk beberapa pattern dengan nilai ketetapan.

19


Gambar4 Flowchart detail pengembangan algoritma Boyer-moore Namun proses filter pada database (recordset) membutuhkan estimasi waktu tertentu. Maka jika dibandingkan proses pencocokan nilai keputusan oleh prosedur preBmBc dan preBmGs untuk pattern yang lebih pendek, proses cek database akan menjadi lebih lama. Untuk itu, keputusan pengecekan database ditentukan dari parameter prosedur BM pada saat pemanggilan. Terdapat pula parameter plusPos yang berfungsi sebagai nilai tambah untuk setiap posisi yang ditemukan. plusPos digunakan pada saat pencocokan string yang membutuhkan posisi akhir, tengah, maupun posisi tertentu dari sebuah karakter yang terdapat pada pattern terhadap teks.Terdapat pula kriteria jumlah pencocokan, kriteria ini difungsikan sebagai parameter jumlah pencocokan yang dibutuhkan. Sebagai contoh, jika terdapat 10 kecocokan, maka pencocokan akan dihentikan ketika mencapai kecocokan ke-5, dimana 5 adalah

20


kriteria jumlah pencocokan. Sehingga menjadikan algoritma Boyer-Moore berjalan lebih optimal dan sesuai kebutuhan Translator. IV. Kesimpulan dan Saran Kesimpulan yang dapat diambil setelah memaparkan pembahasanpembahasan yang telah disajikan pada bahasa sebelumnya antara lain: Penerapan sebuah pencocokan string dapat dilakukan dengan menggunakan bermacam-macam algoritma pencocokan string, salah satunya adalah algoritma Boyer-Moore.Pada umumnya, pencocokan standar akan mencocokan karakter per karakter, ketika ditemukan ketidakcocokan maka pattern akan digeser satu langkah ke arah selanjutnya. Namun tidak demikian pada algoritma Boyer-Moore. Algoritma Boyer Moore disinisebagai pusat pemecahan pernyataan bahasa program yang akanditerjemahkansebagai awal proses penerjemahan dan ketika dibutuhkannya sebuah proses pencocokan string. Saran yang dapat diberikan penulis untuk pembaca yang berkeinginan mengembangkan Translator ini adalah : Algoritma Boyer Moore yang dikembangkandapatdiimplementasikanpada translator antarbahasapemrogramanmisalnyadari PASCAL ke C denganmembakukanalgoritma translator, sehinggadapatdiberlakukannyaaturanpenerjemahandiseluruhsisibahasa. VI. Daftar Pustaka [1] [2] [3] [4] [5] [6]

Charras, Christian.,Lecroq, Thierry., Handbook of Exact String-Matching Algotithms. Sommerville, Ian., Software Engineering (Rekayasa Perangkat Lunak), Erlangga. Jakarta, 2003. Thomas, H. Cormen, Charles E. Leiseson and Ronald L. Rivest, Algorithms. McGraw-Hill Book Company. North America, 1994. http://www.igm.univmlv.fr/~lecroq/string/node14.html#SECTION00140/ TanggalAkses : 2 Februari 2011. http://www.informatika.org/~rinaldi/Stimik/2007-2008/MakalahIF/MakalahIF 22512008.053.pdf/TanggalAkses: 6 Februari 2011. http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm/ TanggalAkses :3 Maret 2011.

21

Pengembangan Algoritma Boyer Moore pada Translator Bahasa Pemrograman

Recommend Documents