ANALISIS DAN PERBANDINGAN ALGORITMA BRUTE FORCE DAN ALGORITMA
HORSPOOL PADA APLIKASI KAMUS BAHASA
INDONESIA - MANDARIN
SKRIPSI
DEAR ARINI PURBA
141421008
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER
FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI
UNIVERSITAS SUMATERA UTARA
MEDAN
2017
Universitas Sumatera Utara
ANALISIS DAN PERBANDINGAN ALGORITMA BRUTE FORCE DAN ALGORITMA
HORSPOOL PADA APLIKASI KAMUS BAHASA
INDONESIA - MANDARIN
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah
Sarjana Ilmu Komputer
DEAR ARINI PURBA
141421008
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER
FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI
UNIVERSITAS SUMATERA UTARA
MEDAN
2017
Universitas Sumatera Utara
PERSETUJUAN
Judul : ANALISIS DAN PERBANDINGAN ALGORITMA
BRUTE FORCE DAN ALGORITMA HORSPOOL
PADA APLIKASI KAMUS BAHASA INDONESIA-
MANDARIN
Kategori : SKRIPSI
Nama : DEAR ARINI PURBA
Nomor Induk Mahasiswa : 141421008
Program Studi : SARJANA (S-1) ILMU KOMPUTER
Departemen : ILMU KOMPUTER
Fakultas : FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI
INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing :
Pembimbing 2 Pembimbing 1
Jos Timanta Tarigan, S.Kom., M.Sc Prof. Dr. Iryanto, M.Si
NIP. 198501262015041001 NIP. 194604041971071001
Diketahui/disetujui oleh
Program Studi S-1 Ilmu Komputer
Ketua,
Dr. Poltak Sihombing, M.Kom.
NIP. 196203171991031001
Universitas Sumatera Utara
PERNYATAAN
ANALISIS DAN PERBANDINGAN ALGORITMA BRUTE FORCE DAN
ALGORITMA HORSPOOL PADA APLIKASI KAMUS BAHASA
INDONESIA - MANDARIN
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa
kutipan dan ringkasan yang masing – masing telah disebutkan sumbernya.
Medan, Maret 2017
Dear Arini Purba
141421008
Universitas Sumatera Utara
UCAPAN TERIMA KASIH
Puji dan syukur penulis ucapkan kepada Tuhan Yang Maha Esa yang telah
memberikanrahmat dan berkat-Nya, sehinggapenulis dapat menyelesaikan
penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer
pada Program Studi S1 Ilmu Komputer Universitas Sumatera Utara.
Penulis ingin menyampaikan rasa hormat dan terima kasih yang sebesar–
besarnya kepada :
1. Bapak Prof. Dr. Runtung Sitepu, S.H., M.Humselaku Rektor Universitas
Sumatera Utara.
2. Bapak Prof. Dr. Opim Salim Sitompul, M.Si, selaku Dekan Fakultas Ilmu
Komputer dan Teknologi Informasi, Universitas Sumatera Utara.
3. Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S1 Ilmu
Komputer Universitas Sumatera Utara yang telah memberikan kritik dan saran
dalam penyempurnaan skripsi ini.
4. Bapak Prof. Dr. Iryanto, M.Si. selaku Dosen Pembimbing I yang telah banyak
memberikan bimbingan, saran,masukan dan dukungan kepada penulis dalam
pengerjaan skripsi ini.
5. Bapak Jos Timanta Tarigan, S.Kom, M.Scselaku Dosen Pembimbing II yang
telah memberikan bimbingan, saran, dan masukan kepada penulis dalam
pengerjaan skripsi ini.
6. Ibu Dr. Maya Silvi Lidya, B.Sc., M.Scselaku Dosen Pembanding I yang
memberikan kritik dan saran untuk penyempurnaan skripsi ini.
7. Bapak M. Andri Budiman, S.T., M.Comp.Sc., M.E.M.selaku Dosen Pembanding
II yang memberikan kritik dan saran untuk penyempurnaan skripsi ini.
8. Seluruh tenaga pengajar dan pegawai Program Studi S1 Ilmu Komputer
Fasilkom-TI USU .
9. Ayahanda Efendi Elias Purba dan IbundaDamelina Saragihyang selalu
memberikan doa dan dukungan serta kasih sayang kepada penulis, serta abang
dan adik tersayang Dittya Purba, Benny Carnegie Purba dan Desy Ulina
Universitas Sumatera Utara
Purbayang terus memberikan dukungan dan dorongan bagi penulis untuk
menyelesaikan skripsi ini.
10. Sahabat penulis Sar Barita, Alvin, Denny, Herman, Leo, Mailinda, Priska, Angga
dan yang lainnya yang telah banyak memberikan doa, dukungan dan semangat
selama proses menyelesaikan skripsi ini.
11. Teman – teman dekat Bangkit, Reynaldi, Rico, One, Hilda, Riris, Tika dan Ika
yang memberikan dukungan dan semangat selama proses menyelesaikan skripsi
ini.
12. Teman – teman kuliahJanuar Andi Sirait dan Mariaty Harefa yang senantiasa
membantu penulis dalam penyelesaian skripsi ini.
13. Dan semua pihak yang telah banyak membantu yang tidak bisa disebutkan satu-
persatu.
Semoga Tuhan Yang Maha Esa melimpahkan berkat dan kasih sayang-Nya kepada
semua pihak yang telah memberikan bantuan, semangat, dukungan dan perhatian serta
doa kepada penulis dalam menyelesaikan skripsi ini.
Medan, April 2017
Penulis
Dear Arini Purba
Universitas Sumatera Utara
ABSTRAK
Bahasa sangat memegang peranan penting dalam berkomunikasi terutama dalam
berinteraksi, baik itu dalam masyarakat ataupun instansi tertentu.Pada saat ini banyak
perusahaan yang membuka lapangan pekerjaan dengan syarat karyawan harus mahir
dalam bahasa mandarin, Untuk dapat belajar bahasa mandarin, kamus dapat dijadikan
sebagai salah satu bahan acuan. Di zaman sekarang ini, aplikasi kamus berbasis
android sangat efisien digunakan untuk belajar menambah kosakata. Dalam membuat
aplikasi kamus, string matching dapat diimplementasikan untuk proses pencarian
katanya. String matching memiliki beberapa algoritma, salah satu algoritmanya adalah
algoritma Brute Force dan algoritma Horspool dan akan diimplementasikan pada
aplikasi kamus tersebut. Algoritma Burte Force melakukan proses pencarian dari kiri
kekanan dan Algoritma Horspool memiliki dua fase yaitu fase preprocessing dan fase
pencarian. Fase preprocessing merupakan proses untuk membuat nilai pergeseran
sesuai dengan pattern yang dimasukkan.Pattern akan bergeser apabila string dan
pattern mengalami ketidakcocokan. Pattern akan berhenti bergeser saat pattern
ditemukan pada teks atau saat jumlah nilai pergeseran lebih besar dari selisih panjang
teks dan panjang pattern.Kedua Algoritma tersebut memiliki kompleksitas
algoritma yang sama yaitu T(n) = θ(mn), tetapi memiliki perbedaan rata-rata running
time sebesar 0,243511 ms, dimana hasil rata-rata running timeAlgoritma Brute
Force adalah 1,38839 ms dan Algoritma Horspooladalah 1,631901 ms.
Kata Kunci : Android, String Matching, Brute Force, Horspool.
Universitas Sumatera Utara
ANALYSIS AND COMPARISON OF BRUTE FORCE AND
HORSPOOL ALGORITHM ON DICTIONARY
INDONESIA –MANDARIN
ABSTRACT
Language has important role in communication because we use it as a tool to deliver
the information, especially in interaction, whether in the public or the company. At
this time many companies are creating jobs on the condition that the employee must
be proficient in Mandarin, To be able to learn Chinese language, the dictionary can
be used as a reference material. In today's age, android based dictionary application
very efficiently used to study add to the vocabulary. In making an application
dictionary, string matching can be implemented for the search process said. String
matching has several algorithms, one algorithm is an algorithm Brute Force and
algorithms Horspool and will be implemented in the dictionary application. Force
Burte algorithms perform the search process from left to right and Horspool
algorithm has two phases which preprocessing and search phase. Preprocessing
phase is a process to make the shift value in accordance with the pattern entered.
Pattern will shift when the string and pattern experienced incompatibility. Pattern will
stop the current shift pattern found on the text or when the amount of shift value is
greater than the difference between the long length of the text and pattern. Both of
these algorithms have the same complexity of the algorithm is T (n) = θ (mn), but have
a difference in the average running time of 0.243511 ms, where the average yield
Brute Force algorithm running time is 1.38839 ms and Algorithms Horspool is
1.631901 ms.
Keyword : Android, String Matching, Brute Force, Horspool.
Universitas Sumatera Utara
DAFTAR ISI
Halaman
Persetujuan ii
Pernyataan iii
Penghargaan iv
Abstrak vi
Abstract vii
Daftar Isi viii
Daftar Tabel x
Daftar Gambar xi
Daftar Lampiran xii
Bab 1 Pendahuluan
1.1 Latar Belakang 1
1.2 Ruang Lingkup Masalah 2
1.3 Batasan Masalah 2
1.4 Tujuan Penelitian 3
1.5 Manfaat Penelitian 3
1.6 Metode Penelitian 3
1.7 Sistematika Penelitian 4
Bab 2 Landasan Teori
2.1 Kamus 5
2.2 Algoritma 6
2.3 Android 6
2.4 String Matching 8
2.4.1 Pengertian String Matching 8
2.4.2 Cara Kerja String Matching 8
2.4.3 Klasifikasi Algoritma String Matching 9
2.5 Algoritma Brute Force 10
Universitas Sumatera Utara
2.6 Algoritma Horspool 12
2.6.1 Pencarian Dengan Algoritma Horspool 13
2.7 Penelitian Terkait 16
Bab 3 Analisis dan Perancangan Sistem
3.1 Analisis Sistem 18
3.1.1 Analisis Masalah 18
3.1.2 Analisis Kebutuhan Sistem 20
3.1.2.1 Analisis Kebutuhan Fungsional Sistem 20
3.1.2.2 Analisis Kebutuhan Non- Fungsional Sistem 20
3.1.3 Pemodelan Sistem 21
3.1.3.1Use – Case Diagram 21
3.1.3.2Activiy Diagram 22
3.1.3.3Sequence Diagram 23
3.2 Flowchart Sistem 23
3.3 Pseudocode Program 25
3.3.1 Pseudocode Algoritma Brute Force 25
3.3.2 Pseudocode Algoritma Horspool 25
3.4 Perancangan Sistem 26
3.4.1 Rancangan Halaman Menu Utama 26
3.4.2 Rancangan Halaman Hasil Pencarian 27
3.4.3 Rancangan Halaman About 28
Bab 4 Implementasi dan Pengujian Sistem
4.1 Implementasi Sistem 30
4.1.1 Tampilan Antarmuka Utama 30
4.1.2 Tampilan Antarmuka Hasil Pencarian 32
4.1.3 Tampilan Antarmuka About 33
4.2 Pengujian Sistem 34
4.2.1 Pengujian Proses Pencarian Dengan Algoritma Brute Force 34
4.2.2 Pengujian Proses Pencarian Dengan Algoritma Horspool 39
4.2.3 Hasil pengujian 45
4.3 Kompleksitas Algoritma 47
4.3.1 Kompleksitas Algoritma Brute Force 47
4.3.2 Kompleksitas Algoritma Horspool 48
Universitas Sumatera Utara
Bab 5 Penutup 50
5.1 Kesimpulan 51
5.2 Saran 52
Daftar Pustaka 53
Lampiran A-1
Universitas Sumatera Utara
DAFTAR TABEL
Nomor Tabel
Nama Tabel Halaman
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
4.1
4.2
4.3
4.4
4.5
4.6
Iterasi Algoritma Brute Force Pertama
Iterasi Algoritma Brute Force Kedua
Iterasi Algoritma Brute Force Ketiga
Iterasi Algoritma Brute Force Keempat
Iterasi Algoritma Brute Force Kelima
Bad Match Pada Pra-proses
Inisialisasi Awal Bad Match
Pembuatan Bad Match
Iterasi Algoritma Horspool Pertama
Iterasi Algoritma Horspool Kedua
Iterasi Algoritma Horspool Ketiga
Tabel Pengujian Algoritma Brute Force
Tabel Pengujian Algoritma Horspool
Hasil Pengujian Algoritma Brute Force dan Algoritma
Horspool
Kompleksitas Fungsi Match Algoritma Brute Force
Kompleksitas Fungsi Shifttable Algoritma Horspool
Kompleksitas Fungsi Match Algoritma Horspool
10
11
11
11
11
14
14
15
15
15
16
34
40
45
47
48
48
Universitas Sumatera Utara
DAFTAR GAMBAR
Nomor Gambar
Nama Gambar Halaman
3.1 Fishbone Diagram 19
3.2 Use – Case Diagram 21
3.3 Activity Diagram 22
3.4 Sequence Diagram 23
3.5 Flowchart Sistem 24
3.6 Tampilan Tab Algoritma Brute Force 27
3.7 Tampilan Tab Algoritma Horspool 27
3.8 Tampilan Tab Hasil Pencarian Algoritma Brute Force 27
3.9 Tampilan Tab Hasil Pencarian Algoritma Horspool 28
3.10 Tampilan Halaman About 29
4.1 Tampilan Awal Tab Algoritma Brute Force 30
4.2 Tampilan Awal Tab Algoritma Horspool 31
4.3 Tampilan Hasil Pencarian Algoritma Brute Force 32
4.4 Tampilan Hasil Pencarian Algoritma Horspool 33
4.5 Tampilan HalamanAbout 33
4.6 Perbandingan Hasil Running Time Algotima Brute Force dan
Algoritma Horspool
46
4.7 Perbandingan Nilai Total dan Rata-rata Algotima Brute Force
dan Algoritma Horspool
46
Universitas Sumatera Utara
DAFTAR LAMPIRAN
Lampiran 1 Listing Program A-1
Lampiran 2 Curriculum Vitae B-1
Universitas Sumatera Utara
BAB 1
PENDAHULUAN
1.1 Latar Belakang
Komunikasi adalah salah satu bentuk interaksi antara satu pihak dengan pihak lain.
Komunikasi antar manusia dilakukan dan dibantu oleh sebuah sarana yaitu bahasa.
Karena manusia terdiri dari berbagai ragam suku dan bangsa maka beragam atau
bermacam juga jenis dan dialog bahasa sehingga kadang kala ada satu suku atau
bangsa yang sulit berkomunikasi dengan bangsa atau suku lain. Maka bahasa sangat
memegang peranan penting dalam berkomunikasi terutama dalam berintraksi antara
satu dengan yang lainnya.
Salah satu bahasa yang popular saat ini digunakan adalah bahasa Mandarin.
Bahasa mandarin tidak hanya popular menjadi bahasa sehari-hari, tetapi seseorang
yang memiliki kemampuan dalam berbahasa mandarin akan memiliki suatu nilai lebih
ketika melamar suatu pekerjaan.
Untuk dapat berbahasa Mandarin dengan lancar dapat dilakukan dengan
memulai percakapan sehari-hari dengan berbahasa Mandarin. Dan bagi orang yang
belum mahir berbahasa mandarin memerlukan kamus sebagai bahan acuannya.Pada
zaman seperti sekarang ini dimana kemajuan teknologi informasi diterapkan di segala
bidang, maka manusia dituntut untuk mengikuti kemajuan teknologi. Begitu kemajuan
dalam penggunaan kamus cetak yang masih dinilai kurang efisien. Hal ini disebabkan
karena pengguna harus mencari kata satu demi satu, membolak-balik halaman kamus
dan mencari dengan telitiserta ukurannya yang tebal dan berat.
Dalam aplikasi kamus bahasa Indonesia-Mandarin ini dengan menggunakan
teknologi makadibutuhkan algoritma pencocokan string (String Matching) yaitu
algoritma yang dapat mencari kata (pattern) dalam sebuah kalimat teks (string) untuk
menemukan satu kata yang pertama kali ditemukan atau yang lebih umum dan
menampilkan sebuah kata yang ditemukan dalam teks.
Algoritma Brute Force dan algoritma Horspool merupakan bagian dari
algoritma exact string matching yang memiliki cara kerja berbeda sehingga jika
diterapkan dalam aplikasi kamus ini mengakibatkan kecepatan pencarian informasi
Universitas Sumatera Utara
juga menjadi berbeda. Dengan adanya perbedaan tersebut, maka perlu adanya analisa
yang membandingkan kedua algoritma exact string matching didalam aplikasi kamus
ini.
Berdasarkan uraian latar belakang diatas, Penulis bermaksud mengangkat
permasalahan tersebut sebagai bahan perancangan. Oleh karena itu, Penulis memilih
topik Tugas Akhir penulis dengan judul “Analisis dan Implementasi Algoritma Brute
Force dan Algoritma Horspool pada Aplikasi Kamus Bahasa Indonesia - Mandarin”.
1.2 Rumusan Masalah
Rumusan masalah pada penelitian ini adalah banyaknya lapangan pekerjaan yang
membutuhkan karyawan mahir dalam bahasa mandarin sehingga dirancang suatu
aplikasi kamus bahasa Indonesia – Mandarin dengansistem perangkat lunak yang
dapat menganalisis dan membandingkan algoritma Brute Force dan algoritma
Horspool.
1.3 Batasan Masalah
Batasanmasalah dari latar belakang penelitian ini yaitu:
1. Parameter yang digunakan untuk membandingkan algoritma Brute Force dan
algoritma Horspool adalah waktu proses dan kompleksitas menggunakan Big-
ϴ.
2. Input dan hasil terjemahan aplikasi kamus ini berupa kata dan bukan
merupakan huruf kanji. Jumlah kata yang tersedia adalah ±500 kata.
3. Kamus ini dirancang menggunakan bahasa pemrograman Java berbasis
Android
4. Aplikasi kamus ini dibangun dengan menggunakan kamus yang diterbitkan
oleh:
a. Penerbit Sketsa dengan judul Kamus Praktis Bahasa Mandarin, penulis
Jennifer Kwan dan Andre Wijaya pada tahun 2007.
b. Penerbit Rumah Ide dengan judul Kamus Saku Mandarin Superkomplet,
penulis Duma Rian pada tahun 2014.
Universitas Sumatera Utara
1.4 Tujuan Penelitian
Tujuan dari penelitian ini adalah untuk memperoleh suatu sistem perangkat lunak
yang dapat menganalisa dan membandingkan antara algoritma Brute Force dan
algoritma Horspool serta mengukur tingkat perbandingan waktu proses dalam satuan
waktu (ms) dan kompleksitas menggunakan Big ϴ.
1.5 Manfaat Penelitian
Manfaat penelitian ini adalah untuk memperoleh sebuah perangkat lunak yang dapat
melakukan pencarian kata dalam kamus bahasa Indonesia-Mandarin.
1.6 Metodologi Penelitian
Dalam penelitian ini, tahapan-tahapan yang akan dilalui adalah sebagai berikut:
1. Studi pustaka
Pada tahap ini penelitian dimulai dengan peninjauan pustaka berupa buku-
buku, artikel - artikel ilmiah, dan penelitian - penelitian yang
didokumentasikan dalam bentuk jurnal yang berhubungan dengan Algoritma
Brute Force danAlgoritma Horspool.
2. Analisis dan Perancangan
Berkaitan dengan batasan masalah, pada tahap ini dilakukan analisa apa saja
yang dibutuhkan dalam penelitian ini dan selanjutnya dirancang dalam sebuah
model alur diagram sehingga menjadi suatu informasi.
3. Implementasi
Pada tahap ini sistem diimplementasikan dengan metode Algoritma Brute
Force dan Algoritma Horspool.
4. Pengujian
Setelah perancangan sistem selesai maka dilakukan tahap pengujian untuk
menentukan kesesuaian teori dan implementasi sistem.Selain itu pengujian
berguna untuk mengetahui kesalahan pada sistem yang dibuat.
5. Dokumentasi
Pada tahap ini pendokumentasian dilakukan selama penelitian, mulai dari
analisa hingga pengujian dalam bentuk skripsi.
Universitas Sumatera Utara
1.7 Sistematika Penulisan
Sistematika penulisan skripsi ini terdiri dari beberapa bagian utama yang dijelaskan
sebagai berikut:
BAB 1 PENDAHULUAN
Bab ini membahas latar belakang, rumusan masalah, batasan
masalah, tujuan penelitian, manfaat penelitian, metode penelitian
serta sistematika penulisan.
BAB 2 LANDASAN TEORI
Bab ini membahas tentang landasan teori tentang algoritma,
algoritma string matching, algoritma Brute Force, Horspool,
kompleksitas algoritma, kamus, dan beberapa penelitian terdahulu
yang relevan.
BAB 3 ANALISIS DAN PERANCANGAN SISTEM
Bab ini membahas mengenai String Matching dengan
algoritmaBrute Force dan Horspool, flow chart sistem serta
perancangan antarmuka aplikasi.
BAB 4 IMPLEMENTASI DAN PENGUJIAN SISTEM
Bab inimembahas tentang implementasi dan pengujian dari
perancangan sistem yang dirancang.
BAB 5 PENUTUP
Bab ini merupakan kesimpulan dari semua pembahasan yang ada
dengan saran-saran yang ditujukan bagi para pembaca atau
pengembang selanjutnya.
Universitas Sumatera Utara
BAB 2
LANDASAN TEORI
2.1 Kamus
Kata kamus berasal dari kata dalam bahasa Arab, yaitu qamus (bentuk
jamaknya qawamus). Bahasa Arab menyerap kata kamus dari kata dalam bahasa
Yunani kuno, okeanos yang berarti lautan. Tentu menjadi pertanyaan, bagaimana
kata kamus yang berurusan dengan kosakata berasal dari bahasa Yunani
kuno okeanos yang berarti lautan. Kalau kita mencoba untuk memahami sejarah kata
itu, jelaslah bahwa kata kamus memiliki makna dasarwadah pengetahuan, khususnya
pengetahuan bahasa yang tidak terhingga dalam dan luasnya, seluas dan sedalam
lautan (Chaer, 2007).
Masih menurut Chaer padanan kata kamus dalam bahasa Inggris adalah
dictionary, mulai digunakan pada karya tulis pada tahun 1526 dan berasal dari kata
dalam bahasa Latin, yaitu dictionarum. Kata ini diturunkan dari katadictio yang
berarti kata atau berkata. Padanannya dalam bahasa Belanda adalah woordenboek
yang dibedakan dariwoordenschat yang dalam bahasa Indonesia dipadankan dengan
perbendaharaan atau kosakata.
Selain pengertian kamus yang telah disebutkan di atas, ada juga pengertian
kamus yang dikemukakan oleh beberapa para ahli (Chaer, 2007) yaitu:
a. Kamus adalah buku referensi yang memuat daftar kata atau gabungan kata dengan
keterangan mengenai berbagai segi maknanya dan penggunaannya dalam bahasa,
biasanya disusun menurut abjad.
b. Kamus adalah sebuah buku berisi kata-kata dari sebuah bahasa, biasanya disusun
secara alfabetis, disertai keterangan akan artinya ucapannya, ejaannya, dan lain-
lain.
c. Kamus adalah buku berisi kumpulan kata-kata sebuah bahasa yang disususn secara
alfabetis diikuti dengan definisi atau terjemahannya dalam bahasa lain.
Universitas Sumatera Utara
d. Kamus sebagai sebuah buku referensi, memuat daftar kata-kata yang terdapat
dalam sebuah bahasa, disusun secara alfabetis, disertai keterangan cara
menggunkan kata itu.
Berdasarkan pengertian kamus yang dikemukakan oleh beberapa ahli di atas, dapat
disimpulkan beberapa hal sebagai berikut:
1. kamus termasuk buku referensi yang berisi kata-kata atau gabungan kata dari
suatu bahasa.
2. kata-kata tersebut disusun secara alfabetis.
3. kata-kata tersebut diberi keterangan tentang makna dan penggunaannya.
4. kata itu selain diberi keterangan maknanya, juga diberi keterangan tentang
ucapannya, ejaannya, dan berbagai hal lain.
5. keterangan tentang makna itu diberikan juga dalam bahasa lain.
2.2 Algoritma
Istilah algoritma (algorithm) berasal dari kata “algoris” dan “ritmis”, yang pertama
kali diungkapkan oleh Abu Ja’far Mohammed Ibn Musa al Khowarizmi (825 M)
dalam buku Al-Jabr Wa-al Muqabla. Dalam bidang pemrograman algoritma
didefenisikan sebagai suatu metode khusus yang tepat dan terdiri dari serangkaian
langkah yang terstruktur dan dituliskan secara matematis yang akan dikerjakan untuk
menyelesaikan suatu masalah dengan bantuan komputer (Jogiyanto, 2005).
Algoritma juga dapat didefenisikan sebagai proses komputasi yang mengambil
beberapa nilai atau menetapkan nilai sebagai input dan menghasilkan atau menetapkan
beberapa nilai sebagai output. Algoritma adalah urutan langkah – langkah komputasi
yang mengubah input menjadi output (Cormen et al. 2001).
2.3 Android
Android adalah generasi terbaru pada sistem operasi mobile yang berjalan pada Linux
Kernel (Holla, S. & Katti, M. 2012). Awalnya Google Inc. membeli Android Inc
pendatang baru yang membuat peranti lunak untuk ponsel. Kemudian untuk
mengembangkan Android, dibentuklah Open Handset Alliance, konsorsium dari 34
perusahaan peranti keras, peranti lunak, dan telekomunikasi, termasuk Google, HTC,
Universitas Sumatera Utara
Intel, Motorola, Qualcomm, T-Mobile, dan Nvidia. Tujuan aliansi tersebut yaitu untuk
mengakselerasi pembaharuan dalam mobile dan menawarkannya ke konsumen yang
lebih kaya, dan sedikit mahal (Gargenta, 2011).
Android merupakan platform yang open source. Seluruh tumpukan, dari modul
Linux tingkat rendah hingga ke library bawaan, dan dari framework aplikasi ke
aplikasi secara komplit, seluruhnya terbuka. Lebih dari itu, Android dilisensikan di
bawah lisensi yang ramah bisnis (Apache/MIT) sehingga orang lain bisa dengan bebas
memperpanjang dan menggunakannya untuk berbagai tujuan. Jadi, seorang
pengembang dapat memiliki akses ke seluruh source code platform. Hal ini
memungkinkan Anda untuk melihat keberanian dari sistem operasi android bekerja.
Sebagai produsen, sistem operasi android dapat ditanamkan untuk perangkat keras
tertentu. Seorang produsen tersebut juga dapat menambahkan bumbu rahasia
kepemilikannya sendiri, tanpa perlu memberitahukan kepada komunitas pengembang
jika seorang produsen tersebut tidak ingin. Kita dapat mulai menggunakannya dan
memodifikasi saat ini. Lebih dari itu, android memiliki banyak kaitan di berbagai
tingkatan platform, yang memungkinkan siapa pun untuk memperluasnya dengan cara
yang tak terduga (Gargenta, 2011).
Android adalah platform yang dibangun ditujukan untuk perangkat mobile.
Ketika merancang android, para tim melihat di masa mendatang kendala perangkat
mobile mungkin tidak akan berubah. Pertama, perangkat mobile bertenaga baterai, dan
kinerja baterai kemungkinan tidak akan bisa lebih baik dalam waktu dekat. Kedua,
perangkat mobile yang berukuran kecil akan selalu terbatas dalam hal memori dan
kecepatan. Android dirancang untuk berjalan pada berbagai fisik perangkat.Android
tidak membuat asumsi tentang ukuran perangkat layar, resolusi, chipset, dan
sebagainya. Intinya android dirancang untuk menjadi portabel (Gargenta, 2011).
Android adalah software untuk perangkat mobile yang mencakup sistem
operasi, middleware, dan kunci aplikasi. Android SDK (Software Development Kit)
menyediakan tools dan API yang diperlukan untuk memulai mengembangkan aplikasi
dengan menggunakan bahasa Java (Holla, S. & Katti, M. 2012).
Universitas Sumatera Utara
2.4 String Matching
2.4.1 Pengertian String Matching
String matching (pencocokan string) biasa digunakan dalam aplikasi seperti skema
database dan sistem jaringan. Ada dua metode pencocokan string yaitu exact
matching dan approximate matching. (Singla, N. 2012).String matching adalah
pencarian sebuah pattern pada sebuah teks (Cormen, T.H. et al. 1994). String
matching digunakan untuk menemukan suatu string yang disebut dengan pattern
dalam string yang disebut dengan teks (Charras, C. & Lecroq, T. 1997). Prinsip kerja
algoritma string matching (Effendi, D. et al. 2013) 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 pergeseran 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 (Effendi, D. et al. 2013),
yaitu:
1. Pattern, yaitu deretan karakter yang akan dicocokkan dengan teks, dinyatakan
dengan 𝑥𝑥[0 …𝑚𝑚 − 1], panjang pattern dinyatakan dengan 𝑚𝑚.
2. Teks, yaitu tempat pencocokan pattern dilakukan. Dinyatakan dengan
𝑦𝑦[0 …𝑛𝑛 − 1], panjang teks dinyatakan dengan 𝑛𝑛.
3. Alfabet, berisi semua simbol yang digunakan oleh bahasa pada teks dan pattern,
dinyatakan dengan ∑ dengan ukuran dinyatakan ASIZE.
2.4.2 Cara Kerja String Matching
Cara yang jelas untuk mencari pattern yang cocok dengan teks adalah dengan
mencoba mencari di setiap posisi awal dari teks dan mengabaikan pencarian secepat
mungkin jika karakter yang salah ditemukan (Knuth, D.E. et al. 1977). Proses pertama
adalah menyelaraskan bagian paling kiri dari pattern dengan teks. Kemudian
dibandingkan karakter yang sesuai dari teks dan pattern. Setelah seluruhnya cocok
Universitas Sumatera Utara
maupun tidak cocok dari pattern, window digeser ke kanan sampai posisi (𝑛𝑛 −𝑚𝑚 +
1) pada teks. Menurut Singh, R. & Verma, H.N.(2011), efisiensi dari algoritma
terletak pada dua tahap:
1. Tahap praproses, tahap ini mengumpulkan informasi penuh tentang pattern
dan menggunakan informasi ini pada tahap pencarian.
2. Tahap pencarian, pattern dibandingkan dengan window dari kanan ke kiri atau
kiri ke kanan sampai kecocokan atau ketidakcocokan terjadi.
Dengan sebuah nilai karakter (m < n) yang akan dicari dalam teks. Dalam
algoritma pencocokan string, teks diasumsikan berada di dalam memori, sehingga bila
kita mencari string di dalam sebuah arsip, maka semua isi arsip perlu dibaca terlebih
dahulu kemudian disimpan di dalam memori. Jika pattern muncul lebih dari sekali di
dalam teks, maka pencarian hanya akan memberikan keluaran berupa lokasi pattern
ditemukan pertama kali (Wulan, 2011).
2.4.3 Klasifikasi AlgoritmaString Matching
Algoritma string matching dapat diklasifikasikan menjadi tiga bagian menurut arah
pencariannya (Charras, C. & Lecroq, T. 1997), yaitu:
1. From left to right
Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk
membaca. Algoritma yang termasuk dalam kategori ini adalah algoritma Brute
Force, algoritma Morris dan Pratt yang kemudian dikembangkan menjadi
algoritma Knuth-Morris-Pratt.
2. From right to left
Dari arah kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara
partikal. Contoh algoritma ini adalah algoritma Boyer-Moore, yang kemudian
banyak dikembangkan menjadi algoritma Tuned Boyer-Moore, algoritma
Turbo Boyer-Moore, algoritma Zhu Takaoka dan algoritma Horspool.
3. In a specific order
Dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini
menghasilkan hasil terbaik secara teoritis. Algoritma yang termasuk kategori
ini adalah algoritma Colussi dan algoritma Crochemore-perrin.
Universitas Sumatera Utara
2.5 Algoritma Brute Force
Algoritma brute force adalah algoritma untuk mencocokkan pattern dengan semua
teks antara 0 dan n-m untuk menemukan keberadaan pattern dalam teks (Sarno et al.
2012). Di dalam pencocokkan string, terdapat istilah teks dan pattern. Teks
merupakan kata yang dicari dan dicocokkan dengan pattern. Sedangkan pattern
merupakan kata yang diinputkan untuk dicocokkan. Secara rinci, langkah–langkah
yang dilakukan algoritma ini saat mencocokkan string adalah:
1. Algoritma brute force mulai mencocokkan pattern dari awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter
pattern dengan karakter pada teks yang bersesuaian, sampai salah satu kondisi
berikut terpenuhi:
a. Karakter di pattern dan di teks yang dibandingkan tidak cocok.
b. Semua karakter di pattern cocok. Kemudian algoritma akan
memberitahukan penemuan di posisi ini.
3. Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan
mengulangi langkah ke-2 sampai pattern berada di ujung teks.
algoritma brute force tidak memerlukan fase preprocessing, dan ruang ekstra konstan
selain pola dan teks. (DU Vidanagama. 2015). Selama fase mencari perbandingan
karakter teks dapat dilakukan dalam urutan apapun. Kompleksitas waktu fase
pencarian ini O (m x n) (ketika mencari (am-1 b dalam an). jumlah yang diharapkan
dari perbandingan karakter teks 2n. (Charras et al. 1997). Sebagai contoh, dapat
dilihat pada Tabel 2.1 berikut.
Text : DEARARINI
Pattern: ARINI
Tabel 2.1 Iterasi algoritma Brute Forcepertama
m 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I I 0 1 2 3 4
Universitas Sumatera Utara
Terdapat ketidakcocokan teks dengan pattern seperti yang terlihat pada Tabel
2.1 maka, dilakukan pergeseran ke kanan pada window sebanyak 1 kali. Hal ini
terlihat pada Tabel 2.2 .
Tabel 2.2 Iterasi algoritma Brute Forcekedua
M 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I I 0 1 2 3 4
Terdapat ketidakcocokan teks dengan pattern seperti yang terlihat pada Tabel
2.2 maka, dilakukan pergeseran ke kanan pada window sebanyak 1 kali. Hal ini
terlihat pada Tabel 2.3 .
Tabel 2.3 Iterasi algoritma Brute Forceketiga
m 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I i 0 1 2 3 4
Terdapat ketidakcocokan teks dengan pattern seperti yang terlihat pada Tabel
2.3 maka, dilakukan pergeseran ke kanan pada window sebanyak 1 kali. Hal ini
terlihat pada Tabel 2.4 .
Tabel 2.4 Iterasi algoritma Brute Forcekeempat
m 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I i 0 1 2 3 4 Terdapat ketidakcocokan teks dengan pattern seperti yang terlihat pada Tabel
2.4 maka, dilakukan pergeseran ke kanan pada window sebanyak 1 kali. Hal ini
terlihat pada Tabel 2.5 .
Tabel 2.5 Iterasi algoritma Brute Forcekelima
m 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I i 0 1 2 3 4
Universitas Sumatera Utara
Pada iterasi kelima yang terlihat pada Tabel 2.5, window telah berada pada
akhir teks dan semua pattern cocok dengan teks “ARINI”. Seluruh pencocokan
karakter menggunakan algoritma Brute Forcetelah selesai dan berhenti pada iterasi
kelima.
2.6 Algoritma Horspool
Algoritma Horspool adalah penyederhanaan dari algoritma Boyer-Moore yang dibuat
oleh R. Nigel Horspool. Menurut Horspool, R.N. (1980), masalah dalam pencarian
teks ini adalah mencari dalam teks yang besar untuk menemukan pattern pertama.
Karena teks yang dicari bisa sangat besar (memungkinkan ratusan ribu karakter) maka
penting untuk menggunakan teknik yang lebih efisien. Algoritma Horspool bekerja
dengan metode yang hampir sama dengan algoritma Boyer-Moore namun tidak
melakukan lompatan berdasarkan karakter pada pattern yang ditemukan tidak cocok
pada teks.Aturan ini sangat tidak efisien ketika bekerja denganhuruf kecil
dibandingkan dengan panjang jika pola. Karena itu,ketika bekerja dengan tabel ASCII
dan pencarian biasa dalameditor teks aturan pergeseran buruk bekerja jauh lebih baik.
(Wahlstrom,S. 2013)
Algoritma Horspool mempunyai nilai pergeseran karakter yang paling kanan
dari window. Pada tahap observasi awal (preprocessing).Secara umum, tahap
preprocessing digunakan untuk preproses karakter pola sebagaicara untuk
mengumpulkaninformasi yang berguna dalam tahap pencarian. Informasiyang
dikumpulkan dalam tahap preprocessing adalahdigunakan untuk meminimalkan
jumlah perbandingan karakter bersama dengan jumlah total usaha. Dalamalgoritma
pencocokan string hybrid yang diusulkan, fase preprocessing tergantung pada
Pencarian Cepat burukKarakter meja (qsBc) untuk menentukan posisi berikutnya dari
jendela teks. Algoritma Pencarian Cepat memberikannilai pergeseran maksimum (m +
1) ketika karakter berikutnya dengan karakter paling kanan pada jendela teks
tidaktidak muncul dalam pola. Di sisi lain, ketika characternext dengan karakter
paling kanan pada tekswindow sama dengan karakter paling kanan, algoritma
Pencarian Cepat memberikan nilai pergeseran minimum.(Al-Dabbagh & Barnouli.
2017).nilai shift akan dihitung untuk semua karakter. Pada tahap ini, dibandingkan
pattern dari kanan ke kiri hingga kecocokan atau ketidakcocokan pattern terjadi.
Karakter yang paling kanan pada window digunakan sebagai indeks dalam
Universitas Sumatera Utara
melakukannilai shift. Dalam kasus ketidakcocokan (karakter tidak terdapat pada
pattern) terjadi, window digeser oleh panjang dari sebuah pattern. Jika tidak, window
digeser menurut karakter yang paling kanan pada pattern (Baeza-Yates, R.A. &
Regnier, M. 1992).
2.6.1 Pencarian Dengan Algoritma Horspool
Terdapat dua tahap pada pencocokan string menggunakan algoritma Horspool (Singh,
R. & Verma, H.N. 2011), yaitu:
1. Tahap praproses
Pada tahap ini, dilakukan observasi pattern terhadap teks untuk membangun
sebuah tabel bad-match yang berisi nilai shift ketika ketidakcocokan antara
pattern dan teks terjadi. Secara sistematis, langkah-langkah yang dilakukan
algoritma Horspool pada tahap praproses adalah:
a. Algoritma Horspool melakukan pencocokan karakter ter-kanan pada
pattern.
b. Setiap karakter pada pattern ditambah ke dalam tabel bad-match dan
dihitung nilai shift-nya.
c. Karakter yang berada pada ujung pattern tidak dihitung dan tidak
dijadikan karakter ter-kanan dari karakter yang sama dengannya.
d. Apabila terdapat dua karakter yang sama dan salah satunya bukan
karakter ter-kanan, maka karakter dengan indeks terbesar yang dihitung
nilai shift-nya.
e. Algoritma Horspool menyimpan panjang dari pattern sebagai panjang
nilai shift secara default apabila karakter pada teks tidak ditemukan
dalam pattern.
f. Nilai (value) shift yang akan digunakan dapat dicari dengan perhitungan
panjang dari pattern dikurang indeks terakhir karakter dikurang 1, untuk
masing-masing karakter, 𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣 = 𝑚𝑚− 𝑖𝑖 − 1.
Sebagai contoh, dapat dilihat pada Tabel 2.6 berikut.
Pattern: ARINI
𝐴𝐴⏟0𝑅𝑅⏟1𝐼𝐼⏟2𝑁𝑁⏟3𝐼𝐼⏟4
Universitas Sumatera Utara
Tabel 2.6Bad-match pada praproses
Value [A[1]] = 5 – 1 – 1 = 3
Value [R[3]] = 5 – 3 – 1 = 1
Value [I[2]] = 5 – 2 – 1 = 2
Value [N[4]] = karena 𝑖𝑖<𝑚𝑚 − 1 maka Value [N[4]] bernilai jumlah karakter pada
pattern (m) yaitu 5. Dan untuk karakter yang tidak terdapat pada
pattern, karakter tersebut bernilai jumlah karakter pattern itu sendiri
yaitu 5
2. Tahap pencarian
Secara sistematis, langkah-langkah yang dilakukan algoritma Horspool pada tahap
pencarian adalah:
a. Dilakukan perbandingan karakter paling kanan pattern terhadap window.
b. Tabel bad-match digunakan untuk melewati karakter ketika ketidakcocokan
terjadi.
c. Ketika ada ketidakcocokan, maka karakter paling kanan pada window berfungsi
sebagai landasan untuk menentukan jarak shift yang akan dilakukan.
d. Setelah melakukan pencocokan (baik hasilnya cocok atau tidak cocok)
dilakukan pergeseran ke kanan pada window.
e. Prosedur ini dilakukan berulang-ulang sampai window berada pada akhir teks
atau ketika pattern cocok dengan teks.
Untuk menggambarkan rincian algoritma, akan diberikan contoh kasus dimana pattern
P = “ARINI” dan teks T = “DEARARINI”. Inisialisasi awal dan pembuatan bad-
match terlihat pada Tabel 2.7 dan Tabel 2.8 berikut.
Tabel 2.7 Inisialisasi awal bad-match
M 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I
Karakter Index Value A 1 3 R 3 1 I 2 2 N 4 4
Universitas Sumatera Utara
I 0 1 2 3 4 Tabel 2.8 Pembuatan bad-match
P A R I N I 1 3 2 4 V 3 1 2 0
Seperti yang terlihat pada Tabel 2.7 di atas, inisialisasi awal bad-match
dilakukan. Setiap teks dan pattern masing-masing diberi nilai m dan i, dimana m
sebagai panjang pattern dan i sebagai indeks. Tabel 2.8 menunjukkan nilai pergeseran
bad-match dengan menghitung nilai v seperti yang telah dilakukan pada Tabel 2.6.
Pada tahap awal pencarian, dilakukan perbandingan karakter paling kanan pattern
terhadap window. Apabila terjadi ketidakcocokan, akan dilakukan pergeseran ke
kanan untuk melewati karakter yang tidak cocok dimana nilai pergeserannya terdapat
pada tabel bad-match. Karakter paling kanan teks pada window berfungsi sebagai
landasan untuk menentukan jarak geser yang akan dilakukan. Hal ini terlihat pada
Tabel 2.9 berikut.
Tabel 2.9 Iterasi algoritma Horspool pertama
M 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I I 0 1 2 3 4
Terdapat ketidakcocokan seperti yang terlihat pada Tabel 2.9. Karakter “A”
adalah karakter paling kanan teks pada window. Pada tabel bad-match, nilai geser
karakter “A” adalah 1. Maka, dilakukan pergeseran ke kanan pada window sebanyak 1
kali. Hal ini terlihat pada Tabel 2.10.
Tabel 2.10 Iterasi algoritma Horspool kedua
M 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I I 0 1 2 3 4
Pada Tabel 2.10, terdapat ketidakcocokan kembali antara karakter “R” dan “I”.
Pada tabel bad-match, nilai geser karakter “R” adalah 3. Maka, dilakukan pergeseran
ke kanan pada window sebanyak 3 kali. Hal ini terlihat pada Tabel 2.11.
Universitas Sumatera Utara
Tabel 2.11 Iterasi algoritma Horspool ketiga
M 1 2 3 4 5 6 7 8 9 T D E A R A R I N I P A R I N I I 0 1 2 3 4
Pada iterasi ketiga yang terlihat pada Tabel 2.11, window telah berada pada
akhir teks dan semua pattern cocok dengan teks “ARINI”. Seluruh pencocokan
karakter menggunakan algoritma Horspool telah selesai dan berhenti pada iterasi
ketiga.
2.7 Penelitian Terkait
Adapun penelitianterdahulu yang terkait dengan penelitian yang dilakukan oleh
penulis antara lain:
a. Penelitian Karunia (2005) mengangkat penelitian dengan judul “Perbandingan
Waktu Proses Pencarian String antara Algoritma Brute Force dengan
Algoritma Not So Naïve”. Hasil penelitian menunjukkan bahwa waktu proses
pencarian string dengan menggunakan algoritma Brute Force lebih singkat
dibandingkan dengan algoritma Not So Naïve.
b. Tambunan (2013) dari Institut Teknologi Bandung mengangkat penelitian
dengan judul “Perbandingan Penggunaan Algoritma BM Dan Algoritma
Horspool Pada Pencarian String Dalam Bahasa Medis”. Didapatkan hasil
bahwa pencarian string pada teks bahasa medis dengan menggunakan
algoritma Boyer-Moore lebih baik dibandingkan dengan algoritma
Horspool. Bahasa medis banyak menggunakan kosakata yang panjang
dengan varian karakter yang beragam. Karakter teks seperti bahasa medis
ini sangat cocok dengan algoritma Boyer-Moore sehingga algoritma ini dapat
bekerja dengan maksimal pada pencarian string dengan teks menggunakan
bahasa medis seperti ini.
c. Penelitian oleh Nababan (2015) mengangkat penelitian dengan judul
“Implementasi Algoritma Brute Force dan Algoritma Knuth-Morris-Pratt
(kmp) dalam Pencarian Word Suggestion”. Hasil penelitian ini didapat bahwa
Algoritma Knuth-Morris-Pratt (KMP) menyimpan sebuah informasi yang
Universitas Sumatera Utara
digunakan untuk melakukan jumlah pergeseran, sehingga algoritma ini
melakukan pergeseran lebih jauh (tidak hanya bergeser satu karakter seperti
dalam Brute Force). Dengan ini penggunaan algoritma Knuth-Morris-Pratt
(KMP) dapat mempersingkat waktu dengan hasil rata-rata runtime 0,42717 ms
dibandingkan dengan algoritma Brute Force yang memiliki hasil rata-rata
runtime 0,44683 ms dalam pencocokan string-nya.
d. Wulan (2011) dari Universitas Islam Negeri Syarif Hidayatullah Jakarta
mengangkat penelitian dengan Judul “Analisis Penerapan String Matching
Dalam Komparasi Data Kepesertaan Jaminan Kesehatan Masyarakat
(JAMKESMAS)“. Hasil penelitian menunjukkan bahwa semakin banyak
kecocokkan yang dipilih maka jumlah kecocokkan yang dimiliki di database
semakin rendah dan semakin lama waktu yang dibutuhkan dalam
pencocokkan. Namun dengan sedikitnya ukuran kecocokkan yang dipilih maka
jumlah kecocokan yang dimiliki di database semakin tinggi dan semakin cepat
waktu yang dibutuhkan dalam pencocokkan.
e. Putra, Anton Gumala. (2014) mengangkat penelitian tentang Analisis
Perbandingan Algoritma Greedy dan Brute Force dalam Pencarian Kartu
Tertinggi pada Kartu Remi. Hasil penelitian menunjukkan bahwaPada
permasalahan pencarian kartu tertinggi 52 kartu ini, Brute Force lebih cepat
rata-rata 0.113 detik dari Greedy. Greedy tidak terlihat optimum dikarenakan
jumlah kartu yang kecil. Sisa akhir kartu pencarian kartu tertinggi secara
ascending dan descending dengan kedua algoritma adalah sama (2 wajik, 2
keriting, 2 hati, 2 sekop, 3 wajik, 3 keriting).
Universitas Sumatera Utara
BAB 3
ANALISIS DAN PERANCANGAN SISTEM
3.1 Analisis Sistem
Analisis sistem adalah sebuah teknik pemecahan masalah yang menguraikan
sebuah sistem menjadi bagian – bagian komponen dengan tujuan mempelajari
seberapa bagus bagian–bagian komponen tersebut bekerja dan berinteraksi untuk
meraih tujuan mereka. Analisis sistem adalah pembelajaran sebuah sistem dan
komponen-komponennya sebagai prasyarat desain sistem, spesifikasi sebuah sistem
yang baru dan diperbaiki. Analisis sistem ini juga merupakan suatu proses
mengumpulkan dan menginterpretasikan kenyataan– kenyataan yang ada,
mendiagnosa persoalan dan menggunakan keduanya untuk memperbaiki sistem
(Whitten et al. 2004).
Analisis sistem memiliki tiga fase untuk mendeskripsikan pengembangan
sistem yaitu, analisis masalah, analisis kebutuhan, dan analisis proses. Tujuan analisis
masalah adalah mempelajari dan memahami bidang masalah dengan cukup baik untuk
secara menyeluruh menganalisis masalah, kesempatan dan batasannya (Whitten et al.
2004). Tujuan dari analisis kebutuhan yaitu menjelaskan fungsi – fungsi yang
ditawarkan dan mampu dikerjakan oleh sistem, baik kebutuhan fungsional maupun
non fungsional. Dan tujuan dari analisis proses yaitu untuk memodelkan tingkah laku
dari sistem.
3.1.1 Analisis Masalah
Analisis masalah merupakan proses mengidentifikasi sebab dan akibat
dibangunnya sebuah sistem agar sistem yang akan dibangun tersebut dapat berjalan.
Aplikasi kamus yang dibangun ini tidak mencari kata secara manual. Dengan
adanya fasilitas pencarian pada aplikasi kamus dapat mempermudah user
mendapatkan kata yang ingin dicarinya. Dengan menggunakan salah satu dari
Universitas Sumatera Utara
Algoritma String Matching seperti, Algoritma Brute Force dan Algoritma Horspool
yang akan mempermudah dan mempercepat pencarian kata dalam kamus.
Untuk mengidentifikasi masalah tersebut digunakan diagram Ishikawa
(fishbone diagram). Diagram Ishikawa/diagram tulang ikan/diagram tulang
ikan/cause-and-effect matrix adalah diagram yang menggambarkan secara detail
semua penyebab yang berhubungan dengan suatu permasalahan. Diagram
Ishikawa berbentuk seperti ikan yang strukturnya terdiridari kepala ikan (fish’s
head) dan tulang-tulang ikan (fish’s bones). Nama atau judul dari masalah yang
diidentifikasi terletak pada bagian kepala ikan, sedangkan tulang-tulang ikan
menggambarkan penyebab-penyebab masalah tersebut. Diagram Ishikawa pada sistem
ini dapat dilihat pada Gambar 3.1.
Sulit mencari kata pada kamus secara manual
Dibutuhkan media untuk mencari kata terjemahan yang lebih praktis
Metode yang dilakukan masih kurang efisien dalam waktu
Metode pencarian kata pada kamus Indonesia-Mandarin belum dirancang dalam bentuk sistem
Kamus Indonesia-Mandarin masih tersedia dalam bentuk buku
Tidak ada fasilitas searching pada kamus manual
Tidak ada algoritma dalam mencocokkan kata karena kamus masih dalam bentuk manual.
Banyaknya lapangan pekerjaan yang membutuhkan karyawan yang mahir bahasa mandarin.
ManusiaManusia MetodeMetode
MateriMateri MesinMesin
Gambar 3.1 Fishbone Diagram
Seperti yang terlihat pada Gambar 3.1 di atas, masalah utama adalah pada
persegi panjang di posisi paling kanan gambar (bagian kepala) Fishbone Diagram.
Kategori masalah ditunjukkan pada empat persegi panjang yang masing-masing
terhubung ke garis utama, sedangkan rincian masalah ditunjukkan dalam bentuk tanda
panah horizontal pada masing-masing kategori masalah.
Universitas Sumatera Utara
3.1.2 Analisis Kebutuhan Sistem
Dalam analisis kebutuhan sistem terdapat dua bagian penting yang harus dipenuhi,
yaitu analisis kebutuhan fungsional sistem dan analisis kebutuhan non-fungsional
sistem.
3.1.2.1 Analisis Kebutuhan Fungsional Sistem
Analisis kebutuhan fungsional sistem adalah analisis terhadap kebutuhan secara
fungsional baik dalam aliran data ataupun informasi dan merupakan hal yang harus
dimiliki oleh sistem untuk mencapai tujuannya. Berikut ini merupakan beberapa
kebutuhan fungsional sistem yang akan dibangun, antara lain:
1. Sistem dapat membaca pattern yang ingin dicari pada teks yang sebelumnya
telah diinput oleh user.
2. Sistem dapat memanggil dan menampilkan data berupa list kata.
3. Sistem dapat menghasilkan arti kata dari pattern yang dicari dengan
menggunakan algoritma Brute Force dan AlgoritmaHorspool.
4. Sistem dapat menghasilkan perbandingan waktu antara Algoritma Brute
Forcedengan AlgoritmaHorspool.
3.1.2.2 Analisis Kebutuhan Non-Fungsional Sistem
Analisis kebutuhan non-fungsional adalah suatu analisis untuk mengetahui elemen-
elemen apa saja yang berhubungan dengan sistem yang sedang berjalan. Untuk
mendukung kinerja sistem, sistem sebaiknya dapat berfungsi sebagai berikut:
1. Performa
Perangkat lunak yang dibangun dapat menunjukkan hasil pencarian kata yang
dimasukkan oleh pengguna dengan lebih cepat.
2. Mudah Dipelajari dan Digunakan
Tampilan dari perangkat lunak yang dibangun adalah ramah pengguna (user
friendly) dan sederhana.
3. Hemat Biaya
Perangkat lunak yang dibangun adalah hemat biaya karena dapat diakses tanpa
menggunakan jaringan internet dan tidak berbayar.
Universitas Sumatera Utara
3.1.3 Pemodelan Sistem
Pemodelan sistem dilakukan untuk memperoleh gambaran yang lebih jelas tentang
objek apa saja yang akan berinteraksi dengan sistem, serta hal-hal apa saja yang harus
dilakukan oleh sebuah sistem sehingga sistem dapat berfungsi dengan baik sesuai
dengan kegunaannya.
Pada penelitian ini digunakan UML (Unified Modeling Language) sebagai
bahasa pemodelan untuk mendesain merancang sistem yang akan dibangun. UML
yang digunakan antara lainuse case diagram, activity diagram dan sequence diagram.
3.1.3.1 Use Case Diagram
Use Case Diagram adalah sebuah diagram yang dapat merepresentasikan interaksi
yang terjadi antara user dengan sistem. Use Case Diagram mendeskripsikan interaksi
tipikal antara pengguna sistem dengan sistem itu sendiri, dengan memberikan sebuah
narasi tentang bagaimana sistem tersebut digunakan. Use CaseDiagram dari sistem
aplikasi kamus ini akan dibangun dan dapat ditunjukkan pada Gambar 3.2.
Gambar 3.2 Use Case Diagram Sistem
Didalam Use Case Diagram diatas terdapat satu actor yang berperan sebagai
user. Untuk menampilkan hasil terjemahan user harus memasukkan inputan berupa
kata yang ingin diterjemahkan ke dalam search box. Selanjutnya sistem akan
melakukan pencarian dan pencocokan kata dengan kosakata yang terdapat pada
Universitas Sumatera Utara
database. Kemudian sistem akan menampilkan hasil terjemahannya serta waktu
pencarian.
3.1.3.2 Activity Diagram
Activity Diagram adalah teknik untuk menggambarkan logika procedural, jalur kerja
sistem.Diagram ini menggambarkan berbagai alur kerja dalam sistem yang sedang
dirancang, bagaimana masing-masing alur kerja berawal, decision yang mungkin
terjadi, dan bagaimana aktifitas atau alur kerja berakhir.ActivityDiagram dari sistem
yang akan dibangun dapat ditunjukkan pada Gambar 3.3.
Gambar 3.3 Activity Diagram
Pada Activity diagramuser dapat dijelaskan bahwa user dapat menginputkan kata
sesuai dengan yang ingin dicari. Lalu user dapat melihat hasil pencocokan kata yang
sesuai dengan inputan beserta terjemahannya dan user dapat mengetahui berapa lama
proses pencarian menggunakan Algoritma Brute Force dan Algoritma Horspool.
Universitas Sumatera Utara
3.1.3.3 Sequence Diagram
Sequence Diagram merupakan diagram yang menunjukkan bagaimana kelompok-
kelompok objek saling berkolaborasi dalam beberapa behavior. Sequence diagram
secara khusus, menjabarkan behavior sebuah scenario tunggal. Diagram tersebut
menunjukkan sejumlah objek contoh dan pesan-pesan yang melewat objek-objek
tersebut di dalam use case.Sequence Diagram dari sistem aplikasi kamus bahasa
Indonesia – Mandarin yang akan dibangun dapat ditunjukkan pada Gambar 3.4.
Gambar 3.4 Sequence Diagram
3.2 Flowchart Sistem
Flowchart atau bagan alir adalah bagan (chart) yang menunjukkan alir (flow) didalam
program atau prosedur sistem secara logika.Flowchart merupakan gambar atau bagan
yang memperlihatkan urutan dan hubungan antar proses beserta pernyataannya.
Dengan demikian setiap simbol menggambarkan proses tertentu. Sedangkan antara
proses digambarkan dengan garis penghubung. Flowchart digunakan terutama untuk
alat bantu komunikasi dan untuk dokumentasi. Flowchart dari sistem yang akan
dibangun dapat ditunjukkan pada Gambar 3.5.
Universitas Sumatera Utara
Gambar 3.5 Flowchart Sistem
Pada Flowchart diatas menggambarkan alur sistem secara umum pada kamus
bahasa Indonesia – Mandarin, dimana user memilih tab algoritma dan menginput kata
yang ingin dicari, kemudian sistem akan memproses pencocokan kata berdasarkan
perhitungan Algoritma Brute Force dan Algoritma Horspool dan menampilkan hasil
pencarian kata beserta terjemahannya.
Universitas Sumatera Utara
3.3 Pseudocode Program
3.3.1 Pseudocode Algoritma Brute Force
Berikut adalah pseudocode algoritma Brute Forcepada tahap pencarian: procedure BruteForceSearch( 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: integer Algoritma: for (i:=0 to m-n) do j:=0 while (j < n and T[i+j] = P[j]) do j:=j+1 endwhile if(j >= n) then ketemu[i]:=true; endif
endfor
3.3.2 Pseudocode Algoritma Horspool
Berikut adalah pseudocode algoritma Horspool pada tahap praproses: Procedure preBmBc ( input P : array[0. . m-1] of char, input m : 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
Dan berikut adalah pseudocode algoritma Horspool pada tahap pencarian:
Procedure HorspoolSearch ( input m, n : integer,
Universitas Sumatera Utara
input P : array[0 . . m-1] of char, input T : array[0 . . n-1] of char, output find : array[0 . . m-1] of boolean ) Deklarasi: j : integer BmBc : array[0 . . n] of integer c : char Algoritma: preBmBc(P, m, BmBc) j := 0 while (j <= n – m) do c = T[j + m – 1]; if (P[m – 1] == c && memcmp(P, T + j, m-1) == 0) then find[j] := true; endif j := j + BmBc[c]; endwhile
3.4 Perancangan Sistem
Proses perancangan antarmuka (interface) sebuah sistem adalah proses yang
cukup penting dalam perancangan sebuah sistem. Merancang antarmuka merupakan
bagian yang paling penting dari merancang sebuah sistem. Sebuah antarmuka harus
dirancang dengan memperhatikan faktor pengguna sehingga sistem yang
dibangun dapat memberikan kenyamanan dan kemudahan untuk digunakan oleh
pengguna.
3.4.1 Rancangan Halaman Menu Utama
Halaman ini merupakan tampilan awal ketika aplikasi pertama kali dijalankan. Pada
halaman ini terdapat dua tab, yaitu tab Algoritma Brute Force dan tab Algoritma
Horspool. Rancangan halaman tab masing-masing algoritma dapat dilihat pada
gambar 3.6 dan gambar3.7.
Universitas Sumatera Utara
Gambar 3.6 Tampilan Tab Algoritma Brute Force
Gambar 3.7 Tampilan Tab Algoritma Horspool
Universitas Sumatera Utara
Keterangan Gambar :
1) Action Bar memuat judul aplikasi dan sebuah icon. Dimana icon memuat
pilihan halaman about.
2) Tabhost digunakan untuk memilih tabalgoritma.
3) FieldText digunakan untuk memasukkan kata yang ingin dicari terjemahannya.
4) Button untuk mencari hasil terjemahan.
5) Textview untuk menampilkan hasil runningtime.
3.4.2 Rancangan Halaman Hasil Pencarian
Pada halaman ini terdapat dua tab, yaitu tab Algoritma Brute Force dan tab Algoritma
Horspool, dimana pengguna yang ingin mencari kata beserta artinya juga dapat
melihat hasil running time dari masing-masing algoritma. Rancangan halaman hasil
pencarian masing-masing algoritma dapat dilihat pada gambar 3.8 dan gambar3.9.
Gambar 3.8 Tampilan Tab Hasil Pencarian Algoritma Brute Force
Universitas Sumatera Utara
Gambar 3.9 Tampilan Tab Hasil Pencarian Algoritma Horspool
Keterangan Gambar :
1) Action Bar memuat judul aplikasi dan sebuah icon. Dimana icon memuat
pilihan halaman about.
2) Tabhost digunakan untuk memilih tabalgoritma.
3) FieldText digunakan untuk memasukkan kata yang ingin dicari
terjemahannya.
4) Button untuk mencari hasil terjemahan.
5) Textview untuk menampilkan hasil running time.
6) Listview untuk menampilkan kata yang ada di dalam database.
3.4.3 Rancangan Halaman About
Halaman about merupakan halaman yang muncul ketika user menekan tombol about
pada halaman menu utama.Rancangan halaman about dapat dilihat pada gambar 3.10.
Universitas Sumatera Utara
Gambar 3.10 Tampilan Halaman About.
Keterangan Gambar :
1) Action Bar berisikan judul dari halaman aplikasi.
2) ImageView untuk menampilkan logo aplikasi.
3) TextView untuk menampilkan judul aplikasi, identitas singkat penulis,
program studi, fakultas, universitas, kota dan tahun.
Universitas Sumatera Utara
BAB 4
IMPLEMENTASI DAN PENGUJIAN SISTEM
4.1 Implementasi Sistem
Tahap implementasi sistem merupakan langkah lanjutan dari tahapan analisis dan
perancangan sistem yang dirangkum di bab tiga. Pada tahapan ini, segala yang telah di
bahas pada tahapan analisis dan perancangan akan diimplementasikan ke dalam
bahasa pemrograman Java. Proses dari sistem dan tampilan antarmuka keduanya
ditangani menggunakan bahasa Java dengan perangkat lunak yang digunakan adalah
Android Studio.
4.1.1 Tampilan Antarmuka Utama
Halaman utama merupakan antarmuka awal ketika aplikasi pertama sekali dijalankan.
Pada halaman ini terdapat dua kondisi, pada saat pengguna memilih untuk mencari
terjemahan bahasa Indonesia ke bahasa Mandarin pada algoritma brute force dan pada
saat pengguna memilih untuk mencari terjemahan bahasa Indonesia ke bahasa
Mandarin pada algoritma horspool.
Gambar 4.1 Tampilan Awal Tab Algoritma Brute Force
Universitas Sumatera Utara
Gambar 4.2 Tampilan Awal Tab Algoritma Horspool
4.1.2 Tampilan Antarmuka Hasil Pencarian
Pada tampilan hasil pencarian, sistem akan menampilkan hasil dari kata yang dicari
oleh pengguna/user. Setiap kata di dalam sumberdata yang mengandung kata yang
dimasukkan oleh pengguna akan ditampilkan di dalam listview.
Gambar 4.3 Tampilan Hasil Pencarian Algoritma Brute Force
Universitas Sumatera Utara
Gambar 4.4 Tampilan Hasil Pencarian Algoritma Horspool
4.1.3 Tampilan Antarmuka About
Pada tampilan menu yang berisi informasi singkat dari penulis. Tampilan menu about
dapat dilihat pada gambar 4.5 berikut ini.
Gambar 4.5 Tampilan Antarmuka About
Universitas Sumatera Utara
4.2 Pengujian Sistem
Pengujian terhadap sistem dilakukan untuk membuktikan bahwa sistem yang telah
dibangun berjalan dengan baik serta sesuai dengan analisis dan perancangan sistem
yang telah dibuat sebelumnya.
4.2.1 Pengujian Proses Pencarian Kata dengan Algoritma Brute Force
Pada bagian ini akan dijelaskan pengujian terhadap algoritma Brute Force yang
dibangun. Pada edittext, pengguna memasukkan kata yang akan dicari seperti contoh:
“ada” maka sistem akan menampilkan beberapa hasil seperti: “ada”, “adalah”, “adat
istiadat” dan lainnya. Untuk hasil pengujian selengkapnya dapat dilihat pada tabel 4.1
Tabel 4.1 Tabel Pengujian dengan Algoritma Brute Force
Pattern Tampilan Aplikasi Hasil Running Time
ab
Cocok 0.915528 ms
Universitas Sumatera Utara
ada
Cocok 3.02124 ms
eka
Cocok 1.220703 ms
Universitas Sumatera Utara
isa
Cocok 1.281739 ms
dada
Cocok 1.495362 ms
Universitas Sumatera Utara
Sap
Cocok 1,014635 ms
wan
Cocok 1,018334 ms
Universitas Sumatera Utara
asi
Cocok
1,965886 ms
Bunga
Cocok 1,004166 ms
Universitas Sumatera Utara
Sabar
Cocok
0,946302 ms
4.2.2 Pengujian Proses Pencarian Kata dengan Algoritma Horspool.
Pada bagian ini, sama dengan penjelasan pada pengujian pencarian kata dengan
algoritma Brute Force akan dijelaskan juga pengujian terhadap algoritma Horspool
yang dibangun.
Pada edittext, pengguna memasukkan kata yang akan dicari seperti contoh:
“ada” maka sistem akan menampilkan beberapa hasil seperti: “ada”, “adalah”, “adat
istiadat” dan lainnya. Untuk hasil pengujian selengkapnya dapat dilihat pada Tabel 4.2
Universitas Sumatera Utara
Tabel 4.2 Tabel Pengujian dengan Algoritma Horspool
Pattern Tampilan Aplikasi Hasil Running Time
ab
Cocok 1.037598 ms
ada
Cocok 3.322031 ms
Universitas Sumatera Utara
eka
Cocok 1.495362 ms
isa
Cocok 1.708984 ms
Universitas Sumatera Utara
dada
Cocok 2.990722 ms
Sap
Cocok 1,071407 ms
Universitas Sumatera Utara
wan
Cocok 1.218854 ms
asi
Cocok
1,062917 ms
Universitas Sumatera Utara
Bunga
Cocok 1,004166 ms
Sabar
Cocok
1,256563 ms
Universitas Sumatera Utara
4.2.3 Hasil Pengujian
Berdasarkan hasil pengujian dari penelitian Tabel 4.1 dan Tabel 4.2, running timedari
pencarian kata dan jumlah hasil pencarian yang dapat ditemukan pada Algoritma
Brute Force dan Horspool yang dilakukan terhadap string yang berbeda dengan 10
kali percobaan dan menghasilkan nilai rata-rata dari setiap string tersebut.
Tabel 4.3 Hasil Pengujian Algoritma Brute Force dan Algoritma Horspool
No String Running Time
Brute Force (ms)
Running Time
Horspool (ms)
1 ab 0.915528 1.037598
2 ada 3.02124 3.02124
3 eka 1.220703 1.495362
4 isa 1.281739 1.708984
5 dada 1.495362 2.99072
6 sap 1.014635 1.071407
7 wan 1.018334 1.218854
8 asi 1.965886 1.062917
9 bunga 1.004166 1.455364
10 sabar 0.946302 1.256563
Total 13.8839 16.31901
Rata- rata 1.38839 1.631901
Adapun hasil pengujian dari kedua Algoritma yang dapat dilihat pada Tabel
4.3.Setelah diperoleh hasil pengujian dari tabel 4.1 dan tabel 4.2 maka dibuat grafik
perbandingan dari hasil pengujian untuk kedua algoritma tersebut.Grafik dapat dilihat
pada Gambar 4.6.
Universitas Sumatera Utara
Gambar 4.6 Perbandingan Hasil Running Time Algoritma Brute Force dan Horspool
Berdasarkan grafik tersebut dijelaskan bahwa Algoritma Brute Force
menghasilkanRunning Time yang relatif kecil untuk dibandingkan dengan Algoritma
Horspool. Algoritma Brute Force lebih cepat dalam proses pencocokan kata
dibandingkan dengan Algoritma Horspool. Rata-rata dari total hasil perbandingan dari
kedua Algoritma tersebut dapat dijelaskan pada Gambar 4.7.
Gambar 4.7 Perbandingan nilai total dan rata rata algoritma Brute Force dan Horspool
0
0,5
1
1,5
2
2,5
3
3,5
ab ada eka isa dada sap wan asi bunga sabar
Brute Force
Horspool
13,8839
1,38839
16,31901
1,631901
02468
1012141618
Total Rata-rata
Brute Force HorspoolRunning Time
Wak
tu
Universitas Sumatera Utara
4.3 Kompleksitas Algoritma
Kompleksitas algoritma yang akan diuji adalah kompleksitas dari algoritma Brute
Force dan algoritma Horspool.
4.3.1 Kompleksitas Algoritma Brute Force
Kompleksitas untuk fungsi match pada algoritma Horspool dapat dilihat pada Tabel
4.4.
Tabel 4.4 Kompleksitas Fungsi match algoritma Brute Force
public static boolean match(String pattern, String subject){
C # C#
int n = subject.length(); C1 1 C1
int m = pattern.length(); C2 1 C2
char sub[] = subject.toCharArray(); C3 1 C3
char patt[] = pattern.toCharArray(); C4 1 C4
for (int i = 0; i < n-m+1; i++){ C5 n C5n
int j = 0; C6 n C6n
while (j < m && sub[i+j] == patt[j]){ C7 n2 C7n2
j++; C6 n2 C6n2
}
if (j == m) C8 n C8n
return true; //return i; C9 n C9n
}
return false; // return -1; C9 1 C9
}
T(n) = C1 + C2 + C3 + C4 +C5n +C6n + C7n2 + C6n2 + C8n + C9n + C9
= C1 + C2 + C3 + C4 + C9 + (C5 + C6 + C8 + C9) n + (C6 + C7) n2
= θ (n2)
Universitas Sumatera Utara
Kompleksitas dari algoritma Brute Force : C adalah konstanta , # adalah frekuensi
yang berfungsi sebagai ukuran masukan dan C# untuk mencari kompleksitas waktu
(T(n)), n adalah jumlah proses. Jumlahkan hasil perkalian C.#, lalu ambil pangkat
terbesar dari hasil masukan (#) dan didapatlah pangkat terbesar yaitu : n2.
Pada algoritma Brute Force fase match memiliki T(n)= θ(n2). Maka
kompleksitas algoritma Brute Force adalah θ(n2).
4.3.2 Kompleksitas Algoritma Horspool
Kompleksitas untuk fungsi Horspool pada algoritma Horspool dapat dilihat pada
Tabel 4.5.
Tabel 4.5 Kompleksitas Fungsi shifttable algoritma Horspool
public Horspool shifttable(String pattern) { C # C#
int m = pattern.length(); C1 1 C1
char p[] = pattern.toCharArray(); C2 1 C2
for (int i = 0; i < SIZE; i++) C3 n C3n
table[i] = m; C4 n C4n
for (int j = 0; j < m - 1; j++) C3 n C3n
table[p[j]] = m - 1 - j; C4 n C4n
return this; C5 1 C5
}
T(n) = C1 + C2 + C3n + C4n +C3n +C4n + C5
= C1 + C2 + (2C3 + 2C4) n + C5
= θ(n)
Kompleksitas untuk fungsi match pada algoritma Horspool dapat dilihat pada tabel
4.6.
Tabel 4.6 Kompleksitas Fungsi match algoritma Horspool
public int match(String pattern, String source) { C # C#
char s[] = source.toCharArray(); C1 1 C1
char p[] = pattern.toCharArray(); C2 1 C2
int m = pattern.length(); C3 1 C3
int n = source.length(); C4 1 C4
Universitas Sumatera Utara
int i, k; C5 1 C5
i = m - 1; C5 1 C5
while (i <= n - 1) { C6 n C6n
k = 0; C5 n C5n
while (k <= m - 1 && p[m - 1 - k] == s[i - k]) { C6 n2 C6n2
k++; C5 n2 C5n2
}
if (k == m) { C7 n C7n
return i - m + 1; C8 n C8n
} else { C9 n C9n
i = i + table[s[i]]; C5 n C5n
}
}
return -1; C8 1 C8
}
T(n) = C1 + C2 + C3 + C4 + C5 + C5 + C6n + C5n + C6n2 + C5n2 + C7n + C8n +
C9n + C5n + C8
= C1 + C2 + C3 + C4 + 2C5 + (2C5 + C6 + C7 + C8 + C9) n + (C5 + C6) n2
= θ(n2)
Kompleksitas dari algoritmaHorspool : C adalah konstanta , # adalah frekuensi yang
berfungsi sebagai ukuran masukan dan C# untuk mencari kompleksitas waktu (T(n)),
n adalah jumlah proses. Jumlahkan hasil perkalian C.#, lalu ambil pangkat terbesar
dari hasil masukan (#) dan didapatlah pangkat terbesar yaitu : n2.
Pada algoritma Horspool fase shifttable memiliki T(n) = θ(n) dan pada fase
match memiliki T(n)= θ(n2). Maka kompleksitas algoritma Horspool adalah θ(n2).
Universitas Sumatera Utara
BAB 5
PENUTUP
5.1 Kesimpulan
Berdasarkan analisis, perancangan, dan pengujian dari penelitian, maka dapat
diperoleh kesimpulan sebagai berikut :
1. Pada penerapannya Algoritma Brute Force memilki waktu pencarian lebih
cepat daripada Algoritma Horspool. Terbukti dengan hasil rata-rata runtime
algoritma Brute Forceadalah1.38839 ms sedangkan algoritma Horspool yang
memiliki hasil rata-rata runtime yang cenderung lebih lambat dari algoritma
Brute Force yakni1.631901ms dalam pencocokan string-nya.
2. Untuk Algoritma Brute Force, best casenya adalah posisi pattern yang ingin
dicari ada pada awal kata (paling kiri), worst casenya adalah pattern yang
ingin dicari ada pada akhir kata (paling kanan). Sedangkan untuk algoritma
Horspool, best casenya adalah posisi pattern yang ingin dicari ada pada akhir
kata (paling kanan), worst casenya adalah pattern yang ingin dicari ada pada
awal kata (paling kiri).
Universitas Sumatera Utara
5.2 Saran
Pada penelitian ini, terdapat beberapa saran yang dapat dipertimbangkan untuk
pengembangan sistem kedepannya :
1. Untuk pengembangan sistem selanjutnya jumlah kata yang ada dapat
ditambahkan untuk semakin menambah kosakata yang dapat dicari
terjemahannya.
2. Untuk pengembangan selanjutnya, diharapkan aplikasi ini dapat menyediakan
menu pencarian kata dalam bahasa Mandarin – Indonesia.
3. Untuk pengembangan selanjutnya, diharapkan aplikasi ini menyediakan
menu pilihan algoritma pencarian string yang baru ditemukan agar terlihat
perbedaan pada pencarian pada string antara Algoritma yang lama dengan
Algoritma yang sudah mengalami proses perkembangan.
Universitas Sumatera Utara
DAFTAR PUSTAKA
Al-Dabbagh & Barnouti. 2017. A New Efficient Hybrid String Matching Algorithm
toSolve the Exact String Matching Problem.BJMCS, 20(2): xxx-xxx, 2017;
Article no.BJMCS.30497
Baeza-Yates, R.A. &Regnier, M. 1992. Average Running Time OfThe Boyer-Moore-
Horspool Algorithm.Journal Theoretical Computer Science Vol. 92, No. 1: 19-
31.
Chaer, A. 2007.Leksikologi dan Leksikografi Indonesia. P.T.Rineka Cipta: Jakarta.
Charras, Christian.,& Lecroq, Thierry. 2004. Handbook of Exact String- Matching
Algorithms. College Publications.
Charras, C. & Lecroq, T. 1997.Handbook of Exact String – Matching
Algorithms.Prancis.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. 2001. Introduction to
Algorithms. 2nd Edition. The MIT Press : London.
DU Vidanagama, 2015. A Comparative Analysis of Various String Matching
Algorithms.Proceedings of 8th International Research Conference.
Effendi, D., Hartono, T. & Kurnaedi, A. 2013. Penerapan String Matching
Menggunakan Algoritma Boyer-Moore pada Translator Bahasa Pascal ke C.
Jurnal UNIKOM, Vol 11(2): 262-275.
Gargenta, M. 2011. Learning Android. O'Reilly : Sebastopol
Holla, S. & Katti, M. 2012. Android Based Mobile Application Development and its
Security. International Journal of Computer Trends and Technology. 3(1): 486
- 490.
Jogiyanto. 2005. Pengenalan Komputer. Yogyakarta: Andi.
Knuth D.E., Morris (Jr) J.H. & Pratt V.R. 1977. Fast pattern matching in strings.
SIAM Journal on ComputingVol. 6, No.1:323-350.
Kurunia, M. 2005. Perbandingan Waktu Proses Pencarian String Antara Algoritma
Brute Force dengan Algoritma Not So Naïve. Skripsi. Tarumanagara.
Nababan, A.A. 2015. Implementasi Algoritma Brute Force dan AlgoritmaKnuth-
Morris-Pratt (KMP) dalam Pencarian Word Suggestion. Skripsi. Universitas
Sumatera Utara.
Putra, Anton Gumala. 2014. Analisis Perbandingan Algoritma Greedy dan Brute -
Universitas Sumatera Utara
Force dalam Pencarian Kartu Tertinggi pada Kartu Remi. Skripsi. Universitas
Sumatera Utara.
Sarno, R., Anistyasari, Y. & Fitri, R. 2012.Semantic Search: Pencarian berdasarkan
konten. Andi Publisher: Yogyakarta.
Singh, R. & Verma, H.N. 2011. A fast string matching algorithm. International
Journal of Computer Technology and Applications Vol. 2, No. 6: 1877-1883.
Singla, N. 2012.String Matching Algorithm and their Applicability in
variousApplication. International Journal of Soft Computing and Engineering
(IJSCE) ISSN:2231-2307, Volume-1, Issue-6.
Tambunan, E.D. 2013. Perbandingan Penggunaan Algoritma BM Dan Algoritma
Horspool Pada Pencarian String Dalam Bahasa Medis. Teknik Informatika:
Institut Teknologi Bandung.
Whitten, J.L., Bentley, L.D. & Dittman, K.C. 2004.Metode Desain & Analisis
Sistem. Terjemahan TIM Penerjemah ANDI. ANDI : Yogyakarta.
Wulan, S. 2011. Analisis Penerapan String Matching dalam Komparasi Data
Kepesertaan Jaminan Kesehatan Masyarakat (JamKesMas). Skripsi.UIN
Syarif Hidayatullah.
Universitas Sumatera Utara
LISTING PROGRAM
1. Main Activity package com.dear.mandarindictionary.activity; import android.content.Intent; import android.support.design.widget.TabLayout; import android.support.v4.app.Fragment; import android.support.v4.app.FragmentManager; import android.support.v4.app.FragmentPagerAdapter; import android.support.v4.view.ViewPager; import android.support.v7.app.AppCompatActivity; import android.os.Bundle; import android.view.Menu; import android.view.MenuInflater; import android.view.MenuItem; import com.dear.mandarindictionary.R; import com.dear.mandarindictionary.core.ParentActivity; import com.dear.mandarindictionary.fragment.BruteForceFragment; import com.dear.mandarindictionary.fragment.HorspoolFragment; import java.util.ArrayList; import java.util.List; public class MainActivity extends ParentActivity { private static final String TAG = "MainActivity"; private ViewPager pager; private TabLayout tabLayout; public MainActivity() { super(R.layout.activity_main); } @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); pager = (ViewPager) findViewById(R.id.view_pager); tabLayout = (TabLayout) findViewById(R.id.tab_layout); tabLayout.addTab(tabLayout.newTab().setText("Contact")); tabLayout.addTab(tabLayout.newTab().setText("Chat")); setupViewPager(pager); tabLayout.setupWithViewPager(pager);
setTitle(getResources().getString(R.string.app_name)); } @Override public boolean onCreateOptionsMenu(Menu menu) { MenuInflater inflater = getMenuInflater();
Universitas Sumatera Utara
inflater.inflate(R.menu.main_menu, menu); return true; } @Override public boolean onOptionsItemSelected(MenuItem item) { switch (item.getItemId()) { case R.id.about: Intent intent = new Intent(this, AboutActivity.class); startActivity(intent); default: return super.onOptionsItemSelected(item); } } private void setupViewPager(ViewPager viewPager) { ViewPagerAdapter adapter = new ViewPagerAdapter(getSupportFragmentManager()); adapter.addFragment(new BruteForceFragment(), "Brute Force"); adapter.addFragment(new HorspoolFragment(), "Horspool"); pager.setAdapter(adapter); } class ViewPagerAdapter extends FragmentPagerAdapter { private List<Fragment> fragmentList = new ArrayList<>(); private List<String> titleList = new ArrayList<>(); public ViewPagerAdapter(FragmentManager fm) { super(fm); } public void addFragment(Fragment fragment, String title) { fragmentList.add(fragment); titleList.add(title); } public int getItemPosition(Object object) { return POSITION_NONE; } @Override public Fragment getItem(int position) { return fragmentList.get(position); } @Override public int getCount() { return fragmentList.size(); } @Override public CharSequence getPageTitle(int position) { return titleList.get(position);
Universitas Sumatera Utara
// return null; } } }
2. Splash Screen
package com.dear.mandarindictionary.activity; import android.content.Intent; import android.os.Handler; import android.support.v7.app.AppCompatActivity; import android.os.Bundle; import com.dear.mandarindictionary.R; public class SplashScreenActivity extends AppCompatActivity { @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_splash_screen); new Handler().postDelayed(new Runnable() { @Override public void run() { // This method will be executed once the timer is over // Start your app main activity Intent i = new Intent(SplashScreenActivity.this, MainActivity.class); startActivity(i); finish(); } }, 1000); } }
3. Brute Force package com.dear.mandarindictionary.algo; import com.dear.mandarindictionary.adapter.DictionaryItem; import java.util.ArrayList; import java.util.List; public class BruteForce { public static boolean match(String pattern, String subject){ int n = subject.length(); int m = pattern.length(); char sub[] = subject.toCharArray(); char patt[] = pattern.toCharArray(); for (int i = 0; i < n-m+1; i++){ int j = 0; while (j < m && sub[i+j] == patt[j]){ j++;
Universitas Sumatera Utara
} if (j == m) return true; //return i; } return false; // return -1; } public static List<DictionaryItem> match(String pattern, List<DictionaryItem> data){ List<DictionaryItem> result = new ArrayList<DictionaryItem>(); for (DictionaryItem item : data) { if (match(pattern, item.getIndonesia())) result.add(item); } return result; } }
4. Horspool package com.dear.mandarindictionary.algo; import com.dear.mandarindictionary.adapter.DictionaryItem; import java.util.ArrayList; import java.util.List; public class Horspool { private int SIZE = 256; private int table[]; private Horspool() { table = new int[SIZE]; } public static Horspool with() { return new Horspool(); } public Horspool shifttable(String pattern) { int m = pattern.length(); char p[] = pattern.toCharArray(); for (int i = 0; i < SIZE; i++) table[i] = m; for (int j = 0; j < m - 1; j++) table[p[j]] = m - 1 - j; return this; } public int match(String pattern, String source) { char s[] = source.toCharArray(); char p[] = pattern.toCharArray(); int m = pattern.length(); int n = source.length(); int i, k;
Universitas Sumatera Utara
i = m - 1; while (i <= n - 1) { k = 0; while (k <= m - 1 && p[m - 1 - k] == s[i - k]) { k++; } if (k == m) { return i - m + 1; } else { i = i + table[s[i]]; } } return -1; } public List<DictionaryItem> match(String pattern, List<DictionaryItem> data) { List<DictionaryItem> result = new ArrayList<DictionaryItem>(); for (DictionaryItem item : data) { if (match(pattern, item.getIndonesia()) > -1) result.add(item); } return result; } }
Universitas Sumatera Utara
CURRICULUM VITAE [ D a f t a r R i w a y a t H i d u p ]
Data Pribadi
Nama Dear Arini Purba Tempat / Tgl Lahir Tanjung Morawa / 26 Juni 1991 Jenis Kelamin Perempuan Kewarganegaraan Indonesia Agama Kristen Protestan Alamat Dusun II Desa Bangun Sari Tanjung Morawa E-mail [email protected]
No HP 085270962212 Alamat Orang Tua Dusun II Desa Bangun Sari Tanjung Morawa No HP Orang Tua 0811634226
Pendidikan
1997-2003 SD ST Antonius Medan
2003-2006 SMP Negeri 3 Medan
2006-2009 SMA Negeri 5 Medan
2010-2013 D-3 Teknik Komputer, Politeknik Negeri Medan
2014-sekarang S1-Ekstensi Ilmu Komputer, Universitas Sumatera Utara
Kemampuan Database MySQL
Bahasa Indonesia, Inggris
Universitas Sumatera Utara