Kompleksitas ruang untuk menghitung perataan string optimal untuk jarak edit Levenshtein

12

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 dn1n2O(n1n2)O(n1n2)ddO(max(n1,n2))

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(n1n2)

a3nm
sumber

Jawaban:

15

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)={if i<m/2jif i=m/2Half(i1,j)if i>m/2 and Edit(i,j)=Edit(i1,j)+1Half(i,j1)if i>m/2 and Edit(i,j)=Edit(i,j1)+1Half(i1,j1)otherwise

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)

masukkan deskripsi gambar di sini

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 bahwaA[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)={O(n)if m1O(m)if n1O(mn)+maxh(T(m/2,h)+T(m/2,nh))otherwise
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)
Jeffε
sumber
5
Karena saya melewatkan ini ketika Dan bertanya pada saya pada ujian kualifikasi saya, itu sebabnya.
Jeff
Saya ingat memiliki ini sebagai latihan (dipandu) dan berpikir itu cukup keren
Sasho Nikolov
3

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(n1+n2)O(n1+n2)O(n1n2)O(n1+n2)

Yuval Filmus
sumber