Edit jarak dalam ruang sublinear

Apa kompleksitas yang paling dikenal untuk menghitung jarak edit yang tepat antara dua string dengan panjang yang sama menggunakan ruang kerja yang sublinear dalam ukuran input? Saya berasumsi input disimpan dalam beberapa format read-only. Apakah ini masalah yang dipelajari sebelumnya?

Untuk membuat pertanyaan sedikit lebih spesifik, bagaimana dengan ruang di manaadalah panjang dari setiap string input. $\Theta(\sqrt{n})$ $n$

Edit. Mengikuti jawaban David Eppstein, sepertinya pertanyaan yang bagus adalah hanya jika jarak sunting dapat ditemukan dalam waktu polinomial dan ruang. Batas bawah mana pun juga akan menarik. $\Theta(\sqrt{n})$

ds.algorithms edit-distance space-time-tradeoff felix
sumber

Mengenai hasil edit: Saya pikir Anda salah mengerti sesuatu. Jawaban David Eppstein menunjukkan bahwa masalah dapat diselesaikan dalam NL, karenanya juga dalam P.

Emil Jeřábek mendukung Monica

... Sebenarnya, algoritma Wagner-Fischer asli sudah melakukan itu.

Emil Jeřábek mendukung Monica

Saya menganggap versi yang diedit dimaksudkan untuk meminta algoritma yang merupakan ruang sublinear dan waktu polinomial.

David Eppstein

@ David Eppstein Ya, persis. Saya telah mengedit lagi untuk klarifikasi.

felix

BTW, dengan asumsi model penetapan harga standar 1 per midmatch / delete / insert, maka jika jarak sunting adalah l, maka jalur yang merealisasikan jalur terpendek dalam matrik jarak sunting akan paling jauh dalam jarak l dari diagonal utama, dan kemudian jarak edit dihitung menggunakan O (l) spasi. Dengan demikian, dengan ruang sqrt (n), Anda dapat menghitung jarak sunting jika kecil (yaitu, lebih kecil dari sqrt (n)). Hanya jika ukurannya besar maka ini tampaknya sulit. Tentu saja, dalam hal ini, bisa dibilang, Anda harus kurang peduli.

Sariel Har-Peled

Edit jarak dalam ruang sublinear

Jawaban: