Levenshtein Distance

Levenshtein distance digunakan untuk mengukur nilai kesamaan atau kemiripan antara dua buah kata (string). Jarak Levenshtein diperoleh dengan mencari cara termudah untuk mengubah suatu string. Secara umum, operasi mengubah yang diperbolehkan untuk keperluan ini adalah:

  • memasukkan karakter ke dalam string,
  • menghapus sebuah karakter dari suatu string,
  • mengganti karakter string dengan karakter lain.

Untuk menghitung jarak, digunakan matriks (n+1) x (m+1) di mana n adalah panjang string s1 dan m adalah panjang string s2. Dua buah string yang akan digunakan sebagai contoh adalah RONALDINHO dengan ROLANDO. Jika dilihat sekilas, kedua string tersebut memiliki jarak 6. Berarti untuk mengubah string RONALDINHO menjadi ROLANDO diperlukan 6 operasi, yaitu:

  • Mensubtitusikan  N dengan L ( RONALDINHO -> ROLALDINHO )
  • Mensubtitusikan L dengan N ( ROLALDINHO -> ROLANDINHO )
  • Mensubtitusikan I dengan O ( ROLANDINHO -> ROLANDONHO )
  • Menghapus O ( ROLANDONHO -> ROLANDONH )
  • Menghapus H ( ROLANDONH -> ROLANDON )

Continue ReadingLevenshtein Distance