## Implementasi Algoritma Zhu-Takaoka Pada Data  Repository Linux Berbasis Web
Khairul Abdi Dongoran, Nelly Astuti Hasibuan, Sumiaty Hutabarat, Garuda Ginting, Saidi Ramadan Siregar
Teknik Informatika, Universitas Budi Darma, Medan, Indonesia
Email: kabdi384@gmail.com Submitted 19-10-2020 ; Accepted 27-10-2020 ; Published 25-04-2021

## Abstrak
Apabila mengetikkan kata kunci software yang dicari pada website maka banyak sekali situs – situs yang menyediakan software tersebut, namun  memerlukan  waktu  yang  lama  untuk  mendapatkan  file  yang  dibutuhkan  karena  mencari  file  secara  manual  serta  tidak  adanya kategori  atau  pengelompokan  software-software  yang  dibutuhkan.Dalam  penyelesaian  tersebut  penulis  menggunakan  Algoritma  Zhu- Takaoka, Zhu-Takaoka merupakan algoritma modifikasi dari algoritma Boyer-Moore. Algoritma Zhu-Takaoka menggunakan array dua dimensi untuk menghitung nilai pergeseran dan melakukan pencocokan dari kanan ke kiri menghasilkan aplikasi yang mampu berjalan dengan  baik  tanpa  ada  error,  pencarian  aplikasi  atau  program  yang  dapat  dilakukan  dengan  cepat  dan  mudah  dengan  ditempatkannya ratusan program atau aplikasi didalam repository.Perancangan yang diharapkan nantinya aplikasi repository linux ini dapat berjalan dengan baik disemua perangkat yang memiliki browser, dan aplikasi yang dirancang ini juga diharapkan mampu membantu khalayak ramai dalam mencari aplikasi atau program linux debian (.deb) berdasarkan nama software yang dicari.
Kata Kunci: Software; Repository; Zhu-Takaoka; Pencarian

## Abstract
When you use a software keyword that is searched on a website, there are a lot of sites that provide the software, it takes a long time to get the files needed because they are looking for files manually and there are no categories or groupings of software needed. In correcting the writer  using  the  Zhu-Takaoka  Algorithm,  Zhu-Takaoka  is  a  modified  algorithm  of  the  Boyer-Moore  algorithm.  The  Zhu-Takaoka algorithm  uses  a  two-dimensional  array  to  calculate  and  execute  functions  from  left  to  left  which  allows  you  to  make  mistakes,  find applications that can be done quickly and easily with the stack of programs or applications in the repository. The expected design of this Linux repository application can run well in all devices that have a browser, and this designed application also allows you to search for debian (.deb) Linux programs using the name of the software you are looking for.
Keywords: Software; Repository; Zhu-Takaoka; Search

## 1. PENDAHULUAN
Penggunaan  Sistem  Operasi Open  Source berbasis  Linux  atau  Distro  Linux  mengalami  pertumbuhan  yang  tinggi. Pertumbuhan ini disebabkan oleh adanya kebebasan dalam hal lisensi. Lisensi Open Source mengijinkan setiap pengembang perangkat  lunak  melakukan  modifikasi  dan  distribusi.  Kebebasan  tersebut  mendorong  pengembang Open  Source untuk membuat aplikasi yang dapat dimodifikasi dan di-distribusikan lagi oleh kita tanpa dikenai biaya lisensi. Banyak pengembang perangkat  lunak  biasanya  mendistribusikan softwarenya secara  gratis  melalui  website.  Apabila  mengetikkan  kata  kunci software yang dicari pada website maka banyak sekali situs – situs yang menyediakan software tersebut , namun memerlukan waktu yang lama untuk mendapatkan file yang dibutuhkan karena mencari file secara manual serta tidak adanya kategori atau pengelompokan software - software yang dibutuhkan[1].
Untuk mengatasi permasalahan tersebut maka perlu dibangun sebuah website yang mempermudah pengguna dalam memilih software dan versi software yang akan di install atau dibutuhkan oleh pengguna dan dengan dibuatnya search box pada repository Linux  berbasis  web  sehingga  cepat  dalam  pencarian software yang  diperlukan  serta  sistem  dapat menampilkan software yang banyak diunduh oleh user . Repository merupakan tempat penyimpanan untuk ratusan data atau program yang telah diatur dan tersedia di akses pada internet. Apabila mencari software pada website maka banyak sekali situs – situs yang menyediakan free software, namun memerlukan waktu yang lama untuk mendapatkan file yang dibutuhkan karena mencari file secara manual. Algoritma Zhu-Takaoka dipublikasikan dan dikembangkan oleh Zhu Rui Feng dan Tadao Takaoka pada tahun 1986. Algoritma Zhu-takaoka merupakan suatu algoritma yang digunakan untuk memecahkan masalah pencocokan sebuah pattern terhadap teks lain atau dengan kata lain sebuah pencarian pola string yang lebih pendek di dalam string  yang  lebih  panjang.  Dengan  kata  yang  dicari,  sehingga  dengan  mudahnya  dapat  menemukan software yang dibutuhkan[2].

## 2. METODOLOGI PENELITIAN

## 2.1 String Matching
String Matching adalah proses pencarian semua kemunculan query yang selanjutnya disebut pattern ke dalam string yang lebih panjang atau teks. Pattern dilambangkan dengan x=x[0..m-1] dan panjangnya adalah m. Teks dilambangkan dengan y=y[0..n-1] dan panjangnya adalah n. Kedua string terdiri dari sekumpulan karakter yang disebut alfabet yang dilambangkan dengan ∑ dan mempunyai ukuran. String matching dibagi menjadi dua, yaitu exact matching dan heuristic matching. String Matching dirumuskan sebagai berikut : x = x[0…m-1] (1)

## y = y[0…n-1]
(2)
Dimana : x adalah pattern m adalah panjang pattern y adalah teks n adalah panjang teks Kedua string terdiri dari sekumpulan karakter yang disebut alfabet yang dilambangkan dengan ∑ (sigma) dan mempunyai ukuran σ (tao). String matching dibagi menjadi dua, yakni exact matching dan heuristic atau statistical matching [3].

## 2.2 Exact Matching
Exact matching digunakan untuk menemukan pattern yang berasal dari satu teks. Contoh pencarian exact matching adalah pencarian kata “pelajar” dalam kalimat “Saya seorang pelajar” atau “Saya seorang siswa”. Sistem akan memberikan hasil bahwa  kalimat  pertama  mengandung  kata  “pelajar”  sedangkan  kalimat  kedua  tidak,  meskipun kenyataannya  pelajar  dan siswa adalah kata yang bersinonim. Algoritma exact matching diklasifikasi menjadi tiga bagian menurut arah pencariannya, yaitu :[3]
1. Arah pembacaan dari kiri ke kanan. Algoritma yang termasuk kategori ini adalah Brute Force, Morris dan Pratt (yang kemudian dikembangkan oleh Knuth, Morris, Pratt).
2. Arah  pembacaan  dari  kanan  ke  kiri.  Algoritma  yang  termasuk  kategori  ini  adalah  Boyer  dan  Moore  yang  kemudian dikembangkan menjadi algoritma turbo Boyer-Moore, tuned Boyer-Moore, dan Zhu-Takaoka.
3. Arah  pembacaan  yang  ditentukan  pemrograman.  Algoritma  yang  termasuk  kategori  ini  adalah  algoritma  Colussi, Chochemore-Perrin..

## 2.3 Algoritma Zhu takaoka
Algoritma Zhu-Takaoka merupakan  algoritma  pencocokan String ( String Matching ) yang dipublikasikan oleh Zhu Rui Feng dan Tadao Takaoka pada tahun 1986.  Dalam makalahnya, Zhu dan  Takaoka menyebut  algoritma  pencocokan String ini sebagai BM Algorithm ( Boyer-Moore Algorithm ). BM Algorithm merupakan Algoritma modifikasi dari Algoritma pencocokan String  Boyer-Moore  Algorithm yang  dibuat  oleh Boyer  R.S dan Moore  J.S. Algoritma BM ( Algoritma  Zhu- Takaoka )  yang  merupakan  modifikasi  dari  Algoritma BM mempunyai  ciri-ciri  yang  sama  dalam  proses  pencarian String . Ciri-ciri tersebut yaitu adanya tahap Preprocessing , Right-to-left Scan, Bad- Character  Rule, dan Good-Suffix  R ule . Perbedaan  antara 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.[4] Array dua  dimensi  yaitu Array yang  dapat  mewakili  suatu  bentuk  tabel  atau  matriks,  yaitu  indeks  pertama menunjukkan baris dan indeks kedua menunjukkan kolom dari tabel atau matriks.
Adapun tahap pencarian Pattern menggunakan Algoritma Zhu-Takaoka adalah sebagai berikut: 1. Preprocessing
Prepocessing dalam  algoritma Zhu-Takaoka meliputi  pencarian  nilai  pergeseran  karakter  ( Good-Suffix  Shift )    dan pergeseran  karakter  jika  karakter  tidak  cocok ( Bad-Character Shift ). Nilai Good-Suffix Shift ditentukan dalam Good- Suffix Prepocessing sedangkan nilai Bad-Character Shift ditentukan dalam Bad-Character Prepocessing . Prepocessing dilakukan sebelum proses inti dari pencarian Pattern dalam suatu Text . 2. Right-to-Left Scan Rule Proses inti  pencarian  algoritma Zhu-Takaoka yaitu  dilakukan  dengan  teknik Right-To-Left Scan Rule . Teknik ini yaitu melakukan perbandingan antara Pattern yang dicari dengan target Text secara terbalik yaitu bergerak dari kanan ke kiri. Perbandingan Pattern dengan target Text dimulai dengan membandingkan karakter terakhir  dari Pattern (karakter paling  kanan)  dengan  target Text paling  kanan. Apabila ada kecocokan maka perbandingan akan dilanjutkan dengan bergerak ke kiri sampai karakter pertama dari Pattern . Sedangkan apabila terjadi ketidak cocokan maka akan dilakukan pergeseran, besarnya pergesaran yang dilakukan ditentukan oleh dua fungsi pergeseran yaitu Bad-Character Shift dan Good-Suffix Shift . 3. Bad-Charcter Shift Rule Aturan Bad-Character Shift dibutuhkan untuk menghindari pengulangan perbandingan yang gagal dari suatu karakter dalam  target Text dengan Pattern .  Besarnya  pergeseran  yang  dilakukan  dalam  aturan Bad-Character  Shift disimpan dalam bentuk tabel Array dua dimensi, tabel ini terdiri dari beberapa kolom yaitu kolom  karakter  dan  kolom Shift yang  menunjukkan  besarnya  pergeseran  yang harus dilakukan.
4. Good Suffix Shift Rule
Aturan Good-Suffix Shift dibuat untuk menangani kasus dimana terdapat pengulangan karakter pada Pattern .

## 2.4 Repository Linux
Repository linux atau biasa disebut repo adalah tempat penyimpanan kumpulan aplikasi atau software yang digunakan untuk menginstal aplikasi tambahan di dalam sistem operasi yang berbasis linux.[5] Repository di linux berbasis debian (.deb) dibagi ke dalam empat area yaitu sebagai berikut: 1. Main adalah software yang didukung secara resmi.
2. Restricted adalah software yang didukung tapi tidak seutuhnya free license . 3. Universe adalah software yang dikelola oleh komunitas. 4. Multiverse adalah software yang tidak free .

## 3. HASIL DAN PEMBAHASAN
Sistem Operasi Open Source berbasis Linux mengalami pertumbuhan yang tinggi. Pertumbuhan ini disebabkan oleh adanya kebebasan dalam hal lisensi. Lisensi Open Source mengijinkan setiap pengembang perangkat lunak melakukan modifikasi dan distribusi. Kebebasan tersebut mendorong pengembang Open Source untuk membuat aplikasi yang dapat dimodifikasi dan di-distribusikan lagi oleh kita tanpa biaya lisensi.Terdapat banyak sekali situs-situs menyediakan aplikasi yang dapat di akses pada internet sehingga membuat para pengguna Linux terkhusus dengan turunan Debian Linux yang berbasis (.deb) kesulitan dan memerlukan waktu yang lama untuk mencari aplikasi yang tersebar di internet.
Untuk mengatasi permasalahan diatas penulis mengimplementaikan algoritma zhu-takaoka . Algoritma zhu-takaoka merupakan salah satu algoritma string matching yang dapat melakukan pencarian kata dengan pergeseran yang yang banyak yaitu dengan array 2 (dua) dimensi. Proses inti pencarian algoritma zhu-takaoka yaitu  melakukan pencarian kata dengan teknik Right-to-left scan rule . Setiap pergeseran pada proses pencarian kata tentukan dari nilai pergeseran yang ada pada tabel Good  Suffix  Shift  Rule dan Bad-Charcter  Shift  Rule .  Adapun  hasil  yang  diperoleh  dari  penelitian  penulis  lakukan adalah sebuah aplikasi yang mempermudah pengguna dalam memilih software dan versi software yang akan di install atau dibutuhkan  oleh  pengguna  dan  dengan dibuatnya  search  box  pada  repository  Linux  berbasis  web  sehingga  cepat  dalam pencarian software yang diperlukan serta sistem dapat menampilkan software yang banyak diunduh oleh user .
Prosedur  kerja  algoritma zhu-takaoka pada  data  repository linux  berbasis  web  yaitu  dengan  membandingkan  atau mencocokkan pattern yang diinputkan di tools pencarian ( EditText ) dengan Text yang disimpan di dalam database . Tahap pencocokan string dilakukan mulai dari arah kanan ke arah kiri yaitu dari akhir karakter pattern dengan karakter text yang sejajar dengan karakter akhir pattern . Setelah terjadi kecocokan maka akan tampil hasil pencarian.

## 3.1 Implementasi Zhu-Takaoka pada Repository
Pada penilitian ini penulis melakukan analisa pencarian pattern menggunakan algoritma zhu-takaoka untuk 2 (dua) contoh kasus  yang  berbeda.  Pada  penelitian  ini  penulis  melakukan  pencarian  data  repository  Spotify adalah  layanan  musik streaming, podcast dan video komersial Swedia yang menyediakan hak digital manajemen yang dilindungi konten dari label rekaman dan perusahaan media. Ini tersedia di sebagian besar Amerika, Eropa Barat dan Oseania. Musik dapat diakses atau dicari oleh artis, album, genre, playlist, atau label rekaman. Spotify merupakan software open source yang bisa berjalan pada beberapa platform termasuk linux. mBerikut proses pencarian Spotify menggunakan algoritma zhu-takaoka : Teks : VLC CLEMENTINE SPOTIFY GIMP Pattern  : SPOTIFY
Tabel 1. Zhu-Takaoka Bad Character Table (ztBc) ZtBc S P O T I F Y * S 6
5 7 7 7 7 7 7 P 6 7 4 7 7 7 7 7 O 6
7 7 3 7 7 7 7 T 6
7 7 7 2 7 7 7 I 6
7 7 7 7 1 7 7 F 6
7 7 7 7 7 7 7 Y 6
7 7 7 7
7 7 7
* 6
7 7 7 7 7 7 7
Tabel ztBc berbentuk array dua  dimensi yang  baris  dan  kolom  diisi  sesuai dengan karakter yang ada pada pattern , tanda *( start ) mewakili seluruh karakter yang tidak ada pada pattern . Tabel inilah yang merupakan hasil modifikasi dari algoritma Boyer Moore yang memiliki table bad character hanya terdiri dari array satu dimensi.
Tabel 2. Boyer-Moore Good Suffixes Table (BmGs) I 0 1 2 3 4 5 6 x[i] S P O T I F Y suff[i] 0 0 0 0 0 0 7 bmGs[i] 7 7 7 7 7 7 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]. Indeks dari ztBc diambil dari dua karakter terakhir
teks yang bersesuaian dengan window, sedangkan indeks bmGs diambil dari indeks pattern pada posisisi karakter yang tidak cocok.
Langkah-langkah pencarian dengan algoritma Zhu-Takaoka adalah sebagai berikut: Langkah 1:
Tabel 3. Pencarian pada teks langkah ke - 1

## Pergeseran 7 (ztBc[L][E])
Dari hasil percobaan ke-1, dapat dilihat bahwa karakter akhir pattern yang dicari yaitu karakter Y sejajar dengan karakter E pada sumber teks. Artinya, pada percobaan ke-1 terjadi ketidakcocokan, maka dilakukan pergeseran sejauh tujuh karakter. Nilai pergeseran tujuh karakter ini diperoleh dari tabel 3.1 ztBc dimana dicocokannya dua karakter akhir pada teks yang sejajar dengan karakter akhir pattern. Pada contoh ini diisi dengan karakter L dan karakter E. Maka cek pada tabel ztBc baris L dan kolom E maka bernilai tujuh.
Langkah 2:
Tabel 4. Pencarian pada teks langkah ke - 2
Pergeseran 7 (ztBc[N][E]) Dari hasil percobaan ke-2, dapat dilihat bahwa karakter akhir pattern yang dicari yaitu karakter Y sejajar dengan karakter E pada sumber teks. Artinya, pada percobaan ke-2 terjadi ketidakcocokan, maka dilakukan pergeseran sejauh tujuh karakter. Nilai pergeseran tujuh karakter ini diperoleh dari tabel 3.1 ztBc dimana dicocokannya dua karakter akhir pada teks yang sejajar dengan karakter akhir pattern. Pada contoh ini diisi dengan karakter N dan karakter E. Maka cek pada tabel ztBc baris N dan kolom E maka bernilai tujuh.
Langkah 3:
Tabel 5. Pencarian pada teks langkah ke - 3
Pergeseran 1 (ztBc[I][F])
Dari hasil percobaan ke-3, dapat dilihat bahwa karakter akhir pattern yang dicari yaitu karakter Y sejajar dengan karakter F pada sumber teks. Artinya, pada percobaan ke-3 terjadi ketidakcocokan, maka dilakukan pergeseran sejauh tujuh karakter. Nilai pergeseran satu karakter ini diperoleh dari tabel 3.1 ztBc dimana dicocokannya dua karakter akhir pada teks yang sejajar dengan karakter akhir pattern. Pada contoh ini diisi dengan karakter I dan karakter F. Maka cek pada tabel ztBc baris I dan kolom F maka bernilai satu.
Langkah 4:
Tabel 6. Pencarian pada teks langkah ke - 3
Pergeseran 7 (ztBc[I][F])
Dari hasil percobaan ke-4, dapat dilihat bahwa karakter akhir pattern yang dicari yaitu karakter Y sejajar dengan karakter Y  pada  sumber  teks.  Artinya,  pada  percobaan  ke-4  terjadi  kecocokkan,  maka  pencocokan  dilakukan  terhadap  karakter sebelum Y, yaitu F,I,T,O,P,S pada pattern , bandingkan dengan karakter yang sejajar, terjadi kecocokan pada semua pattern, dan  untuk  melanjutkan  pencocokan gunakan  pergeseran  tujuh  karakter  diambil  dari 3.2 ztGs  karakter  S.  Karena  jumlah pergeseran lebih besar dibandingkan dengan sisa karakter pada teks, maka pencocokan selesai.
Keterangan dari hasil pencarian diatas sebagai berikut:
1. Pada tahap pencocokan dengan algoritma Zhu-Takaoka di atas, pencocokan dilakukan sebanyak 4 iterasi. Ditemukan pada iterasi ke-4.
2. Jumlah indeks pada teks adalah 26, pattern ditemukan pada indeks ke 15-21.
3. Jumlah perbandingan adalah 22, pattern ditemukan pada perbandingan ke 15.
I
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 … Teks V L C C L E M E N T I N E S … Pattern S P O T I F Y I 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 … Teks V L C C L E M E N T I N E S … Pattern S P O T I F Y I 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Teks N E S P O T I F Y G I M P Pattern S P O T I F Y I 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Teks N E S P O T I F Y G I M P Pattern S P O T I F Y

## 4. KESIMPULAN
Berdasarkan  hasil  analisa  yang  dilakukan,  maka  kesimpulan  dari  penelitian  ini  proses  pencarian  yang  dilakukan  aplikasi repository linux berbasis web dengan algoritma Zhu-Takaoka sangat efektif dalam proses pencarian karena menghasilkan banyak informasi saat melakukan pencarian. Algoritma Zhu-Takaoka bisa diterapkan pada aplikasi repository linux berbasis web sangat efektif dalam proses pencarian karena menghasilkan banyak informasi saat melakukan pencarian. Pencarian pada aplikasi repository linux dapat membantu user dalam melakukan pencarian string dengan cepat.

## REFERENCES
[1] D. Nugraha and S. Winiarti, “Pengembangan Media Pembelajaran Sistem Pelacakan Pada Mata Kuliah Kecerdasan Buatan Berbasis Multimedia,” J. Sarj. Tek. Inform., vol. 2, no. 1, pp. 738–748, 2014.
[2] W. J. Teahan, Artificial Intelligence – Agents and Environments. Bookboon, 2010.
[3] R. F. Riyanarto Sarno, Yeni Anistyasari, Semantic Search. Yogyakarta: Andi, 2012.
[4] F.  F.  C.  Gutman  Togatorop,  Aan  Erlansari,  “IMPLEMENTASI  ALGORITMA  ZHUTAKAOKA  PADA  APLIKASI  KAMUS ISTILAH MUSIK BERBASIS ANDROID,” vol. 5, no. 2, pp. 147–153, 2017.
[5] I.  G.  M.  D.  Kadek  Jeny  Femila  Devi,  I  Ketut  Resika  Arthana,  “Pengembangan  Distribusi  Luxpati  Berbasis  Ubuntu  Sebagai Penunjang Proses Belajar Mengajar di Jurusan Pendidikan Teknik Informatika,” vol. 4, pp. 87–95, 2015.
[6] M. Y. Ricky, “Pengembangan Aplikasi Online Mobile Repository,” vol. 2012, no. semnasIF, pp. 154–159, 2012.
[7] E. Bowo, Ubuntu : From Zero. Jasakom, 2010.
[8] R. Khairil, Nugroho Ponco Riyanto, “Membangun webserver intranet dengan linux,” J. Media Infotama, vol. 9, no. 1, pp. 1–24, 2013.
[9] M. S. Rosa A.S., Rekayasa Perangkat Lunak : Terstruktur dan Beorientasi Objek. Bandung: Informatika Bandung, 2011.
[10]  Z. Ali, 36 Menit Belajar Komputer: Php Dan Mysql. Jakarta: PT Elex Media Komputindo, 2008.
[11]  Huda Miftakhul dan Komputer Bunafit, Membuat Aplikasi Database dengan Java, MySQL dan NetBeans. Jakarta: PT. Elex Media Komputindo, 2010.
[12]  W. Komputer, Adobe Dreamweaver CS5 untuk beragam desain website interaktif. Yogyakarta: Penerbit Andi, 2011.