Beberapa waktu yang lalu *biar kedengeran kaya lagi dongeng* ada orang yang bertanya tentang suatu algoritma yang bisa mendeteksi kemiripan dari dokumen atau lebih dikenal dengan dokumen similaritas, dalam hati sebenernya jujur saya belum pernah denger algoritma apa yang cocok buat itu *maklum waktu jadi mahasiswa jarang banget gaul ke perpustakaan* tapi karna keingintahuan dan ke-soktahuan yang tinggi *untung waktu itu nannya-nya lewat BBM jadi bisa searching dulu* akhirnya ketemu lah suatu algoritma yang disebut bisa mendeteksi atau memeriksa kemiripan sebuah objek (dalam hal ini bisa string kata, dan dokumen) , dan karena pengen ngoprek algoritma ini akhirnya nyemplung lah untuk ngoprek algoritma ini dari model yang sederhana aja (string kata), kita akan memulai dari yang kecil dulu (huruf -> kata -> kalimat -> paragraf -> dokumen).
Sebelum kita mulai membahas algoritma ini, kita harus kenalan dulu sama algoritma levenshtein karena ada pepatah mengatakan “tak kenal maka tak sayang” :p.
Algoritma ini lebih dikenal dengan Levenshtein Distance yaitu algoritma yang mengukur kesamaan antara 2 string, nantinya akan lebih dikenal dengan string sumber (s) dengan string target (t), contoh :
- Jika (s) = “coba”, dan (t) = “coba” ==> maka Levenshtein(s,t) = 0, karena kedua string tersebut sama / tidak ada perbedaan
- Jika (s) =”coba”, dan (t) = “cona” ==> maka Levenstein(s,t) =1 , karena adanya perbedaan antara kedua string tersebut di huruf yang ketiga yakni ‘b’ dengan ‘n’.
Algoritma ini ditemukan oleh Vladimir Losifovich Levenshtein yang merupakan ilmuan dari Rusia pada tahun 1965.
Gambar 1. Vladimir Losifovich Levenshtein
Algoritma ini telah digunakan untuk :
- Spell Checking
- Speech recognition
- DNA Analysis
- Plagiarism Detection
Perlu diketahui cara kerja dari algoritma ini termasuk yang agak rumit karena mensimulasikannya melalui model matriks, tapi tenang aja itu kan model matematikanya *pusing dah* untuk penerapan di teknologinya ada sekitar 7 langkah yang bisa kita implementasi lewat bahasa pemrograman (bahasa pemrogramannya bebas).
Langkah-langkahnya sebagai berikut :
- Langkah pertama
- Set variabel N yang menyimpan panjang string source (S)
- Set variabel M yang menyimpan panjang string target (T)
- Jika N = 0 atau M=0 maka exit
- Buat matriks ber-ordo [0 – N][0 – M]
- Langkah Kedua
- Inisialisasi baris 0 – N
- Inisialisasi kolom 0 – M
- Langkah Ketiga
- Periksa setiap karakter dari string S (looping dari 1 ke N -> variabel i)
- Langkah Keempat
- Periksa setiap karakter dari string T (looping dari 1 ke M -> variabel j)
- Langkah Kelima
- jika S[i] = T[i] –>cost = 0
- jika S[i] != T[i] –> cost = 1
- Langkah Keenam
- set value d[i,j] yang diambil dari minimum jumlah :
- d[i-1,j] + 1
- d[i,j-1] + 1
- d[i-1,j-1] + cost
- set value d[i,j] yang diambil dari minimum jumlah :
- Langkah Ketujuh
- Setelah langkah 3,4,5,6 selesai (tidak ada looping lagi), hasilnya akan ketemu di element d[N,M]
Contoh kasus untuk mengimplementasikan algoritma diatas adalah sebagai berikut :
Jika ada 2 buah kata x = BARU dengan y = BATU, berapakah perbedaan huruf dari kedua kata tersebut.
ekspektasi dari outputnya adalah 1 kata,
Langkah 1 & 2
| B | A | R | U | ||
| 0 | 1 | 2 | 3 | 4 | |
| B | 1 | ||||
| A | 2 | ||||
| T | 3 | ||||
| U | 4 |
Langkah 3 – 6, ketika i = 1, dan j = 1
*x[i] = B , y[i] = B, cost = 0
kemudian ambil nilai minimal dari
- d[i-1,j] + 1 ===> d[1-1,1] + 1 = 1
- d[i,j-1] + 1 ===> d[1,1-1] + 1 = 2
- d[i-1,j-1] + cost ===> d[1-1,1-1] + 0 = 0
| B | A | R | U | ||
| 0 | 1 | 2 | 3 | 4 | |
| B | 1 | 0 | |||
| A | 2 | ||||
| T | 3 | ||||
| U | 4 |
Lakukan langkah tersebut sampai akhirnya mendapatkan hasil.
| B | A | R | U | ||
| 0 | 1 | 2 | 3 | 4 | |
| B | 1 | 0 | 1 | 2 | 3 |
| A | 2 | 1 | 0 | 1 | 2 |
| T | 3 | 2 | 1 | 1 | 2 |
| U | 4 | 3 | 2 | 2 | 1 |
Dari sini bisa kelihatan perbedaan antara kedua kata :
x : BARU
y: BATU
adalah 1 huruf,
Mudah bukan? :p
silahkan mencoba 🙂
Referensi :
ijalandhika 
makasih banyak broo!