Edit Distance

Q: Bisakah Edit Distance diselesaikan dengan satu array?

Ya. Isi satu array row secara langsung, dari kiri ke kanan. Sebelum kamu menimpa row[j] , nilainya masih berasal dari baris di atas, dan row[j-1] sudah menyimpan nilai baris saat ini. Hanya nilai diagonal yang hilang, jadi simpan row[j] lama dalam sebuah variabel dan gunakan sebagai nilai diagonal untuk j + 1 .

SulitDynamic programming

+10

Kamu mendapatkan dua kata, word1 dan word2. Satu penyuntingan mengubah word1 dengan salah satu dari tiga cara: menyisipkan huruf di mana saja, menghapus huruf, atau mengganti huruf dengan huruf lain. Kembalikan jumlah penyuntingan paling sedikit untuk mengubah word1 menjadi word2.

Fungsi

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

word1string: kata yang kamu ubah
word2string: kata yang harus dicapai
Mengembalikaninteger: jumlah penyisipan, penghapusan, dan penggantian paling sedikit yang mengubah word1 menjadi word2

Batasan

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Kedua kata hanya berisi huruf kecil alfabet Inggris.

Contoh

Input: word1 = "spot"word2 = "stop"
Output: 2
Penjelasan: Ganti p dengan t dan t dengan p: spot menjadi stot, lalu stop. Satu perubahan saja tidak cukup, karena kedua kata berbeda di dua tempat dan penyisipan atau penghapusan akan mengubah panjangnya.

Input: word1 = "garden"word2 = "ardent"
Output: 2
Penjelasan: Hapus g untuk mendapatkan arden, lalu sisipkan t di akhir untuk mendapatkan ardent. Mengganti huruf satu per satu akan memerlukan biaya 6, karena kedua kata berbeda di setiap posisi.

Input: word1 = "rain"word2 = "shine"
Output: 3
Penjelasan: Ganti r dengan s dan a dengan h, lalu sisipkan e. Dua pengeditan tidak cukup: r dan a tidak ada dalam shine, jadi masing-masing memerlukan pengeditan yang mempertahankan panjangnya, dan kata tersebut tetap harus bertambah satu huruf.

Pertanyaan lanjutan

Bisakah kamu juga mengembalikan satu daftar perubahan terpendek, selain jumlahnya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Perubahan saling berinteraksi: garden dan ardent berbeda di keenam posisi, tetapi dua perubahan saja sudah cukup. Jadi, lihat huruf terakhir dari setiap kata. Keduanya mungkin sama, atau salah satu dari tiga perubahan dapat membuatnya sama, dan setiap pilihan menyisakan masalah yang sama pada prefiks yang lebih pendek. Sebuah tabel menyelesaikan setiap pasangan prefiks satu kali.

Coba ketiga pengeditan dengan rekursi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Misalkan edits(i, j) adalah jumlah edit paling sedikit untuk mengubah sufiks word1[i:] menjadi word2[j:]. Jika huruf pertama sama, pertahankan huruf itu dan geser kedua indeks: menggunakan satu edit untuk huruf yang sama tidak akan membantu. Jika tidak, ambil 1 ditambah nilai terkecil dari tiga pemanggilan: penggantian menggeser kedua indeks, penghapusan word1[i] menggeser i, dan penyisipan word2[j] menggeser j. Ketika salah satu kata habis, setiap huruf yang tersisa pada kata lainnya membutuhkan satu edit.

Setiap ketidakcocokan memulai tiga pemanggilan: dua kata yang masing-masing terdiri dari 15 huruf tanpa satu pun huruf yang sama membutuhkan sekitar 6.7 × 10^10 pemanggilan. Namun, hanya ada (n+1) × (m+1) pasangan (i, j) yang berbeda, jadi hampir setiap pemanggilan mengulang pemanggilan sebelumnya.

Algoritma

Jika i sudah melewati akhir word1, kembalikan m - j; jika j sudah melewati akhir word2, kembalikan n - i.
Jika word1[i] == word2[j], kembalikan edits(i+1, j+1).
Jika tidak, kembalikan 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)).
Jawabannya adalah edits(0, 0).

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)

Isi tabel prefiks

Intuisi

Misalkan dp[i][j] adalah jumlah edit paling sedikit untuk mengubah i huruf pertama dari word1 menjadi j huruf pertama dari word2. Jika word1[i-1] sama dengan word2[j-1], salin nilai diagonal dp[i-1][j-1]. Jika tidak, tambahkan 1 pada nilai tetangga termurah: sel diagonal berarti penggantian, sel di atas berarti menghapus word1[i-1], dan sel di sebelah kiri berarti menyisipkan word2[j-1]. Baris dan kolom dasar bukan nol: mengubah i huruf menjadi kosong memerlukan i penghapusan, jadi dp[i][0] = i, dan demikian pula dp[0][j] = j.

Untuk mengubah spot menjadi stop, baris terakhirnya adalah [4, 3, 2, 2, 2]. Sel terakhir membandingkan t dengan p; nilai diagonalnya (mengubah spo menjadi sto) adalah 1 dan nilai tetangga lainnya adalah 2, jadi jawabannya adalah 1 + 1 = 2. Dua kata yang masing-masing terdiri dari 500 huruf mengisi 2.5 × 10^5 sel, dengan waktu konstan untuk setiap sel.

Algoritma

Buat dp dengan (n+1) × (m+1) sel, dp[i][0] = i dan dp[0][j] = j.
Untuk i dari 1 hingga n dan j dari 1 hingga m: jika word1[i-1] == word2[j-1], tetapkan dp[i][j] = dp[i-1][j-1].
Jika tidak, tetapkan dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Kembalikan dp[n][m].

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]

Hanya sisakan dua baris

Intuisi

Baris i hanya membaca baris i-1 dan sel-selnya sendiri di sebelah kiri, jadi dua array sudah cukup: prev untuk baris yang sudah selesai dan cur untuk baris yang sedang kamu isi. Diagonalnya adalah prev[j-1], bagian atasnya adalah prev[j], dan bagian kirinya adalah cur[j-1]. Kolom dasar kini berada di entri pertama setiap baris, jadi tetapkan cur[0] = i sebelum mengisi baris i.

Mengubah word2 menjadi word1 memerlukan jumlah edit yang sama, karena penyisipan dan penghapusan saling bertukar. Tukar kedua kata agar baris berjalan mengikuti kata yang lebih pendek: min(n, m) + 1 angka per baris, bukan tabel dengan hingga 251,001 sel, dengan jumlah kerja yang sama, yaitu O(n × m).

Algoritma

Jika word2 lebih panjang daripada word1, tukar keduanya.
Tetapkan prev = [0, 1, ..., m].
Untuk setiap i dari 1 hingga n, tetapkan cur[0] = i dan isi cur[1..m] menggunakan aturan tabel, dengan membaca diagonal dan bagian atas dari prev, serta bagian kiri dari cur. Lalu tukar prev dan cur.
Kembalikan prev[m].

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]

Jebakan dan kasus tepi

Mengisi baris 0 dan kolom 0 dengan nol, seperti pada longest common subsequence. Mengubah abc menjadi prefiks kosong memerlukan 3 penghapusan, bukan 0.
Lupa menuliskan cur[0] = i pada versi dua baris. Entri pertama mempertahankan nilai dari dua baris sebelumnya, dan setiap sel setelahnya menjadi tidak tepat.
Membayar biaya edit saat ada kecocokan. Dengan 1 + min(...) untuk huruf yang sama, mengubah a menjadi a memerlukan biaya 1.
Membaca tetangga kiri dari prev, bukan dari cur. Nilai di sebelah kiri adalah penyisipan word2[j-1] pada baris saat ini.
Rekursi dengan memoization di Python pada kata sepanjang 500 huruf. Pemanggilan mencapai kedalaman 1000, melewati batas rekursi default.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Edit Distance?

Solusi tabel mengisi satu sel untuk setiap pasangan prefiks dalam waktu konstan: waktu O(n × m) untuk panjang n dan m. Solusi ini menggunakan memori O(n × m) untuk tabel lengkap, atau O(min(n, m)) dengan dua baris. Rekursi biasa tanpa tabel membutuhkan waktu eksponensial.

Apakah jarak edit sama dengan jarak Levenshtein?

Versi ini adalah jarak Levenshtein: penyisipan, penghapusan, dan penggantian masing-masing berbiaya satu. Jarak edit adalah nama kelompoknya. Jika hanya menggunakan penyisipan dan penghapusan, hasilnya n + m - 2 × LCS, jika hanya menggunakan penggantian pada string dengan panjang yang sama, hasilnya jarak Hamming, dan jika menambahkan pertukaran dua huruf yang bersebelahan, hasilnya versi Damerau.

Bisakah Edit Distance diselesaikan dengan satu array?

Ya. Isi satu array row secara langsung, dari kiri ke kanan. Sebelum kamu menimpa row[j], nilainya masih berasal dari baris di atas, dan row[j-1] sudah menyimpan nilai baris saat ini. Hanya nilai diagonal yang hilang, jadi simpan row[j] lama dalam sebuah variabel dan gunakan sebagai nilai diagonal untuk j + 1.

def minDistance(word1, word2):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

word1 = "spot"
word2 = "stop"

Output yang diharapkan

Edit Distance

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Coba ketiga pengeditan dengan rekursi

Isi tabel prefiks

Hanya sisakan dua baris

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa