Levenshtein Mesafesi Hesaplama

Nasıl hesaplanır?

Diziler Unicode karakterlerine ayrılır; yani aksanlı bir harf tek karakter sayılır. Bir tablo doldurulur: (i, j) hücresi, A'nın ilk i karakterini B'nin ilk j karakterine çevirmenin en ucuz yolunu tutar: d(i, j) = min(d(i−1, j) + 1, d(i, j−1) + 1, d(i−1, j−1) + c); iki karakter aynıysa c = 0, farklıysa c = 1. Köşedeki hücre mesafe d değeridir. Benzerlik (1 − d / max(|A|, |B|)) × 100 ile bulunur ve bir ondalıkla yüzde olarak gösterilir. Karşılaştırma büyük-küçük harfe duyarlıdır ve boşluklar karakter sayılır. İki boş dizide sonuç çıkmaz; iki uzunluğun çarpımı 1.000.000'u aşan çiftlerde de sonuç verilmez.

Sık yapılan hatalar

• Büyük ve küçük harfin eşleşmesini beklemek. Kitten ile kitten bir düzenleme farklıdır, çünkü büyük K farklı bir karakter sayılır.
• Yapıştırılan metnin sonunda boşluk bırakmak. Boşluk da karakterdir; abc ile sonunda boşluk olan abc arasındaki mesafe 1'dir.
• Benzerliği anlam benzerliği sanmak. Yalnızca karakterleri sırayla karşılaştırır; aynı anlama gelen iki kelime düşük puan alabilir.
• Mesafeyi farklı konum sayısı sanmak. Ekleme ve silme sonrasındaki her şeyi kaydırır; bu yüzden mesafe, konum konum karşılaştırmanın gösterdiğinden çok daha küçük olabilir.
• İki uzun metni yapıştırıp sonuç beklemek. İki uzunluğun çarpımı bir milyonu geçince araç sonuç vermez; daha kısa parçaları karşılaştırın.