Edytuj odległość w przestrzeni podliniowej

Jaka jest najbardziej znana złożoność obliczenia dokładnej odległości edycji między dwoma ciągami o tej samej długości przy użyciu przestrzeni roboczej, która jest podliniowa w wielkości wejścia? Zakładam, że dane wejściowe są przechowywane w jakimś formacie tylko do odczytu. Czy to wcześniej badany problem?

Aby uczynić pytanie nieco bardziej szczegółowym, co powiesz o spacji gdzie jest długością każdego łańcucha wejściowego. $\Theta(\sqrt{n})$ $n$

Edytować. Po odpowiedzi Davida Eppsteina wydaje się, że dobrym pytaniem jest po prostu, czy odległość edycji można znaleźć w czasie wielomianowym i spacji . Interesujące byłyby również wszelkie dolne granice. $\Theta(\sqrt{n})$

ds.algorithms edit-distance space-time-tradeoff

— Felix
źródło

Odnośnie edycji: Myślę, że coś źle zrozumiałeś. Odpowiedź Davida Eppsteina pokazuje, że problem można rozwiązać w NL, a więc także w P.

— Emil Jeřábek popiera Monikę

... Właściwie oryginalny algorytm Wagnera-Fischera już to robi.

— Emil Jeřábek wspiera Monikę

Zakładam, że edytowana wersja ma pytać o algorytmy, które byłyby zarówno przestrzenią podliniową, jak i czasem wielomianowym.

— David Eppstein,

@DavidEppstein Tak, dokładnie. Zredagowałem ponownie dla wyjaśnienia.

— felix

BTW, zakładając standardowy model wyceny 1 na pół-dopasowanie / usuwanie / wstawianie, to jeśli odległość edycji wynosi l, wówczas ścieżka realizująca najkrótszą ścieżkę w matematyce odległości edycji idzie w odległości co najwyżej l od głównej przekątnej, a następnie odległość edycji oblicza się za pomocą odstępu O (l). Zatem za pomocą spacji sqrt (n) możesz obliczyć odległość edycji, jeśli jest ona mała (tj. Mniejsza niż sqrt (n)). Wydaje się to trudne tylko wtedy, gdy jest duże. Oczywiście w tym przypadku zapewne nie powinno cię to obchodzić.

— Sariel Har-Peled,

Tylko po to, aby zacząć działać, zamiast próbować rozwiązać ten problem: istnieje oczywisty niedeterministyczny algorytm wykorzystujący logarytmicznie wiele bitów przestrzeni (poszukiwanie pojedynczej ścieżki przez dynamiczną matrycę programowania), więc według twierdzenia Savitcha istnieje algorytm deterministyczny z przestrzenią . Czas musi mieć postać , quasi-wielomianowy, a nie wykładniczy. $O(\log^2 n)$ $n^{O(\log n)}$

Istnieją pewne dolne granice miejsca dla odległości edycji w http://arxiv.org/abs/1106.4412, ale nie sądzę, aby pasowały do twojej wersji problemu.

— David Eppstein
źródło

Jak sprawdzić, czy znaleziona ścieżka jest optymalna?

— Lembik

Wyszukiwanie binarne lub sekwencyjne dla najmniejszej odległości, dla której można znaleźć ścieżkę, tj. Nic poza standardową równoważnością problemów decyzyjnych i wyszukiwania. Nie wpływa to na formy ani przestrzeni, ani czasu.

— David Eppstein,

@ David Uważam, że masz rację, więc usunąłem odpowiedź.

— SamiD

Czy jest to w ogóle obliczalne w przestrzeni dziennika?

— Lembik