## PENERAPAN ALGORITMA BOYER MOORE PADA POSTING TWITTER TMC POLDA METRO JAYA UNTUK MELAPORKAN KONDISI LALULINTAS DAN RUTE JALAN KOTA JAKARTA

## Rudi Setiawan
Program Studi Sistem Informasi, Fakultas Telematika, Universitas Trilogi, Jakarta Selatan +62-8192454119, Email: rudi@universitas-trilogi.ac.id

## Abstrak
Setiap  harinya  jutaan  tweets  di  share  oleh  berbagai  pengguna  Twitter  didunia, salah satunya tweets yang terdapat pada accountTwitter TMC Polda Metro Jaya, yang mana  informasinya  didapat  dari  pengguna  Twitter  yang  peduli  terhadap  kondisi lalulintas kota Jakarta. Dengan menggunakan algoritma Boyer-Moore yang merupakan algoritma  pencarian  string,  pada  data  tweets  TMC  Polda  Metro  Jaya  dilakukan pencarian  nama  jalan  atau  lokasi  beserta  kondisi  lalulintasnya,  kemudian  dilakukan visualisasi menggunakan peta Google Map, sehingga ketika user memilih  lokasi tujuan perjalanan dari suatu tempat ke tempat lainnya di kota Jakarta maka akan ditampil rute jalan beserta kondisi lalulintasnya berdasarkan data tweets yang telah dilaporkan pada hari tersebut. Berdasarkan hasil penelitian, pada sampel 1 hari percobaan ditanggal 17 November 2014 dengan jumlah data 232 tweets, didapat data tweets yang teridentifikasi kondisi  lalulintasnya  sebanyak  196  tweets  artinya  sebanyak  84,48%  tweets  dapat teridentifikasi  dan  yang  tidak  teridentifikasi  kondisi  lalulintasnya  sebanyak  15,52%. Penyebab  utama  dari  tidak  teridentifikasinya  kondisi  lalulintas  pada  data  tweets dikarenakan  pada  data  tweets  tersebut  tidak  melaporkan  kondisi  lalulintas  melainkan melaporkan  informasi  lain  seperti  kecelakaan,  kondisi  jalan  berlubang  dan  lain sebagainya.
Kata Kunci :  Algoritma Boyer-Moore, TMC Polda Metro Jaya, Twitter

## 1. PENDAHULUAN
Fenomena  jejaring  sosial  dan  situs microblogging mulai  dari Facebook, Twitter, LinkeIn, Path, Google+ dan lain sebagainya, kini semakin marak digunakan oleh  masyarakat  sebagai  sarana  berbagi  informasi.  Dengan  didukung  perangkat mobile dan teknologi jaringan nirkabel yang memadai, kini masyarakat dapat berbagi informasi kapan dan dimanapun mereka berada. Mengenai maraknya penggunaan situs microbloggingTwitter, pada penelitian yang dilakukan Rodiansyah (2012), dinyatakan bahwa pada pertengahan tahun 2010 Twitter memiliki lebih dari 106 juta pengguna diseluruh dunia dan terus meningkat setiap harinya sebanyak 300.000 pengguna, dan Twitter setiap harinya mendapatkan lebih    dari  3  juta request .  Dari  angka  tersebut  Indonesia  menjadi  negara  yang menduduki  peringkat 8 dalam mengakses situs Twitter . Twitter menerima tweets dari pengguna sebanyak 55 juta pesan setiap harinya. Dengan  adanya Big  Data yang  dimiliki  oleh Twitter, penulis  mencoba memanfaatkan  data tweets untuk  kemudian  diolah  menggunakan  algoritma Boyer Moore. Algoritma Boyer Moore digunakan untuk mengindentifikasi data tweets yang
melaporkan  tentang  kondisi  lalulintas  jalan  raya  di  kota  Jakarta,  untuk  kemudian dengan  bantuan Google  Maps kondisi  lalulintas  jalan  raya  akan  divisualisasikan kedalam peta lokasi perjalanan.

## 2. METODE PENELITIAN
Sistem  yang  dirancang  merupakan  sistem  yang  diharapkan  dapat  menemukan informasi  lalu  lintas  dari  posting Twitter yang  terdapat  pada accountTwitter TMC Polda  Metro  Jaya,  menggunakan  algoritma  pencocokan  string boyer  moore sebagai pengolah  kata  yang  terdapat  pada tweets untuk  menemukan  kondisi  lalulintas, kemudian  menggunakan GoogleMapsAPI untuk  menampilkan  rute  perjalanan  dari lokasi A ke lokasi B berdasarkan pilihan pengguna.

## 2.1 PENGUMPULAN DATA
Data  yang  dikumpulkan  merupakan  data tweet yang  terdapat  pada account  Twitter TMP Polda Metro Jaya, yang secara realtime didownload dengan memanfaatkan API search yang    disediakan    oleh Twitter .    Kemudian    data  yang  telah  didownload tersebut disimpan  kedalam database.  Data tweet yang  dikumpulkan  antara  lain : isi tweet , tanggal dan waktu tweet .

## 2.2 ARSITEKTUR SISTEM
Secara  umum  sistem  yang  dirancang  terdiri  dari  empat  bagian  diantaranya  adalah download  tweet (pengambilan  data), preprocessing    tweet ,    pencarian  kata  yang mencerminkan  kondisi  lalulintas  dan  visualisasi  rute  lalulintas  beserta  kondisi lalulintasnya. Adapun  desain  arsitektur  sistem  dapat  terlihat  pada gambar 1.

## Gambar 1. Rancangan Arsitektur Sistem

## 2.3 PERANCANGAN SISTEM
Secara garis besar sistem ini bertujuan melaporkan kondisi lalulintas berdasarkan data tweets dan menggunakan teknik pencocokan string dengan metode pencocokan string menggunakan algoritma boyer moore , kemudian hasilnya akan divisualisasikan dengan  bantuan Google  Map berdasarkan  rute  perjalanan  yang  telah  dipilih  oleh pengguna aplikasi. Gambar 2 memperlihatkan gambaran umum sistem.
Visualisasi rute dan kondisi LaLin Pencarian kata PreProcess tweet Download tweet
API search twitter
Data twitt Hasil download - Filtering - Casefolding Twitt bersih Pencarian kondisi lalin beserta nama jalan/lokasi menggunakan Algoritma Boyer Moore Database nama jalan & kondisi lalin informasi kondisi lalin beserta nama jalan/lokasi Google Map API koordinat lokasi rute perjalanan Visualisasi Google Map dan Kondisi Lalulintas Internet Server Twitter Download twitt respon request Data twitt Memilih rute perjalanan Database twitt Pencarian lokasi

## Gambar 2. Gambaran umum sistem
Cara  kerja  sistem  dimulai  dengan  mengambil  data tweets yang  tersimpan  di  server Twitter menggunakan bantuan API Search Twitter . Pada proses pengambilan data ini juga dilakukan pelabelan data. Kemudian data tersebut diproses untuk tahap persiapan ( preprocessing ) agar data siap  digunakan  untuk proses identifikasi. Hal ini dilakukan karena tidak semua data tweets tersebut dapat digunakan. Pada data preprocessing ini  dilakukan  pembersihan  data tweets dari  kata-kata  yang  tidak  digunakan  dan mengganti kata-kata tertentu dengan daftar  sinonim yang  sudah  ada.

## 3. HASIL DAN PEMBAHASAN
3.1 Twitter API Twitter merupakan  sebuah  web micro  blogging dimana  penggunanya  dapat mengekspresikan moment atau  ide  nya  kedalam  sebuah  teks,  foto  maupun  video. Jutaan tweets di share secara realtime setiap  harinya  dan Twitter menolong  anda dalam  membuat  dan  membagi  ide  dan  informasi  secara instant tanpa  ada  batasan. Gambar 3 merupakan contoh postingan Twitter .

## JURNAL INFORMATIKA Vol. 9, No. 1, Jan 2015
Untuk  dapat  menggunakan API  Twitter ,  pengguna  diwajibkan  login  di  alamat https://dev.Twitter.com untuk  mendapatkan  4  buah key berupa consumer  key, consumer  secret,  access  token dan access  token  secret yang  akan  digunakan sebagai  syarat authentication untuk  dapat  mengakses  data Twitter .  Gambar  4 merupakan source code untuk melakukan download tweets .
Gambar 4. Source code download tweetss
Pada  baris  kode  ke  26  dan  27  dari  gambar  4,  data  hasil  download tweets dimasukkan  kedalam  sebuah table yang  bernama tabletweets ,  data  yang  berada ditabel tweets tersebutlah yang nantinya akan diproses untuk mendapatkan kondisi lalu lintas dari setiap nama jalan atau lokasi yang telah dilaporkan oleh pengguna Twitter . Gambar 5 menunjukkan data tweets hasil download.
Gambar 5. Data tweets hasil download

## 3.2 Algoritma Boyer Moore
Algoritma Boyer  Moore dipublikasikan  oleh  Robert  S.  Boyer,dan  J.  Strother Moore  pada  tahun  1977.  Pencocokan  karakter  yang  dilakukan  menggunakan algoritma boyer  moore dimulai  dari  string  sebelah  kanan pattern .  Ide  di  balik algoritma ini ialah dengan memulai pencocokan karakter dari kanan, maka akan lebih banyak informasi yang didapat. Gambar 6, menunjukkan pseudocode algoritma Boyer Moore pada fase pencarian.
BOYER_MOORE_MATCHER (T, P)
procedure BoyerMooreSearch( input m, n : integer, input P : array[0..n-1] of char, input T : array[0..m-1] of char, output ketemu : array[0..m-1] of boolean )
Deklarasi:
i, j, shift, bmBcShift, bmGsShift: integer BmBc : array[0..255] of interger BmGs : array[0..n-1] of interger
Algoritma: preBmBc(n, P, BmBc) preBmGs(n, P, BmGs) i:=0 while (i<= m-n) do
j:=n-1 while (j >=0 n and T[i+j] = P[j]) do
j:=j-1 endwhile if(j < 0) then ketemu[i]:=true; endif bmBcShift:= BmBc[chartoint(T[i+j])]-n+j+1 bmGsShift:= BmGs[j] shift:= max(bmBcShift, bmGsShift)
i:= i+shift
Gambar 6. Pseudocode algoritma Boyer-Moore (Sumber: http://id.wikipedia.org)
Algoritma Boyer Moore termasuk algoritma string matching yang paling efisien dibandingkan  algoritma-algoritma string    matching lainnya  (Cormen  dkk.  1994). Karena  sifatnya  yang  efisien,  banyak  dikembangkan  algoritma string  matching dengan bertumpu pada konsep algoritma Boyer Moore , beberapa di antaranya adalah algoritma Turbo BM dan algoritma Quick Search . Adapun  langkah-langkah  pencarian  string  pada  algoritma  Boyer  Moore  sebagai berikut :
1. Pertama  diperlukan  2  tabel  dengan  pendekatan  Match  Heuristic  (MH)  dan Occurrence  Heuristic  (OH)  untuk  menentukan  jumlah  pergeseran  yang  akan dilakukan  pada  pattern  (P)  jika  ditemukan  karakter  yang  tidak  cocok  pada proses pencocokan terhadap karakter pada teks (S).
2. Jika  pada  proses  pembandingan  terdapat  ketidakcocokan  karakter  antara karakter pada P dan S, maka pergeseran dilakukan dengan melihat kedua tabel dengan nilai pergerseran paling besar yang dipilih.
3. Kemungkinan penyelesaian dalam melakukan pergeseran pada P  adalah  jika pada pencocokan sebelumnya tidak ada karakter yang cocok maka pergeseran dilakukan  dengan  melihat  nilai  pergeseran  pada  tabel  occurrence  heuristic. Jika  karakter  yang  sedang  dibandingkan  tidak  terdapat  pada  P  maka pergeseran  dilakukan  sebanyak  jumlah  karakter  yang  terdapat  pada  P,  tetapi jika  karakter  yang  tidak  cocok  tersebut  terdapat  pada  string  P,  maka pergeseran dilakukan berdasarkan tabel.
4. Jika karakter pada teks yang sedang dibandingkan cocok dengan karakter pada string  P,  maka  posisi  pengecekan  karakter  pada  P  dan  S  masing-masing bergeser  kekiri  1  posisi  dari  posisi  sebelumnya,  kemudian  lanjutkan  dengan pencocokan  pada  posisi  tersebut  dan  seterusnya,  kemudian  jika  terjadi ketidakcocokan  karakter  pada  P  dan  S,  maka  pergeseran  dilakukan  dengan melihat tabel match heuristic dan occurrence heuristic dimana nilai pergeseran yang terbesar yang akan dipilih dikurangi dengan jumlah karakter yang telah cocok.
5. Jika  semua  karakter  telah  cocok,  artinya  P  telah  ditemukan  didalam  S, selanjutnya geser pattern sebesar 1 karakter, lanjutkan sampai akhir pattern S.
3.3 Google Maps API Google  Maps  API ( Application  Programming  Interface )  merupakan  layanan gratis dari google  yang memungkinkan peta dunia berbentuk 2 dimensi maupun peta  dunia  2  dimensi  bercitra  satellit  dapat  ditampilkan  kedalam  browser.  Pada Google  Maps  API terdapat  file library yang  berbentuk JavaScript ,  penggunaan Google MapsAPI sangat memungkinkan untuk dilakukan penambahan fitur sesuai kebutuhan pengembang. Gambar  7  merupakan  pemanfaatan Google  Maps  API dalam  menampilkan visualisasi peta rute perjalanan yang telah dipilih oleh pengguna. Pada Gambar 7 terdapat kondisi lalulintas dari lokasi perjalanan yang dihasilkan dari data tweets yang di share oleh pengguna Twitter pada saat itu.

## Gambar 7. Visualisasi rute dan kondisi lalulintas

## 4. KESIMPULAN
1. Nama  jalan  atau  lokasi  yang  terdapat  didatabase,  yang  kemudian  dijadikan pattern pencarian pada algoritma Boyer Moore mampu ditemukan pada data tweets yang telah didownload  sehingga  kondisi  lalulintas  dari  nama  jalan  atau  lokasi  tersebut  dapat teridentifikasi.
2. Data tweets yang  tidak  teridentifikasi  kondisi  lalulintasnya,  umumnya  disebabkan karena pada data tidak mengandung informasi kondisi lalulintas melainkan informasi lainnya seperti kecelakaan, kondisi jalan yang berlubang dan lain sebagainya.
3. Aplikasi  yang  telah  dibuat  belum  mampu  memberikan  rute  alternative  perjalanan sehingga perlu dilakukan pengembangan lebih lanjut.

## DAFTAR PUSTAKA
Rodiyansyah,  2012, Klasifikasi  Posting  Twitter  Kemacetan  Lalu  Lintas  Kota  Bandung Menggunakan  Naive  Bayesian  Classification ,  Tesis,  Universitas  Gadjah  Mada, Yogyakarta.
Cormen,  Thomas.  H.,  Leiseson,  Charles.  E.,  Rivest,  Ronald.  L.,  1994, Algorithm . McGraw-Hill Book Company, North America. http://id.wikipedia.org/wiki/Algoritma_Boyer-Moore . 12 Agustus 2014.