Perbandingan Algoritma Edit Distance, Levenshtein Distance, Hamming Distance, Jaccard Similarity Dalam Mendeteksi String Matching

Sari

Saat sekarang ini dunia membutuhkan pencaraian yang cepat, tepat dan efisien. Pencarian yang dilakukan  Penulis tertarik untuk membandingkan algoritma string matching  karena belum ada yang membandingkan empat algoritma yaitu algoritma Edit Distance, Levenshtein, Hamming dan Jaccard similarity. Tujuan penulisan ini membandingkan  kecepatan akses 4 (empat) algoritma yaitu, algoritma Edit Distance, Levenstein Distance, Humming Distance,  dan Jaccard Similarity mana yang lebih cepat, tepat dengan tingkat error yang rendah, menentukan sililaritas dokumen,  dalam pencarian. Hal ini diakibatkan karena sering terjadi kesalahan pengetikan sehingga terjadi kesalahan ejaan. Kesalahan pengetikan ini biasanya  terjadi saat adalah, penghapusan, penambahan, pengantian  serta modofikasi data. Penulis mengunakan  data dari kamus besar bahasa Indonesia yang meliputi kata dasar, kata ber-awalan,  kata ber-akhiran, kata ber-imbuhan, kata sambung, kata depan, dan kata yang termasuk dalam kata bahasa baku.  Metode evaluasi yang dipakai dalam penelelitian ini adalah mAP bahasa pemograman yang digunakan adalah C++. Berdasarkan ujicoba yang dilakukan rata-rata waktu pencarian terhadap algorima Edit Distance = 47,55 ms, Levensthtein Distance = 13,125 ms, Hamming Distance = 14,25 ms, dan Jaccard similarity = 37,125 ms  Ini berarti Levenshtein Distance memiliki waktu pencarian tercepat.