Levenshtein mesafesi

Kısaca: Levenshtein mesafesi, bir sözcüğü başka bir sözcüğe dönüştürmek için gereken en az tek karakterli ekleme, silme ve değiştirme sayısını sayar.

Biraz daha ayrıntılı: “kitten” → “sitting” mesafesi 3’tür (k→s, e→i, g ekle). Yazım denetimi, “Bunu mu demek istediniz …?” ve bulanık aramanın temelindedir.

Ayrıntılı

• Yöntem: A’nın ilk i karakteri ile B’nin ilk j karakteri arasındaki mesafe için d[i][j] tablosuyla dinamik programlama.
• Özyineleme: d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + (a[i]≠b[j])).
• Maliyet: O(m·n) zaman; yalnızca iki satır tutulursa O(min(m, n)) bellek.
• Varyantlar: Damerau-Levenshtein bitişik karakterlerin yer değiştirmesini de sayar. Hamming mesafesi yalnızca eşit uzunluklu sözcükler için geçerlidir.
• Pratikte: Büyük sözlüklerde her sözcüğü tek tek karşılaştırmak yerine BK ağaçları veya n-gramlar gibi indeksler kullanılır.

Ayrıca bak: Metin arama algoritmaları