Kompleksitas ruang untuk menghitung perataan string optimal untuk jarak edit Levenshtein

Jika kita diberi dua string ukuran dan n 2 , perhitungan jarak edit Levenshtein standar adalah dengan algoritma dinamis dengan kompleksitas waktu O ( n 1 n 2 ) dan kompleksitas ruang O ( n 1 n 2 ) . (Beberapa perbaikan dapat dibuat sebagai fungsi dari jarak edit d , tapi kami tidak membuat asumsi pada $n_1$$n_2$$O(n_1 n_2)$$O(n_1 n_2)$$d$$d$$O(\max(n_1, n_2))$

Namun, jika Anda ingin mendapatkan hasil aktual dari skrip edit optimal, apakah mungkin melakukan lebih baik daripada penggunaan memori , mungkin dengan mengorbankan waktu berjalan?$O(n_1 n_2)$

Tidak perlu untuk tradeoff yang disarankan Yuval. Keseluruhan urutan pengeditan yang optimal dapat dihitung dalam waktu dan ruang , menggunakan campuran pemrograman dinamis dan divide-and-conquer yang pertama kali dijelaskan oleh Dan Hirschberg. ( Algoritma ruang linear untuk menghitung urutan umum maksimal. Kom. ACM 18 (6): 341-343, 1975.)O ( n + m $O(nm)$$O(n+m)$

Secara intuitif, ide Hirschberg adalah untuk menghitung operasi pengeditan tunggal setengah jalan melalui urutan pengeditan yang optimal, dan kemudian secara rekursif menghitung dua bagian dari urutan. Jika kita menganggap urutan edit optimal sebagai jalur dari satu sudut tabel memoisasi ke sudut lainnya, kita perlu pengulangan yang dimodifikasi untuk merekam di mana jalur ini melintasi baris tengah tabel. Satu pengulangan yang berfungsi adalah sebagai berikut:

$$Half(i,j) = \begin{cases} \infty & \text{if $i<m/2$}\\ j & \text{if $i=m/2$}\\ Half(i-1,j) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i-1,j)+1$}\\ Half(i,j-1) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i,j-1)+1$}\\ Half(i-1,j-1) & \text{otherwise} \end{cases}$$

Nilai-nilai dapat dihitung pada waktu yang sama dengan tabel edit jarak , menggunakan waktu . Karena setiap baris tabel memoisasi hanya bergantung pada baris di atasnya, menghitung dan hanya membutuhkan ruang .$Half(i,j)$$Edit(i,j)$$O(mn)$$Edit(m,n)$$Half(m,n)$$O(m+n)$

Akhirnya, urutan pengeditan optimal mengubah string input menjadi terdiri dari urutan optimal yang mengubah menjadi diikuti oleh urutan optimal yang mengubah menjadi . Jika kita menghitung kedua urutan secara rekursif, keseluruhan waktu berjalan mematuhi perulangan berikut: Tidak sulit untuk membuktikan bahwa$A[1..m]$$B[1..n]$$A[1 .. m/2]$$B[1 .. Half(m, n)]$$A[m/2 + 1 .. m]$$B[Half(m, n) + 1 .. n]$

$$T(m,n) = \begin{cases} O(n) & \text{if $m\le 1$}\\ O(m) & \text{if $n\le 1$}\\ O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right) & \text{otherwise} \end{cases}$$ O ( m + n $T(m,n) = O(mn)$. Demikian pula, karena kita hanya membutuhkan ruang untuk satu lintasan pemrograman dinamis pada satu waktu, batas total ruang masih . (Ruang untuk tumpukan rekursi dapat diabaikan.)$O(m+n)$

Algoritma yang Anda gambarkan yang berjalan di ruang sebenarnya memulihkan hasil edit terakhir, dan menyatakan sesaat sebelum edit akhir. Jadi, jika Anda menjalankan algoritma ini kali, Anda dapat memulihkan seluruh urutan edit, dengan mengorbankan peningkatan runtime. Secara umum, ada trade-off ruang-waktu yang dikendalikan oleh jumlah baris yang Anda pertahankan pada saat itu. Dua titik ekstrim pertukaran ini adalah ruang dan ruang , dan di antaranya, produk waktu dan ruang konstan (hingga O besar).O ( n 1 + n 2 ) O ( n 1 n 2 ) O ( n 1 + n 2$O(n_1 + n_2)$$O(n_1 + n_2)$$O(n_1n_2)$$O(n_1+n_2)$