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.

2 responses to “Levenshtein Distance

  1. gan sory nh…… mw tnya gmn cra y ngtung matrik y, ane gak pham, mklum new bie…. krim lwat email y gan…..achmad.arif294@gmail.com

  2. gan saya juga mohon dikirimkan cara ngitung matrik dan masukin rumus contoh, ke email : susi_r_st@yahoo.co.id, thanks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s