Studi Perbandingan Algoritma Pencarian String dalam Metode Approximate String Matching untuk Identifikasi Kesalahan Pengetikan Teks

Yeny Rochmawati, Retno Kusumaningrum

Abstract


Abstract. Error typing resulting in the change of standard words into non-standard words are often caused by misspelling. This can be addressed by developing a system to identify errors in typing. Approximate string matching is one method that is widely implemented to identify error typing by using several string search algorithms, i.e. Levenshtein Distance, Hamming Distance, Damerau Levenshtein Distance and Jaro Winkler Distance. However, there is no study that compares the performance of the four algorithms.  Therefore, this research aims to compare the performance between the four algorithms in order to identify which algorithm is the most accurate and precise in the search string based on various errors typing. Evaluation is performed by using users’ relevance judgments which produce the mean average precision (MAP) to determine the best algorithm. The result shows that Jaro Winkler Distance algorithm is the best in word-checking with 0.87 of MAP value when identifying the typing error of 50 incorrect words.

Keywords: Errors typing, Levenshtein, Hamming, Damerau Levenshtein, Jaro Winkler

Abstrak. Kesalahan pengetikan mengakibatkan kata baku berubah menjadi kata tidak baku karena ejaan yang digunakan tidak sesuai. Hal tersebut dapat ditangani dengan mengembangkan sistem untuk mengidentifikasi kesalahan pengetikan. Metode approximate string matching merupakan salah satu metode yang banyak diterapkan untuk mengidentifikasi kesalahan pengetikan dengan berbagai jenis algoritma pencarian string yaitu Levenshtein Distance, Hamming Distance, Damerau Levenshtein Distance dan Jaro Winkler Distance. Akan tetapi studi perbandingan kinerja dari keempat algoritma tersebut untuk Bahasa Indonesia belum pernah dilakukan. Oleh karena itu penelitian ini bertujuan untuk melakukan studi perbandingan kinerja dari keempat algoritma tersebut sehingga dapat diketahui algoritma mana yang lebih akurat dan tepat dalam pencarian string berdasarkan kesalahan penulisan yang bervariasi. Evaluasi yang dilakukan menggunakan user relevance judgement yang menghasilkan nilai mean average precision (MAP) untuk menentukan algoritma yang terbaik. Hasil penelitian terhadap 50 kata salah menunjukkan bahwa algoritma Jaro Winkler Distance terbaik dalam melakukan pengecekan kata dengan nilai MAP sebesar 0,87.

Kata Kunci: Kesalahan pengetikan, Levenshtein, Hamming, Damerau Levenshtein, Jaro Winkler


Full Text:

PDF

References


. Hamming, R.W., 1950. Error detecting and error correcting codes. Bell System Technical Journal, XXIX(2), pp.147-60.

. Khatami, S., 2013. Comparison and Improvement of Basic String Metrics for Surname Matching. Life Science Journal, X(5), pp.128-32.

. Kornain, A., Yansen, F., & Tinaliah, T. 2014. Penerapan Algoritma Jaro-Winkler Distance untuk Sistem Pendeteksi Plagiarisme pada Dokumen Teks Berbahasa Indonesia. Jurnal Ilmu Komputer dan Teknologi Informasi, pp.62-70.

. Luqman, 2009. Perancangan Program Aplikasi Pengoreksian Ejaan Bahasa Indonesia Berbasis Web. Jurnal Pengkajian dan Penerapan Teknik Informatika (JURNAL PETIR), II(1), pp.13-19.

. Mulyanto, A., 2010. Analisis Edit Distance Menggunakan Algoritma Dynamic Programming. Saintek, V(2).

. Pyriana, D.R., 2011. Program Aplikasi Editor Kata Bahasa Indonesia Menggunakan Metode Approximate String Matching dengan Algoritma Levenshtein Distance Berbasis Java. Skripsi. Malang: Universitas Brawijaya.

. Sagita, V. & Prasetiyowati, M.I., 2012. Studi Perbandingan Implementasi Algoritma Boyer-Moore, Turbo Boyer-Moore, dan Tuned Boyer-Moore dalam Pencarian String. Ultimatics, IV(1), pp.31-37.

. Setiadi, I., 2013. Damerau-Levenshtein Algorithm and Bayes Theorem for Spell Checker Optimization. Bandung: Institut Teknologi Bandung.

. Sutisna, U. & Adisantoso, J., 2010. Koreksi Ejaan Query Bahasa Indonesia Menggunakan Algoritma Damerau Levenshtein. Jurnal Ilmiah Ilmu Komputer, XV(2), pp.25-29.




DOI: https://doi.org/10.24002/jbi.v7i2.491

Refbacks

  • There are currently no refbacks.