Jelaskan Contoh dari Jarak Levenshtein

Sebagai contoh, jarak Levenshtein antara kata "kartun" dan kata "gantung" adalah 3, karena tiga pengeditan berikut mengubah satu kata ke kata yang lain, dan tidak ada cara untuk melakukannya dengan kurang dari tiga pengeditan:

kartun → gartun (substitusi "k" menjadi "g")

gartun → gantun (substitusi "r" menjadi "n")

gantun → gantung (penyisipan "g" di akhir).

Batas atas dan batas bawah

Jarak Levenshtein memiliki beberapa batas atas dan batas bawah yang sederhana. Beberapa diantaranya adalah:

Bernilai setidaknya sebesar perbedaan ukuran kedua string tersebut.

Maksimum bernilai sebesar panjang dari string yang lebih panjang.

Bernilai nol jika dan hanya jika kedua string sama.

Jika kedua string berukuran sama, jarak Hamming adalah batas atas bagi jarak Levenshtein.

Jarak Levenshtein antara dua string tidak pernah lebih besar dari jumlah jarak Levenshtein mereka dengan suatu string lain (pertidaksamaan segitiga).

Sebuh contoh bagi jarak Levenshtein antara dua string dengan panjang yang sama, bernilai lebih kecil dari jarak Hamming, adalah pasangan kata "makan" dan "akang". Di sini jarak Levenshtein sama dengan 2 (hapus huruf "m" di awal dan sisipkan "g" di akhir), sedangkan jarak Hamming mereka sebesar 5.