Edit Distance

Q: Düzenleme Mesafesi tek bir diziyle çözülebilir mi?

Evet. Tek bir row dizisini yerinde, soldan sağa doldurun. row[j] üzerine yazmadan önce bu hücre hâlâ yukarıdaki satırdaki değeri tutar ve row[j-1] zaten mevcut satırdaki değeri tutar. Yalnızca köşegen değer kaybolur; bu yüzden eski row[j] değerini bir değişkende saklayın ve j + 1 için köşegen değeri olarak kullanın.

ZorDinamik programlama

+10

Sana iki kelime verilir: word1 ve word2. Bir düzenleme, word1 kelimesini üç yoldan biriyle değiştirir: herhangi bir yere bir harf eklemek, bir harfi silmek veya bir harfi başka bir harfle değiştirmek. word1 kelimesini word2 kelimesine dönüştürmek için gereken en az düzenleme sayısını döndür.

Fonksiyon

minDistance(word1: string, word2: string) → integer

word1string: düzenlediğin kelime
word2string: ulaşmak kelimesi
Döndürürinteger: word1 sözcüğünü word2 sözcüğüne dönüştüren en az sayıda ekleme, silme ve değiştirme

Kısıtlar

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Her iki sözcük de yalnızca küçük İngilizce harfler içerir.

Örnekler

Girdi: word1 = "spot"word2 = "stop"
Çıktı: 2
Açıklama: p'yi t ile ve t'yi p ile değiştir: spot, stot'a, ardından stop'a dönüşür. Tek bir düzenleme yeterli değildir, çünkü sözcükler iki yerde farklıdır ve ekleme ya da silme uzunluğu değiştirir.

Girdi: word1 = "garden"word2 = "ardent"
Çıktı: 2
Açıklama: arden elde etmek için g harfini silin, ardından ardent elde etmek için sona t ekleyin. Harfleri tek tek değiştirmek 6'ya mal olurdu; çünkü iki sözcük her konumda farklıdır.

Girdi: word1 = "rain"word2 = "shine"
Çıktı: 3
Açıklama: r'yi s ile ve a'yı h ile değiştir, ardından e ekle. İki düzenleme işe yaramaz: shine içinde r ve a yoktur, bu yüzden her biri uzunluğu koruyan bir düzenleme gerektirir ve kelimenin uzunluğu yine de bir artmalıdır.

Ek soru

Değişikliklerin sayısının yanı sıra, en kısa değişiklik listesini de döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Düzenlemeler etkileşimlidir: garden ve ardent altı konumun tamamında farklıdır, ancak iki düzenleme yeterlidir. Bu yüzden her kelimenin son harfine bak. Ya ikisi aynıdır ya da üç düzenlemeden biri onları aynı hâle getirir ve her seçim, daha kısa öneklerde aynı problemi bırakır. Bir tablo, her önek çiftini bir kez çözer.

Özyineleme ile üç düzenlemenin tümünü deneyin

Doğru, ama en büyük testlerde bitmiyor

Sezgi

edits(i, j), word1[i:] son ekini word2[j:] son ekine dönüştürmek için gereken en az düzenleme sayısı olsun. İlk harfler eşleşiyorsa onları koruyup her iki indeksi de ilerlet: eşleşen bir harfi düzenlemek hiçbir zaman işe yaramaz. Aksi takdirde, üç çağrıdan en ucuzunun üzerine 1 ekle: değiştirme her iki indeksi de ilerletir, word1[i] harfini silmek i değerini ilerletir ve word2[j] harfini eklemek j değerini ilerletir. Sözcüklerden biri bittiğinde, diğerinde kalan her harfin maliyeti bir düzenlemedir.

Her uyuşmazlık üç çağrı başlatır: ortak harfi olmayan iki 15 harfli sözcük yaklaşık 6.7 × 10^10 çağrı gerektirir. Oysa yalnızca (n+1) × (m+1) farklı (i, j) çifti vardır; bu nedenle çağrıların neredeyse tamamı önceki bir çağrıyı tekrarlar.

Algoritma

i, word1'in sonunu geçtiyse m - j döndür; j, word2'nin sonunu geçtiyse n - i döndür.
word1[i] == word2[j] ise edits(i+1, j+1) döndür.
Aksi takdirde 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)) döndür.
Yanıt edits(0, 0)'dır.

def minDistance(word1, word2):
    n, m = len(word1), len(word2)

    def edits(i, j):
        # Fewest edits to turn word1[i:] into word2[j:]
        if i == n:
            return m - j  # insert the rest of word2
        if j == m:
            return n - i  # delete the rest of word1
        if word1[i] == word2[j]:
            return edits(i + 1, j + 1)
        return 1 + min(edits(i + 1, j + 1),  # replace word1[i] with word2[j]
                       edits(i + 1, j),      # delete word1[i]
                       edits(i, j + 1))      # insert word2[j]

    return edits(0, 0)

Önekler tablosunu doldurun

Sezgi

dp[i][j], word1 sözcüğünün ilk i harfini word2 sözcüğünün ilk j harfine dönüştürmek için gereken en az düzenleme sayısı olsun. word1[i-1], word2[j-1] değerine eşitse, çaprazdaki dp[i-1][j-1] değerini kopyalayın. Aksi hâlde 1 ekleyip en ucuz komşuyu seçin: çapraz hücre değiştirme, üstteki hücre word1[i-1] harfini silme, soldaki hücre ise word2[j-1] harfini ekleme işlemidir. İlk satır ve sütun sıfır değildir: i harfi hiçbir şeye dönüştürmek için i silme gerekir, yani dp[i][0] = i; aynı şekilde dp[0][j] = j.

spot sözcüğünü stop sözcüğüne dönüştürürken son satır [4, 3, 2, 2, 2] olur. Son hücre t ile p harflerini karşılaştırır; çaprazındaki değer (spo sözcüğünü sto sözcüğüne dönüştürme) 1, diğer komşuları ise 2’dir; dolayısıyla sonuç 1 + 1 = 2 olur. 500 harfli iki sözcük, her biri sabit zamanda hesaplanan 2.5 × 10^5 hücre doldurur.

Algoritma

(n+1) × (m+1) hücreli bir dp oluşturun; dp[i][0] = i ve dp[0][j] = j olsun.
1'den n'ye kadar i ve 1'den m'ye kadar j için: word1[i-1] == word2[j-1] ise dp[i][j] = dp[i-1][j-1] olarak ayarlayın.
Aksi halde dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) olarak ayarlayın.
dp[n][m] değerini döndürün.

def minDistance(word1, word2):
    n, m = len(word1), len(word2)
    # dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i  # delete all i letters
    for j in range(m + 1):
        dp[0][j] = j  # insert all j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                   dp[i - 1][j],      # delete word1[i-1]
                                   dp[i][j - 1])      # insert word2[j-1]
    return dp[n][m]

Sadece iki satır kalsın

Sezgi

i satırı yalnızca i-1 satırını ve kendi solundaki hücreleri okur; bu yüzden iki dizi yeterlidir: tamamlanmış satır için prev, doldurmakta olduğunuz satır için cur. Köşegen prev[j-1], üst prev[j] ve sol cur[j-1] değeridir. Taban sütunu artık her satırın ilk elemanında yer alır; bu nedenle i satırını doldurmadan önce cur[0] = i değerini atayın.

word2 sözcüğünü word1 sözcüğüne dönüştürmek aynı sayıda düzenleme gerektirir; çünkü ekleme ve silme işlemleri birbirinin yerine geçer. Satırların daha kısa sözcük boyunca ilerlemesi için sözcükleri yer değiştirin: her satırda min(n, m) + 1 sayı kullanılır; en fazla 251,001 hücreli bir tabloya gerek kalmaz ve işlem sayısı yine O(n × m) olur.

Algoritma

word2, word1'den daha uzunsa yerlerini değiştir.
prev = [0, 1, ..., m] olarak ayarla.
1'den n'ye kadar her i için cur[0] = i olarak ayarla ve cur[1..m] değerlerini tablo kuralını kullanarak doldur; köşegeni ve üsttekini prev'den, solu ise cur'dan oku. Ardından prev ve cur'yi değiştir.
prev[m] değerini döndür.

def minDistance(word1, word2):
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # the rows run along the shorter word
    m = len(word2)
    # prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
    prev = list(range(m + 1))
    for i in range(1, len(word1) + 1):
        cur = [i] + [0] * m  # i letters into an empty prefix: delete them all
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],  # replace
                                 prev[j],      # delete word1[i-1]
                                 cur[j - 1])   # insert word2[j-1]
        prev = cur
    return prev[m]

Tuzaklar ve uç durumlar

En uzun ortak alt dizide olduğu gibi, 0. satırı ve 0. sütunu sıfırlarla doldurmak. abc dizisini boş bir öneke dönüştürmek 0 değil, 3 silme işlemi gerektirir.
İki satırlı sürümde cur[0] = i atamasını unutmak. İlk giriş, iki satır öncesinden gelen bir değeri korur ve bundan sonraki her hücre yanlış olur.
Eşleşme durumunda bir düzenleme işlemi uygulamak. Eşit harfler için 1 + min(...) kullanıldığında, a dizisini a dizisine dönüştürmenin maliyeti 1 olur.
Sol komşuyu cur yerine prev içinden okumak. Sol komşu, geçerli satırda word2[j-1] ekleme işlemidir.
Python'da 500 harfli sözcükler üzerinde özyinelemeli memoizasyon kullanmak. Çağrılar 1000 derinliğe kadar çıkar ve varsayılan özyineleme sınırını aşar.

Sıkça sorulan sorular3

Edit Distance algoritmasının zaman karmaşıklığı nedir?

Tablo çözümü, önek çiftleri başına bir hücreyi sabit zamanda doldurur: n ve m uzunlukları için O(n × m) zaman alır. Tam tablo için O(n × m) bellek, iki satırla ise O(min(n, m)) bellek kullanır. Tablo kullanmadan yapılan yalın özyineleme üsteldir.

İşlem mesafesi, Levenshtein mesafesiyle aynı mıdır?

Bu sürüm Levenshtein uzaklığıdır: ekleme, silme ve değiştirme işlemlerinin her biri bir maliyetlidir. Düzenleme uzaklığı, genel adıdır. Yalnızca ekleme ve silme işlemleri n + m - 2 × LCS sonucunu verir; uzunluklar eşitse yalnızca değiştirme işlemleri Hamming uzaklığını verir ve birbirine komşu iki harfi değiştirme işlemini eklemek Damerau sürümünü verir.

Düzenleme Mesafesi tek bir diziyle çözülebilir mi?

Evet. Tek bir row dizisini yerinde, soldan sağa doldurun. row[j] üzerine yazmadan önce bu hücre hâlâ yukarıdaki satırdaki değeri tutar ve row[j-1] zaten mevcut satırdaki değeri tutar. Yalnızca köşegen değer kaybolur; bu yüzden eski row[j] değerini bir değişkende saklayın ve j + 1 için köşegen değeri olarak kullanın.

def minDistance(word1, word2):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

word1 = "spot"
word2 = "stop"

Beklenen Çıktı

Edit Distance

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Özyineleme ile üç düzenlemenin tümünü deneyin

Önekler tablosunu doldurun

Sadece iki satır kalsın

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler