BAB 1
PENDAHULUAN
1.1
Latar Belakang
Berkomunikasi satu sama lain merupakan salah satu sifat dasar manusia. Komunikasi berfungsi sebagai sarana untuk saling berinteraksi satu sama lain. Manusia terkadang ingin menguasai lebih dari satu bahasa asing. Apalagi jika bahasa itu sedang popular. Manusia pun tidak ingin ketinggalan zaman menguasai bahasa itu. Dengan adanya kamus maka manusia dapat mempelajari bahasa serta mengetahui bahasa-bahasa apa saja yang ingin dikuasai. Selama ini jika seseorang ingin mempelajari bahasa asing, salah satu contohnya adalah bahasa Korea, media yang digunakan untuk memperlancar penguasaan kosakatanya adalah melalui kamus. Oleh karena kamus bentuknya masih berupa seperti buku, tidak fleksibel, susah untuk dibawa, mengakibatkan kurang efektif apabila sedang berada di luar atau dijalan. Diperlukan sebuah media baru yang praktis dan efektif seperti media Smartphone karena Smartphone mendukung berbagai macam aplikasi seperti aplikasi kamus. Aplikasi kamus didalam Smartphone tidak mencari kata secara manual. Tetapi adanya Fasilitas pencarian pada aplikasi kamus tersebut mempermudah
user
mendapatkan
kata
yang
ingin
dicarinya.
Dengan
memanfaatkan salah satu dari Algoritma string matching seperti Algoritma Knuth Morris Pratt dan Boyer Moore, maka mempermudah dan mempercepat pencarian kata dalam kamus. Dijelaskan bahwa Algoritma Knuth Morris Pratt mulai mencocokkan pattern pada awal teks. Pencocokan kata dimulai dari posisi kiri hingga akhirnya sampai pada posisi paling kanan, algoritma ini akan mencocokkan karakter per
2
karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi yaitu karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch) dan semua karakter di pattern cocok, kemudian algoritma akan memberitahukan penemuan di posisi ini. Algoritma kemudian menggeser pattern berdasarkan tabel shift, lalu mengulangi langkah 2 sampai pattern berada di ujung teks (Wibowo, T., et al. 2012). Sedangkan Algoritma Boyer Moore ini melakukan pencocokan kata dimulai dari posisi kanan hingga akhirnya sampai pada posisi paling kiri,langkah ini berbeda dengan metode pencarian string matching sejenisnya yang memulai pencarian kata dari posisi kiri. Algoritma ini menerapkan prinsip good sufix (dimana karakter yang dicari disejajarkan dengan karakter yang menyerupainya) serta prinsip bad character (dimana jika karakter tidak memiliki kemiripan akan langsung dieliminasi). Dengan kedua prinsip ini, informasi string yang diperoleh dalam pencarian akan semakin banyak sehingga output yang dihasilkan akan menjadi lebih baik (Susanto,2014). Menurut Bille, P. (2011) Algoritma Knuth Morris Pratt memecahkan masalah pencocokan string dalam waktu linear itu optimal karena kita dapat membaca satu karakter pada waktu yg bersamaan. Pada string kita dapat membaca beberapa karakter dalam waktu yang konstan (tidak berubah-ubah) dan karenanya berpotensi lebih baik untuk pencocokan string. Menurut Franek, F., et al. (2007) Algoritma Boyer Moore menyediakan Average-Case dan Best-Case yang hampir optimal, dan juga melakukan eksekusi sangat cepat dalam prakteknya. Menurut Linhart, C. & Shamir, R. (2009) banyak sekali algoritma yang efisien dikembangkan selama beberapa tahun terakhir, tetapi algoritma tercepat untuk menyelesaikan masalah dalam waktu linear, yaitu seperti Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore. Untuk mengetahui Algoritma yang mampu mencocokkan string paling cepat, maka kedua algoritma ini akan dibandingkan. Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore telah dibahas pada penelitian yang terdahulu dengan judul Implementasi Algoritma Levenshtein Distance dan Boyer Moore
3
untuk fitur Autocomplete dan Autocorrect pada aplikasi katalog perpustakaan daerah Aceh Timur (Hajar, T.I. 2015) dan Implementasi Algoritma Levenshtein Distance dan Knuth Morris Pratt dalam fitur word completion pada search engine (Priyatna, R.D. 2015).
1.2
Perumusan Masalah
Berdasarkan uraian dari latar belakang diatas, rumusan masalah yang akan dibahas adalah bagaimana melakukan pencarian kata pada Kamus Bahasa Asing dengan menggunakan Algoritma String Matching. 1.3
Ruang Lingkup Penelitian
Adapun batasan masalah dalam penelitian ini adalah sebagai berikut : 1. Input dan hasil pencarian hanya berupa kata dan tidak berupa kalimat. 2. Aplikasi ini dirancang untuk menerjemahkan kata dari Bahasa Indonesia ke Bahasa Korea dan sebaliknya secara Offline. 3. Mengingat banyaknya kata yang terdapat didalam kamus maka penulis membatasi kata yang diinputkan yaitu 1400 kata. 4. Parameter pembanding yang digunakan adalah Running Time dan Kompleksitas Algoritma yaitu Big O, Big Ω, dan Big Ɵ. 5. Algoritma string matching yang digunakan adalah Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore . 6. Aplikasi ini dirancang untuk Smartphone android versi 4.2 Jelly Bean, Menggunakan bahasa pemrograman Java dan Android Studio sebagai compilernya. 7. Aplikasi menggunakan DBMS SQLite untuk penyimpanan data kamus.
1.4
Tujuan Penelitian
Adapun tujuan penelitian dalam tugas akhir ini adalah : 1. Membangun
Aplikasi
Kamus
Bahasa
Indonesia-Korea
dengan
menerapkan Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore.
4
2. Mengetahui Algoritma yang lebih baik diantara Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore untuk proses pencocokan kata.
1.5
Manfaat Penelitian
Adapun manfaat dari penelitian ini adalah : 1. Penelitian ini diharapkan memudahkan pengguna Smarthphone dalam mencari kata terjemahan dari Bahasa Indonesia ke Bahasa Korea dan sebaliknya. 2. Penelitian ini diharapkan mampu membantu pengguna mempelajari Bahasa Korea. 3. Penelitian ini diharapkan menghasilkan perbandingan dalam pembuatan sistem berbasis Android menggunakan Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore. 4. Penelitian ini diharapkan dapat dijadikan acuan dalam memilih antara Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore sebagai Algoritma dalam Kamus pada search engine.
1.6
Metode Penelitian
Tahapan penelitian yang dilakukan dalam penelitian ini adalah : 1. Studi Literatur Pada tahap ini dilakukan pengumpulan referensi. Hal ini dilakukan untuk memperoleh informasi dan data yang diperlukan untuk penulisan skripsi ini. Referensi yang digunakan dapat berupa buku, jurnal, paper, baik berupa media cetak maupun media internet mengenai Algoritma pencocokan string khususnya untuk Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore. 2. Analisis dan Perancangan Pada tahap ini digunakan untuk mengolah data dari hasil studi literatur yang kemudian dilakukan analisis dan perancangan sistem. Kemudian sistem dirancang dengan membuat gambaran sistem menggunakan flowchart, UML, dan user interface.
5
3. Implementasi Pada tahap ini perancangan diimplementasikan dalam pembuatan suatu aplikasi berbasis android dengan menggunakan Bahasa Pemrograman Java dan menggunakan DBMS SQLite sebagai penyimpanan data kamus. 4. Pengujian Pada tahap ini dilakukan pengujian kinerja sistem dan kebenaran hasil perbandingan yang dilakukan dengan dua Algoritma pencocokan string yang berbeda. 5. Dokumentasi Pada tahap ini pendokumentasian dilakukan selama penelitian dalam bentuk skripsi.
1.7
Sistematika Penulisan
Dalam penulisan skripsi ini penulis membagi membuat sistematika penulisan terbagi menjadi lima bab dengan susunan sebagai berikut:
BAB 1 PENDAHULUAN Bab ini membahas tentang latar belakang pemilihan judul, perumusan masalah, ruang lingkup penelitian, tujuan penelitian, manfaat penelitian, metode penelitian, dan sistematika penulisan.
BAB 2 LANDASAN TEORI Bab ini membahas tentang teori-teori yang berhubungan dengan Algoritma String Matching, Algoritma Knuth Morris Pratt, Algoritma Boyer Moore, Kompleksitas Algoritma dan Android.
BAB 3 ANALISIS DAN PERANCANGAN SISTEM Bab ini membahas mengenai Analisis Sistem serta perancangan Aplikasi Kamus Bahasa Indonesia-Korea berbasis Android.
6
BAB 4 IMPLEMENTASI DAN PENGUJIAN SISTEM Bab ini membahas tentang hasil implementasi dan pengujian sistem serta pembahasan dari hasil yang diperoleh.
BAB 5 KESIMPULAN DAN SARAN Bab ini membahas tentang kesimpulan yang diperoleh dari hasil penelitian serta saran-saran yang ditujukan bagi para pembaca dan pengembang sistem selanjutnya.
