Apa itu Algoritma Levenshtein Distance? Berikut Definisinya

String metric merupakan matriks berbasis karakter atau tekstual yang dapat menghasilkan nilai kemiripan atau ketidakmiripan dari dua buah teks string untuk proses perbandingan dan penyamaan. 

String metric umumnya dipakai untuk deteksi kecurangan, analisa fingerprint, deteksi plagiarisme, analisis DNA dan RNA, data mining, dan lain-lain.

Salah satu algoritma yang didasarkan pada string metric adalah algoritma Levenshtein Distance.

Apakah itu? Simak artikel berikut.

Sumber gambar: pixabay.com

Daftar Isi

Pengertian Levenshtein Distance

Algoritma Levenshtein Distance, atau sering disebut dengan Edit Distance merupakan algoritma untuk mencari jumlah perbedaan antara dua buah string.

Algoritma ini ditemukan pada tahun 1965 oleh seorang ilmuwan Rusia bernama Vladimir Levenshtein.

Algoritma Levenshtein Distance pada dasarnya akan menghitung jumlah minimum dari upaya transformasi suatu string menjadi string lain. Transformasi ini meliputi penggantian, penghapusan, dan penyisipan.

Algoritma ini digunakan untuk mengoptimalkan pencarian string karena apabila dilakukan pencarian setiap kombinasi operasi-operasi string tersebut maka akan membutuhkan sumber daya yang besar dan tidak efektif.

Algoritma ini menggunakan matriks dua dimensi dalam perhitungan nilai jarak edit (edit distance).

Matriks tersebut akan berisi nilai berupa jumlah operasi penghapusan, penyisipan dan penukaran yang dibutuhkan dalam mengubah string sumber ke string target.

Operasi-Operasi pada Levenshtein Distance

Berikut adalah operasi-operasi yang terdapat pada algoritma Levenshtein Distance:

1. Operasi Penyisipan Karakter (Insertion)

Operasi penyisipan karakter ialah menambahkan karakter ke dalam suatu string.

Contohnya string ‘tdk’ menjadi string ‘tidak’, dilakukan penyisipan karakter ‘i’ dan 'a' di antara karakter akhir dan awal. Penyisipan tidak hanya bisa dilakukan di tengah string, namun bisa juga disisipkan di awal maupun disisipkan di akhir string.

2. Operasi Penghapusan Karakter (Deletion)

Operasi penghapusan karakter ialah proses menghapus karakter dari suatu string. 

Contohnya string ‘ashar’ karakter tengah dihilangkan sehingga menjadi string ‘asar’. Pada operasi ini dilakukan penghapusan karakter ‘h'.

3. Operasi Penukaran Karakter (Subtitution)

Operasi penukaran karakter merupakan operasi mengganti sebuah karakter dengan karakter lain. 

Contohnya penulis menuliskan string ‘kempes’ menjadi ‘kempis’. Dalam kasus ini karakter ‘e’ yang terdapat pada string d diubah dengan huruf ‘i’.

Langkah-Langkah Algoritma Levenshtein Distance

Rumus operasi penghapusan, penyisipan, dan penukaran karakter yang digunakan untuk mengisi nilai matriks pada Levenshtein Distance dapat dilihat pada gambar di bawah:

Adapun langkah-langkah algoritma Levenshtein distance dalam mendapatkan nilai edit distance adalah sebagai berikut:

Misalkan S = String sumber, dan T = String target

Langkah 1: Inisialisasi

a) Hitung panjang S dan T, misalkan m dan n

b) Buat matriks berukuran 0...m baris dan 0...n kolom

c) Inisialisasi baris pertama dengan 0...n

d) Inisialisasi kolom pertama dengan 0...m

Langkah 2: Proses

a) Periksa S[i] untuk 1 < i < n

b) Periksa T[j] untuk 1 < j < m

c) Jika S[i] = T[j], maka entrinya adalah nilai yang terletak pada tepat didiagonal atas sebelah kiri, yaitu d[i,j] = d[i-1,j-1]

d) Jika S[i] ≠ T[j], maka entrinya adalah d[i,j] minimum dari:

• Nilai yang terletak tepat diatasnya, ditambah satu, yaitu d[i,j-1]+1
• Nilai yang terletak tepat dikirinya, ditambah satu, yaitu d[i-1,j]+1 
• terletak pada tepat didiagonal atas sebelah kirinya, ditambah satu, yaitu d[i-1,j-1]+1

Langkah 3: Hasil entri matriks pada baris ke-i dan kolom ke j, yaitu d[i,j]

Langkah 2 diulang hingga entri d[m,n] ditemukan.

Penjelasan:

Langkah awal dari algoritma Levenshtein Distance, yaitu melakukan penyeleksian panjang kedua string terlebih dahulu. 

Jika salah satu atau kedua string merupakan string kosong, jalannya algoritma ini berhenti dan memberikan hasil edit distance yang bernilai nol atau panjang string yang tidak kosong.

Jika panjang string keduanya tidak nol, setiap string memiliki sebuah karakter terakhir, misalnya c1 dan c2. Misalnya bagian string pertama tanpa c1 adalah s1 dan bagian string kedua tanpa c2 adalah s2, dapat dikatakan penghitungan yang dilakukan adalah cara mentransformasikan s1+c1 menjadi s2+c2. 

Jika c1 sama dengan c2, dapat diberikan nilai cost 0 dan nilai edit distance-nya adalah nilai edit distance dari pentransformasian s1 menjadi s2. Jika c1 berbeda dengan c2, dibutuhkan pengubahan c1 menjadi c2 sehingga nilai cost-nya 1. Akibanya, nilai edit distance-nya adalah nilai edit distance dari pentransformasian s1 menjadi s2 ditambah 1. 

Kemungkinan lain adalah dengan menghapus c1 dan mengedit s1 menjadi s2+c2 sehingga nilai edit distance-nya dari pentransformasian s1 menjadi s2+c2 ditambah 1.

Begitu pula dengan penghapusan c2 dan mengedit s1+c1 menjadi s2. Dari kemungkinan-kemungkinan tersebut, dicarilah nilai minimal sebagai nilai edit distance.

Untuk lebih jelasnya, proses algoritma Levenshtein Distance dapat dilihat pada pseucode berikut:

Trivusi Ikatlah ilmu dengan menulis. Menebar manfaat dengan berbagi :)

Berbagi :