## Journal of Computer System and Informatics (JoSYC)

## ISSN 2714-7150 (media cetak)

## Implementasi Algoritma Zhu Takaok Pada Aplikasi Translator Bahasa Indonesia-Finlandia Berbasis Android

## Seli Trisia
Program Studi Teknik Informatika, Universitas Budi Darma, Medan, Indonesia Email: seli@gmail.com
Submitted: 28/06/2020 ; Accepted: 20/08/2020 ; Published: 21/08/2020
Abstrak −Pendidikan adalah salah satu hal yang sangat penting bagi kehidupan seseorang, pendidikan juga berperan besar bagi kemajuan dan perkembangan sebuah bangsa. Sebuah bangsa yang maju dan besar tentu ditunjang dengan kualitas pendidikan yang  memadai  bagi  warganya.  Salah  satu  negara  yang  memiliki  tingkat  pendidikan  terbaik  dunia  yaitu  Finlandia.  Saat  ini Finlandia berada pada posisi kelima setelah Hongkong. Melanjutkan pendidikan kuliah ke Finlandia merupakan keinginan oleh banyak  pelajar  maupun  mahasiswa/I  Indonesia  terutama  melalui  jalur  beasiswa  karena  dengan  melanjutkan  pendidikan  di Finlandia  dapat  meraih  banyak  ilmu  yang  mungkin  jarang  ditemukan  di  Indonesia.  String  Matching  merupakan  salah  satu algoritma  yang  digunakan  untuk mempercepat  proses  pencarian  kata  yang  diinginkan. String matching dibagi menjadi  dua, yakni exact matching  dan  heuristic atau statistical matching.  Algoritma  string matching telah  sering  digunakan sebelumnya seperti  contoh  pada  proses  pencocokan  string  berdasarkan  persamaan  teks  data  yaitu  Brute  Force.  Dalam  hal  ini,  dipilih algoritma brute force karena algoritma ini dapat digunakan untuk melakukan pencarian string atau teks. Algoritma brute force adalah algoritma untuk mencocokkan pattern dengan semua teks antara 0 dan n-m untuk menemukan keberadaan pattern dalam teks. Dengan berkembangnya teknologi sekarang ini string matching juga dapat digunakan dalam dunia pendidikan. Pendidikan adalah salah satu hal yang sangat penting bagi kehidupan seseorang. Untuk mengatasi permasalahan diatas penulis membangun sebuah  aplikasi  berbasis  android,  yaitu  aplikasi  translator  bahasa  Indonesia-Finladia.  Pada  tools  pencarian  penulis mengimplementasikan algoritma string matching yaitu algoritma zhu takaoka. Algoritma zhu takaoka merupakan salah satu algoritma  terbaik yang  dapat melakukan  proses pencocokan  string  dengan  cepat karena melakukan  pergeseran dengan  bad- character untuk dua karakter text secara berturut-turut dari arah kanan ke arah kiri.
Kata Kunci: Pendidikan, String Matching, Zhu Takaoka.
Abstract −Education  is one  thing that is  very  important  for one's life, education  also  plays a big  role for the  progress and development of a nation. A developed and large nation that is certainly supported by adequate quality education for its citizens. One  of  the  countries  that has the  best education level in  the  world  is Finland.  Finland is  currently in  fifth  place  after  Hong Kong.  Continuing  college  education  in  Finland  is  the  desire  of  many  Indonesian  students,  especially  through  scholarships, because continuing education in Finland can gain a lot of knowledge that may be rarely found in Indonesia. String Matching is an  algorithm  used  to  speed  up  the  search  process  for  the  desired  word.  String  matching  is  divided  into  two,  namely  exact matching and heuristic or statistical matching. The string matching algorithm has often been used before as an example in the string matching process based on the data text equation, namely Brute Force. In this case, the brute force algorithm is chose n because this algorithm can be used to search strings or texts. Brute force algorithm is an  algorithm to match patterns with all text between 0 and n-m to find the existence of patterns in text. With the development of technology today string matching can also  be used  in  education.  Education  is  one  thing  that  is  very important  for  one's  life.  To  overcome the above  problems the authors build an android-based application, namely the Indonesian-Finnish translator application. In the search tools the author implements  the  string  matching  algorithm  namely  zhu  takaoka  algorithm.  The  zhu  takaoka  algorithm  is  one  of  the  best algorithms that can do the string matching process quickly because it shifts with bad characters for two text characters in a row from right to left.
Keywords : Education, String Matching, Zhu Takaoka.

## 1. PENDAHULUAN
String Matching merupakan salah satu algoritma yang digunakan untuk mempercepat proses pencarian kata yang diinginkan.  String  matching  dibagi  menjadi  dua,  yakni  exact  matching  dan  heuristic  atau  statistical  matching. Algoritma  string  matching  telah  sering  digunakan  sebelumnya  seperti  contoh  pada  proses  pencocokan  string berdasarkan persamaan teks data yaitu Brute Force. Dalam hal ini, dipilih algoritma brute force karena algoritma ini dapat digunakan untuk melakukan pencarian string atau teks. Algoritma brute force adalah algoritma untuk mencocokkan  pattern  dengan  semua  teks  antara  0  dan  n-m  untuk  menemukan  keberadaan  pattern  dalam  teks. Berdasarkan arah pencariannya, algoritma ini diklasifikasikan sebagai algoritma yang membaca string dari kiri ke kanan[1].
Dengan  berkembangnya  teknologi  sekarang  ini  String  Matching  juga  dapat  digunakan  dalam  dunia pendidikan.  Pendidikan  adalah  salah  satu  hal  yang  sangat  penting  bagi  kehidupan  seseorang,  pendidikan  juga berperan  besar  bagi  kemajuan  dan  perkembangan  sebuah  bangsa.  Sebuah  bangsa  yang  maju  dan  besar  tentu ditunjang  dengan  kualitas  pendidikan  yang  memadai  bagi  warganya.  Salah  satu  negara  yang  memiliki  tingkat pendidikan  terbaik  dunia  yaitu  Finlandia.  Saat  ini  Finlandia  berada  pada  posisi  kelima  setelah  Hongkong. Melanjutkan  pendidikan  kuliah  ke  Finlandia  merupakan  keinginan  oleh  banyak  pelajar  maupun  mahasiswa/I Indonesia  terutama  melalui  jalur  beasiswa  karena  dengan  melanjutkan  pendidikan  di  Finlandia  dapat  meraih banyak ilmu yang mungkin jarang ditemukan di Indonesia.

## Journal of Computer System and Informatics (JoSYC)

## ISSN 2714-7150 (media cetak)
Salah satu persyaratan untuk melanjutkan pendidikan kenegara Finlandia adalah menguasai bahasa resmi Finlandia yaitu bahasa Finlandia. Bahasa Finlandia sangatlah  susah untuk dimengerti dikarenakan sangat berbeda dengan  kosakata  bahasa  Indonesia.  Hal  ini  menjadi  permasalahan  bagi  seseorang  yang  ingin  melanjutkan pendidikan  ke  Finlandia,  karena  dengan  kekurangan  di  bidang  bahasa  akan  mempersulit  seseorang  dalam berkomunikasi baik dalam menjalani proses pendidikan maupun menjalani kehidupan sehari-hari selama berada di negara tersebut.
Untuk mengatasi permasalahan diatas penulis membangun sebuah aplikasi berbasis android, yaitu aplikasi translator  bahasa  Indonesia-Finladia.  Pada  tools  pencarian  penulis  mengimplementasikan  algoritma  string matching yaitu algoritma zhu takaoka. Algoritma zhu takaoka merupakan salah satu algoritma terbaik yang dapat melakukan proses pencocokan string dengan cepat karena melakukan pergeseran dengan bad-character untuk dua karakter  text  secara  berturut-turut  dari  arah  kanan  ke  arah  kiri.  Ada  pun  hasil  dari  penelitian  ini  yaitu  sebuah aplikasi  translator  bahasa  Indonesia-Finlandia    yang  memiliki  tools  pencarian  yang  cepat  dalam  menemukan terjemahan bahasa Indonesia-Finlandia yang dapat dioperasikan pada smartphone berbasis android sehingga dapat membantu seseorang untuk melanjutkan pendidikan ke  Finlandia.
Berdasarkan  penelitian  sebelumnya  yang  dilakukan  oleh  Adhi  Kusnadi  dan  Abraham  Khrisnandi Wicaksono(2017), Vol.IX, No.1 Hal.15 dengan judul perbandingan algoritma horspool dan algoritma zhu-takaoka dalam pencarian string berbasis dekstop. Telah menunjukan hasil pengujian aplikasi, bahwa algoritma horspool lebih cepat 19.82845 persen pada uji coba pertama menggunakan 50 file text kelipatan 1000 kata dengan pattern yang  sama  dan  15.9442  persen  pada  uji  coba  kedua  dengan  file  text  7000  kata.  Sehingga  dapat  disimpulkan algoritma horspool lebih cepat dari pada algoritma zhu-takaoka[2].
Berdasarkan  penelitian  sebelumnya  yang  dilakukan  oleh  Gutman  Togatorop,  Aan  Erlansari,  dan  Funny Farady  Coastera(2017),  Rekursif,  Vol.5  No.2  Hal.147  dengan  judul  implementasi  algoritma  zhu-takaoka  pada aplikasi kamus istilah musik berbasis android. Telah berhasil menjalankan aplikasi tersebut dengan baik tanpa ada error.  pencarian  kata  dan kalimat  dapat dilakukan  dengan cepat  dan  mudah  dibandingkan  dengan mencari  kata pada kamus cetak[3].

## 2. METODOLOGI PENELITIAN

## 2.1 String Matching
String Matching merupakan salah satu algoritma yang digunakan untuk mempercepat proses pencarian kata yang diinginkan. String  matching dibagi  menjadi  dua,  yakni exact  matching dan heuristic atau statistical  matching . Algoritma string  matching telah  sering  digunakan  sebelumnya  seperti contoh  pada  proses  pencocokan string berdasarkan persamaan teks data yaitu Brute Force . Dalam hal ini, dipilih algoritma brute force karena algoritma ini dapat digunakan untuk melakukan pencarian string atau teks. Algoritma brute force adalah algoritma untuk mencocokkan pattern dengan  semua  teks  antara  0  dan  n-m  untuk  menemukan  keberadaan pattern dalam teks. Berdasarkan arah pencariannya, algoritma ini diklasifikasikan sebagai algoritma yang membaca string dari kiri ke kanan [3].

## 2.2 Algoritma Zhu Takaoka
Algoritma Zhu-Takaoka menjelaskan bahwa pencarian pattern dilakukan mulai dari tiap baris mulai dari baris ke 0  dan  berakhir  pada  baris  ke  n1  –  m1.  Zhu  dan  Takaoka  merancang  sebuah  algoritma  yang  dapat  bekerja menggunakan  pergeseran  dengan bad-character untuk  dua  karakter text secara  berturut-turut.  Selama  fase pencarian pencocokan karakter dilakukan dari kanan ke kiri dan ketika proses berada di posisi y[j..j + m-1] dan ketidakcocokan  terjadi  diantara  x[m-k]  dan  y[j+m-k]  ketika  x  [m  –  k+1..m-1] = y[j+m-k+1..j+m-1] pergeseran dilakukan  dengan  pergeseran bad-character untuk text karakter  y[j+m-2]  dan y[j+m-1].  Tabel good-suffix dari algoritma boyer-moore juga  digunakan untuk menghitung  pergeseran.  Pada  awal  proses algoritma zhu-takaoka melakukan preprocessing untuk menghitung bad character shift dan good suffix dari algoritma boyer-moore [5]. Berikut prosedur algoritma Zhu Takaoka pada proses pencocokan string :
1. Menjalankan prosedur preZTBc dan preBmGs untuk mendapatkan inisialisasi.
a. Menjalankan  prosedur preZTBc .  Fungsi  dari  prosedur  ini  adalah  untuk  menentukan  berapa  besar pergeseran  yang  dibutuhkan  untuk  mencapai  karakter  tertentu  pada pattern dari  dua  karakter  pattern terakhir/terkanan. Hasil dari prosedur preZTBc disimpan pada tabel ZTBc .
b. Menjalankan  prosedur preBmGs .  Sebelum  menjalankan  isi  prosedur  ini,  prosedur suffix dijalankan terlebih dulu pada pattern . Fungsi dari prosedur suffix adalah memeriksa kecocokan sejumlah karakter yang dimulai dari karakter terakhir/terkanan dengan sejumlah karakter yang dimulai dari setiap karakter yang lebih kiri dari karakter terkanan tadi.
c. Dengan prosedur preBmGs , dapat diketahui berapa banyak langkah pada pattern dari sebeuah segmen ke segmen lain yang sama yang letaknya lebih kiri dengan karakter di sebelah kiri segmen yang berbeda.
2. Dilakukan proses pencarian string dengan menggunakan hasil dari prosedur preBmBc dan preBmGs yaitu tabel BmBc dan BmGs [6].

## Journal of Computer System and Informatics (JoSYC)

## ISSN 2714-7150 (media cetak)

## 2.3 Translator Bahasa Indonesia – Finlandia
Penerjemahan  adalah  pengalihan  makna  dari  bahasa  sumber  ke  dalam  bahasa  sasaran.  Selain  itu,  dalam penerjemahan terjadi penggantian bentuk bahasa sumber dengan bentuk bahasa sasaran. Dalam menerjemahkan bahasa sumber ke bahasa sasaran, bentuk boleh diubah tapi makna harus dipertahankan [7] Berdasarkan tersebut penulis mengambil kesimpulan bahwa Translator Bahasa Indonesia  – Finlandia adalah pengalihan suatu bahasa yang menerjemahkan bahasa Indonesia ke dalam bahasa Finlandia.

## 3. HASIL DAN PEMBAHASAN

## 3.1 Analisa Masalah
Analisis  sistem  merupakan  penguraian  dari  suatu  sistem  yang  utuh kedalam bagian-bagian komponennya dengan  maksud  untuk  mengidentifikasikan  dan  mengevaluasi  permasalahan-permasalahan,  kesempatan- kesempatan hambatan-hambatan yang terjadi dan kebutuhan-kebutuhan yang diharapkan sehingga dapat diusulkan perbaikan-perbaikannya.
Analisa  masalah  yang  ada  di  dalam  penelitian  ini  menggambarkan  kesulitan  untuk  mencari  terjemahan bahasa Indonesia ke dalam bahasa Finlandia yang cepat  dan tepat bagi masyarakat umum yang baru mengenal bahasa Finlandia terutama yang ingin melanjutkan pendidikan ke negara Finlandia sehingga dibutuhkan aplikasi translator bahasa Indonesia – bahasa Finlandia dengan menerapkan algoritma zhu-takaoka.
Aplikasi translator  bahasa  Indonesia  –  bahasa  Finlandia  yang  dibangun  oleh penulis pada  penelitian ini adalah aplikasi berbasis android. Aplikasi translator bahasa Indonesia  – bahasa Finlandia berbasis android yang dibangun memiliki keunggulan yaitu mudah dipahami dan memiliki ukuran yang tidak terlalu besar sehingga tidak membutuhkan tempat penyimpanan yang terlalu besar pada saat akan dibawa ke suatu tempat.
Penerapan algoritma Zhu Takaoka pada aplikasi translator bahasa Indonesia – bahasa Finlandia yang peulis bangun mempermudah user atau pengguna aplikasi tersebut untuk mendapatkan hasil translator dengan cepat dan tepat.  Cara  kerja  algoritma  Zhu  Takaoka  dalam  melakukan  pencocokan  string  yaitu  memulai  pencocokan  dari karakter paling kana ke karakter paling kiri dengan menggunakan array  2 (dua) dimensi berdasarkan nilai tabel ZtBc dan BmBc.

## 3.2 Penerapan Algoritma Zhu Takaoka
Pada penelitian ini dilakukan pencocokan string dengan menerapkan algoritma Zhu Takaoka untuk menemukan hasil pencocokan karakter pattern dengan karakter teks. Contoh kasus pencocokan string pada penelitian ini yaitu penccokan pattern “IBU” dengan text “ DOA IBU SAYA”.
Tahap pertama yang dilakukan sebelum pencocokan string adalah menciptakan dua buah tabel shif atau pergesaran Zhu Takaoka Bad Character dan Boyer Moore Good Suffixes. Tabel Zhu Takaoka Bad Character Table dapat dilihat pada tabel berikut ini :
Tabel 1. Zhu Takaoka Bad Character Table ZtBc B I U * B 2 3 1 3 I 2 3 3 3 U 2 3 3 3 * 2 3 3 3
Tabel Zhu  Takaoka Bad  Character berbentuk array dua  dimensi   yang  baris  dan  kolomnya  diisi berdasarkan  pada pattern yang  akan  dicari.  Tabel Zhu  Takaoka  Bad  Character adalah  hasil  modifikasi  dari algoritma boyer moore yang hanya memiliki bentuk array datu dimensi yaitu tabel Boyer Moore Good Suffixes . Tanda * pada tabel Zhu Takaoka Bad Character berfungsi untuk mewakili setiap karakter yang tidak terdapat pada pattern yang akan dicari.
Tabel 2. Boyer Moore Good Suffixes I 0 1 2 x[i] I B U suff[i] 0 0 3 bmGs[i] 3 3 1
Tahapan  selanjutnya  adalah  melakukan  pencarian  dengan  teknik right-to-left  scan  rule .  Pencarian dilakukan dengan membandingkan karakter demi karakter mulai karakter paling kanan menuju karakter paling kiri.  Jika  terjadi  ketidak  cocokan  karakter,  pergeseran  akan  dilakukan  berdasarkan  nilai max antara ZtBc dan BmGs , dan apabila semua pattern cocok pergeseran menggunakan nilai dari bmGs[0] . Index dari ztBc diambil dari  dua  karakter  terakhir  teks  yang  bersesuaian  dengan  window,  sedangkan index bmGs diambil  dari index

## Journal of Computer System and Informatics (JoSYC)
Volume 1, No. 4, Agustus 2020, Page 324-327 ISSN 2714-8912 (media online)

## ISSN 2714-7150 (media cetak)
pattern pada  posisisi  karakter  yang  tidak  cocok. Langkah-langkah  yang  dilakukan  dalam  proses    pencocokan pattern “Ibu” dengan text “Doa Ibu Saya” menggunakan algoritma zhu takaoka adalah sebagai berikut : Langkah ke- 1
Tabel 3. Langkah Ke-1 window Text D O A I B U S A Y A Pattern I B U Index 0 1 2
Terlihat  pada  langkah  ke-1  karakter  U  dengan  Karakter A  sejajar  tidak  ditemukan  kecocokan.  Maka dilakukan pergeseran berdasarkan nilai max ZtBc dan BmGs yaitu sebanyak 3 langkah .
Langkah ke- 2 Tabel 4. Langkah Ke-2 window I B Text D O A I B U S A Y A Pattern I B U Index 0 1 2
Terlihat  pada  langkah  ke-2  karakter  U  dengan  Karakter  B  sejajar  tidak  ditemukan  kecocokan.  Maka dilakukan pergeseran berdasarkan nilai bmGs[i] = bmGs[2] = 1 yaitu sebanyak 1 langkah . Langkah Ke-3
Tabel 5. Langkah ke- 3 window Text D O A I B U S A Y A Pattern I B U Index 0 1 2
Terlihat  pada  langkah  ke-3  seluruh  karakter pattern memiliki  kecocokan  dengan  karakter text .  Maka dilakukan pergeseran diberhentikan.

## 4. KESIMPULAN
Berdasarkan hasil dari penelitian ini penulis menguraikan kesimpulan sebagai berikut ini :
1. Implementasi algoritma Zhu Takaoka pada aplikasi translator bahasa Indonesia – Finlandia berbasis android dapat  mempermudah  pengguna  untuk  menemukan  kata  atau  kalimat  yang  berhubungan  dengan  bahasa Finlandia.
2. Perancangan aplikasi translator bahasa Indonesia – Finlandia berbasis android menggunakan software atau alat bantu perancangan eclipse juno , dalam hal ini eclipse juno sebagai media yang digunakan untuk merancang apikasi translator bahasa Indonesia – Finlandia dengan mengimplementasikan algoritma zhu takaoka.

## REFERENCES
[1] Adhi Kusnaidi, Abraham Khrisnandi Wicaksono,Perbandingan Algoritma Horspool dan Algoritma Zhu-Takaoka dalam pencarian String Berbasis Desktop, Gading Serpong:Universitas Multimedia Nusantara.2010.
[2] Gutman Togatorop, Aan Erlan Sari, Funny Farady Coastera, IMPLEMENTASI ALGORITMA ZHUTAKAOKA PADA APLIKASI KAMUS ISTILAH MUSIK BERBASIS ANDROID, Bengkulu:Universitas Bengkulu, 2017.
[3] Mesran, "Implementasi Algoritma Brute Force Dalam Pencarian Data Katalog Buku Perpustakaan," 2014.
[4] Fince Tinus Waruwu, "Implementasi Algoritma Knuth Morris Pratt Pada Aplikasi Kamus Istilah Latin Flora dan Fauna Berbasis Android," 2014.
[5] Adhi Kusnadi & Braham Khrisnandi Wicaksono, "Perbandingan Algoritma Horspool dan Algoritma Zhu-Takaoka dalam Pencarian String Berbasis Desktop," vol. Vol. IX, 2017.
[6] Dkk  Gutman  Togatorop, "IMPLEMENTASI  ALGORITMA ZHUTAKAOKA  PADA  APLIKASI KAMUS  ISTILAH MUSIK BERBASIS ANDROID," vol. Vol. 5, 2017.
[7] Dkk.  Rizal, "Rancang  Bangun  Aplikasi  Realtime  Translation  Untuk  Penerjemahan  Bahasa  Inggris  Indonesia  Berbasis Augmented Reality Pada Android," vol. Vol. 4, 2016.