Abstand im sublinearen Raum bearbeiten

19

Was ist die bekannteste Komplexität für die Berechnung des genauen Bearbeitungsabstands zwischen zwei Zeichenfolgen gleicher Länge unter Verwendung des Arbeitsraums, der in der Größe der Eingabe sublinear ist? Ich gehe davon aus, dass die Eingabe in einem schreibgeschützten Format gespeichert ist. Ist das ein zuvor untersuchtes Problem?

Um die Frage etwas genauer zu formulieren, wie wäre es mit , wobei die Länge jeder Eingabezeichenfolge ist.Θ(n)n

Bearbeiten. Nach der Antwort von David Eppstein scheint es eine gute Frage zu sein, ob die Bearbeitungsentfernung in Polynomzeit und -Raum gefunden werden kann. Irgendwelche Untergrenzen wären auch interessant.Θ(n)

ds.algorithms edit-distance space-time-tradeoff felix
quelle
1
Zum Schnitt: Ich denke du verstehst etwas falsch. Die Antwort von David Eppstein zeigt, dass das Problem in NL lösbar ist, daher auch in P.
Emil Jeřábek unterstützt Monica
1
... Eigentlich macht das der ursprüngliche Wagner-Fischer-Algorithmus schon.
Emil Jeřábek unterstützt Monica
3
Ich gehe davon aus, dass die bearbeitete Version nach Algorithmen fragen soll, die sowohl sublinearer Raum als auch Polynomzeit sind.
David Eppstein
@ DavidEppstein Ja, genau. Ich habe zur Klarstellung nochmal editiert.
Felix
Übrigens, unter der Annahme des Standardpreismodells von 1 pro Midmatch / Löschen / Einfügen, und wenn der Bearbeitungsabstand 1 ist, dann geht der Pfad, der den kürzesten Pfad in der Bearbeitungsabstandsmatrix realisiert, höchstens 1 von der Hauptdiagonale entfernt, und dann Die Bearbeitungsentfernung wird unter Verwendung des O (l) -Raums berechnet. Mit sqrt (n) space können Sie also den Bearbeitungsabstand berechnen, wenn er klein ist (dh kleiner als sqrt (n)). Nur wenn es groß ist, scheint dies schwierig zu sein. Natürlich sollten Sie sich in diesem Fall weniger darum kümmern.
Sariel Har-Peled

Antworten:

16

O(Log2⁡n)nO(Log⁡n)

Unter http://arxiv.org/abs/1106.4412 gibt es einige Leerzeichen für die Bearbeitungsentfernung, aber ich denke, sie stimmen nicht mit Ihrer Version des Problems überein.

David Eppstein
quelle
Wie überprüfen Sie, ob der gefundene Pfad optimal ist?
Lembik
1
Binäre Suche oder sequentielle Suche nach der kleinsten Entfernung, für die ein Pfad gefunden werden kann, dh nichts anderes als die Standardäquivalenz von Entscheidungs- und Suchproblemen. Dies hat keinen Einfluss auf die Form der räumlichen oder zeitlichen Begrenzung.
David Eppstein
@ David Ich denke, Sie sind richtig, also habe ich meine Antwort gelöscht.
SamiD
2
Ist es überhaupt im Protokollbereich berechenbar?
Lembik