Analisis Algoritma Approximate String Matching Pada Fitur Autocorrect dalam Pencarian Data

Arie Satia Dharma; Joko Banjarnahor; Okta Nainggolan; Yulianty Sihombing

Arie Satia Dharma Institut Teknologi Del
Joko Banjarnahor Institut Teknologi Del
Okta Nainggolan Institut Teknologi Del
Yulianty Sihombing Institut Teknologi Del

Keywords: Mesin Pencari; Autocorrect; Levenshtein Algorithm; Hamming Distance Algorithm

Abstract

Abstract— In searching, users will receive results that do not match what they want if they enter the wrong word on the search engine. There is an usefull applications for perform correction when searching a word that autocorrect feature. There are many string matching algorithms that can be used to apply the autocorrect feature. This paper applied a Levenshtein Distance algorithm and Hamming Distance algorithm on a prototipe of search engine. The performance of search engine is measured by using a comparison parameter that is running time, memory usage and accuracy. Keywords used in searching data is done by applying test scenarios on the scope of character substitution operation. Results obtained from this research is in terms of memory consumption and running time algorithm Hamming Distance is better than the Levenshtein Distance whereas in terms of accuracy Levenshtein algorithm is better than the Hamming Distance.

Keywords— Search Engine; Autocorrect; Levenshtein Distance Algorithm; Hamming Distance Algorithm.

Intisari—Dalam melakukan pencarian, pengguna akan menerima hasil yang tidak sesuai dengan yang diinginkan jika memasukkan kata yang salah pada mesin pencari. Terdapat sebuah aplikasi yang berguna untuk melakukan pengkoreksian kata ketika melakukan pencarian yaitu fitur autocorrect. Ada banyak string matching yang dapat digunakan untuk menerapkan fitur autocorrect. Dalam penelitian ini digunakan algoritma Levenshtein Distance dan algoritma Hamming Distance pada prototipe mesin pencari. Kinerja mesin pencari diukur dengan menggunakan parameter pembanding yaitu running time, memory usage, dan accuracy. Kata kunci yang digunakan dalam pencarian data dilakukan dengan menerapkan skenario uji pada lingkup operasi penggantian karakter. Hasil yang diperoleh dari penelitian ini adalah dalam hal pemakaian memori dan running time Algoritma Hamming Distance lebih baik dari pada Levenshtein Distance sedangkan dalam hal akurasi algoritma Levenshtein lebih baik dari pada Hamming Distance.

Kata Kunci— Mesin Pencari; Autocorrect; Levenshtein Algorithm; Hamming Distance Algorithm.