Perbandingan Algoritma Knuth Morris Pratt dan Boyer Moore dalam Pencarian String pada File Teks Berbasis Android
No Thumbnail Available
Date
2018-09-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Pencarian string di dalam teks disebut juga dengan pencocokan string (string matching atau pattern matching), permasalahan pencarian string adalah untuk mencari beberapa karakter atau pattern dalam sejumlah besar teks. Contoh permasalahan yang dihadapi adalah dalam aplikasi text editor seperti Microsoft Word atau Notepad, dan dalam lingkup yang lebih besar lagi adalah pencarian di internet yang dilakukan oleh mesin pencari seperti Google, Yahoo!, dan Bing. Algoritma Knuth Morris Pratt merupakan algoritma yang menggunakan metode alami, yaitu pencarian string dari arah kiri ke kanan. Sedangkan, algoritma Boyer Moore merupakan algoritma yang melakukan pencarian string dari arah kanan ke kiri.
Penelitian ini dilakukan untuk mengetahui perbandingan algoritma Knuth Morris Pratt dan Boyer Moore dalam melakukan pencarian string pada file teks. Ada 5 file teks berjenis txt yang diuji coba untuk mencari 3 pattern yang berbeda. Pada penelitian, dikembangkan sebuah aplikasi berbasis Android untuk melakukan uji coba algoritma Knuth Morris Pratt dan Boyer Moore dalam mencari pattern tersebut pada setiap file teks. Berdasarkan penelitian, algoritma Boyer Moore lebih efisien dibanding algoritma Knuth Morris Pratt dengan perbandingan efisiensi algoritmanya adalah 2,9:1 iterasi per milidetik.
Description
Keywords
Pencarian string, Algoritma, Knuth Morris Pratt