Algoritma Levenshtein Distance / Edit Distance 4

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:

Contoh daftar kata tersebut adalah sebagai berikut:

Dim daftarKata(9) As String
daftarKata(0) = "film"
daftarKata(1) = "karyawan"
daftarKata(2) = "motor"
daftarKata(3) = "mobil"
daftarKata(4) = "pegawai"
daftarKata(5) = "pelanggan"
daftarKata(6) = "skor"
daftarKata(7) = "sejarah"
daftarKata(8) = "terima"
daftarKata(9) = "tolak"

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan kata yang akan dicari usulannya

Console.WriteLine("Masukkan kata yang akan dicari usulannya: ")
Dim input As String = Console.ReadLine

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)

For i As Integer = 0 To daftarKata.Length - 1
	levenshtein(i) = New Levenshtein(daftarKata(i))
	levenshtein(i).jarak = levenshtein(i).HitungJarak(input, levenshtein(i).kata)
Next

* 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:

Public Class Levenshtein
    Implements IComparable(Of Levenshtein)
    Public kata As String
    Public jarak As Integer

    Public Sub New(ByVal kata As String)
        Me.kata = kata
        Me.jarak = 0
    End Sub

	. . .
End Class

Memasuki perhitungan pada fungsi Hitung Jarak

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

If input Is Nothing OrElse kataTerpilih Is Nothing Then
	Return Integer.MaxValue
End If

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

If Math.Abs(input.Length - kataTerpilih.Length) > limit Then
	Return Integer.MaxValue
End If

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

input = input.ToLower
kataTerpilih = kataTerpilih.ToLower

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

If input = kataTerpilih Then Return 0

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

Dim jarak(1, (panjangKataTerpilih + 2)) As Integer
For i = 0 To panjangKataTerpilih + 1
	jarak(1, i) = i
Next

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

jarak(posisiSekarang, 0) = i

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

If i - limit >= 1 Then
	jarak(posisiSekarang, i - limit - 1) = Integer.MaxValue
End If

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

If input.Substring(i - 1, 1) = kataTerpilih.Substring(j - 1, 1) Then
	jarak(posisiSekarang, j) = jarak(1 - posisiSekarang, j - 1)
Else
	Dim nilaiTerendah As Integer = Integer.MaxValue
	If nilaiTerendah > jarak(1 - posisiSekarang, j - 1) Then nilaiTerendah = jarak(1 - posisiSekarang, j - 1)
	If nilaiTerendah > jarak(1 - posisiSekarang, j) Then nilaiTerendah = jarak(1 - posisiSekarang, j)
	If nilaiTerendah > jarak(posisiSekarang, j - 1) Then nilaiTerendah = jarak(posisiSekarang, j - 1)
	jarak(posisiSekarang, j) = nilaiTerendah + 1
End If

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

If jarak(posisiSekarang, j) <= limit Then
	isNilaiJarakKurangDariLimit = True
End If

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

If i + limit <= panjangKataTerpilih Then
	jarak(posisiSekarang, i + limit + 1) = Integer.MaxValue
End If

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

If Not isNilaiJarakKurangDariLimit Then
	Return Integer.MaxValue
End If

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

If jarak(1 - posisiSekarang, panjangKataTerpilih) > limit Then
	Return Integer.MaxValue
End If

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

Return jarak(1 - posisiSekarang, panjangKataTerpilih)

3. Urutkan jarak dari yang terendah sampai yang tertinggi

Array.Sort(levenshtein)

4. Ambil 3 kata dengan jarak terendah sebagai jawaban

For i As Integer = 0 To 2
	Console.WriteLine("Usulan " & i + 1 & " dari kata " & input & " adalah " & levenshtein(i).kata.PadRight(10) & " dengan jarak " & levenshtein(i).jarak)
Next

Hasil akhir adalah: (klik untuk perbesar gambar)

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.