## Institut Riset dan Publikasi Indonesia (IRPI)
MALCOM: Indonesian Journal of Machine Learning and Computer Science
Journal Homepage: https://journal.irpi.or.id/index.php/malcom Vol. 4 Iss. 1 January 2024, pp: 282-292 ISSN(P): 2797-2313 | ISSN(E): 2775-8575

## Virtual Robot Using Knuth Morris Pratt Method

## Robot Virtual Menggunakan Metode Knuth Morris Pratt
Ahamd Nizar 1* , Prihastuti Harsani 2 , Irma Anggraeni 3
1,2,3 Program Studi Ilmu Komputer, Universitas Pakuan, Indonesia
E-Mail: 1 ahmad065118238@unpak.ac.id,
2 prihastuti.harsani@unpak.ac.id, 3 irmairhamna@unpak.ac.id
Received Oct 20th 2023; Revised Dec 05th 2023; Accepted Jan 15th 2024 Corresponding Author: Ahamd Nizar

## Abstract
Human work is now starting to be replaced by robots that are specially programmed to do various jobs. Among the current bot developments, a virtual assistant based on artificial intelligence has been created. Currently, society is entering the era of Society 5.0 where society must integrate technology into life in a more intelligent, humane and sustainable way, but unfortunately there are many factors that make society unable to utilize technology in everyday life, such as cost factors, devices that do not capable, and accessibility is difficult so that Indonesian society is still very far from the Society 5.0 era. So from this research, we designed a virtual assistant robot system with Natural Language Processing technology based on Artificial Intelligence to help people in their daily activities. This robot system was created on a website platform so that it is not like Google Assistant which requires quite large storage memory on the device and also requires an operating system that supports Google Assistant. This robot system does not require memory storage on the device and also supports all operating systems so that any device/gadget can use it. This Virtual Robot was created using the Knuth Morris Pratt (KMP) Algorithm. The results of this virtual robot can receive commands to create alarms, weather, YouTube, and search on Google.
Keyword: Artificial Intelligence, Knuth Morris Pratt, Pencocokan Pola, Preprocessing, Robot Virtual, Virtual.

## Abstrak
Pekerjaan manusia saat ini mulai dapat tergantikan oleh robot yang di program khusus untuk melakukan berbagai pekerjaan. Di  antara  perkembangan  bot  yang  ada  saat  ini,  tercipta  sebuah  virtual  assistant  berbasis  kecerdasan  buatan.  Saat  ini masyarakat  saat  ini  sedang  memasuki  era  Society  5.0  dimana  masyarakat  harus  mengintegrasikan  teknologi  ke  dalam kehidupan dengan cara yang lebih cerdas, manusiawi dan perkelanjutan namun sayangnya banyak faktor yang membuat masyarakat tidak dapat memanfaatkan teknologi dalam kehidupan sehari-hari seperti faktor biaya, perangkat yang tidak mumpuni, dan aksesbilitas yang sulit sehingga membuat masyarakat indonesia masih sangat jauh dalam era Society 5.0 . Maka dari penelitian ini merancang sebuah sistem robot virtual assistant dengan teknologi Natural Language Processing berbasis  Artificial  Intelligence  untuk  membantu  seseorang  dalam  kegiatan  sehari-harinya.  Sistem  robot  ini  dibuat  pada platform website sehingga tidak seperti Google Assistant yang membutuhkan memori penyimpanan pada perangkat yang cukup  besar  dan  juga  membutuhkan  sistem  operasi  yang  men-support  google  assistant  tersebut.  Sistem  robot  ini  tidak membutuhkan penyimpanan memori pada perangkat dan juga support dengan semua sistem operasi sehingga device/gadget manapun dapat menggunakannya. Robot Virtual ini dibuat dengan menggunakan Algoritma Knuth Morris  Pratt (KMP). Hasil robot virtual ini dapat menerima perintah untuk membuat alarm, cuaca, Youtube, serta pencarian di Google.
Kata Kunci: Kecerdasan Buatan, Knuth Morris Pratt, Pencocokan Pola, Preprocessing, Robot Virtual, Virtual.

## 1. PENDAHULUAN
Abad ke-21 ini membuat kehidupan manusia sangat bergantung dengan internet dan barang elektronik. Keduanya  menjadi  hal  penting  yang  dibutuhkan  untuk  membantu  dalam  kehidupan  sehari-hari.  Berbagai pekerjaan  manusia  mulai  dapat  tergantikan  oleh  hadirnya  bot  yang  di  program  khusus  untuk  melakukan berbagai  pekerjaan.  Dengan AI  atau  kecerdasan  buatan,  bot  ini  dapat  berpikir  layaknya  manusia.  Di  antara perkembangan bot yang ada saat ini, tercipta sebuah virtual assistant berbasis kecerdasan buatan atau Artificial Intelligence (AI). Berdasarkan penelitian Organisation For Economic CoOperation And Development (OECD) menyebutkan  indonesia  berada  diposisi  3  dengan  negara  yang  paling  buruk keseimbangan  antara  kerja  dan
kehidupan  dengan  angka  mencapai  14,3%  [1].  Berdasarkan  hal  tersebut,  Masyarakat  Indonesia  memiliki masalah dengan pengoptimalan waktu. Selain dari itu masyarakat saat ini sedang memasuki era Society 5.0 dimana  masyarakat  harus  mengintegrasikan  teknologi  ke  dalam  kehidupan  dengan  cara  yang  lebih  cerdas, manusiawi  dan  perkelanjutan  [2]  namun  sayangnya  banyak  faktor  yang  membuat  masyarakat  tidak  dapat memanfaatkan teknologi dalam kehidupan sehari-hari seperti faktor biaya, device/gadget yang tidak mumpuni, dan aksesbilitas yang sulit sehingga membuat masyarakat indonesia masih sangat jauh dalam era Society 5.0 . Maka  dari  itu  peneliti  ingin  merancang  sebuah  sistem  robot  virtual  assistant  dengan  teknologi  Natural Language  Processing  berbasis  Artificial  Intelligence  untuk  membantu  seseorang  dalam  kegiatan  sehari- harinya,  Sehingga  seluruh  masyarakat  dapat  mengitegrasikan  kehidupan  berteknologi  tanpa  hambatan  dari faktor yang dijelaskan sebelumnya karena sistem robot ini akan dibuat pada platform website sehingga tidak seperti Google Assistant yang membutuhkan memori penyimpanan pada perangkat yang cukup besar dan juga membutuhkan sistem operasi yang men-support google assistant tersebut. Sistem robot ini tidak membutuhkan penyimpanan memori pada perangkat dan juga support dengan semua sistem operasi sehingga device/gadget manapun  dapat  menggunakannya.  Penelitian  ini  diharapakan  membuat  era  Society  5.0  ini  dapat  berjalan dengan  baik  dan  penelitian  ini  menjadi  referensi  untuk  perkembangan  penelitian-penelitian  berbasis  AI selanjutnya.
Penelitian  serupa  yang  memanfaatkan  teknologi  NLP  juga  pernah  dilakukan  sebelumnya.  Penelitian oleh Dadan (2019) membangun sebuah robot humanoid yang dapat merespon pertanyaan dari pengguna dan berkomunikasi  dua  arah,  robot  tersebut  dapat  mengenali  suara  seseorang  menggunakan  Mel-Frequency Cepstrum Coeficients (MFCC). Penelitian selanjutnya oleh Nuraini (2020) yang membangun sebuah sistem Kamus  Digital  dengan  metode  KMP  sebagai  algoritma  dalam  mencocokan  kata  dari  bahasa  Indonesia  ke bahasa Aceh begitupun sebaliknya, kata yang hendak dicari persamaannya maka akan mencari kecocokan kata tersebut  dalam  bahasa  daerah.  Terakhir  penelitian  oleh  Gandi  (2022)  dengan  membuat  penelitian  tentang Analisis Ketetapan Respon Chatbot Menggunakan Algoritma Boyer Moore dengan algoritma Boyer Moore ini membandingkan pola mulai dari kanan ke kiri jika terjadi ketidakcocokan pola string maka pola akan bergerak ke arah kiri, gerakan ini akan memberikan informasi berapa banyak pergeseran untuk mencocokan karakter yang sesuai dengan pola awal. Beberapa penelitian sebelumnya memiliki kekurangan diantara lain algoritma yang  digunakan  kurang  maksimal  karena  diperlukan  algoritma  yang  dapat  melewatkan  perbandingan- perbandingan sehingga tidak melakukan hal yang sama berulang-ulang dan juga kurangnya aksesbilitas yang dikarenakan  pengoperasiannya  masih  menggunakan  chat/text  sehingga  tidak  optimal  dalam  proses mendapatkan informasi.
Penelitian ini akan menggunakan metode Knuth Morris Pratt (KMP). Metode KMP merupakan salah satu algoritma pencocokan pattern/pola. Pada penelitian ini KMP akan digunakan pada data input oleh user yang sebelumnya telah melalui preprocessing pada proses Text Mining yang akan dicocokan dengan pattern yang tersimpan pada server, apabila terjadi nilai kecocokan yang tinggi antara input dengan pattern maka sistem akan  melakukan  aksi  yang  sesuai  dengan  patternnya.  Sebaliknya  apabila  terjadi  ketidakcocokan  maka  data input tersebut akan melakukan pengambilan informasi tertentu demi menentukan dimana langkah selanjutnya pencarian dilakukan. Metode pencarian KMP bekerja dengan melewatkan perbandingan- perbandingan yang tidak  diperlukan  untuk  menghindari  besarnya  jumlah  perbandingan  [3].  Kemudian  sistem  yang  akan  dibuat dapat terintegrasi oleh suara sehingga memudahkan aksesbilitas dan mengoptimalkan multitasking.

## 2. BAHAN DAN METODE
Penelitian  ini  membutuhkan  beberapa  tahapan  yang  butuh  dilakukan,  tahapan-tahapan  berikut diantaranya  adalah  tahap  analisis  permasalahan,  pengumpulan  data,  preprocessing,  menentukan  pattern  dan menghitung border function, mencocokan pattern dan teks dengan Algoritma Knuth Morris Pratt, perancangan karakter  2D  Live,  pembuatan  website  serta  tahapan  evaluasi  sistem  dengan  Blackbox  dan  juga  Confusion Matriks. Tahap pengumpulan data dilakukan dengan cara menyebarkan kuisioner kepada masyarakat sekitar, data tersebut akan menjadi perintah-perintah yang akan diujikan pada sistem. Garis besar dari tahapan yang akan  dilakukan  dalam  penelitian  ini  dapat  dilihat  pada  gambar  1.  Kemudian  gambaran flowchart dari  alur sistem Robot Virtual Personal Assistant untuk pengguna dapat dilihat pada gambar 2.
Pengguna dapat memilih untuk memberikan perintah ingin melalui suara atau teks karena sistem dapat menerima kedua inputan tersebut. Setelah pengguna mengirimkan perintah kepada robot tersebut, maka proses pertama yang akan sistem lakukan adalah membersihkan inputan atau perintah tersebut menggunakan tahap preprocessing oleh text mining agar perintah dapat dimengerti oleh sistem. Kemudian hasil input tersebut akan berupa string yang mana string tersebut akan mulai di proses oleh Knuth Morris Pratt untuk dicocokan dengan pattern yang telah di pahami oleh sistem, yang mana pattern tersebut sebelumnya pun telah dihitung terlebih dahulu Border Functionnya, dengan Border function inilah pattern akan melakukan pencocokan dengan string dan melakukan pergeseran apabila terjadi ketidakcocokan [3]. Apabila pattern ditemukan dalam string tersebut maka proses selanjutnya sistem akan memberikan output berupa aksi sesuai dengan perintah kepada pengguna.
Gambar 1. Metode Penelitian

## 2.1. Proses Data Input
Proses menangkap data yang diinputkan melalui voice akan menggunakan sebuah service yang terdapat pada  Javascript  yang  dinamakan  SpeechRecognition.  Speech  recognition  atau  pengenalan  pola  suara  juga dikenal  sebagai  Automatic  Speech  Recognition  (ASR)  merupakan  sistem  yang  digunakan  untuk  mengenali perintah  kata  dari  suara  manusia  dan  kemudian  diterjemahkan  menjadi  suatu  data  yang  dimengerti  oleh komputer [4]. Sistem speech recognition dapat diartikan juga sebagai proses mengubah inputan suara ke media lain misalnya teks oleh karena itu speech recognition terkadang disebut sebagai speech-to-text (STT). Service Speech Recognition milik javascript ini akan menghasilkan sebuah transcript, lalu transcript tersebut yang akan masuk ke input dari sistem ini dan masuk ke proses Preprocessing.

## 2.2. Preprocessing
Data  yang  direkam  oleh  sistem  dari  user  biasanya  merupakan  data  yang  tidak  terstruktur  dan  masih banyak noise pada data tersebut. Hal ini dapat mempengaruhi hasil analisis sistem. Oleh karena itu, dibutuhkan tahap preprocessing agar data yang diinputkan menjadi terstruktur sehingga dapat diproses oleh sistem. Pada gambar tahap preprocessing terdiri dari tahap case folding, tokenizing, normalisasi dan filtering.

## 2.3. Algoritma Knuth-Morris-Pratt (KMP)
Algoritma Knuth-Morris-Pratt (KMP) adalah salah satu algoritma pencocokan pola. Metode pencarian KMP  bekerja  dengan  melewatkan  perbandingan-perbandingan  yang  tidak  diperlukan  untuk  menghindari besarnya jumlah perbandingan, dengan demikian mencapai waktu berjalan yang optimal dalam kasus terburuk ( worst case ) pencocokan pola algoritma harus memeriksa semua karakter teks dan semua karakter dari pola setidaknya  sekali  [5].  KMP  ini  berjalan  kiri  ke  kanan  dan  akan  mencocokan  karakter  per  karakter pattern , dengan karakter di teks yang bersesuaian sampai salah satu kondisi berikut terpenuhi adalah karakter di pattern dan  diteks  yang  dibandingkan  tidak  cocok  ( mismatch )  serta  semua  karakter  di pattern cocok.  Kemudian algoritma akan memberitahu penemuan posisi ini. Algoritma kemudian menggeser pattern berdasarkan table next , lalu menghitung langkah berikutnya sampai pattern berada diujung teks.
Berikut persamaan algoritma Knuth-Morris-Pratt
O(n+m) (1)
Dengan: O = waktu optimal N = string M = pattern
2.4. Penerapan Algoritma 2.4.1.  Algoritma Fase Pra-Pencarian Berikut ini adalah algoritma fase pra-pencarian.
Fase pra-pencarian function longestPrefix(str) { var table = new Array(str.length); var maxPrefix = 0; table[0] = 0;
for (var i = 1; i < str.length; i++) { while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) { maxPrefix = table[maxPrefix - 1]; } if (str.charAt(maxPrefix) === str.charAt(i)) { maxPrefix++; } table[i] = maxPrefix; } return table; }

## 2.4.2.  Algoritma Fase Pencarian
Berikut ini adalah algoritma fase pencarian.
Fase pencarian function kmpMatching(str, pattern) { var prefixes = longestPrefix(pattern); var matches = []; var j = 0; var i = 0; while (i < str.length) { if (str.charAt(i) === pattern.charAt(j)) { i++; j++; } if (j === pattern.length) { matches.push(i-j); j = prefixes[j-1]; } else if (str.charAt(i) !== pattern.charAt(j)) { if (j !== 0) { j = prefixes[j-1]; } else { i++; } } } return matches; };

## 2.4.1.  Beberapa Perintah Algoritma Lain
Langkah awal sebelum mencocokan Pattern dengan Teks yang telah melalui tahap Preprocessing adalah menghitung Border Function dari pattern. Border f(j) didefinisikan sebagai ukuran awal terpanjang dari P yang merupakan akhiran dari P[1..j]. Border Function f(j)=j+1 akan dijabarkan dalam Tabel berikut: Keterangan:
j =  indeks P[j]   =  Pattern dari indeks ke j=0 sampai dengan j=n f(j)   =  Fungsi pinggiran dari indeks ke j=0 sampai dengan j=n dan diawali dengan f(0) = 0 langkah penghitungan f(j):
1. f(0) = 0
J 0 1 2 3 4 P[j] a l a r m F(j) 0
2. f(1) , melalui pencocokan P[j](0) dengan Pnext[j](n)  P[j]0 = a
P[j]1 = l P[j]0 ≠ P[j]1 > tidak ada kecocokan
Jika tidak ada kecocokan maka nilai f(j) = 0 .  Jadi nilai f(1) =  0
J 0 1 2 3 4 P[j] a l a r m F(j) 0 0
3. f(2) , melalui pencocokan P[j](0) dengan Pnext[j](n)  P[j]0 = a
P[j]2 = a P[j]0 = P[j]1 > terjadi kecocokan
Jika ada kecocokan maka nilai f(j) = j + 1 .  Jadi nilai f(2) = 0 + 1 = 1
J 0 1 2 3 4 P[j] a l a r m F(j) 0 0 1
4. f(1) , melalui pencocokan P[j](0) dengan Pnext[j](n)  P[j]1 = l
P[j]3 = r
P[j]1 ≠ P[j]3
> tidak ada kecocokan
Jika tidak ada kecocokan maka P[j] kembali lagi ke 0 P[j]0 ≠ P[j]3 => a  ≠  r Maka nilai f(j) = 0 .  Jadi nilai f(3) =  0
J 0 1 2 3 4 P[j] a l a r m F(j) 0 0 1 0
5. f(1) , melalui pencocokan P[j](0) dengan Pnext[j](n)  P[j]0 = a
P[j]4 = m
P[j]0 ≠ P[j]4 > tidak ada kecocokan
Jika tidak ada kecocokan maka nilai f(j) = 0 .  Jadi nilai f(4) =  0
J 0 1 2 3 4 P[j] a l a r m F(j) 0 0 1 0 0
Perhitungan pergeseran pada algoritma ini adalah sebagai berikut, bila terjadi ketidakcocokan pada saat pattern(P) sejajar dengan teks(T) [i..i + n – 1], dapat diasumsikan ketidakcocokan pertama terjadi di antara T [I + j] dan P [j], dengan 0 < j < n . Berarti, T [i..i + j – 1] = P [0..j – 1] dan a = T [I +j] tidak sama dengan b = P[j]. Ketika proses pergeseran, sangat memungkinkan bila ada sebuah awalan v dari pattern akan sama dengan sebagian akhiran u dari sebagian teks. Sehingga pattern dapat melakukan pergeseran agar awalan v tersebut sejajar dengan akhiran dari u.
Text:
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13  14 15 t B U A T A L A R M J A M 9
Pattern:
p A L A R M f(j) 0 0 1 0 0
1. Langkah pertama : Seperti yang dijelaskan pada sebelumnya proses perhitungan Knuth Morris Pratt  akan  melakukan  perbandingan  dari  ujung  kiri  teks  dan  ujung  kiri  pattern  dimulai  dari indeks(i) ke 0 sampai dengan I <= T(m) . Pada langkah pertama ini karena T[0] ≠ P[0] dan j = 0 maka lakukan pergeseran sebanyak 1 kali ke kanan.
I 0 1 2 3 4 5 6 7 8 9 t B U A T A L A R M p A L A R M
2. Langkah kedua :Pada langkah kedua ini karena T[1] ≠ P[0] dan j = 0 maka lakukan pergeseran sebanyak 1 kali ke kanan.
i 0 1 2 3 4 5 6 7 8 9 t B U A T A L A R M p A L A R M
3. Langkah ketiga: Pada langkah ketiga ini karena T[2] == P[0] maka T[j] + 1 dan P[j] + 1 i 0 1 2 3 4 5 6 7 8 9 t B U A T A L A R M p A L A R M
4. Langkah keempat :Pada langkah keempat ini karena T[3] ≠ P[1] maka lakukan pergeseran dengan rumus : I – f(j) = 1 – 0 = 1 . jadi geser pattern 1 kali ke kanan.
i 0 1 2 3 4 5 6 7 8 9 t B U A T A L A R M p A L A R M
5. Langkah kelima : Pada langkah kelima ini karena T[3] ≠ P[0] . maka lakukan pergeseran sebanyak 1 kali ke kanan.
i 0 1 2 3 4 5 6 7 8 9 t B U A T A L A R M p A L A R M 6. Langkah keenam : Pada langkah keenam ini karena T[5] == P[0] maka T[j] + 1 dan P[j] + 1 i 0 1 2 3 4 5 6 7 8 9 t B U A T A L A R M p A L A R M
7. Hingga T[9] == P[4] pattern sama dengan teks oleh karena hal tersebut Algoritma Knuth Morris Pratt akan menyimpan informasi ini.
i 0 1 2 3 4 5 6 7 8 9 t B U A T A L A R M p A L A R M
Perbandingan  berhasil  antara  pattern  dan  teks  berhasil  ditemukan  apabila  kondisi  I  masih  I  <=T(m) sehingga  proses  perbandingan  masih  di  lakukan  sampai  kondisi  I  >  T(m)  .  karena  sudah  melakukan perbandingan  sampai  akhir  pattern  maka  border  function  yang  diambil  adalah  yang  terakhir  f(j)  =  0, perbandingan dilakukan kembali ke pattern index ke 0 dan T[11] ≠ P[0] maka perbandingan akan bergeser terus hingga ke akhir teks sampai dengan I > T(m) dan perbandingan selesai.

## 2.5. Persiapan API
Proses untuk mengerjakan perintah yang diberikan oleh user yaitu dengan menghubungkan sistem ke beberapa  situs  api  kemudian  sistem  akan  melakukan  pertukaran  data.  API  itu  sendiri  adalah  antarmuka pemrosesan aplikasi antara server web dan peramban web [6]. Seperti pada gambar 3, sistem menghubungkan ke web api google untuk melakukan pertukaran data youtube dan google, selain menghubungkan ke api google, sistem juga menghubungkan ke api openweather untuk melakukan pertukaran data cuaca.
Gambar 3. Desain Live2D

## 2.6. Tahap Pembuatan Karakter Live2D
Aplikasi robot ini akan memiliki sebuah karakter Live2D sebagai mascot dari robot itu sendiri yang berperan  membuat  kesan  UI  dari  tampilan  sistem  lebih  interaktif  dan  menarik.  Animasi  Live2D  ini  sendiri dirancang  menggunakan  software  Reality  dan  juga  Alight  Motion  setelah  animasi  terbuat  maka  animasi tersebut  akan  dimasukan  kedalam  sistem  dan  animasi  akan  bergerak  menyesuaikan  dengan  voice  yang dikeluarkan oleh sistem.

## 2.7. Evaluasi
Proses evaluasi merupakan proses yang dilakukan untuk menguji kesesuaian program dengan hasil yang direncanakan sekaligus mengukur performa dari sistem tersebut. Proses evaluasi ini akan dilakukan dengan blackbox dan Confusion Matriks, dimana UAT akan menguji sistem dengan tujuan memastikan bahwa sistem robot  mampu  mengerjakan  perintah  sesuai  yang  diminta  oleh  user,  kemudian  confusion  matriks  digunakan untuk menghitung seberapa baik sebuah sistem dapat memprediksi label dari sebuah data yang telah diinputkan [7].

## 3. HASIL DAN PEMBAHASAN
Berikut  ini  merupakan  hasil  jadi  dan  hasil  evaluasi  dari  Aplikasi  Robot  Virtual  Personal  Assistant Menggunakan Metode Knuth Morris Pratt, yang meliputi hasil dari perancangan, proses pencocokan dengan Knuth Morris Pratt, hasil desain Live2D, tampilan proses output, dan juga tampilan dari website sistem ini. Berikut adalah penjelasannya.

## 3.1. Hasil Preprocessing
Proses ketika user menginputkan perintah dengan suara ataupun teks data tersebut akan ditangkap oleh sistem kemudian masuk kedalam textbox yang ada pada UI. Setelah sebelumnya dijelaskan bahwa sistem akan menggunakan SpeechRecognition dalam mengubah inputan suara ke media lain misalnya teks [4]. Data suara yang  ditangkap  akan  menghasil  sebuah  transript  berupa  string  kata-kata  seperti  gambar  4.  Kemudian  nilai transcript kata tersebut akan kita tangkap sebagai data perintah kemudian data tersebut akan kita olah pada proses selanjutnya.
Gambar 4. Hasil Preprocessing

## 3.2. Knuth Morris Pratt
Proses  Algoritma  Knuth  Morris  Pratt  ini  berjalan  kiri  ke  kanan  dan  akan  mencocokan  karakter  per karakter  pattern,  dengan  karakter  di  teks  yang  bersesuaian  sampai  salah  satu  kondisi  terpenuhi,  kemudian algoritma akan memberitahu penemuan posisi ini. Algoritma kemudian menggeser pattern berdasarkan table next, lalu menghitung langkah berikutnya sampai pattern berada diujung teks. Setelah data perintah didapatkan sebelumnya maka perintah tersebut akan masuk ke algoritma KMP dan akan memberikan nilai output berupa nilai/string yang matching. Berikut adalah tampilan ketika data perintah dilakukan proses KMP maka sistem akan memberitahu dimana pattern ditemukan.

## 3.3. Hasil API
Data perintah yang berhasil dinyatakan terdapat match maka perintah tersebut akan dicocokan dengan fungsi-fungsi  yang  ada pada sistem  kemudian  fungsi  tersebut  akan melakukan  pertukaran  data  dengan  API yang  sesuai  kemudian  hasil  data  dari  API  tersebut  akan  ditampilkan  oleh  sistem  robot  ini.  Gambar  6  ini merupakan  tampilan  ketika  user  memerintahkan  untuk  mencarikan  sebuah  video  atau  lagu  yang  ada  di Youtube, robot akan menampilkan hasil video yang sesuai berdasarkan apa yang user mau. Seperti contoh pada gambar  6,  sistem  menemukan  kecocokan  pada  perintah  mencari  video  youtube  maka  sistem  menampilkan video-video yang sesuai dengan apa yang user ingin lihat.
Gambar 6. Hasil API

## 3.4. Evaluasi
Pada  Penelitian  ini  menggunakan  2  metode  pengujian  yaitu  Blackbox  dan  confusion  matrix  sebagai berikut.
1. Pengujian Blackbox
Pengujian blackbox ini dilakukan untuk menentukan apakah sebuah output yang diberikan sistem telah sesuai  dengan  apa  yang  perintah  yang  diminta  oleh  user,  lalu  memastikan  apakah  keyword  yang ditentukan  sudah  benar  sesuai  dan  jelas  atau  belum.  Kemudian  pada  uji  blackbox  ini  juga  menguji seberapa banyak perintah yang berhasil dikerjakan oleh sistem dan seberapa banyak perintah yang gagal ataupun tidak sesuai dikerjakan oleh sistem. Adapun nilai Knuth Morris Pratt (KMP) yang didapatkan pada sebuah perintah yang berhasil dinyatakan matching untuk melihat kapan terjadinya matching pada nilai string.
Tabel 1. Pengujian Blackbox No. Perintah Keyword Knuth Morris Pratt Output Status 1. Halo Yuki Halo String = 1|2|3|4|5|6|7|8|9| Keyword = 0|0|0|0 Matching[i] = [1|2||3|4] Robot menyapa User Berhasil 2. Apa yang dapat kamu lakukan ? Dapat String = 1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19 |20|21|22|23|24|25|26|27 Keyword = 0|0|0|0 Matching[i] = [10|11|12|13] Robot menjelaskan apa  yang  dapat dilakukan Berhasil 3. Tampilkan informasi cuaca Cuaca String = 1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19 |20|21|22|23|24|25| Keyword = 0|0|0|1|0 Matching[i] = [21|22|23|24|25] Robot menampilkan informasi suhu, range  tempratur, keterangan  cuaca, kecepatan angin saat itu Berhasil 4. Carikan video di Youtube Youtube String = 1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19 |20|21|22|23|24 Keyword = 0|0|0|0|0|0|0 Matching[i] = [18|19|20|21|22|23|24] Robot menampilkan video  yang  ingin dicari user di youtube Berhasil 5 Buatkan Alarm! Alarm String = 1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| Keyword = 0|0|1|0|0 Matching[i] = [10|11|12|13|14] Robot membuatkan alarm pengingat dari kegiatan  yang  di input user Berhasil
No. Perintah Keyword Knuth Morris Pratt Output Status 6 Cari informasi di Google Google String = 1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19 |20|21 Keyword = 0|0|0|1|0|0 Matching[i] = [16|17|18|19|20|21] Robot  mengirim data  ke  search engine google dan tampilan sistem otomatis akan pergi ke google 7. Kerjakan PR saya - String = 1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| Robot akan menyampaikan permintaan  maaf karena perintah tidak dapat dikerjakan Berhasil
Dari hasil pengujian Blackbox yang dilakukan terhadap sistem didapatkan hasil sebagai berikut:
1) Dari  40  responden  yang  dimintai  data  berupa  kalimat  perintah  dihasilkan  70  perintah  yang berbeda.
2) Dari 70 perintah yang diujikan ke robot terdapat 5 perintah yang gagal dikerjakan oleh robot, 56 perintah yang berhasil dikerjakan dengan baik.
3) Dari  5  perintah  yang  tidak  terjawab  dengan  baik  dikarenakan  tidak  adanya  kata  kunci  yang dimengerti oleh robot. Hal ini terjadi karena beberapa faktor yaitu terjadi kesalahan pengetikan ataupun penyebutan perintah. Adapun 9 perintah yang hasilnya tidak sesuai dengan perintah yang dikerjakan  karena  adanya  ambigu  ketika  menyebutkan  perintah.  Pada  gambar  7  menunjukan persetase pengujian menggunakan metode Blackbox.
2. Nilai Confusion Metrik
Confusion matrix memberikan informasi hasil klasifikasi yang dilakukan oleh sistem (model) dengan hasil klasifikasi sebenarnya. Pada uji blackbox sebelumnya kita mendapat data berapa banyak perintah yang  berhasil  dikerjakan,  perintah  yang  berhasil  dikerjakan  akan  disebut  True-Positif,  kemudian perintah yang  dijawab  akan  tetapi  tidak  sesuai  hasilnya  maka  akan  disebut  sebagai  False-positif  dan True-negatif.  Terakhir  perintah  yang  sama  sekali  tidak  dapat  dikerjakan  akan  disebut  False-negatif. Kemudian nilai-nilai dari hasil uji sebelumnya akan dimasukkan ke dalam tabel confusion matriks untuk ditentukan nilai akurasi, presisi dan recall ditunjukkan pada gambar 8. Nilai Confusion Matriks dapat dilihat pada tabel 2.
Tabel 2. Nilai Confusion Matriks Positif Negatif True 56 3 False 6 5
Gambar 7. Grafik Blackbox
Gambar 8. Nilai Evaluasi

## 4. KESIMPULAN
Berdasarkan  hasil  dari  penelitian  yang  dilakukan  dalam  membuat  aplikasi  robot  virtual  personal assistant  dengan  algoritma  Knuth  Morris  Pratt  ini,  maka  didapatkan  bahwa  hasil  dari  pengujian  User Acceptence Testing (UAT) yaitu mencocokan antara perintah dengan pattern memiliki status berhasil karena output yang diberikan berupa perintah yang dikerjakan telah sesuai yang diharapkan pada perancangan awal,
80% 13% 7% 0% 20% 40% 60% 80% 100% Berhasil Tidak Sesuai Gagal BlackBox 84,0% 90,3% 91,0% 80,0% 82,0% 84,0% 86,0% 88,0% 90,0% 92,0% Akurasi Presisi Recall Persentase Evaluasi
kemudian Algoritma KMP pun berhasil menemukan pattern pada string sesuai dengan index array pada string. Perhitungan Confusion Matriks yang telah dilakukan sebelumnya pada sistem ini 70 perintah yang diujikan kepada robot 56 perintah berhasil dikerjakan dengan baik kemudian terdapat 5 perintah yang gagal dikerjakan dan 9 perintah yang kurang sesuai perintah. Berdasarkan perhitungan Confusion Matriks sistem robot virtual ini memiliki nilai Akurasi sebesar 84% hal ini bisa dibilang baik karena lebih dari 80%. Adapun nilai lainnya yaitu  Presisi  90,3%  dan  juga  Recall  91%  membuktikan  bahwa  robot  virtual  ini  sudah  cukup  baik  untuk digunakan.

## REFERENSI
[1] Aldis, “Analisis Ketetapan Respon Chatbot dengan Algoritma Boyer Moore,” Jurnal Sistemasi, vol. 11, no. 1, pp. 207-223, 2022.
[2] Enemsi,  Pembangunan  Chatbot  Seputar  Informasi  Pendaftaran  Mahasiswa  Baru  Sebagai  Virtual Assistant Unit Admisi Promosi, Yogyakarta: Universitas Kristen Duta Wacana, 2021.
[3] Fahrizal, “Implementasi Voice Recognition Berbasis Machine Learning,” EduElektrika, vol. 11, no. 1, pp. 50-62, 2022.
[4] Febriyanti, “Implementasi Blackbox Testing Pada Sisem Informasi Manajemen Dosen,” Jurnal Ilmiah Teknologi, vol. 2, no. 3, pp. 535-544, 2021.
[5] Harahap, “Aplikasi Chatbot Berbasis Web Menggunakan Metode Dialogflow,” JICOM, vol. 1, no. 1, pp. 6- 13, 2020.
[6] Irfan, “Analisis Penerapan Algoritma Pada Preprocessing Data,” Jurnal Cyberarea, vol. 2, no. 5, pp. 1- 8, 2022.
[7] Jesselyn, “Nester-Wadah Rekreasi dan Kebugaran,” Jurnal Stupa, vol. 2, no. 1, pp. 283-296, 2020.
[8] Khairan,  “Penerapan  algoritma  knuth  morris  pratt  pada  fitur  pencarian  definisi  istilah  standar operasional prosedur (sop),” Jurnal Pendidikan Teknologi, vol. 3, no. 1, pp. 26-40, 2019.
[9] Mumtahanah,  “Aplikasi  Pengarsipan  Dokumen  Menggunakan  Metode  String  Matching,”  Jurnal Informatika, vol. 5, no. 1, pp. 9-16, 2019.
[10] Nastiti, “Kesiapan Pendidikan Indonesia Menghadapi era society 5.0,” Jurnal Kajian Teknologi, vol. 5, no. 1, pp. 61-66, 2019.
[11] Nursobah, “Penerapan algorima pencarian kmp dalam sistem informasi perpustakaan smk ti pratama,”
[12] Jurnal Sebatik, vol. 1, no. 5, pp. 112-115, 2019.
[13] Oktarini, Web programming, Yogyakarta: Graha Ilmu, 2019.
[14] Prasetyo,  “Implementasi  Natural  Language  Processing  Dalam  Pembuatan  Chatbot  Pada  Program Information Technology Universitas Surabaya,” Jurnal Teknika, vol. 10, no. 2, pp. 114-121, 2021.
[15] Rio, “Aplikasi Pendeteksi Plagiat Terhadap Karya Tulis Menggunakan Algoritma Knuth Morris Pratt,”
[16] Jurnal Coding, vol. 4, no. 1, pp. 33-44, 2017.
[17] Sa'ad, Otodidak Web Programming: Membuat Website Edutainment, Jakarta: Elex Media Komputindo, 2020.
[18] Soofastaei, Virtual Assistant, Australia: IntechOpen, 2021.
[19] Tsamarah, “Perancangan Animasi Video Pembelajaran Menggunakan Live2D,” Jurnal Sains, vol. 2, no. 3, pp. 369-374, 2022.
[20] Vajjala,  Practical  NLP:  Acomprehensive  Guide  to  building  real-world  NLP  systems,  California:  O Reilly Media, 2020.
[21] Yulian, Buku ajar text mining, Sidoarjo: UMSIDA Press, 2020.
[22] Zekson, “Implementasi Algoritma String Matching Pencarian Kata Dari Makna Rambu Lalu lintas,” Jurnal Sistem Informasi Kaputama (JSIK), vol. 2, no. 1, pp. 101-106, 2018.