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 )
  • Menghapus N ( ROLANDON -> ROLANDO )

Dengan menggunakan representasi matriks dapat dilihat pada tabel di bawah.

Pada Tabel 1, elemen baris 1 kolom 1 (M[1,1]) adalah jumlah operasi yang diperlukan untuk mengubah substring dari kata ROLANDO yang diambil mulai dari karakter awal sebanyak 1 (R) ke substring dari kata RONALDINHO yang diambil mulai dari karakter awal sebanyak 1 (R). Sementara M[3,5] adalah jumlah operasi antara ROL (substring yang diambil mulai dari karakter awal sebanyak 3) dengan RONAL (substring yang diambil mulai dari karakter awal sebanyak 5). Hal ini disimpulkan bahwa elemen M[p,q] adalah jumlah operasi antara substring kata pertama yang diambil mulai dari awal sebanyak p dengan substring kata kedua yang diambil dari awal sebanyak q. Dengan demikian, matriks pada Tabel diatas dapat diisi seperti pada Tabel dibawah ini.

Elemen terakhir (kanan bawah) adalah elemen yang nilainya menyatakan jarak kedua string yang dibandingkan. Lalu untuk menghitung nilai kemiripan menggunakan rumus:

Sim = Similarity/ nilai kemiripan
Dis = jarak Levenshtein
MaxLength = nilai string terpanjang
Jika nilai similarity adalah 1, maka kedua string yang dibandingkan sama. Di lain hal, jika similarity 0, maka kedua string yang dibandingkan tidak sama.

3 thoughts on “Levenshtein Distance”

Tinggalkan Balasan