n-dimensionaler Mustervergleich

20

Welche Ergebnisse sind bekannt, um ein genaues n-dimensionales Subarray in einem n-dimensionalen Array zu finden?

In 1D handelt es sich nur um ein String-Matching-Problem. KMP führt dies in linearer Zeit durch.

In 2D wurde in diesem Artikel gezeigt, dass dies in linearer Zeit mit wenig zusätzlichem Platz durchgeführt werden kann.

Kann dieses Problem im ungünstigsten Fall linearer Zeit für eine feste Dimension gelöst werden?

ds.algorithms reference-request string-matching Chao Xu
quelle

Antworten:

13

Sie können das Problem in einer festgelegten Anzahl von Dimensionen lösen, indem Sie die ursprüngliche lineare Zeitlösung von Bird aus dem Jahr 1977 ( http://www.sciencedirect.com/science/article/pii/0020019077900175) erweitern (Abonnement leider erforderlich).

Die allgemeine Idee (in 2D) besteht in Schritt 1 darin, einen Aho-Corasick-Automaten aus den Zeilen des 2D-Musters zu erstellen und dann die Zeilen des 2D-Texts nacheinander einzugeben. Sie finden dann alle Positionen, mit denen die Musterzeilen im Text übereinstimmen. Zum Abschluss müssen Sie nur noch 1D nach den (Bezeichnungen von) Zeilen des Musters in der richtigen Reihenfolge in einer Spalte in der Ausgabe von Schritt 1 suchen, indem Sie beispielsweise KMP verwenden. Dies alles benötigt lineare Zeit.

Mit derselben Methode können Sie das exakte Übereinstimmungsproblem jeder Dimension d auf ein Problem der Dimension d-1 reduzieren. Auf diese Weise erhalten Sie eine lineare Zeitlösung für jede feste Dimension d.

Raphael
quelle
9

Es ist möglich, es in nahezu linearer Zeit (bis zum Polylog-Faktor) unter Verwendung von FFT-Techniken zu lösen. Sie können auf dem Papier nachschauen: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf, wo wir FFT-Techniken für den eindimensionalen Mustervergleich verwenden. Wenn Sie mehrdimensionale Mustervergleiche lösen möchten, müssen Sie nur eine hochdimensionale FFT verwenden.

Klim
quelle
Angesichts der Veröffentlichung aus dem Jahr 2008 gehe ich davon aus, dass lineare Zeitalgorithmen noch nicht bekannt sind.
Chao Xu
Ich habe es nur als Beispiel für eine Technik angegeben, die zur Lösung Ihres Problems verwendet werden kann. Vorteil dieses Ansatzes ist, dass Sie damit auch das Problem mit Fehlpaarungen lösen können und sich nicht darum kümmern müssen. Für genau eine dimensionale Musterübereinstimmung existiert jedoch eine lineare Zeitalgorithmus. so mag es sein, ist es für mehrdimensionale bekannt.
Klim
1
Ich denke, das grundlegende Ergebnis für den Mustervergleich mit Platzhaltern stammt von Fischer und Paterson aus dem Jahr 1974 und wurde dann kontinuierlich optimiert und vereinfacht, bis cs.bris.ac.uk/Publications/pub_master.jsp?id=2000602 (entschuldigt sich für das Selbstzitat ). Es kann jedoch ein leichter Overkill für das vom OP angeforderte Problem sein, wenn man die weiter unten erwähnte ältere Methode für die exakte Zuordnung zugrunde legt.
Raphael