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

Edytuj odległość w przestrzeni podliniowej

Odpowiedzi: