Düzenleme Mesafesi (Edit Distance)

#Nasıl çalışır?

Düzenleme mesafesi (Levenshtein mesafesi), bir kelimeyi diğerine çevirmek için gereken en az tek harflik işlem sayısıdır. İzin verilen işlemler: bir harfi değiştirmek, silmek ya da eklemek. KITTEN → SITTING için mesafe 3'tür: K→S, E→I ve sona G eklemek.

dp[i][j], X'in ilk i harfini Y'nin ilk j harfine çevirmenin en düşük maliyetidir. Son harfler aynıysa işlem gerekmez ve çapraz değer alınır. Farklıysa üç seçenekten en ucuzu seçilir: değiştirmek (çapraz), X'teki harfi silmek (üst) ya da Y'deki harfi eklemek (sol); hepsine 1 eklenir.

Yapısı LCS'e çok benzer; LCS ortak olanı en büyüklerken düzenleme mesafesi farkı en küçükler. Tablonun sağ alttan geri izlenmesi, işlemlerin listesini verir.

#Kendin dene

#Adım adım

1. 01İlk satır dp[0][j] = j (j harf eklemek), ilk sütun dp[i][0] = i (i harf silmek).
2. 02Harfler aynıysa dp[i][j] = dp[i − 1][j − 1].
3. 03Farklıysa dp[i][j] = 1 + min(çapraz, üst, sol).
4. 04dp[m][n] mesafedir; sağ alttan geri izleyerek işlemleri oku.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def edit_distance(x: str, y: str) -> int:
    m, n = len(x), len(y)
    # dp[i][j] = cheapest way to turn x[:i] into y[:j].
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i  # delete everything
    for j in range(n + 1):
        dp[0][j] = j  # insert everything
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # no edit needed
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                   dp[i - 1][j],      # delete
                                   dp[i][j - 1])      # insert
    return dp[m][n]


print(edit_distance("KITTEN", "SITTING"))   # K->S, E->I, +G
print(edit_distance("SUNDAY", "SATURDAY"))

#Karmaşıklık

Her hücre sabit sürede doldurulur. Yalnızca mesafe gerekiyorsa iki satır yeterlidir. Mesafenin küçük bir k değerinden az olup olmadığı soruluyorsa sadece köşegen etrafındaki bant hesaplanarak O(k · n) zamana inilebilir.

#Ne zaman kullanılır?

Yazım denetimi ve "bunu mu demek istediniz?" önerileri, arama motorlarında bulanık eşleştirme, DNA dizilerinin karşılaştırılması, OCR ve konuşma tanıma çıktılarının düzeltilmesi ve diff araçları düzenleme mesafesi kullanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.