PENERAPAN ALGORITMA BOYER MOORE PADA APLIKASI PENGAJUAN JUDUL SKRIPSI BERBASI WEB

Volume : III, Nomor : 1, Mei 2014

Majalah Ilmiah

Informasi dan Teknologi Ilmiah (INTI) ISSN : 2339-210X

PENERAPAN ALGORITMA BOYER MOORE PADA APLIKASI PENGAJUAN JUDUL SKRIPSI BERBASI WEB Guidio Leonaerde Ginting Dosen Tetap Program Studi Teknik Informatika STMIK Budi Darma Medan Jl. Sisingamangaraja No.338 Simpang Limun Medan http:// www.inti-budidarma.com // Email : [email protected] Abstrak Perubahan dan pembaharuan dalam bidang teknologi informasi seperti otomatisasi dan komputerisasi telah berkembang dengan cepat dan menuntut kalangan industri dan praktisi yang berkecimpung didalamnya untuk lebih siap menghadapi kemajuan yang ada, dengan selalu mencari inovasi-inovasi baru sebagai solusi pemecahan dari setiap persoalan yang dihadapi. Dalam hal masalah yang dihadapi oleh lembaga pendidikan khususnya pendidikan perguruan tinggi swasta adalah masalah pengajuan judul skripsi yang diajukan oleh mahasiswa, dimana untuk mengajukan judul skripsi yang selama ini dikerjakan secara manual dalam memutuskan diterima atau ditolak judul yang diajukan oleh mahasiswa. Adapun cara yang dilakukan adalah dengan melakukan pencocokan judul skripsi yang diajukan dengan judul skripsi yang telah diterima. Jika judul skripsi yang diajukan dengan judul skripsi yang telah diterima menghasilkan karakter (string) yang sama dalam rentang tertentu maka judul skripsi dinyatakan tidak diterima dan jika judul skripsi yang diajukan dengan judul yang telah diterima menghasilkan karakter (string) yang tidak sama dalam rentang tertentu maka judul dinyatakan diterima. Algorima Boyer Moore adalah algorima salah satu dari pencarian string yang tepat dan terkenal yang digunakan dalam pencocokan pattern tunggal dan dianggap sangat cepat dalam kinerjanya. Algorita Boyer Moore menggunakan metode pencocokan string dari kanan ke kiri dengan men-scan karakter pattern mulai dari karakter paling kanan. Fungsi yang digunakan adalah good suffix shift dan bad-character shift apabila ditemukan ketidakcocokan antara karakter pattern dengan karakter teks. Berdasarkan hasil dari kesamaan string yang dihasilkan maka dalam rentang tertentu judul diputuskan diterima atau sebaliknya. Kata Kunci : string matching, searching, boyer moore, pattern matching 1. Pendahuluan 1.1. Latar Belakang Masalah Algoritma Booyer Moore banyak diterapkan terhadap proses pencarian. Fasilitas Find/Search pada berbagai aplikasi pengolah teks, web browser, dan aplikasi lainnya mungkin saja telah memanfaatkan algoritma Booyer-Moore dalam pencarian tersebut, karena algoritma Booyer Moore paling banyak diimplementasikan dalam berbagai aplikasi untuk fasilitas pencarian teksnya walaupun sebenarnya pencarian yang dilakukan dapat berupa pencarian terhadap teks, dokumen, atau juga file yaitu dengan melakukan pencocokan string antara kata kunci dengan objek yang dicari atau terhadap kata dengan mengacu pada sebuah database leksikal. Dalam suatu lembaga pendidikan telah banyak sistem informasi atau aplikasi yang digunakan untuk membantu kelancaran suatu pekerjaan. Perubahan dan pembaharuan dalam bidang teknologi informasi seperti otomatisasi dan komputerisasi telah berkembang dengan cepat dan menuntut kalangan industri dan praktisi yang berkecimpung didalamnya untuk lebih siap menghadapi kemajuan yang ada, dengan selalu mencari inovasi-inovasi baru sebagai solusi pemecahan dari setiap persoalan yang dihadapi. Dalam hal masalah yang dihadapi oleh lembaga pendidikan khususnya pendidikan perguruan tinggi

swasta adalah masalah pengajuan judul skripsi yang dialami dari tahun ke tahun, dimana untuk mengajuan judul skripsi yang selama ini di kerjakan secara manual dalam memutuskan diterima atau ditolak judul yang diajukan oleh mahasiswa. Untuk memecahkan masalah tersebut tentu saja diperlukan suatu aplikasi yang dapat mengurangi masalah tersebut. Dalam hal ini aplikasi yang diharapkan harus dapat menentukan judul skripsi yang diajukan dapat diterima atau tidak berdasarkan hasil perbandingan karakter string yang sama judul yang diajukan dengan judul yang telah diterima. Algoritma Boyer Moore menggunakan metode pencocokan string dari kanan ke kiri dengan men-scan karakter pattern mulai dari karakter paling kanan. Fungsi yang digunakan adalah good suffix shift dan bad-character shift apabila ditemukan ketidakcocokan antara karakter pattern dan karakter teks. Berdasarkan hasil dari kesamaan string yang dihasilkan maka dalam rentang tertentu maka judul diputuskan diterima dan sebaliknya. 1.2.

Perumusan Masalah Berdasarkan latar belakang di atas, maka permasalahan yang timbul dapat dirumuskan sebagai berikut : 1. Bagaimana algoritma Boyer Moore melakukan searching, retrieve, dan compare dengan

Penerapan Algoritma Boyer Moore Pada Aplikasi Pengajuan Judul Skripsi Berbasi Web. Oleh : Guidio Leonaerde Ginting

123


Majalah Ilmiah


2.

3.

menggunakan bahasa pemrograman PHP dan MySQL ?. Bagaimana menentukan sebuah judul skripsi diterima atau tidak berdasarkan persentasi rentang kesamaan string ? Bagaimana hasil penerapan algoritma Boyer Moore terhadap aplikasi pengajuan judul skripsi?

1.3.

Batasan Masalah Agar tidak melebar dari latar belakang dan permasalahan yang telah dijelaskan sebelumnya maka dalam menyelesaikan penelitian ini penulis membuat batasan masalah sebagai berikut : 1. Kesamaan arti suatu kata atau beberapa kata tidak mempengaruhi rentang kecocokan string antara judul yang diajukan dengan judul yang diterima. 2. Mahasiswa yang dapat mengajukan judul terhadap pengajuan judul skripsi hanya mahasiswa semester VII Medan. 3. E-skripsi dibangun dalam bentuk Website dengan menggunakan bahasa Pemograman PHP, CSS, dan MySQL. 4. Penentujuan judul diterima atau tidak diterima berdasarkan persentasi kecocokan antar judul yang diajukan dengan judul yang telah diterima yang ditentukan oleh pihak kampus. 2. Landasan Teori Dalam penulisan tesis ini, penulis akan memberikan beberapa pengertian yang berhubungan dengan judul penelitian yang diajukan, karena tanpa pengertian yang jelas akan menyebabkan informasi yang disajikan tidak sesuai dengan yang diharapkan. Teori-teori yang menjadi landasan dalam penulisan tesis ini antara lain teori kecerdasan buatan, string matching dan booyer moore karena metode yang digunakan dalam penelitian ini ada dalam bagian dari string matching dan string matching yang termasuk dalam kecerdasan buatan, dan pada tesis ini juga penulis juga menyampaikan jenis dan bentuk dari algoritma yang meliputi algoritma boyer moore, 2.1

Defenisi Kecedasan Buatan Ilmu yang mempelajari cara membuat komputer dapat bertindak dan memiliki kecerdasan seperti manusia disebut kecerdasan butan (Kursini, S.Kom, 2006) Bidang-bidang yang termasuk dalam kecerdasan buatan antar alain : Penglihatan komputer (Komputer Vision), Pengolahan Bahasa alami (Natural Language Processing), Robotika (Robotics). Sistem Syarat Buatan (Artificial Neural Systems), dan Sistem Pakar (Expert System). Kecerdasan buatan adalah suatu ilmu yang mempelajari cara membuat komputer melakukan sesuatu seperti yang dilakukan oleh manusia (Minsky, 1989). Defenisi lain diungkapkan oleh H. A. Simon (1987). Kecerdasan buatan (Artificial Intelligence) merupakan kawasan penelitian, apabila dan instruksi yang terkait dengan pemrograman komputer untuk

melakukan sesuatu hal yang – dalam pandangan manusia adalah cerdas. Rich and Knight (1991) mendefinisikan kecerdasan buatan (AI) sebagai sebuah studi tentang bagaimana membuat komputer melakukan hal-hal yang pada saat ini dapat dilakukan lebih baik oleh manusia. Sementara Ensiklopedia Britannica mendefinisikan kecerdasan buatan (AI) sebagai cabang dari ilmu komputer yang dalam meprepresentasi pengetahuan lebih banyak menggunakan bentuk symbol-simbol daripada bilangan, dan memproses informasi berdasarkan metode heuristic atau dengan berdasarkan sejumlah aturan. Ada tiga tujuan kecerdasan buatan, yaitu : membuat komputer lebih cerdas, mengerti tentang kecerdasan, dan membuat mesin lebih berguna. Yang dimaksud kecerdasan adalah kemampuan untuk belajar atau mengerti dari pengalaman, memahami pesan yang kontradiktif dan ambigu, menanggapi dengan cepat dan baik atas situasi yang baru, menggunakan penalaran dalam memecahkan masalah serta penyelesaiannya dengan efektif (Kursini, S.Kom, 2006). 2.3.

Booyer Moore Algoritma Boyer Moore diciptakan oleh R.M Boyer dan J.S Moore. Algoritma ini terkenal karena banyak diterapkan pada algoritma pencocokan untuk banyak string (multi pattern) (Imam Sulistyo, 2010) The Boyer-Moore algorithm is one of the famous exact string matching algorithms that used in single pattern matching and it considers very fast in its performance. (Awsan Abdulrahman Hasan dan Nur’Aini Abdul Rashid, 2012) Algoritma Boyer-Moore adalah salah satu dari pencarian string yang tepat dan terkenal algoritma pencocokan yang digunakan dalam pencocokan pola tunggal dan menganggap sangat cepat dalam kinerjanya. Dengan mengunakan algoritma ini, secara rata-rata proses pencarian akan menjadi lebih cepat jika dibandingakan dengan algoritma lainnya. alasan melakukan pencocokan dari kanan (posisi terakhir pattern yang dicari) ditunjukan dalam contoh berikut:

Pada contoh diatas, dengan melakukan pembandingan dari posisi paling akhir pattern dapat dilihat bahwa karakter “u” pada string “jambu” tidak cocok dengan karakter “n” pada string “makan” yang dicari, dan karakter “n” tidak pernah ada dalam string “jambu” yang dicari sehingga pattern “jambu” dapat digeser melewati string “makan” sehingga posisinya menjadi

Dalam contoh terlihat bahwa algoritma Boyer-Moore memiliki loncatan karakter yang besar


124


Majalah Ilmiah


sehingga mempercepat pencarian pattern karena dengan hanya memeriksa sedikit karakter, dapat langsung diketahui bahwa string yang dicari tidak ditemukan dan dapat digeser ke posisi berikutnya. Algoritma Boyer Moore telah dibuktikan sebagai salah satu algoritma yang paling efisien dalam aplikasi pencarian string dengan menggunakan natural language (bukan binary language). Algoritma ini telah sering diimplementasikan untuk fungsi “Search” dan “Subtitute” pada text editor. Padasarnya cara kerja algoritma ini mirip dengan algoritma Knuth-MorrisPrat (KMP) dimana kedua algoritma ini akan melakukan lompatan pengecekan dalam proses pencarian string. Namun berbeda dengan algoritma KMP, algoritma Boyer Moore ini melakukan perbandingan pattern mulai dari kanan ke kiri. (Evlyn Dwi Tambun, 2010) Idea of the Boyer-Moore Algorithm The algorithm uses knowledge of the search text to improve search speed significantly. It uses a step of preprocessing to create an occurance-function and shifting function which are used to perform bad character heuristics and good suffix heuristics respectively. (Prabhakar Gupta, et al. 2010). Ide dari algoritma Boyer-Moore Algoritma Boyer-Moore menggunakan pengetahuan tentang pencarian teks untuk meningkatkan kecepatan pencarian secara signifikan. Algortima Boyer-Moore menggunakan suatu langkah sebelum proses untuk membuat occurance-function dan shifting-function yang digunakan untuk melakukan bad character heuristics dan good suffix heuristics masing-masing. Boyer Moore menggunakan dua heuristik untuk memutuskan seberapa jauh melompat: badcharacter heuristic, juga sering disebut occurrence heuristic, dan heuristik yang good-character, juga disebut match heuristic. Informasi untuk heuristik setiap dipertahankan dalam sebuah array yang dibangun pada awal operasi yang cocok. (Jon Orwant, et al, 1999) 3. Analisa Dan Perancangan 3.1. Analisa Kebutuhan Data Analisa kebutuhan data yang dilakukan terhadap sistem e-Skripsi yang dibangun merupakan analisa terhadap data-data yang perlukan sebagai input untuk selanjutnya akan digunakan dalam analisa kebutuhan proses. Analisa kebutuhan data mendefenisikan data-data secara terperinci dimana data-data tersebut merupakan entiti yang terlibat atau yang akan digunakan pada tahap pemrosesan. Data-data yang diperlukan dalam pembangunan e-skripsi dapat dilihat pada tabel 1:

3.2. Analisa Kebutuhan Proses Analisa kebutuhan proses yang dilakukan dalam e-skripsi adalah menganalisa perangkat lunak apa saja yang butuhkan dalam proses pembangunannya. Untuk lebih jelasnya analisa kebutuhan proses telah diuraikan secara rinci dapat dilihat pada tabel 2 Tabel 2 Tabel Hasil Analisa Kebutuhan Proses

3.3. Analisa Kebutuhan Infrastruktur Analisa kebutuhan infrastruktur yang dilakukan dalam e-skripsi adalah pengolahan datadata hasil analisa kebutuhan data yang telah dilakukan sebelumnya. Proses-proses yang dapat dilakukan merupakan fitur-fitur atau fasilitas-fasilitas yang tersedia dalam e-skripsi. Untuk lebih jelasnya analisa kebutuhan proses telah diuraikan secara rinci dapat dilihat pada tabel 3 Tabel 3 : Tabel Hasil Analisa Kebutuhan Infrastruktur

Tabel 1 : Tabel Hasil Analisa Kebutuhan Data 3.4. Analisa BM (Boyer Moore) Metode BM (Boyer Moore) memiliki beberapa langkah dalam mencocokan teks yang Penerapan Algoritma Boyer Moore Pada Aplikasi Pengajuan Judul Skripsi Berbasi Web. 125 Oleh : Guidio Leonaerde Ginting


Majalah Ilmiah


dapat dirincikan sebagai berikut : 1. Buat nilai pergeseran pattern yang dicari (P) dengan pendekatan Match Heuristic (MH) dan Occurence Heuristic (OH) untuk menentukan jumlah pergeseran yang akan dilakukan jika mendapat karakter tidak cocok pada proses pencocokan dengan string pada teks (S) Judul dibandingkan : Judul 1 : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Judul 2 : PERANCANGAN PERANGKAT LUNAK PEMBELAJARAN KRIPTOGRAFI METODE MMB (MODULAR MULTIPLICATION-BASED BLOCK CIPHER) Tahap 1 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : PERANCANGAN

Langkah-langkah : a. Pada pergeseran pertama karakter N pada pattern dengan karakter N pada text cocok maka pencocokan dimundurkan satu langkah. b. Pada pergeseran ke-2 karakter A pada pattern dengan karakter A pada text cocok maka pencocokan dimundurkan satu langkah. c. Pada pergeseran ke-3 karakter G pada pattern dengan karakter G pada text cocok maka pencocokan dimundurkan satu langkah. d. Dilanjutkan sampai Pada pergeseran ke-11 karakter P pada pattern dengan karakter P pada text cocok

Langkah-langkah : a. Pada pergeseran pertama karakter T pada pattern dengan karakter G pada text tidak cocok, maka pergeseran selanjutnya berdasarkan nilai terbesar dari OH dan MH. Pada rule OH nilai karakter T bernilai 1 dan rule MH karakter G bernilai 3, maka bergeser sebesar 3 karakter. b. Pada pergeseran ke-2 karakter T pada pattern dengan karakter spasi pada text tidak cocok, maka pergeseran berdasarkan nilai terbesar dari OH dan MH, pada rule MH nilai karakter T bernilai satu dan rule OH karakter spasi bernilai 9 (selain karakter pada tabel bernilai sepanjang karakter) c. Pada pergeseran ke-3 karakter T pada pattern cocok dengan karakte T pada text, maka pencocokan dimundurkan satu karakter. d. Pada pergeseran ke-4 karakter A pada pattern cocok dengan karakte A pada text, maka pencocokan dimundurkan satu karakter. e. Dilanjutkan sampai pada pergeseran ke-11 karakter P pada pattern cocok dengan karakter P pada text Tahap 3 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : LUNAK Pattern Occurence Heuristic Match Heuristic

L 4 4

U 3 4

N 2 4

A 1 4

K 0 1

Tahap 2 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : PERANGKAT Langkah-langkah : a. Pada pergeseran pertama karakter K pada pattern dengan karakter N pada text tidak cocok, maka pergeseran selanjutnya berdasarkan nilai Penerapan Algoritma Boyer Moore Pada Aplikasi Pengajuan Judul Skripsi Berbasi Web. Oleh : Guidio Leonaerde Ginting

126


Majalah Ilmiah


b.

c.

d.

e.

f.

g.

h.

terbesar dari OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter N bernilai 2, maka bergeser sebesar 2 karakter. Pada pergeseran ke-2 karakter K pada pattern dengan karakter A pada text tidak cocok, maka pergeseran selanjutnya berdasarkan nilai terbesar dari OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter A bernilai 1, maka bergeser sebesar 1 karakter. Pada pergeseran ke-3 karakter K pada pattern dengan karakter N pada text tidak cocok, maka pergeseran selanjutnya berdasarkan nilai terbesar dari OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter N bernilai 2, maka bergeser sebesar 2 karakter. Pada pergeseran ke-4 karakter K pada pattern dengan karakter A pada text tidak cocok, maka pergeseran selanjutnya berdasarkan nilai terbesar dari OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter A bernilai 1, maka bergeser sebesar 1 karakter. Pada pergeseran ke-5 karakter K pada pattern dengan karakter N pada text tidak cocok, maka pergeseran selanjutnya berdasarkan nilai terbesar dari OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter N bernilai 2, maka bergeser sebesar 2 karakter. Pada pergeseran ke-8 karakter K pada pattern dengan karakter L pada text tidak cocok, maka pergeseran selanjutnya berdasarkan nilai terbesar dari OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter L bernilai 4, maka bergeser sebesar 4 karakter. pada pergeseran ke-9 karakter K pada pattern cocok dengan karakter K pada text, maka pencocokan dimundurkan satu karakter. dilanjutkan sampai pada pergeseran ketigabelas karakter L pada pattern cocok dengan karakter L pada text

a.

b.

c.

d.

e.

Pada pergeseran pertama karakter N pada pattern tidak cocok dengan karakter spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter spasi bernilai 12, maka pergeseran sebesar 12 karakter. Pada pergeseran ke-2 karakter N pada pattern tidak cocok dengan karakter U pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter U bernilai 12, maka pergeseran sebesar 12 karakter. Pada pergeseran ke-3 karakter N pada pattern tidak cocok dengan karakter I pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter I bernilai 12, maka pergeseran sebesar 12 karakter. Pada pergeseran ke-4 karakter N pada pattern tidak cocok dengan karakter G pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter G bernilai 12, maka pergeseran sebesar 12 karakter. Pada pergeseran ke-6 karakter N pada pattern tidak cocok dengan karakter A pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter A bernilai 1, maka pergeseran sebesar 1 karakter.

Tahap 5 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : KRIPTOGRAFI

Tahap 4 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : PEMBELAJARAN

Langkah-langkah :

Langkah-langkah : a. Pada pergeseran pertama karakter I pada pattern tidak cocok dengan karakter N pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter I bernilai 1 dan rule OH karakter N bernilai 12, maka pergeseran sebesar 11 karakter. b. Pada pergeseran ke-2 karakter I pada pattern tidak cocok dengan karakter spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter I bernilai 1 dan


127


Majalah Ilmiah


c.

d.

e.

f.

g.

rule OH karakter spasi bernilai 11, maka pergeseran sebesar 11 karakter. Pada pergeseran ke-3 karakter I pada pattern tidak cocok dengan karakter A pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter I bernilai 1 dan rule OH karakter A bernilai 2, maka pergeseran sebesar 2 karakter. Pada pergeseran ke-4 karakter I pada pattern tidak cocok dengan karakter D pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter I bernilai 1 dan rule OH karakter D bernilai 11, maka pergeseran sebesar 11 karakter. Pada pergeseran ke-5 karakter I pada pattern tidak cocok dengan karakter E pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter I bernilai 1 dan rule OH karakter E bernilai 11, maka pergeseran sebesar 11 karakter. Pada pergeseran ke-7 karakter I pada pattern tidak cocok dengan karakter R pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter I bernilai 1 dan rule OH karakter R bernilai 3, maka pergeseran sebesar 3 karakter. Pada pergeseran ke-8 karakter I pada pattern tidak cocok dengan karakter M pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter I bernilai 1 dan rule OH karakter M bernilai 11, karena pergeseran melewati teks, maka pencarian dihentikan.

Tahap 6 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : METODE Pattern Occurence Heuristic Match Heuristic

M 5 6

E 0 6

T 3 6

O 2 6

D 1 6

E 0 1

OH karakter C bernilai 6, maka pergeseran sebesar 6 karakter. b. Pada pergeseran ke-2 karakter E pada pattern tidak cocok dengan karakter spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter E bernilai 1 dan rule OH karakter spasi bernilai 6, maka pergeseran sebesar 6 karakter. c. Pada pergeseran ke-3 karakter E pada pattern tidak cocok dengan karakter G pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter E bernilai 1 dan rule OH karakter G bernilai 6, maka pergeseran sebesar 6 karakter. d. Pada pergeseran ke-4 karakter E pada pattern tidak cocok dengan karakter U pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter E bernilai 1 dan rule OH karakter U bernilai 6, maka pergeseran sebesar 6 karakter. e. Pada pergeseran ke-13 karakter E pada pattern tidak cocok dengan karakter M pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter E bernilai 1 dan rule OH karakter M bernilai 5, maka pergeseran sebesar 5 karakter. f. Pada pergeseran ke-14 karakter E pada pattern tidak cocok dengan karakter U pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter E bernilai 1 dan rule OH karakter U bernilai 6, maka pergeseran sebesar 6 karakter. g. Pada pergeseran ke-17 karakter E pada pattern tidak cocok dengan karakter C pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter E bernilai 1 dan rule OH karakter C bernilai 6, maka pergeseran sebesar 6 karakter tapi pergeseran tidak dapat dilakukan karena melewati teks) Tahap 7 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : MMB Pattern Occurence Heuristic Match Heuristic

M 1 3

M 1 3

B 0 0

Langkah-langkah : a. Pada pergeseran pertama karakter E pada pattern tidak cocok dengan karakter C pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter E bernilai 1 dan rule Penerapan Algoritma Boyer Moore Pada Aplikasi Pengajuan Judul Skripsi Berbasi Web. Oleh : Guidio Leonaerde Ginting

128


Majalah Ilmiah


Langkah-langkah : a. Pada pergeseran pertama karakter B pada pattern tidak cocok dengan karakter R pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter R bernilai 3, maka pergeseran sebesar 3 karakter. b. Pada pergeseran ke-2 karakter B pada pattern tidak cocok dengan karakter C pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter C bernilai 3, maka pergeseran sebesar 3 karakter. c. Pada pergeseran ke-3 karakter B pada pattern tidak cocok dengan karakter G pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter G bernilai 3, maka pergeseran sebesar 3 karakter. d. Pada pergeseran ke-4 karakter B pada pattern tidak cocok dengan karakter Spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter Spasi bernilai 3, maka pergeseran sebesar 3 karakter. e. Pada pergeseran ke-5 karakter B pada pattern tidak cocok dengan karakter R pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter R bernilai 3, maka pergeseran sebesar 3 karakter. f. Pada pergeseran ke-6 karakter B pada pattern tidak cocok dengan karakter G pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter G bernilai 3, maka pergeseran sebesar 3 karakter. g. Pada pergeseran ke-7 karakter B pada pattern tidak cocok dengan karakter T pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter T bernilai 3, maka pergeseran sebesar 3 karakter. h. Pada pergeseran ke-13 karakter B pada pattern tidak cocok dengan karakter Spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter Spasi bernilai 3, maka pergeseran sebesar 3 karakter. i. Pada pergeseran ke-14 karakter B pada pattern tidak cocok dengan karakter T pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter T bernilai 3, maka pergeseran sebesar 3 karakter. j. Pada pergeseran ke-25 karakter B pada pattern tidak cocok dengan karakter C pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter B bernilai 1 dan rule OH karakter U bernilai 3, maka pergeseran

sebesar 3 karakter tapi pergeseran tidak dapat dilakukan dikarenakan melebihi panjang text. Tahap 8 Text (S) : PERANCANGAN PERANGKAT PENYANDIAN DATA MENGGUNAKAN ALGORITMA RC6 Pattern (P) : Modular Pattern M O D Occurence Heuristic 6 5 4 Match Heuristic 7 7 7

LUNAK DENGAN

U 3 7

L 2 7

A 1 7

Langkah-langkah : a. Pada pergeseran pertama karakter R pada pattern tidak cocok dengan karakter A pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter R bernilai 1 dan rule OH karakter A bernilai 1, maka pergeseran sebesar 1 karakter. b. Pada pergeseran ke-2 karakter R pada pattern tidak cocok dengan karakter N pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter R bernilai 1 dan rule OH karakter N bernilai 7, maka pergeseran sebesar 7 karakter. c. Pada pergeseran ke-3 karakter R pada pattern cocok dengan karakter R pada text, maka pencocokan dimundurkan satu karakter. d. Pada pergeseran ke-4 karakter A pada pattern tidak cocok dengan karakter E pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter A bernilai 7 dan rule OH karakter E bernilai 6, maka pergeseran sebesar 7 karakter. e. Pada pergeseran ke-5 karakter R pada pattern tidak cocok dengan karakter spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter R bernilai 1 dan rule OH karakter spasi bernilai 7, maka pergeseran sebesar 7 karakter. f. Pada pergeseran ke-8 karakter R pada pattern tidak cocok dengan karakter A pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter R bernilai 1 dan rule OH karakter A bernilai 1, maka pergeseran sebesar 1 karakter. g. Pada pergeseran ke-14 karakter R pada pattern cocok dengan karakter R pada text, maka pencocokan dimundurkan satu karakter.


129

R 0 1


Majalah Ilmiah


h.

Pada pergeseran ke-15 karakter A pada pattern tidak cocok dengan karakter spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter A bernilai 7 dan rule OH karakter spasi bernilai 6, maka pergeseran sebesar 7 karakter tapi pergeseran tidak dapat dilakukan karena sudah melebih panjang text.

Tahap 9 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : Multiplication

MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter spasi bernilai 14, maka pergeseran sebesar 14 karakter. Tahap 10 Text (S) : PERANCANGAN PERANGKAT PENYANDIAN DATA MENGGUNAKAN ALGORITMA RC6 Pattern (P) : Based Pattern B A S Occurence Heuristic 4 3 2 Match Heuristic 5 5 5

LUNAK DENGAN

E 1 5

D 0 1

Langkah-langkah : a. Pada pergeseran Pertama karakter D pada pattern tidak cocok dengan karakter N pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter D bernilai 1 dan rule OH karakter N bernilai 5, maka pergeseran sebesar 5 karakter. b. Pada pergeseran ke-2 karakter D pada pattern tidak cocok dengan karakter A pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter D bernilai 1 dan rule OH karakter A bernilai 3, maka pergeseran sebesar 3 karakter. c. Pada pergeseran ke-3 karakter D pada pattern tidak cocok dengan karakter P pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter D bernilai 1 dan rule OH karakter P bernilai 5, maka pergeseran sebesar 5 karakter. d. Pada pergeseran ke-4 karakter D pada pattern tidak cocok dengan karakter G pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter D bernilai 1 dan rule OH karakter G bernilai 5, maka pergeseran sebesar 5 karakter. e. Pada pergeseran ke-5 karakter D pada pattern tidak cocok dengan karakter L pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter D bernilai 1 dan rule OH karakter L bernilai 5, maka pergeseran sebesar 5 karakter. f. Pada pergeseran ke-17 karakter D pada pattern tidak cocok dengan karakter C pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter D bernilai 1 dan rule OH karakter C bernilai 5, maka pergeseran Penerapan Algoritma Boyer Moore Pada Aplikasi Pengajuan Judul Skripsi Berbasi Web. 130 Oleh : Guidio Leonaerde Ginting Langkah-langkah : a. Pada pergeseran pertama karakter N pada pattern tidak cocok dengan karakter E pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter E bernilai 14, maka pergeseran sebesar 14 karakter. b. Pada pergeseran ke-2 karakter N pada pattern tidak cocok dengan karakter spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter spasi bernilai 14, maka pergeseran sebesar 14 karakter. c. Pada pergeseran ke-3 karakter N pada pattern tidak cocok dengan karakter T pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter T bernilai 3, maka pergeseran sebesar 3 karakter. d. Pada pergeseran ke-4 karakter N pada pattern tidak cocok dengan karakter D pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter D bernilai 14, maka pergeseran sebesar 14 karakter. e. Pada pergeseran ke-5 karakter N pada pattern tidak cocok dengan karakter A pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter N bernilai 1 dan rule OH karakter A bernilai 4, maka pergeseran sebesar 4 karakter. f. Pada pergeseran ke-6 karakter N pada pattern tidak cocok dengan karakter spasi pada text, maka pergeseran selanjutnya maksimal OH dan


Majalah Ilmiah


sebesar 5 karakter tapi pergeseran tidak dapat dilakukan karena sudah melebihi panjang text. Tahap 11 Text (S) : PERANCANGAN PERANGKAT LUNAK PENYANDIAN DATA DENGAN MENGGUNAKAN ALGORITMA RC6 Pattern (P) : BLOCK Pattern Occurence Heuristic Match Heuristic

B 4 5

L 3 5

O 2 5

C 1 5

K 0 1

Langkah-langkah : a. Pada pergeseran Pertama karakter K pada pattern tidak cocok dengan karakter N pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter N bernilai 5, maka pergeseran sebesar 5 karakter. b. Pada pergeseran ke-2 karakter K pada pattern tidak cocok dengan karakter A pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter A bernilai 5, maka pergeseran sebesar 5 karakter. c. Pada pergeseran ke-3 karakter K pada pattern tidak cocok dengan karakter N pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter R bernilai 5, maka pergeseran sebesar 5 karakter. d. Pada pergeseran ke-4 karakter K pada pattern tidak cocok dengan karakter A pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter A bernilai 5, maka pergeseran sebesar 5 karakter. e. Pada pergeseran ke-5 karakter K pada pattern tidak cocok dengan karakter N pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter N bernilai 5, maka pergeseran sebesar 5 karakter. f. Pada pergeseran ke-16 karakter K pada pattern tidak cocok dengan karakter spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter K bernilai 1 dan rule OH karakter spasi bernilai 5, maka

pergeseran sebesar 5 karakter. pergeseran tidak dapat dilanjutkan karena sudah melebihi panjang text. Tahap 12 Text (S) : PERANCANGAN PERANGKAT PENYANDIAN DATA MENGGUNAKAN ALGORITMA RC6 Pattern (P) : CHIPER Pattern C I P Occurence Heuristic 5 4 3 Match Heuristic 6 6 6

LUNAK DENGAN

H 2 6

E 1 6

R 0 1

Langkah-langkah : a. Pada pergeseran Pertama karakter R pada pattern tidak cocok dengan karakter C pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter R bernilai 1 dan rule OH karakter C bernilai 6, maka pergeseran sebesar 6 karakter. b. Pada pergeseran ke-2 ke karakter R pada pattern tidak cocok dengan karakter N pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter R bernilai 1 dan rule OH karakter N bernilai 6, maka pergeseran sebesar 6 karakter. c. Pada pergeseran ke-3 ke karakter R pada pattern tidak cocok dengan karakter N pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter R bernilai 1 dan rule OH karakter N bernilai 6, maka pergeseran sebesar 6 karakter. d. Pada pergeseran ke-15 ke karakter E pada pattern tidak cocok dengan karakter Spasi pada text, maka pergeseran selanjutnya maksimal OH dan MH. Pada rule MH nilai karakter E bernilai 6 dan rule OH karakter Spasi bernilai 5, maka pergeseran sebesar 6 karakter. pergeseran tidak dapat dilakukan karena sudah melebihi panjang text. Hasil perbandingan dari kedua judul : Kata yang cocok 3 kata dari 9 kata, persentase kesamaan 11.11 % 3.5. Rancangan DesignAplikasi Sistem e-skripsi Rancangan design dariaplikasi sistem eskripsi menampilkan menu dan bagian-bagian yang


131


Majalah Ilmiah


ada dalam aplikasi sistem e-skripsi. Rancangan design dari aplikasi sistem e-skripsi yaitu : 1. Rancangan halaman pengajuan judul Halaman pengajuan judul merupakan halaman input judul yang akan diajukan. halaman pengajuan judul dapat dilhat pada gambar 1 berikut ini :

2.

2.

atau arti dari pattern yang cocok. Maka untuk pengembangannya penulis memberikan saran untuk menambahkan algoritma yang dapat membandingkan ari dari sebuah string atau gabungan dari beberapa string. Alplikasi pengajuan judul skripsi dibangun dengan menggunakan bahasa pemrograman PHP dan MySQL sehingga syarat untuk menjalankan aplikasi tersebut dianjurkan pada perangkat keras komputer, maka untuk pengembangan selanjutnya, pembangunan aplikasi pengajuan judul skripsi ditujukan untuk telepon selular jenis terbaru dan lebih khusus seperti untuk smart phone androit atau tablet.

Gambar 1 : Rancangan Form Menu Utama

5. DAFTAR PUSTAKA

Rancangan Halaman hasil pengajuan judul Halaman hasil pengajuan judul merupakan halaman yang menampilkan hasil dari pengajuan judul. Rancangan halaman hasil pengajuan judul dapat dilihat pada gambar 2 berikut ini :

[1]

[2]

[3]

[4] Gambar 2 : Rancangan Pengajuan Judul 4. Kesimpulan Dan Saran 4.1 Kesimpulan Setelah melakukan perencangan dan implementasi maka penulis dapat menarik beberapa kesimpulan seperti berikut : 1. Algoritma Boyer Moore cocok digunakan untuk melakukan pencarian string tetapi tidak cocok digunakan untuk mengambil informasi dari kecocokan string berdasarkan satu kata atau lebih. 2. Untuk menentukan judul diterima ditentukan dari hasil persentase kesamaan string, hal tersebut tidak terlalu efektif dikarenakan judul dapat memiliki kesamaan string yang besar tetapi tidak memiliki arti yang sama atau sebaliknya.

[5]

4.2. Saran-saran Untuk kepentingan lebih lanjut dari aplikasi ini maka penulis memberikan beberapa saran sebagai berikut : 1. Algoritma Boyer Moore merupakan algoritma pencocokan string yang sering diterapkan dalam berbagai aplikasi pencarian, namun algoritma tersebut tidak baik digunakan untuk mencocokkan string untuk mengambil informasi

[10]

[6]

[7]

[8]

[9]

[11]

Kursini (2006). Sistem Pakar Teori dan Aplikasi. Yogyakarta. Penerbit Andi Yogyakarta : hal. 1 Antonius Rachmat C (2010). Algoritma dan Pemrograman dengan Bahasa C Konsep, Teori, & Implementasi. Yogyakarta. Penerbit Andi Yogyakarta: ha14. Abdul Kadir (2012). Algoritma & Pemrograman Menggunakan Java.Yogyakarta. Penerbit Andi Yogyakarta. Hal. 43 Devia Puspita, Juni Nurma Sari dan Heni Rachmawati (2012). Aplikasi Chatter Bot untuk SMA Cendana Rumbai Dengan Menggunakan Metode Boyer Moore. Imam Sulistyo, Andie Pradipto, Adi Setia Perwira (2008). Algoritma BoyerMoore Dalam Pencarian String. Awsan Abdulrahman Hasan dan Nur Aini Abdul Rashid (2012). Has-Boyer MooreHorspool String Matching Algorithm for instrusion Detection System. Elvyn Dwi Tambun (2010). Perbandingan Penggunaan Algoritma BM dan Algoritma Horspool Pada Pencarian String Dalam Bahasa Medis. Prabhakar Gupta, Vineet Agarwal, dan Manish Varshney (2010). Design and Analiysis ofAlgorithms. New Delhi. Jon Orwant, Jarkko Hietaniemi, dan John Macdonald (1999). Mastering Algorithms R'ith Perl. Penerbit O'Reilly United States. Rama Aulia (2008). Analisa Algoritma %nuth Morris Pratt dan Algoritma Boyer Moore dalam Prses Pencarian String. Critabella Chiquita B (2011). Penerapan Algoritma Boyer Moore-Dynamic Programming untuk layanan Auto-Complate dan Auto-correct


132

PENERAPAN ALGORITMA BOYER MOORE PADA APLIKASI PENGAJUAN JUDUL SKRIPSI BERBASI WEB

Recommend Documents