IMPLEMENTASI ALGORITMA KNUTH MORRIS PRATT PADA APLIKASI PENERJEMAHAN BAHASA MANDAILING-INDONESIA
Rivalri Kristianto Hondro 1 , Zumrotul Aqobah Hsb 2 , Suginam 3 , Ronda Deli Sianturi 4
1, 3, 4 Dosen Tetap STMIK Budi Darma
2 Mahasiswa Teknik Informatika STMIK Budi Darma
1,2,3,4 Jl. Sisimangaraja No.338 Simpang Limun Medan

## ABSTRAK
Lahirnya teknologi informasi komputer dan fasilitas pendukung seprti layanan internet saat ini membuat perkembangan yang sangat  luas.  Segala  informasi-informasi  dapat  didapatkan  begitu  cepat  membuat  jarak  dan  waktu  tidak  menjadi  masalah. Namaun disamping itu masih jarang ditemukan aplikasi yang dapat mempermudah proses tranlasi suatu kata kedalam bahasa Mandailing-Indonesia.  Aplikasi  ini  dirasa  perlu  karna  banyaknya  masyarakat  yang  belum  mengetahui  sebagian  dari  arti bahasa Mandailing itu sendiri. Proses tranlasi kata ini dilakukan hanya dalam bentuk kata dimana kata yang akan dicari akan muncul beserta arti kata tersebut. Pencarian kata meneraapkan prinsip good sufix(dimana karakter yang dicari sejajar dengan karakter  yang  menyerupainya) serta prinsip bad  character(dimana jika tidak  memiliki  kemiripan langsung  dibuang).  Dalam skripsi  ini  akan  dibahas  tentang  cara  menciptakan  Aplikasi  Penerjemahan  Bahasa  Mandailing-Indonesia  yang  bermamfaat sebagai  pembelajaran  bagi  masyarakat  mandailing  Natal  itu  sendiri,  serta  untuk  mepermudah  pengguna  dalam  proses translasi  suatu  kata  dengan  memamfaatkan  algoritma  knuth  morris  pratt.  Algoritma  knuth  morris  pratt  merupakan pencocokan string yang dianggap lebih mudah pada aplikasi ini, dan dirancang menggunakan Microsoft Visual Studio 2008.
Kata Kunci : Bahasa Mandailing, Algoritma KMP.

## I. PENDAHULUAN
Indonesia  terdiri  atas  beraneka  ragam  suku, budaya, dan bahasa. Masyarakat Indonesia merupakan masyarakat bilingual. Sebagai masyarakat yang  bilingual,  masyarakat  Indonesia  menggunakan dua  bahasa.  Bahasa  Indonesia  sebagai  bahasa nasional  dan bahasa  daerah  digunakan oleh masyarakat untuk berinteraksi antar anggota kelompok  etnis.  Bahasa  Indonesia  merupakan  salah satu  identitas  bangsa  Indonesia.  Identitas  bangsa Indonesia  tidak  hanya  berpatokan  pada  bahasa Indonesia  sebagai  bahasa  nasional,  tetapi  juga didukung oleh bahasa-bahasa daerah. Oleh karena itu, Bahasa  Indonesia  dapat  dibina  dan  dikembangkan melalui  bahasa-bahasa  daerah.  Bahasa  daerah  dapat berfungsi  sebagai  lambang  kebangsaan  daerah, lambang  identitas  daerah,  alat  perhubungan  di  dalam keluarga dan masyarakat.
Setiap  suku  yang  ada  di  Indonesia  memiliki bahasa  yang  berbeda-beda, diantaranya  bahasa  Batak Toba  dan  bahasa  Batak  Mandailing.  Bahasa  Batak Toba  dan  Bahasa  Batak  Mandailing  merupakan  dua bahasa  yang  tergolong  dalam  keluarga  bahasa Austronesia yang dituturkan oleh masyarakat di Pulau Sumatera bagian utara. Suku Batak adalah suatu suku yang  tinggal  di  Provinsi  Sumatera  Utara.  Secara geografis  di  Provinsi  Sumatera  Utara,  suku  Batak terdiri  dari  5  etnis,  yaitu  Batak  Toba  (Tapanuli), Batak  Simalungun,  Batak  Karo,  Batak  Mandailing (Angkola),  dan  Batak  Pakpak  (Dairi)  yang  memiliki bahasa yang berbeda-beda.
Pada  penelitian  ini  Bahasa  yang  akan  dipakai adalah  Bahasa  Mandailing.  Bahasa  Mandailing sebagai  bahasa  daerah,  bahasa  Mandailing  memiliki ciri  khas  dalam  hal  tata  bahasa  dan  arti  kata.  Hal  itu
yang  membedakannya  dari  bahasa  daerah  lain, khususnya  dengan  bahasa  daerah  yang  ada  di Indonesia.  Bahasa  Mandailing    juga  memiliki  ciri khas seperti penggunaan dialog. Penerjemahan bahasa Mandailing-Indonesia ini disusun untuk mereka yang ingin memahami atau mempelajari bahasa Mandailing, Dan juga untuk mereka yang sebenarnya masyarakat Mandailing Natal.
Pada  dasarnya,  suatu  aplikasi  penerjemah  teks bekerja  dengan  melakukan string  matching atau pencocokan  string  berdasarkan  kata-kata  yang terdapat  dalam  database  yang  merupakan  kamus aplikasi  tersebut.  Seperti yang  kita  ketahui, pencocokan  string  dapat  dilakukan  dengan  berbagai algoritma  yang  ada,  seperti Brute  Force dan Knuth Morris Pratt . Algoritma Knuth  Morris  Prat t  atau  disingkat KMP merupakan algoritma pencocokan atau pencarian string yang merupakan pengembangan dari algoritma Brute  Force .  Berbeda  dengan  algoritma Brute  Force yang  melakukan  pencocokan  string dengan  pergeseran  satu  per  satu  karakter,  algoritma KMP mampu melakukan  pencocokan  dengan pergeseran yang lebih baik.

## II. TEORITIS A. Perancangan
Perancangan  sistem  adalah  merancang  atau mendesain suatu sistem yang baik, yang isinya adalah langkah-langkah  operasi  dalam  proses  pengolahan data dan prosedur untuk mendukung operasi sistem.

## B. Aplikasi
Aplikasi  berasal  dari  kata application yang artinya  penerapan,  lamaran,  penggunaan.  Secara
istilah aplikasi adalah program siap pakai yang direka untuk melaksanakan suatu fungsi bagi pengguna atau aplikasi  yang  lain  dan  dapat  digunakan  oleh  sasaran yang  dituju.  Aplikasi  Komputer  atau  Aplikasi Software  adalah  Program  komputer  yang  ditulis dalam  suatu  bahasa  pemrograman  dan  dipergunakan untuk menyelesaikan masalah tertentu.

## C. Algoritma knuth Morris Pratt
Algoritma Knuth Morris Pratt (KMP) dikembangkan  oleh  D.  E.  Knuth,  bersama  dengan  J. H.  Morris  dan  V.  R.  Pratt.  Untuk  pencarian  string dengan  menggunakan  algoritma  Brute  Force  ,  setiap kali  ditemukan  ketidakcocokan  pattern  dengan  teks, maka  pattern  akan  digeser  satu  karakter  ke  kanan. Sedangkan  Algoritma  Knuth  Morris  Pratt  bekerja dengan  memanfaatkan  pergeseran  yang  semaksimal mungkin  dalam  pencocokan  string  dalam  teks. Misalkan saja terdapat kata “kabar” yang ingin dicari padanannya dalam bahasa Inggris. Aplikasi penerjemah  haruslah  melakukan  pencocokan  kata untuk  mencari  kata  tersebut  dalam  bahasa  asing. Haruslah  diperhitungkan  apakah  kata  tersebut merupakan  bagian  dari  kata  majemuk  lainnya. Misalkan  kata  “kabar”  yang  dimaksud  disini merupakan  bagian  dari  kata  “apa  kabar”  yang  dapat dianggap sebagai satu kesatuan kata majemuk. Proses dengan  menggunakan  algoritma  KMP  akan  menjadi sebagai berikut:
Sebelumnya  dilakukan  pencocokan  dengan katakata  lain  yang  terdapat  dalam  kamus,  hingga akhirnya  tiba  dalam  kalimat  “apa  kabar”,  algoritma KMP  akan  mengenali  terdapat  kata  “kabar”  dalam kalimat tersebut dengan proses sebagai berikut:
Ket. Kata yang dibaris atas merupakan kata yang diperiksa,  dan  kata  yang  dibawah  merupakan  kata yang dicocokkan.
A P A K A B A R K A B A R Dalam  proses  pencocokan  pertama  tidak ditemukan  kemiripan  dalam  kata  tersebut,  maka selanjutnya  akan  dilakukan  penggeseran  untuk pencocokan selanjutnya. Dalam kasus diatas, penggeseran akan dilakukan sejauh satu karakter, dan terus  berulang selama  tiga  kali  pencocokan selanjutnya  (dalam  tiga  kali  pencocokan  selanjutnya tidak  ditemukan  kesamaan  karakter),  sehingga pencocokan selanjutnya adalah sebagai berikut:
A P A K A B A R K A B A R Dan  akhirnya  ditemukan  bahwa  kata  “kabar” merupakan bagian dari kata “apa kabar”.
Dalam  contoh  lain  dapat  dilihat  bahwa  dalam algoritma  KMP  memiliki  perhitungan  khusus  dalam melakukan  pergeseran  string.  Misalkan  untuk pencocokan  kata  “abcabd”  dalam  “abcabcabd”.
Prosesnya adalah sebagai berikut: A B C A B C A B D A B C A B D
Dalam  tahap  awal  dilakukan  pencocokan  mulai dari karakter paling kiri, dapat dilihat bahwa terdapat kecocokan hingga 5 karakter, namun pada karakter ke 6,  yaitu  “D”  terdapat  perbedaan.  Untuk  menentukan sejauh  apa  pergeseran  yang  akan  dilakukan,  terlebih dahulu  haruslah  dilakukan  penghitungan  terhadap fungsi  pinggiran  untuk  karakter  yang  cocok.  Fungsi pinggiran  merupakan  ukuran  awalan  terpanjang  dari suatu string P yang merupakan akhiran dari P[1..j].
Sebagai gambaran lengkap, berikut daftar fungsi pinggiran untuk kata “abcabd”:
A B C A B D 0 0 0 1 2 0
Dalam  kasus  diatas,  string  yang  cocok merupakan  string  “abcab”  yang  memiliki  fungsi pinggiran  ab  (bernilai,  2  karakter).  Sehingga berdasarkan  algoritma  KMP,  pergeseran  yang dilakukan  adalah  sejauh  panjang  “abcab”  dikurangi nilai  fungsi  pinggirannya  yaitu  5-2=3.  Maka pergeseran yang dilakukan adalah sejauh 3 karakter.
A B C A B C A B D A B C A B D Setelah dilakukan penggeseran akhirnya ditemukan kecocokan dalam string diatas.

## III. ANALISA dan PEMBAHASAN
Penerjemahan  bahasa  mandailing  indonesia yang  akan  dirancang  ini  sebuah  aplikasi  seperti halnya  kamus  yang  dijalankan  pada  sebuah  laptop. Perancangan  akan  dilakukan  dengan  menggunakan microsoft  visual  studio 2008  dan  mengunakan microsoft  access sebagai  tempat  penyimpanan databasenya.
Penerjemahan  bahasa  ataupun  kamus  umumnya dalam  bentuk buku  yang  berukuran  besar. Tapi  yang akan  penulis  buat  bukan  buku  yang  sejenis  itu  tetapi sebuah  penerjemahan  bahasa  mandailing  indonesia dalam  bentuk  aplikasi.  Dengan  adanya  aplikasi  ini bisa  membantu  masyarakat  Mandailing  natal  dan khususnya  masyarakat  natal  atau  masyarakat  di  luar Mandailing natal  yang belum  mengetahui  arti  bahasa atau kata dari bahasa Mandailing itu sendiri, sehingga masyarakat  atau  penggunanya  lebih  mudah  dan paham arti bahasa mandailing.
Oleh  karena  itu,  aplikasi  kamus  bahasa mandailing-indonesia  dengan  menggunakan  metode string matching knuth morris pratt dalam penerjamahan  kata  yang  dicari  diharapkan  dapat menyelesaikan  masalah tersebut  dimana dalam  string matching knuth  morris  pratt akan  melakukan  proses seleksi  terhadap  kata  yang  dicari  sampai  ditemukan berdasarkan  isi teks itu  sendiri  dengan  menggunakan kata kunci pattern .
Proses Pencocokan Algoritma Knuth Morris Pratt Penerjemahan  bahasa  Mandailing  Indonesia yang  dirancang  akan  menggunakan  algoritma Knuth Morris  Pratt sebagai  solusi  dalam  pencarian  kata seperti  halnya  dalam  penggunaan  kamus  berbentuk
buku  dimana  penyajian  kata  yang  sesuai  dengan urutan  abjadnya,  sehingga  para  pengguna  sangat terbantu dalam mencari kata yang ingin diterjemahkan.
Perhitungan  penggeseran  pada  algoritma  knuth morris  pratt  adalah  sebagai  berikut,  bila  terjadi ketidakcocokkan  pada  saat  pattern  sejajar  dengan teks, maka bisa menganggap ketidakcocokan pertama terjadi di antara  teks  dan  pattern.  Maka di  lanjut kan pergeseran  kesebelah  kanan  satu  karakter  Sehingga pattern tersebut sejajar dengan teks .
Berikut  ini  adalah  cara  kerja  dari  algortima knuth morris pratt adalah sebagai berikut:
1. Algoritma knuth morris pratt mulai mencocokan pattern pada awal teks.
2. Dari  kiri  ke  kanan,  algoritma  ini  akan mencocokkan  karakter  per  karakter  pattern, dengan karakter di teks yang bersesuaian sampai salah satu kondisi berikut terpenuhi :
a. Karakter  di  pattern  dan  diteks  yang dibandingkan tidak cocok (mismatch).
b. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan diposisi ini.
Contoh  penggunaan  algoritma knuth  morris  pratt untuk pencarian pattern dalam teks.
Contoh Teks : ARAMBIR, BURANGIR, MARPANGIR Pattern : IR Cara kerja :
Langkah ke-1 Pattern I R Teks 1 A R A M B I R Indeks 1          2         3          4         5         6          7 Teks 2 B U R A N G I R Indeks 1          2         3         4          5          6         7          8 Teks 3 M A R P A N G I R Indeks 1         2         3         4           5          6         7          8          9
Langkah 1 : dalam proses pencocokan pertama tidak ditemukan kemiripan pattern dengan teks maka selanjutnya akan dilakukan pergeseran satu karakter ke kanan untuk pencocokan string berikutnya.
Langkah ke-2 Pattern I R Teks 1 A R A M B I R Indeks 1          2         3          4         5         6          7 Teks 2 B U R A N G I R Indeks 1          2         3         4          5          6         7          8 Teks 3 M A R P A N G I R Indeks 1         2         3         4           5          6         7          8          9
Langkah  2  :  dalam  proses  pencocokan  kedua  ini  juga  tidak  ditemukan  kemiripan pattern dengan  teks  maka selanjutnya akan dilakukan pergeseran satu karakter untuk langkah pencocokan selanjutnya.
Langkah ke-3 Pattern I R Teks 1 A R A M B I R Indeks 1          2         3          4         5         6          7 Teks 2 B U R A N G I R Indeks 1          2         3         4          5          6         7          8 Teks 3 M A R P A N G I R Indeks 1         2         3         4           5          6         7          8          9
Langkah  3  :  dalam  proses  pencocokan  ketiga  ini  juga  tidak  ditemukan  kemiripan pattern dengan  teks  maka selanjutnya akan dilakukan pergeseran satu karakter untuk langkah pencocokan selanjutnya.
Langkah ke-4 Pattern I R Teks 1 A R A M B I R Indeks 1          2         3          4         5         6          7 Teks 2 B U R A N G I R Indeks 1          2         3         4          5          6         7          8 Teks 3 M A R P A N G I R Indeks 1         2         3         4           5          6         7          8          9
Langkah  4  :  dalam  proses  pencocokan  keempat  ini  juga  tidak  ditemukan  kemiripan pattern dengan  teks  maka selanjutnya akan dilakukan pergeseran satu karakter untuk langkah pencocokan selanjutnya.
Langkah ke-5 Pattern I R Teks 1 A R A M B I R Indeks 1          2         3          4         5         6          7 Teks 2 B U R A N G I R Indeks 1          2         3         4          5          6         7          8 Teks 3 M A R P A N G I R Indeks 1         2         3         4           5          6         7          8          9
Langkah  5  :  dalam  proses  pencocokan  kelima  ini  juga  tidak  ditemukan  kemiripan pattern dengan  teks  maka selanjutnya akan dilakukan pergeseran satu karakter untuk langkah pencocokan selanjutnya.
Langkah ke-6 Pattern I R Teks 1 A R A M B I R Indeks 1          2         3          4         5         6          7 Teks 2 B U R A N G I R Indeks 1          2         3         4          5          6         7          8 Teks 3 M A R P A N G I R Indeks 1         2         3         4           5          6         7          8          9
Langkah  6  :  dan  pada  proses  pencocokan  keenam akhirnya  ditemukan    kecocokan pattern pada  teks ARAMBIR ,
Jika  semua  huruf  pada Pattern sudah  cocok dengan String maka akan ditemukan sebuah pola kosa didalam string .  Dalam  menemukan  sebuah  pola Pattern di  dalam String akan  dilakukan  pergeseran beberapa  kali  untuk  mencocokkan  setiap  huruf  pada pattern yang dimulai dari sebelah kiri ke kanan.
Berdasarkan  contoh  di  atas  maka  dapat  di ambil  sebuah  kesimpulan  bahwa  informasi  yang digunakan  untuk  melakukan  pergeseran  adalah berdasarkan  hitungan  ketidakcocokan pattern pada sebuah string (teks).
IV. IMPLEMENTASI a. Tampilan Form Menu Utama
Tampilan  ini  merupakan  tampilan  dari  form  menu utama dimana berfungsi untuk melakukan pemanggilan terhadap form-form yang lain.

## Gambar 2. Form Menu
b.  Tampilan Form  Terjemahan  Mandailing Indonesia
Tampilan  ini  adalah  form  terjemahan  dimana  dapat berfungsi  untuk  menampilkan  hasil  terjemahan  dari mandailing-indonesia.
Gambar 3. Form Terjemahan
e.  Tampilan Form Tambah Kata
Tampilan  ini  adalah  form  tambah  kata  dimana  form tambah  kata  ini  berfungsi  menambahkan  kata, menghapus kata, dan mengedit kata.
Gambar 3. Form Tambah Kata

## V. KESIMPULAN
Berdasarkan hasil penelitian analisa dan perancangan aplikasi  penerjemah  bahasa  mandailing  indonesia maka  dapat  ditarik  beberapa  kesimpulan  sebagai berikut:
1. Algoritma Knuth  Porris  Pratt pada  aplikasi Penerjemahan bahasa Mandailing-Indonesia sangat  penting  dan  berguna  sehingga  proses pencarian kata yang diterjemahkan lebih mudah.
2. Aplikasi  penerjemahan  bahasa  Mandailing- Indonesia  dapat  membantu  pengguna  dalam menterjemahkan kata Mandailing ke Indonesia.

## VI. DAFTAR PUSTAKA
1. Nasip  Purba  (2013)  “Perancangan  aplikasi  distribusi  obat genetik  dengan  metode  modi  berbasis  web  (studi  kasus  : pt.kimia farma)”ISSN 2301-9425)
2. Firmansyah  (2014)  “aplikasi  pembelajaran  pengenalan  huruf hijaiyah  pada  anak  dengan  menggunakan  metode  computer assited instruction (cai)”ISBN:2339-210X.
3. Parlaungan  Ritonga,”Bahasa  Indonesia  Praktis”,  Medan, BARTONG JAYA, 2009.
4. Okharyadi Saputra (2013) “Penerapan Algoritma Knuth Morris Pratt dalam Aplikasi Penerjemah Teks”.
5. Rosa  A.S  dan  M.Shalahuddin,  “Rekayasa  Perangkat  Lunak”, Bandung, MODULA, 2011.
6. Rahmatpriyanto,”Langsung  bisa  visual  basic.net  2008”, Bandung, ANDI, 2009.
7. Mesran,  “IMPLEMENTASI  ALGORITMA  BRUTE  FORCE DALAMPENCARIAN DATA KATALOG BUKU PERPUSTAKAAN,” Maj.  Ilm.  INTI ,  vol.  3,  no.  1,  pp.  100–
104, 2014.
8. J.  I.  Sinaga,  Mesran,  and  E.  Buulolo,  “APLIKASI  MOBILE PENCARIAN  KATA  PADA  ARTI  AYAT  AL-QUR’AN BERBASIS  ANDROID  MENGGUNAKAN  ALGORITMA STRING  MATCHING,” INFOTEK ,  vol.  2,  no.  2,  pp.  68–72, 2016.
9. Andi, Microsoft Visual Studio.Net 2008 . Andi, 2009.
10. Mesran, Visual Basic . Jakarta: Mitra Wacana Media, 2009.
11. G.  L.  Ginting,  “Implementasi  Algoritma  Boyer-Moore  Pada Aplikasi  Pengajuan  Judul  Skripsi  Berbasis  Web,” Pelita Inform. , vol. 3, no. 1, 2014.