Düzenleme Mesafesi (Edit Distance)

Düzenleme Mesafesi nedir?

Düzenleme mesafesi (edit distance), iki metin dizisinin birbirine ne kadar benzediğini ölçen bir yöntemdir. Bir diziyi diğerine dönüştürmek için gereken en az işlem sayısı olarak tanımlanır. En yaygın türü, 1965'te Sovyet matematikçi Vladimir Levenshtein tarafından tanımlanan ve onun adıyla anılan Levenshtein mesafesidir.

Levenshtein mesafesinde üç temel işleme izin verilir:

• Ekleme: Bir karakter eklemek ("kalem" → "kalemi").
• Silme: Bir karakter silmek ("kitap" → "kitp").
• Değiştirme: Bir karakteri başka biriyle değiştirmek ("masa" → "kasa").

Örneğin "kitap" ile "kitabı" arasındaki mesafe 2'dir: "p" harfini "b" ile değiştirmek ve sona "ı" eklemek.

Nasıl çalışır?

Düzenleme mesafesi genellikle dinamik programlama ile hesaplanır. İki metnin karakterleri bir tablonun satır ve sütunlarına yerleştirilir. Tablonun her hücresi, birinci metnin ilk i karakterini ikinci metnin ilk j karakterine dönüştürmenin en düşük maliyetini tutar. Her hücre, komşu hücrelerden (ekleme, silme ya da değiştirme adımıyla) hesaplanır. Tablonun sağ alt köşesindeki değer, iki metin arasındaki toplam mesafeyi verir.

Bu yöntemin hesaplama maliyeti, iki metnin uzunluklarının çarpımıyla orantılıdır. Kısa metinler için çok hızlıdır, ama çok uzun metinlerde ya da büyük veri tabanlarında tek tek karşılaştırma yapmak pahalı hale gelebilir.

Farklı ihtiyaçlar için varyasyonlar da vardır:

• Damerau-Levenshtein: Yan yana iki harfin yer değiştirmesini ("kaelm" → "kalem") tek işlem sayar. Yazım hatalarında daha gerçekçi sonuç verir.
• Hamming mesafesi: Sadece değiştirmeye izin verir; aynı uzunluktaki diziler için kullanılır.
• Ağırlıklı mesafe: Klavyede yan yana olan harflerin karıştırılmasına daha düşük maliyet vermek gibi.

Normalleştirilmiş düzenleme mesafesi, sonucu metin uzunluğuna bölerek farklı uzunluktaki metinleri karşılaştırılabilir hale getirir.

Neden önemli?

Düzenleme mesafesi, "bu iki metin ne kadar benzer?" sorusuna basit, anlaşılır ve hızlı bir cevap verir. Anlamsal değil, yüzeysel (karakter düzeyinde) bir benzerlik ölçüsüdür: "araba" ile "otomobil" arasındaki mesafe büyüktür, oysa anlamları aynıdır. Anlamsal benzerlik için embedding tabanlı yöntemler kullanılır.

Kullanım alanları

• Yazım denetimi: Hatalı yazılmış bir kelimeye en yakın doğru kelimeleri önermek.
• Arama: Kullanıcının yazım hatası yaptığı sorgularda bulanık eşleştirme (fuzzy matching) yapmak.
• Veri temizleme: "Ahmet Yılmaz" ile "Ahmet Yilmaz" gibi mükerrer kayıtları bulmak.
• Biyoinformatik: DNA ve protein dizilerini karşılaştırmak.
• Model değerlendirmesi: Konuşma tanıma ve OCR sistemlerinde kelime/karakter hata oranını hesaplamak.