IMPLEMENTASI ALGORITMA KNUTH-MORRIS-PRATT PADA PENCARIAN KUMPULAN RUMUS MATEMATIKA

Jurnal INFOTEK, Vol 1, No 2, Juni 2016

ISSN 2502-6968 (Media Cetak)

IMPLEMENTASI ALGORITMA KNUTH-MORRIS-PRATT PADA PENCARIAN KUMPULAN RUMUS MATEMATIKA Andry Saputra Saragih (12110441) Mahasiswa Program Studi Teknik Informatika, Stmik Budidarma Medan Jl. Sisimangaraja No.338 Simpang Limun Medan http://stmik-budidarma.ac.id// E-Mail : [email protected]

ABSTRAK Lahirnya teknologi informasi komputer dan fasilitas pendukungnya seperti layanan internet saat ini membuat perkembangan yang sangat luas. Segala informasi-informasi dapat didapatkan begitu cepat membuat jarak dan waktu tidak menjadi masalah. Namun disamping itu masih jarang ditemukan aplikasi yang dapat mempermudah proses mencari rumus matematika. Pencarian rumus ini dirasa perlu karna banyaknya pala perlahar yang belum mengetahui sebagian dari rumus matematika . Proses mencari rumus matematika ini dilakukan hanya dalam bentuk rumus dimana setiap rumus yang akan dicari akan muncul beserta rumus tersebut. Pencarian sejumlah rumus tersebut pada pencarian kumpulan rumus matematika ini dapat menggunakan algoritma Knuth-MorrisPratt (KMP). Knuth-Morris-dan Pratt (KMP) adalah algoritma untuk melakukan pencocokan string dari sebuah teks. Algoritma ini merupakan algoritma pencocokan string yang cukup baik. Semua kemungkinan solusi akan dicoba dan divalidasi oleh algoritma Knuth-Morris-danPratt (KMP) hingga mendapatkan solusi yang benarbenar sesuai dengan aturan permasalahan. Pada Skripsi ini akan dideskripsikan mengenai pembuatan pencarian kumpulan rumus matematika yang bermanfaat sebagai pembelajaran bagi para pelajar itu sendiri, serta untuk mempermudah pengguna dalam proses mencari rumus tersebut yang akan dilakukan dengan memenfaatkan algoritma Knuth-Morris-danPratt (KMP). algoritma Knuth-Morris-danPratt (KMP) merupakan pencocokan string dianggap paling efisien pada pencarian ini. Dan dirancang menggunakan Microsoft Visual Studio 2008, untuk mengimplementasikan cara kerja dan hasil dari translasi kata tersebut. Kata Kunci : Kumpulan rumus, Matematika , Knuth-Morris-Pratt (KMP) 1. PENDAHULUAN 1.1 Latar Belakang Matematika diambil dari salah satu kata dalam bahasa latin "mathemata" yang memiliki arti "sesuatu yang dipelajari". Sedangkan matematika di dalam bahasa Belanda dikenal dengan sebutan wiskunde yang memiliki arti "ilmu pasti". Jadi secara umum dapat diartikan bahwa matematika merupakan sebuah ilmu pasti yang berkenaan dengan penalaran. Matematika merupakan salah satu ilmu yang mendasari kehidupan manusia. Dari awal ditemukannya, matematika terus berkembang secara dinamis seiring dengan perubahan zaman. Perkembangannya tidak pernah berhenti karena matematika akan terus dibutuhkan dalam berbagai sisi kehidupan manusia. Pencarian (Searching) adalah proses pencarian data dari sekumpulan data yang sudah ada. Pencarian data sering juga disebut dengan table look-up atau store and retrieval information. Hasil dari suatu pencarian dapat bernilai salah (tidak ketemu atau tidak sukses) atau benar (ketemu atau sukses). Untuk data yang tidak ketemu biasanya ada prosedur tersendiri untuk menambah atau menyisipkan data yang belum ada tersebut. Matematika merupakan mata pelajaran inti di sekolah. Siswa sekolah dasar hingga perguruan tinggi tidak dapat terlepas dari rumus dan hitungan matematika. Para pelajar selalu berasumsi bahwa

pelajaran matematika merupakan salah satu pelajaran yang cukup menyulitkan dan tidak menyenangkan. Sangat Banyaknya rumus dan panjang rumus matematika yang ada seringkali membuat para pelajar merasa rumit dalam pelajaran matematika seringkali membuat siswa merasakan kesulitan dalam memahami, menghafal dan mempelajarinya, terutama para siswa yang memiliki kemampuan daya ingat terbatas, bingungnya dengan operasional tanda-tanda dalam pelajaran matematika maupun yang kurang menyukai pelajaran yang berkaitan dengan menghitung dan menghafal rumus, sehingga dibutuhkan suatu alternatif untuk mengatasi dan membantu permasalahan yang ada saat ini. Dengan melihat permasalahan yang ada penulis ingin membuat sebuah aplikasi untuk mempermudah kita terutama para pelajar dalam mempelajari, memahami dan menghafal rumus-rumus terutama rumus matematika. Penulis berharap dengan menciptakan aplikasi ini para pelajar di setiap jenjang pendidikannya dapat lebih mudah dalam mempelajari rumus – rumus matematika. Matematika tidak lagi menjadi mata pelajaran yang ditakuti ataupun dibenci para pelajar, matematika akan berubah menjadi mata pelajaran yang disukai dan ditunggu-tunggu oleh para pelajar. Algoritma Knuth-Morris-Pratt adalah salah satu algoritma pencarian string, dikembangkan secara

Implementasi Algoritma Knuth-Morris-Pratt Pada Pencarian Kumpulan Rumus Matematika Oleh: Andry saputra saragih

15


terpisah oleh Donald E. Knuth pada tahun 1967 dan James H. Morris bersama Vaughan R. Pratt pada tahun 1966, namun keduanya mempublikasikannya secara bersamaan pada tahun 1977. 1.2 Perumusan Masalah Berdasarkan uraian latar belakang yang telah dikemukakan, maka dapat dirumuskan masalahnya yaitu : 1. Bagaimana proses pencarian kumpulan rumus matematika? 2. Bagaimana menerapkan algoritma Knuth-MorrisPratt pada pencarian kumpulan rumus matematika? 3. Bagaimana merancang aplikasi pencarian kumpulan rumus matematika? 1.3 Batasan Masalah Agar permasalahan yang ditinjau tidak terlalu luas dan sesuai dengan maksud dan tujuan yang dicapai, maka penulis membatasi masalah sebagai berikut 1. Hanya membahas tentang kumpulan rumus matematika tingkat SMP. 2. Algoritma yang di gunakan adalah algoritma Knuth-Morris-Pratt. 3. Bahasa pemograman yang digunakan adalah Visual Basic. Net 2008. 4. Aplikasi database yang digunakan adalah MySQL. 5. pada pencarian rumus matemtika yang dicari adalah nama rumus dan rumusnya. 1.4 Tujuan Tujuan dari penelitian adalah sebagai berikut : 1. Untuk mengetahui proses pencarian kumpulan rumus matematika 2. Untuk menerapkan algoritma Knuth-Morris-Pratt pada pencarian kumpulan rumus matematika 3. Untuk merancang sebuah aplikasi pencarian kumpulan rumus matematika dengan menggunakan visual studio 2008 1.5 Manfaat Adapun manfaat yang ingin dicapai adalah sebagai berikut : 1. Mempermudah dan menambah sumber pembelajaran serta memberi alternatif cara belajar. 2. Dapat digunakan sebagai media pembelajaran mandiri oleh para siswa untuk mempelajari rumus matematika. 3. Meningkatkan motivasi dan menarik minat belajar para siswa untuk lebih mendalami dan memahami dalam mempelajari rumus matematika. 2. LANDASAN TEORI 2.1 Algoritma Knuth-Morris-Pratt Algoritma Knuth-Morris-Pratt adalah salah satu algoritma pencarian string, dikembangkan terpisah oleh oleh D. E. Knuth pada tahun 1967 dan James H. Morris bersama Vaughan R. Pratt pada tahun 1966. Namun keduanya mempublikasikanya secara bersamaan pada tahun 1977.Metode pencarian KMP bekerja dengan cara melewatkan iterasi-iterasi yang tidak perlu karena dinilai tidak akan menghasilkan kesesuaian antara pola atau kata yang dicari dengan


susunan polaatau kalimat utama. Misal sebuah pencarian berjumlah m di dalam sebuah kalimat K yang mengandung kata k. Algoritma yang paling mudah adalah dengan mencari kecocokan karakter pada nilai-nilai yang berurutan dari indeks m , posisi dalam string yang dicari , yaitu K[m]. Jika indeks m mencapai akhir dari string maka tidak ada karakter yang cocok, dalam hal pencarian dikatakan gagal. Pada setiap posisi m, algoritma mengecek keseusaian dari karakter pertama dalam kata yang dicari, yaitu K[m] = k[0]?. Jika kecocokan ditemukan, algoritma menguji karakter lain dalam mencari kata dengan memeriksa nilai-nilai yang berurutan dari posisi indeks kata, i. Algoritma mengambil karakter k[i] dalam mencari kata dan memeriksa kesetaraan ekspresi K[m+i] = k[i]?. Jika semua karakter yang berurutan sesuai dalam k pada posisi m maka kecocokan ditemukan pada posisi dalam string pencarian. Dengan metode seperti itu, performa tidak dijamin optimal. Jika string tidak acak, kemudian memeriksa percobaan m dapat mengambil banyak perbandingan karakter. Kasus terburuk adalah jika dua string cocok dalam semua kecuali huruf terakhir. Bayangkan bahwa string K[] terdiri dari 1 milyar karakter yang semuanya A, dan bahwa kata k[] adalah 999 A karakter dan diakhiri dengan huruf B. Algoritma pencocokan string sederhana sekarang akan memeriksa 1000 karakter pada setiap posisi trial sebelum menolak hasil dan memajukan posisi trial pengecekan. Kini contoh sederhana pencarian akan mengambil sekitar 1000 perbandingan karakter kali 1 miliar untuk posisi 1 triliun perbandingan karakter. Jika panjang k [] adalah n, maka kinerja kasus terburuk adalah O (k ⋅ n). Pada algoritma KMP, pergeseran untuk setiap pengecekan dapat dikurangi. Perhitungan penggeseran pada algoritma ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan teks[i..i+n-1], kita bisa menganggap ketidakcocokan pertama terjadi di antara teks[i+j] dan pattern[j], dengan 0 < j < n. Berarti, teks[i..i+j-1] = pattern[0..j-1] dan a=teks[i+j] tidak sama dengan b=pattern[j]. Ketika kita menggeser, sangat beralasan bila ada sebuah awalan v dari pattern akan sama dengan sebagian akhiran u dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan v tersebut sejajar dengan akhiran dari u. Dengan kata lain, pencocokkan string akan berjalan secara efisien bila kita mempunyai tabel yang menentukan berapa panjang kita seharusnya menggeser seandainya terdeteksi ketidakcocokkan di karakter ke-j dari pattern. Tabel itu harus memuat next[j] yang merupakan posisi karakter pattern[j] setelah digeser, sehingga kita bisa menggeser pattern sebesar j-next[j] relatif terhadap teks. Secara sistematis, langkah-langkah yang dilakukan algoritma Knuth-Morris- Pratt pada saat mencocokkan string: 1. Algoritma Knuth-Morris-Pratt mulai Implementasi Algoritma Knuth-Morris-Pratt Pada Pencarian Kumpulan Rumus Matematika 16 Oleh: Andry saputra saragih



mencocokkan pattern pada awal teks. 2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern Tabel 3.5 Tabel Tahapan Pencarian Kata Iterasi ke-4 dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi: 1. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch). 2. Semua karakter di pattern cocok. Kemudian Tabel 3.6 Tabel Tahapan Pencarian Kata Iterasi ke-5 algoritma akan memberitahukan penemuan di posisi ini. 3. Algoritma kemudian menggeser pattern berdasarkan tabel next, lalu mengulangi langkah 2 sampai pattern berada di ujung teks. Tabel 3.7 Tabel Tahapan Pencarian Kata Iterasi ke-6 3. ANALISA DAN PERANCANGAN 3.1 Analisa Algoritma Knuth Morris Pratt Algoritma Knuth Morris Pratt bekerja dengan memanfaatkan pergeseran yang semaksimal mungkin dalam pencocokan string dalam kata. Misalkan saja Tabel 3.8 Tabel Tahapan Pencarian Kata Iterasi ke-7 terdapat rumus dengan kata “SAMA” yang ingin dicari dalam rumus matematika. Aplikasi kumpulan rumus matematika haruslah melakukan pencocokan kata untuk mencari rumus tersebut dalam rumus matematika. Haruslah diperhitungkan apakah rumus tersebut Tabel 3.9 Tabel Tahapan Pencarian Kata Iterasi ke-8 merupakan bagian dari rumus majemuk lainnya. Misalkan kata “SAMA” yang dimaksud disini merupakan bagian dari kata “SAMA” yang dapat dianggap sebagai satu kesatuan kata majemuk. Proses dengan menggunakan algoritma Knuth Morris Pratt, tahapan pertama tahap Tabel 3.10 Tabel Tahapan Pencarian Kata Iterasi ke-9 preprocessing akan menghitung nilai pinggiran dari pattern SAMA, maka lihat pada tabel 3.1 yaitu tabel nilai pinggiran sebagai berikut : Tabel 3.1 Tabel Pencarian Nilai Pinggiran

Ket : J = Index P[j] = Pattern B[j] = Nilai pinggiran Sebelumnya dilakukan pencocokan dengan katakata lain yang terdapat dalam rumus, hingga akhirnya tiba dalam kalimat “Sama”, algoritma Knuth Morris Pratt akan mengenali terdapat kata “sama” dalam kalimat tersebut dengan proses sebagai berikut: Tabel 3.2 Tabel Tahapan Pencarian Kata Iterasi ke-1

Tabel 3.3 Tabel Tahapan Pencarian Kata Iterasi ke-2


Pada tahap pencarian dengan algoritma Knuth-MorrisPratt diatas pencarian selesai setelah melakukan sebanyak 9 iterasi. Pada pencarian rumus matematika, adapun rumusnya adalah sebagai berikut : Proses dengan menggunakan algoritma Knuth Morris Pratt, tahapan pertama tahap preprocessing akan menghitung nilai pinggiran dari pattern AxT, maka lihat pada tabel 3.11 yaitu tabel nilai pinggiran sebagai berikut :

Ket : J = Index P[j] = Pattern B[j] = Nilai pinggiran Sebelumnya dilakukan pencocokan yang terdapat dalam rumus, hingga akhirnya tiba dalam Rumus “AxT”, algoritma Knuth Morris Pratt akan mengenali terdapat Rumus “AxT” dalam kalimat tersebut dengan proses sebagai berikut: Tabel 3.12 Tabel Tahapan Pencarian Kata Iterasi ke-1


17



Pattern 1 tidak cocok dengan Teks 1, maka digeser 1 langkah 2 ½ A T A

T


Karena langkah-langkah dalam pencarin rumus matematika yang digunakan adalah mencari kata atau kalimat dan rumus. Untuk mengetahui pencarian rumus matematika dengan hasil kata atau kalimat dan rumusnya telah diproses oleh algoritma Knuth-MorrisPratt. Adapun langkah ke dua yang dilakukan adalah mencari rumus, dapat dilihat pada gambar 4.3.

Pattern 2 tidak cocok dengan Teks 2, maka digeser 1 langkah 2 ½ A T A

T

Tabel 3.14 Tabel Tahapan Pencarian Kata Iterasi ke-3 Pattern 3 cocok dengan Teks 3, maka selesai melakukan pencarian 2 ½ A T A

T

Pada tahap pencarian dengan algoritma Knuth-MorrisPratt diatas pencarian selesai setelah melakukan sebanyak 3 iterasi. 4. IMPLEMENTASI Implementasi sistem merupakan lanjutan dari tahapan analisa dan perancangan sistem. Sistem ini dibangun dengan menggunakan bahasa pemrograman Visual Basic.Net dan menggunakan Software Microsoft Visual Studio 2008. Pada sistem ini terdapat 3 (tiga) tampilan halaman, yaitu HalamanUtama, Halaman cari rumus, HalamanTentang. 1. Tampilan Halaman Menu Utama

Gambar 4.1: Tampilan halaman Utama 2. Tampilan Form Mencari Rumus

Gambar 4.2 Tampilan Mencari Kata/Kalimat Dalam melakukan pencarian rumus matematika yang di cari adalah kata atau kalimat dan rumus.

Gambar 4.3 Tampilan Mencari Rumus 5. KESIMPULAN DAN SARAN 5.1 Kesimpulan Berdasarkan hasil yang di dapat dalam penelitian dan penyusunan skripsi ini serta disesuaikan dengan tujuan, maka diperoleh kesimpulan sebagai berikut: 1. Aplikasi pencarian kumpulan rumus matematika dapat membantu para pelajar dalam pencarian rumus matematika lebih cepat. 2. Algoritma Knuth-Morris-Pratt pada pencarian rumus dapat diterapkan sehinggah proses pencarian dapat lebih mudah. 3. Algoritma Knuth-Morris-Pratt haruslah dilakukan secara detail dengan menampilkan pseudocode dan bagian yang dieksekusinya serta pergerakan pattern terhadap teks. 3.2 Saran Saran yang diberikan untuk pengembangan selanjutnya adalah sebagai berikut: 1. pengujian dilakukan dengan rentang data yang lebih besar lagi sehinggah skalabilias algoritma dapat dikukur laeih jauh. 2. Menambahkan fitur dua bahasa, sehinggah bisa lebih dimengerti oleh lebih banyak pengguna berbagai macanegara saat ini aplikasi hanya menggunakan bahasa indonesia saja. 3. Tampilan kumpulan rumus matematika dapat dikembangkan lagi sehinggah menjadi kumplan rumus matematika yang menarik dan seutuhnya. DAFTAR PUSTAKA 1. Adi Atmo pawiro, Alsasian. 2006. Pengkajian dan Analisis Tiga Algoritma Efisien Rabin-Karp, Knuth-Morris-Pratt dan Boyer-Moore dalam Pencarian Pola dalam Suatu Teks. Skripsi. Institut Teknologi Bandung.


18



2.

Ekaputri, 2006, Aplikasi Algoritma Pencarian String Knuth-Morris-Pratt, Informatika, Bandung 3. Indrajani, S.Kom, MM. 2011. Perancangan Basis Data Dalam Allin1. Elex Media Komputindo. Jakarta. 4. Munir, Rinaldi. 2007. Strategi Algoritmik Bandung: Program Studi Teknik Informatika STEI ITB 5. Mukhairil, 2006, Adam. Kompleksitas Algoritma. Jurusan Teknik Informatika, Universitas Komputer Indonesia 6. Priyanto, Rahmat, 2009, Langsung Bisa Visual Basic.Net 2008 ,Penerbit ANDI, Yogyakarta. 7. Almanda, Rio. 2016, Aplikasi pendeteksi plagiat terhadap karya tulis berbasis web menggunakan natural language processing dan algoritma knuth-morris-pratt. Skripsi.Universitas Tanjungpura. 8. Ginting, G. L. (2014a). Implementasi Algoritma Boyer-Moore Pada Aplikasi Pengajuan Judul Skripsi Berbasis Web. Pelita Informatika, 3(1). 9. Ginting, G. L. (2014b). Implementasi Algoritma Boyer-Moore Pada Aplikasi Pengajuan Judul Skripsi Berbasis Web. Pelita Informatika. 10. Mesran. (2014). IMPLEMENTASI ALGORITMA BRUTE FORCE DALAMPENCARIAN DATA KATALOG BUKU PERPUSTAKAAN. Majalah Ilmiah INTI, 3(1), 100–104. 11. Waruwu, F. T., & Mesran. (2014). IMPLEMENTASI ALGORITMA KNUTH MORRIS PRATT PADA APLIKASI KAMUS ISTILAH LATIN FLORA DAN FAUNA BERBASIS ANDROID. Majalah Ilmiah INTI, 4(1), 96–102.


19

IMPLEMENTASI ALGORITMA KNUTH-MORRIS-PRATT PADA PENCARIAN KUMPULAN RUMUS MATEMATIKA

Recommend Documents