Jelaskan Definisi dari Jarak Levenshtein

Jarak Levenshtein antara dua string  (yang panjangnya masing-masing  dan ) didapatkan dengan menghitung , yang didefinisikan sebagai

Dengan  dari string  adalah string dari semua kecuali karakter pertama dari , dan  adalah karakter ke- dari string , dengan  menandakan karakter pertama. Perhatikan bahwa elemen-elemen di  secara berurutan adalah penghapusan (dari  ke ), penyisipan, dan subtitusi. Definisi ini adalah salah bentuk definisi yang rekursif.