## KLIK: Kajian Ilmiah Informatika dan Komputer
ISSN 2723-3898 (Media Online) Vol 1, No 4, Februari 2021 Hal 154-159 https://djournals.com/klik

## Perancangan Aplikasi Marga Etnis Batak (MEB) Berbasis Web Dengan Menerapkan Algoritma Turbo Boyer Moore

## Fika Liana Marbun
Teknik Informatika, Universitas Budi Darma, Medan, Indonesia Email: fikaliana95@gmail.com
Asbrak- Suku  batak  merupakan  salah  satu  suku  bangsa  terbesar  di  Indonesia  .  nama  ini  merupakansebuah  tema  kolektif  untuk mengidentifikasikan  beberapa  suku  bangsa  yang  berkmukim  dan  berasal  dari  Pantai  Barat  dan  Pantai  Timur  di  propinsi  Sumatera Utara. Suku bangsa yang dikategorikan sebagai Batak terdiri dari Toba, Karo, Pakpak, Simalungun, Angkola dan Mandailing. Suku Batak memilik marga dengan jumlah yng mencapai ratusanyang berbagai atas etnis yang berbeda-beda dan silsilah yang berbeda-beda. Suku Batak merupakan rumpun suku-suku yang mendiami sebagian besar wilayah Sumatera Utara Dengan demikian maka diperlukan sebuah perancangan Aplikasi marga etnis Batak Algoritma Turbo Boyer Moore pada perancangan Aplikasi Marga Etnis Batak  dapat mempermudah suku batak untuk memperoleh informasi mengenai marga-maraga etnis batak dengan cepat dan tepat.
Kata Kunci: Turbo Boyer Moore, Marga Etnis Batak.
Abstract- Batak tribe is one of the largest ethnic groups in Indonesia. this name is a collective theme to identify several tribes that are settled and originating from the West Coast and East Coast in the province of North Sumatra. The ethnic groups categorized as Batak consist  of  Toba,  Karo,  Pakpak,  Simalungun,  Angkola  and  Mandailing.  Batak  tribes  belong  to  clans  with  a  number  that  reaches  a hundred more and different different pedigrees. The Batak tribe is a family of tribes that inhabit a large part of North Sumatra. Thus a design of the application of ethnic Batak clans is needed. Boyer Moore's Turbo Algorithm in the design of the Application of Batak Ethnic Clans can facilitate the Batak tribe to obtain information about Batak ethnic clans quickly and precisely.
Keywords: Turbo Boyer Moore, Clan of Batak Ethnics.

## 1. PENDAHULUAN
Marga adalah nama persekutuan dari orang-orang bersaudara, sedarah, seketurunan menurut garis ayah, yang mempunyai tanah sebagai milik bersama di tanah asal atau tanah leluhur. Marga dapat membina kekompakan dan solidaritas sesama anggota marga sebagai keturunan dari satu leluhur. Walau pun keturunan suatu leluhur pada suatu ketika mungkin akan terbagi atas marga-marga cabang, namun sebagai keluarga besar, marga-marga cabang tersebut akan selalu mengingat kesatuannya dalam marga pokoknya[1].
Suku Batak merupakan salah satu suku bangsa terbesar di Indonesia. Nama ini merupakan sebuah tema kolektif untuk  mengidentifikasikan  beberapa  suku  bangsa  yang  bermukim  dan  berasal  dari  Pantai  Barat  dan  Pantai  Timur  di Provinsi Sumatera Utara. Suku bangsa yang dikategorikan sebagai Batak terdiri dari beberapa etnis yaitu Toba, Karo, Pakpak, Simalungun, Angkola, dan Mandailing. Suku batak memiliki marga dengan jumlah yang mencapai ratusan yang terbagi atas etnis berbeda-beda dan silsilah yang berbeda.  Suku Batak merupakan rumpun suku-suku yang mendiami sebagian besar wilayah Sumatera Utara,  namun selain di sumatera utara pemeluk suku batak saat ini telah banyak yang merantau di luar wilayah sumatera utara[2].
Adapun  masalah  yang  dihadapi  dalam  penelitian  ini  yaitu  Zaman  modern  saat  ini  banyak  bangsa  batak  atau pemeluk  suku  batak  yang  berdomisili  di  daerah  yang  bukan  termasuk  wilayah  suku  batak  toba.  Beradaptasi  dengan lingkungan tanah perantauan pemeluk suku batak sehingga terbiasa menggunakan kebiasaan atau budaya suku lainnya. Dengan  berjalannya  waktu  bangsa  batak  atau  pemeluk  suku  batak  yang  berdomisili  di  tanah  perantauan  sulit  untuk mencari informasi mengenai Marga Etnis Batak untuk dipelajari..Saat ini penyedia informasi tentang marga etnis batak masih terbatas . Hal ini masyarakat umum kesulitan dalam mencari informasi mengenai Marga Etnis Batak dengan cepat dan  tepat.  Algoritma  string  matching  merupakan  algoritma  yang  digunakan  untuk  melakukan  pencocokan  string. Algoritma string yang diterapkan pada aplikasi marga etnis batak (meb) berbasis web pada penelitian ini adalah turbo boyer  moore.  turbo  boyer  moore  merupakan  algoritma  string  matching  yang  mampu  melakukan  pencocokan  string dengan cepat dari arah sebelah kanan ke arah sebelah kiri dengan pergeseran turbo[3].

## 2. METODOLOGI PENELITIAN

## 2.1 Perancangan
Perancangan  adalah  penggambaran,  perencanaan  dan  pembuatan  sketsa  atau  pengaturan  dari  beberapa  elemen  yang terpisah ke dalam satu kesatuan yang utuh dan berfungsi Perancangan sistem dapat dirancang dalam bentuk bagan alir sistemr (system flowchart), yang merupakan alat bentuk grafik yang dapat digunakan untuk menunjukan urutan-urutan proses dari sistem. Untuk dapat merancang konsep dalam membuat aplikasi   dibutuhkan kreatifitas. Kreatifitas adalah kemampuan untuk menyajikan gagasan atau ide baru. Sedangkan inovasi merupakan aplikasi dari gagasan atau ide baru tersebut. Untuk menciptakan ide yang orisinil tidaklah mudah, maka dapat digunakan beberapa teknik untuk menciptakan ide, yaitu penyesuaian (adaptasi), Multimedia yang telah ada dianggap belum sesuai dengan lingkungan yang dituju[4].

## 2.2 Aplikasi
Aplikasi  merupakan  penerapan  dari  rancang  system  untuk  mengolah  data  yang  menggunakan  aturan  atau  ketentuan bahasa pemograman tertentu . Aplikasi adalah suatu program computer yang dibuat untuk mengerjakan dan melaksanakan tugas khusus dari pengguna atau pernyataan yang disusun sedemikian rupa sehingga computer dapat memproses input menjadi output[4].

## 2.3 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  [4].. String  matching adalah proses pencarian semua kemunculan query yang selanjutnya disebut pattern ke dalam string yang lebih panjang. String matching dirumuskan dengan  x = x [0....m-1] (1)  dan y = y [0.....n-1] (2). dimana : x = pattern m = panjang pattern y = Teks n = Panjang teks [3]. Algoritma String Matching adalah algoritma yang dapat digunakan untuk penyelesaian masalah pencocokan string , secara garis besar algoritma string matching dibedan menjadi 3 bagian berdasarkan arah pencocokan string , yaitu : a. Arah pembacaan dari kiri ke kanan.
Algoritma  yang termasuk kategori ini adalah Brute Force , Levenshtein Distance, Morris dan Pratt (yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt). b. 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 . c. Arah  pencarian  yang  ditentukan  program.  Algoritma  yang  termasuk  kategori  ini  adalah  algoritma Colussi , Crochemore-Perrin.

## 2.4 Torbo Boyer More
Turbo Boyer Moore adalah sebuah variasi dari algoritma Boyer-Moore. Bila dibandingkan dengan algoritma Boyer- Moore ,  algoritma  ini  membutuhkan  ruang  lebih  tapi  tidak  memerlukan  pemrosesan  ekstra.  Ruang  ekstra  yang diperlukan berguna untuk mengingat faktor dari teks yang cocok dengan akhiran dari string yang dicari selama attempt terakir dan hanya jika good-suffix shift dilakukan [3]. Teknik pencocokan string menggunakan algoritma turbo boyer moore mempunyai dua keunggulan, Yaitu memungkinkan untuk melompati faktor dari teks tersebut dan mengijinkan sebuah pergeseran turbo. Perpindahan yang dilakukan pada turbo boyer moore ketika proses pencarian string akan berbeda  dengan  proses  yang  dilakukan  pada  algoritma Boyer-moore .  Perpindahan  ini  disebut  dengan  perpindahan turbo. Perpindahan turbo ini hanya dapat dilakukan jika pada saat melakukan perbandingan pada saat tersebut, panjang dari  karakter  yang  sama  antara pattern dan  teks  lebih  besar  dari  panjang  dari  karakter  sama  yang  telah  disimpan sebelumnya di variabel faktor pengingat. Akibatnya, proses pencarian akan menjadi lebih singkat Adapun Prinsip kerja dari algoritma Turbo-BM adalah sebagai berikut : a. Algoritma Boyer-moore mulai mencocokkan pattern pada awal teks.
b. Algoritma  Turbo  Boyer-Moore mengijinkan  suatu  pergeseran  turbo yang dapat  terjadi  bila attempt yang  sedang dilakukan, akhiran dari pattern yang cocok dengan teks yang lebih pendek dari bagian teks yang diingat dari attempt sebelumnya.
c. Dari kanan ke kiri, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter pada teks yang bersesuaian sampai salah satu kondisi berikut dipenuhi
1. Di pattern dan di teks yang dibandingkan tidak cocok ( missmatch ). 2. Semua karakter di pattern cocok. Algoritma akan memberitahukan penemuan di posisi ini.
3. Algoritma kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix dan penggeseran bad-character , Lalu mengulangi langkah 2 sampai pattern berada di ujung teks
4. Setiap karakter yang ada di pattern diberi nilai sesuai dengn ukuran jauhnya karakter tersebut dari karakter paling akhir dari pattern dan untuk karakter yang tidak terdapat didalam pattern akan diberi nilai yang sama yaitu panjang dari pattern yang dimasukkan .

## 2.5 Batak Toba
Suku  Batak  merupakan  etnis  keenam  terbesar  di  Indonesia  sesudah  Jawa,  Sunda,  Tionghoa-Indonesia,  Melayu  dan Madura. Pada waktu itu penduduk Indonesia sudah ada sebanyak 237.641.326 jiwa. Suku Batak terdiri atas enam sub- suku yaitu Angkola dan Mandailing di sebelah selatan, Toba di pusat, Dairi/Pakpak di sebelah Barat-laut, Karo di sebelah Utara, dan Simalungun di sebelah Timur-laut Orang Batak Toba terutama hidup dari pertanian. Berabad-abad lamanya mereka mengusahakan pertanian sawah dengan pengairan terpadu maka tidak heran kalau orang Batak Toba berdiam di lembah-lembah  dan  sekitar  Danau  Toba  sebab  disana  ada  cukup  air  untuk  persawahan.  Kondisi  geografis  lembah
membuat mereka hidup dalam ruang yang terbatas dan terisolasi. Komunitas-komunitas ini hidup dalam ikatan keluarga yang kuat [5].

## 3. HASIL DAN PEMBAHASAN
Analisa masalah yang terdapat pada penelitian ini yaitu jumlah marga etnis batak yang banyak berdasarkan pembagiannya dan  belum  banyak  penyedia  informasi  mengenai marga  etnis  batak  menyebabkan  masyarakat  umum  kesulitaan untuk mencari informasi mengenai marga etnis batak. Maka untuk mengatasi permasalah tersebut merancang aplikasi Marga Etnis Batak (MEB)  Berbasis Web . Aplikasi ini dirancang menggunakan bahasa pemrograman PHP dengan alat bantu editor notepad++. Database sebagai  media  penyimpanan  data  yang  digunakan  pada  penelitian  ini  adalah database MySQL . Pada aplikasi Marga Etnis Batak (MEB) Berbasis Web tentunya akan disimpan data Marga Etnis Batak (MEB) yang sangat banyak, agar dapat meminimalisir waktu yang dibutuhkan dalam proses pencarian informasi mengenai data Marga  Etnis  Batak  (MEB)    pada  aplikasi  yang  dirancang  diterapkan  algoritma turbo  boyer  moore .  Diterapkannya algoritma turbo boyer moore pada aplikasi Marga Etnis Batak (MEB) Berbasis Web yang dirancang diharapkan dapat mempermudah untuk menemukan hasil pencarian Marga Etnis Batak (MEB). Adapun kelebihan aplikasi Marga Etnis Batak (MEB) Berbasis Web yang dibangun pada penelitian ini yaitu dapat diakses oleh masyarakat umun atau user di berbagai tempat dengan menggunakan internet sehingga penggunaan aplikasi ini tidak terbatas dengan jarak atau lokasi. Adapun daftar- daftar marga dalam adat batak Toba adalah sebanyak 88 marga

## 3.1  Implementasi Algoritma Turbo Boyer Moore
Fase pencarian dalam algoritma Turbo Boyer Moore , proses yang dilakukan hampir sama dengan fase pencarian pada Algoritma Boyer Moore . Yang membedakan adalah adanya variabel yang berfungsi untuk menampung nilai pergeseran apabila pada putaran sebelumnya nilai yang diambil untuk pergeseran berasal dari tabel good suffix shift . Nilai ini nantinya akan digunakan sebagai nilai yang mungkin digunakan untuk pergeseran pattern. Fase inisialisasi pada algoritma ini sama dengan fase inisialisasi pada algoritma Boyer Moore , yaitu mempunyai kompleksitas waktu dan ruang sebesar O(n + σ) dengan σadalah besar ruang alfabet. Sedangkan pada fase pencocokan, algoritma ini mempunyai kompleksitas waktu sebesar O(m) dengan jumlah pencocokan karakter pada algoritma ini adalah 2m . Implementasi  algoritma turbo  boyer  moore pada  aplikasi  Marga  Etnis  Batak  (MEB)  Berbasis  Web  digunakan untuk mencari etnis batak. Sebagai contoh penyelesaian masalah pencarian yang  dilakukan pada penelitian ini penulis menggunakan “ Marbun ” sebagai pattern dan “P omparan Toga Marbun ” sebagai text .
Tabel 2. BmBc dan BmGs Index 0 1 2 3 4 5 Pattern M A R B U N BmBc 5 4 3 2 1 0 BmGs 5 5 5 5 5 1 Tabel 3. Pergeseran I
P O  M  P  A  R  A  N  T  O  G  A    M  A  R  B  U  N

## M  A  R  B  U  N
Terlihat perbedaan pada index R : a. Geser BmBc (R) – m + ( index bawah + 1) = 3 – 6 + 6 = 3 b. BmGs [5] = 1 Maka geser pattern sebesar 3 langkah (nilai maksimal dari kedua perhitungan)
Tabel 4. Pergeseran II P  O  M  P  A  R  A  N

## T  O  G  A    M  A  R  B  U  N

## M  A  R  B  U  N
Terlihat perbedaan pada index Spasi : a. Geser BmBc ( Spasi ) – m + ( index bawah + 1) = 6 – 6 + 6 = 6 b. BmGs [5] = 1 Maka geser pattern sebesar 6 (nilai maksimal dari kedua perhitungan)
Tabel 5. Pergeseran III P  O  M  P  A  R  A  N T  O  G  A M  A  R  B  U  N M  A  R  B  U  N
Terlihat perbedaan pada index M : a. Geser BmBc ( M ) – m + ( index bawah + 1) = 5 – 6 + 6 = 5 b. BmGs [5] = 1 Maka geser pattern sebesar 5 (nilai maksimal dari kedua perhitungan)
Tabel 6. Pergeseran IV

## P  O  M  P  A  R  A  N    T  O  G  A M  A  R  B  U  N
M  A  R  B  U  N
Pada  pergeseran  IV  terlihat  semua  karakter pattern memiliki  persamaan  dengan  karakter text, maka  pergeseran diberhentikan.

## 3.2 Perancangan Aplikasi
Perancangan sistem merupakan gambaran proses kegiatan yang akan diterapkan dalam sebuah sistem dan menjelaskan kebutuhan yang diperlukan sistem agar sistem dapat berjalan dengan baik. Tahap-tahap pemodelan dalam analisa sistem menggunakan UML (Unified Modeling Language) pada penelitian ini yaitu Use Case Diagram, Activity Diagram , dan Sequence Diagram . a. Use Case Diagram Use case diagram merupakan konstruksi untuk mendeskripsikan  hubungan-hubungan yang terjadi antar aktor dengan aktivitas  yang  terdapat  pada  sistem.  Sasaran  pemodelan use  case  diagram di  antaranya  adalah  mendefinisikan kebutuhan  fungsional  dan  operasional  sistem  dengan  mendefinisikan  skenario  penggunaan  sistem  yang  akan dibangun.

## Gambar 1. Use Case Diagram
b. Activity Diagram Activity  diagram merupakan  state  diagram  khusus,  dimana  sebagian  besar  state  adalah  action  dan  sebagian  besar transisi di-trigger oleh selesainya state sebelumnya ( internal processing ).
Gambar 2. Activity Diagram
c. Sequence Diagram
Sequence Diagram adalah diagram interaksi yang menekankan pada pengiriman pesan dalam suatu waktu tertentu. Sequence diagram biasa digunakan untuk menggambarkan skenario atau rangkaian langkah-langkah yang dilakukan sebagai respons dari sebuah event untuk menghasilkan output tertentu.

## 4. KESIMPULAN
Berdasarkan hasil penelitian yang dilakukan oleh penulis maka dapat diuraikan beberapa kesimpulan  yaitu berdasarkan struktur pembagian etnis batak toba dapat mempermudah pembaca untuk mencari struktur atau daftars-daftar marga etnis batak toba. Serta penerapan algoritma turbo boyer moore pada aplikasi Marga Etnis Batak berbsis web yang dirancang dapat mempermudah proses pencocokan string dalam mencari Marga Etnis Batak (MEB). Dan aplikasi Marga Etnis Batak (MEB) pada penelitian ini dirancang menggunakan bahasa pemrograman HTML, PHP, dan CSS dan dapat diakses oleh masyarakat umum atau user  diberbagai tempat dengan menggunakan internet sehingga penggunaan aplikasi ini tidak terbatas jarak atau lokasi .

## REFERENCES
[1] https://id.wikipedia.org/wiki.Suku _Batak,.
[2] Dkk.Vina Sagita, “Studi Perbandingan Implementasi Algorita Boyer Moore,Turbo Boyer Mooredan TUnned Boyer Moore Dalam Pencaruan String ”,vol. Vil.IV,2013.
[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] Togar Nainggolan, Batak Toba : Sejarah dan Transformasi Religi, Bina Media Perintis, Medan, 2012.
[6] P. P. Widodo, Menggunakan UML untuk Memodelkan Analisis & Desain Sistem Berorientasi. Bandung: Informatika, 2011.
[7] R. A. S and M. Shalahuddin, Rekayasa Perangkat Lunak (Terstruktur dan Berorientasi Objek). Bandung: Informatika, 2014.