Pemrograman DinamisMenengahFase D–FE1E5

Edit Distance (Levenshtein)

Edit Distance menghitung jumlah minimal operasi (sisip, hapus, ganti) untuk mengubah satu kata jadi kata lain. Dynamic Programming mengisi tabel: tiap sel = biaya termurah dari tiga tetangganya. Ini otak di balik autocorrect dan saran ejaan.

Contoh kasus

Autocorrect: mengukur seberapa mirip kata yang salah ketik dengan kandidat perbaikan untuk memilih yang paling dekat.

Silabus

Edit Distance menghitung jumlah minimal operasi sisip, hapus, atau ganti untuk mengubah satu kata menjadi kata lain.

Tujuan Belajar

·Memahami tiga operasi dasar: sisip, hapus, dan ganti huruf
·Menjelaskan cara tabel DP mengambil biaya termurah dari tetangga
·Menerapkan Edit Distance untuk mengukur kemiripan dua kata

Cara Kerja

·Buat tabel di mana baris dan kolom mewakili tiap huruf kedua kata
·Isi baris dan kolom pertama dengan biaya mengubah dari/ke kata kosong
·Bila dua huruf sama, salin nilai diagonal (tanpa biaya tambahan)
·Bila beda, ambil 1 + minimum dari sisip, hapus, atau ganti
·Nilai di pojok kanan bawah adalah jarak edit minimum

Prasyarat

·Tabel 2D (matriks)
·String

Contoh Nyata

·Autocorrect memilih koreksi paling mirip dengan kata yang salah ketik
·Fitur saran ejaan saat mengetik pesan di HP
·Mesin pencari menebak maksud saat kata kunci typo

Kompleksitas O(m x n) untuk panjang kata m dan n