Algoritma Levenshtein Distance / Edit Distance


Algoritma Levenshtein Distance / Edit Distance adalah salah satu algoritma yang digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai penentuan penentuan kata-kata usulan yang paling mendekati kata awal.
Fitur usulan dan juga auto koreksi biasanya sering terlihat pada mesin-mesin pencarian di internet. Sewaktu pengguna internet ingin mengetikkan sebuah kata misalnya “pegawai”, pada saat pengetikkan masih pada saat “pegaw”, mesin pencarian sudah memberikan usulan “pegawai” sebagai sebagai kata jawaban. Juga pada saat ternyata pengguna internet salah menulis “pefawai”, mesin pencarian juga melakukan auto koreksi, sehingga kata tersebut tetap dapat memberikan pencarian mengenai “pegawai”. Kedua fitur tersebut dapat dihitung dengan algoritma ini.



Diasumsikan ada 10 daftar kata yang akan dijadikan sebagai acuan
Kemudian akan diinputkan sebuah kata yang akan dicari usulannya
Maka tentukan 3 kata usulan yang paling mendekati inputan kata
Diasumsikan 10 kata tersebut adalah sebagai berikut:

Daftar Kata
film
karyawan
motor
mobil
pegawai
pelanggan
skor
sejarah
terima
tolak

Contoh daftar kata tersebut adalah sebagai berikut:


Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan kata yang akan dicari usulannya

2. Lakukan perulangan pada semua daftar kata
Lakukan proses perhitungan jarak antara kata inputan dengan kata pada daftar kata
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2a – 2h)

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Levenshtein untuk menampung data kata dan nilai jarak untuk kata tersebut. Deklarasi Class Levenshtein adalah sebagai berikut:

Memasuki perhitungan pada fungsi Hitung Jarak

2a. Jika input kata dan kata terpilih sama-sama kosong, maka tidak perlu menghitung jarak

2b. Jika selisih huruf antara input dan kata terpilih melebihi limit, maka tidak perlu menghitung jarak juga

2c. Lakukan konversi kata input dan kata terpilih menjadi huruf kecil semua

2d. Apabila kata input dan kata terpilih sama persis, maka nilai jaraknya adalah 0

2e. Inisialisasi matriks jarak 2 dimensi sebesar jumlah kata terpilih
Beri nilai awal pada matriks jarak dimensi ke 2, i dengan nilai i

2f. Lakukan perhitungan mulai dari huruf pertama sampai huruf terakhir pada kata input (poin 2f1 – 2f5)

2f1. beri nilai awal posisi sekarang dengan nilai i

2f2. Jika banyak huruf yang diganti lebih dari limit, maka nilai jarak pada posisi sekarang adalah nilai tertinggi (terburuk)

2f3. Lakukan perulangan pada setiap huruf ke i dari kata input
pada huruf-huruf pada posisi i – limit sampai kepada i + limit dari kata terpilih

2f3a. Jika huruf ke j antara kata input dan kata terpilih adalah sama,
maka nilainya adalah nilai terendah pada posisi ke j
Selain itu, cari nilai terendah dari 3 pilihan
antara nilai posisi terendah ke j, posisi terendah ke j – 1, dan posisi ke j – 1

2f3b. Jika nilai jarak yang ditemukan kurang dari limit,
maka beri nilai status untuk digunakan untuk perhitungan dibawah

2f4. Jika nilai i + limit kurang dari jumlah huruf pada kata terpilih,
maka nilai jarak pada posisi berikutnya adalah nilai tertinggi (terburuk)

2f5. Jika nilai status yang sudah didapatkan sebelumnya bernilai salah,
maka nilai pengembalian adalah nilai tertinggi (terburuk)

2g. Jika nilai terendah pada posisi ke [jumlah huruf pada kata terpilih] lebih dari limit,
maka nilai pengembalian adalah nilai tertinggi (terburuk)

2h. Nilai jawaban jarak adalah nilai pada indeks tertinggi pada matriks jarak

3. Urutkan jarak dari yang terendah sampai yang tertinggi

4. Ambil 3 kata dengan jarak terendah sebagai jawaban


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd60


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *