## Implementasi String Matching Untuk Mencari Informasi Negara-Negara Anggota PBB Berbasis Android dengan Metode Zhu-Takaoka

## Daniel Siregar
Prodi Teknik Informatika, Universitas Budi Darma, Medan, Indonesia Email: danielr3gar@gmail.com
Abstrak- Dalam menambah pengetahuan umum kita mengenai negara-negara yang ada di dunia kita membutuhkan informasi tentang Negara  tersebut.  Terutama  pada  siswa-siswi  SMA  yang  mengambil  jurusan  IPS  (Ilmu  Pengetahuan  Sosial).  Namun  dalam mempelajari tentu siswa-siswi ini dibebankan akan biaya untuk membeli buku serta jumlah informasi yang banyak serta memerlukan waktu yang lama untuk mendapatkannya. Dalam hal pencarian informasi negara-negara PBB menggunakn Zhu - Takaoka ini sangat pantas  digunakan  kaena  karena  mampu  melakukan  pencarian  perbandingan  dilakukan  dari  kanan  ke  kiri.  Algoritma Zhu - Takaoka dapat menyelesaikan masalah proses pencarian informasi negara-negara PBB karena lebih mudah dan cepat. Adapun solusi masalah dari  permasalahan tersebut  adalah  dengan  cara  merancang  dan  membangun  aplikasi  pencarian  informasi  negara-negara  PBB  yang mudah  diakses  dimanapun  berada  dan  mudah  dalam  mengoperasikannya  Dengan  adanya  aplikasi  informasi  negara-negara  PBB diharapkan dapat memudahkan siswa-siswi mencari dan mengetahui tentang negara-negara yang bergabung dalam organisasi dunia PBB.
Kata Kunci : Pencarian, PBB, Algoritma Zhu-Takaoka, Aplikasi
Abstract -In increasing our general knowledge about countries in the world we need information about that  country. Especially for high school students who major in Social Sciences (Social Sciences). But in learning of course these students will be charged the cost of buying books and a large amount of information and require a long time to get it. In terms of  searching for information from UN countries,  using  Zhu-Takaoka  is  very  appropriate  to  use  because  it  is  able  to search  for  comparisons  from  right to  left.  The  Zhu- Takaoka algorithm can solve the problem of the UN information seeking process because it is easier and faster. The solution to the problem of these problems is by designing and building information retrieval applications of UN countries that are easily accessible wherever they are and are easy to operate. With the application of information from the United Nations, it is hoped that students can find and know about countries join the UN world organization.
Keyword : Search, UN, Zhu-Takaoka Algorithm, Application

## 1. PENDAHULUAN
Kemajuan pada teknologi informasi ditandai dengan semakin banyaknya aplikasi yang menggantikan peranan buku atau bahan  baca  lainnya.  Dalam  hal  ini  gadget  khususnya handphone telah  mengambil  peranannya  besar  ditengah-tengah masyarakat. Dengan adanya software pemograman yang dapat membantu dalam membangun sebuah sistem informasi yang dapat mempermudah dalam proses informasi, sehingga masyarakat dapat menikmati informasi secara mudah dan instan.
Salah satu dari sekian banyak informasi adalah pengetahuan untuk mempelajari negara-negara yang ada di dunia ini.  Salah  satunya  negara  yang  tergabung  di  dalam  organisasi  PBB  (Perserikatan  Bangsa-  Bangsa).  PBB  adalah organisasi  yang  dibentuk  oleh  negara-negara  besar  setelah  Perang  Dunia  II  yang  tidak  menginginkan  adanya  perang selanjutnya.  Organisasi  ini  bergerak  dalam  memelihara  perdamaian  internasional  dan  meningkatkan  kerjasama  dalam memecahkan permasalahan ekonomi, sosial, dan kemanusiaan.
Adapun permasalahan yang sering ditemui dalam proses pencarian informasi adalah saat membolak-balik buku yang memakan waktu untuk mencari negara yang diinginkan karena adanya urutan nama sesuai abjad atau istilah yang digunakan. Belum lagi berat  dari buku yang harus dibawa kemana-mana serta biaya yang dikeluarkan untuk  membeli buku. Khususnya  siswa-siswi  SMA  yang  mengambil  jurusan  IPS  (Ilmu  Pengetahuan  Sosial)  untuk  mata  pelajaran Kewarganegaraan. Sedangkan jika mencari informasi dari internet siswa-siswi akan mengeluarkan biaya untuk membeli pulsa  (kuota  internet)  atau  pun  pergi  ke  warnet. Aplikasi  pencarian  informasi  negara  yang  akan  dirancang  ini  adalah aplikasi  yang  akan  dijalankan  pada handphone yang  didukung  dengan  sistem  operasi  android. Dengan  aplikasi pencarian  tersebut  diharapkan  juga  dapat  meningkatkan  keingintahuan  serta  minat  baca  masyarakat.  Dikarenakan masyarakat  pada  zaman  ini  yang  lebih  sering  terpaku  pada  keperluan  menggunakan gadget . Serta  adanya  memberi kemudahan untuk menghemat biaya untuk buku dan internet.
Untuk mempermudah pencarian kata kunci untuk setiap negara dalam aplikasi tersebut, maka aplikasi pencarian informasi  negara  yang  akan  dirancang  pada  android  tersebut  menggunakan  algoritma Zhu-Takaoka .  Algoritma Zhu- Takaoka merupakan  salah  satu  dari  tiga  algoritma  pencarian  string  yang  merupakan  pengembangan  dari  algoritma Boyer-Moore .  Cara  kerja  algoritma Zhu-Takaoka adalah  mencocokan  pattern  pada  awal  teks  dari  kanan  ke  kiri  yang biasanya menghasilkan hasil terbaik  secara partikal. Algoritma Zhu-Takaoka akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian sampai kondisi yang sudah ditentukan terpenuhi.

## 2. METODOLOGI PENELITIAN

## 2.1 Algoritma Zhu-Takaoka
Algoritma  Boyer-Moore  dan  Algoritma  Zhu-Takaoka  yaitu  terletak  pada  tahap  penentuan bad  character  rule .  Dalam Boyer-Moore, bad  character hanya  terdiri array satu  dimensi,  sedangkan  dalam  Zhu-Takaoka  dimodifikasi  menjadi array dua dimensi. Karakteristik Algoritma Zhu-Takaoka: 1. Pengembangan dari algoritma Boyer-Moore
2. Menggunakan array dua dimensi untuk menghitung nilai pergeseran.
3. Melakukan pencocokan dari kanan ke kiri Pada preproccesing terhadap  pattern  P  dengan  menghitung  fungsi  pinggiran  (dalam  literatur  lain  menyebut fungsi overlap ,  fungsi failure ,  dsb)  yang  mengindikasikan  pergeseran  s  terbesar  yang  mungkin  dengan  menggunakan perbandingan  yang  dibentuk  sebelum  pencarian string .  Fungsi  pinggiran  hanya  bergantung  pada  karakter-karakter  di dalam pattern ,  dan  bukan  pada  karakter  -  karekter  di  dalam  teks  yang  dicari.  Oleh  karena  itu,  kita  dapat  melakukan perhitungan fungsi awalah sebelum pencarian string dilakukan.
Tabel 1. Fungsi Awalan Sebelum Pencarian String ztBc A C G T A 8 8 2 8 C 5 8 7 8 G 1 6 7 8 T 8 8 7 8 Sumber: Sholiq, 2006, 7, [9] Tabel 2. Fungsi Pinggiran Untuk Pattern GCAGAGAG I 0 1 2 3 4 5 6 7 x[i] G C A G A G A G BmGs[i] 7 7 7 2 7 4 7 1
Sumber: Sholiq, 2006, 7, [9]

## 3. HASIL DAN PEMBAHASAN
Aplikasi Pencarian Informasi Anggota PBB akan dirancangan dengan menggunakan bahasa pemograman android yang dirancang  dengan  menggunakan  algoritma  Zhu-Takaoka,  Oleh  karena  itu  pada  perancangan  aplikasi  pencarian    ini diharapkan  dapat  menyelesaikan  permasalahan  tersebut.  Proses  pencarian  kata  dengan  menerapkan  algoritma, merupakan hal  penting dalam  pencarian informasi anggota PBB ini karena proses tersebut merupakan bagian inti dari pembuatan aplikasi pencarian informasi tersebut.
Tahapan preprocessing yaitu  menciptakan  dua  buah  tabel  shif/pergesaran  ztBc  ( Zhu-Takaoka  Bad  Character ) dan  bmGs  ( Boyer-Moore  Good  Suffixe s).  Kedua  tabel  berikut  ini  ini  diciptakan  merujuk  kepada pattern yang  akan dicari sehingga pattern berubah maka tabel juga akan berubah. Hasil preprocessing untuk pattern abeg.
Tabel 3. Bad Character Zhu-Takaoka ZtBc D I N O * D 4 3 2 1 4 I 4 3 4 4 4 N 4 3 4 4 4 O 4 3 4 4 4 * 4 3 4 4 4
Tabel ztBc berbentuk array dua dimensi yang baris dan kolom diisi sesuai dengan karakter yang ada pada pattern , tanda *( star ) mewakili seluruh karakter yang tidak ada pada pattern .
Tabel 4. Boyer-Moore Good Suffixes Table I 0 1 2 3 Pattern I N D O bmGs(i)  4 4 2 1
Tahapan  selanjutnya  adalah  tahapan  pencarian  yaitu  dengan  menggunakan  teknik    right-to-left  scan  rule.  Pencarian dilakukan  dengan    membandingkan  karakter  demi  karakter  dari  mulai  karakter  paling  kanan  menuju  karakter  paling kiri. Jika terjadi ketidakcocokan karakter, pergeseran akan dilakukan dengan mencari nilai max antara ztBc dan bmGs, dan  apabila  semua  pattern  cocok  pergeseran  menggunakan  nilai  dari  bmGs[0].  Langkah-langkah  pencarian  dengan algoritma Zhu-Takaoka.
Langkah pertama:
Tabel 5. pencarian pada teks langkah pertama Windows * * Teks R  E P U  B  L  I  K    I  N  D  O  N  E  S  I  A Pattern I N  D  O
I
ZTbC[*][*]=4 bmGs[i] = bmGs = 1 Pergesaran dilakukan sebanyak 4 kali (pergeseran maksimal)
Langkah kedua:
Tabel 6 . pencarian pada teks langkah kedua Windows * * Teks R  E P U B  L I K I N D O N E S I A Pattern I  N D O I 0  1 2 3
ZTbC[*][*]=4 bmGs[i] = bmGs = 1 Pergesaran dilakukan sebanyak 4 kali (pergeseran maksimal)
Langkah Ketiga:
Tabel 7 . pencarian pada teks langkah ketiga windows Teks R  E  P  U  B  L  I  K I N  D  O  N  E  S  I  A Pattern I  N  D  O I 0  1 2 3
ZTbC[I][I]=3 bmGs[i] = bmGs = 1 Pergesaran dilakukan sebanyak 3 kali (pergeseran maksimal)
Langkah Keempat:
Tabel 8. pencarian pada teks langkah keempat windows Teks R  E  P  U  B  L  I  K I N  D  O  N  E  S  I  A Pattern I N  D  O I 0  1 2 3
Karakter Cocok Pergeseran tidak dilakukan lagi.

## 4. KESIMPULAN
Berdasarkan hasil akhir pada penelitian skripsi ini penulis menarik sebuah kesimpulan yang sekiranya dapat bermanfaat bagi  pembaca,  adapun  kesimpulannya  pencarian  yang  dilakukan  aplikasi  Informasi  Negara  Anggota  PBB    sangat membantu karena dapat melakukan pencarian string dengan cepat dan memberikan hasil yang tepat, tidak memerlukan koneksi  internet, serta mengurangi pengeluaran untuk  membeli buku,  menghasilkan banyak informasi  saat  melakukan pencarian,  serta  menghasilkan  tampilan interface yang  sederhana  dan  tampilan output pencarian  mudah  untuk dimengerti.

## REFERENCES
[1] T. Pada and A. Kamus, “IMPLEMENTASI ALGORITMA ZHU-,” vol. 5, no. 2, pp. 147–153, 2017.
[2] Andri  Kinoyo  Kusrini,  Tuntunan  Praktis  Membangun  Sistem  INformasi  Akutansi  dengan  Microsoft  Visual  Basic  &  SQL Server. Yogyakarta: Andi Offset, 2007.
[3] Rinaldi Munir, Matematika Diskrit. Bandung: Informatika, 2012.
[4] Tata Sutabri, Analisa Sistem Informasi. Yogyakarta : Andi, 2012.
[5] https://id.wikipedia.org/wiki/Perserikatan_Bangsa-Bangsa, tanggal akses 8 Agustus 2018
[6]   T. Ilmiah. "Implementasi Algoritma Brute Force dalama Pencarian Data Katalog Buku Perpustakaan, " pp. 100-104, 2014.
[7] A. Knuth, M. Pratt, D. A. N. Algoritma, B. Moore, A. Knuth, and A. B. Moore, "Perancangan aplikasi pencarian kata dengan kombinasi algoritma knuth morris pratt dan algoritma boyer moore, " no. May, 2017.
[8] Adi  Nugroho,  Rekayasa  Perangkat  Lunak  Berorientasi  Objek  Dengan  Menggunakan  Metode  USDP.  Bandung:  Andi  Offset, 2010.
[9] Sholiq, Pemodelan Sistem Informasi Berorientasi Objek Dengan UML. Yogyakarta: Graha Ilmu, 2006.
[10]  http://www.ubaya.ac.id/2014/content/articles_detail/7/Andorid-Sistem-Operasi-pada-Smartphone.html
[11]  Nazaruddin  Safaat  H,  Pemograman  Aplikasi  Mobile  Smartphone  dan  Tablet  PC  Berbasis  Android.  Bandung:  Informatika, 2015.
[12]   https://tekno.kompas.com/read/2016/10/17/19480037/evolusi.os.android.dari.versi.1.0.hingga.7.0.nougat
[13]  Yuniar Supriadi, Pemograman Database Dengan Java dan MySQL. Jakarta: PT.Alex Media Kompetindo, 2007.