Analisis kinerja algoritma pelacakan string dengan toleransi kesalahan

Abstract

Pelacakan string banyak diperlukan pada pemrosesan string misalriya untuk pengeditan teks. Terkadang pelacakan string tidak berhasil dilakukan, salah satu penyebabnya adalah adanya kesalahan ejaan. Untuk itu perlu dilakukan pelacakan string yang tidak eksak atau pelacakan dengan toleransi kesalahan. Agar pelacakan string memiliki kinerja yang baik maka diperlukan metode yang tepat untuk digunakan dengan mempertimbangkan keefektifan algoritma dalam menemukan perkiraan kata yang cukup baik dan waktu proses yang cepat dalam menampilkan perkiraari kata tersebut. Dalam penelitian ini dilakukan perbandingan dua jenis algoritma pelacakan string dengan toleransi kesalahan, yaitu algoritma Wu-Manber (selanjutnya disebut algoritma WM) dan algoritma Pemrograman Dinamis (selanjutnya disebut algoritma DP). Perbandingan dilakukan untuk melihat efisiensi kedua jenis algoritma ditinjau dari keefektifannya dalam menampilkan perkiraan kata dan waktu proses yang diperiukan dalam menampilkan perkiraan kata. Pengujian dilakukan dengan menggunakan 3720 kata yang dijadikan kamus referensi dan direpresentasikan menggunakan struktur data trie. Proses yang dilakukan adalah membandingkan kata- kata pada file yang diperiksa dengan kata-kata yang terdapat pada struktur data trie. Jika kata terdapat pada kamus referensi struktur data trie, maka kata tersebut mempunyai ejaan yang benar. Jika tidak, maka dilakukan pencarian kata perkiraan pada kamus referensi struktur data trie dengan melakukan perhitungan jarak edit antara kata yang diperiksa terhadap kata yang terdapat pada struktur data trie menggunakan algoritma WM dan DP. Jarak edit yang dimaksud adalah jumlah minimal perbedaan antara dua string yang diakibatkan oleh operasi perubahan penggantian, penghapusan, penyisipan atau gabungan dari ketiganya. Hasil dari penelitian ini diperoleh bahwa algoritma WM dan DP keduanya memberikan kinerja yang sama bagusnya yaitu 100% terkoreksi untuk semua jenis kesalahan dan waktu proses algoritma WM kurang lebih 3 kali lebih cepat dibandingkan waktu proses algoritma DP.