Vergleich von Array innerhalb eines Array anhand eines Teiles des Arrays

[Jesus_666]

Mein erster Gedanke dabei ist: Reguläre Ausdrücke. Regexps lösen das genau gleiche Problem, nur in einem anderen Kontext. Man kann vielleicht dein Problem auf diesen Kontext abbilden (in welchem Fall ein Regexp es lösen kann) oder aber sich ansehen, wie Regexp-Bibliotheken wie PCRE die Eusdrücke evaluieren und dazu ein Analogon bauen.

Ich empfehle dir, dir mal String-Suchalgorithmen anzusehen; einige der Kniffe da kannst du übernehmen Beispielsweise könnte der Boyer-Moore-Algorithmus dir erlauben, die Suchzeit deutlich einzuschränken. Das ist auch der Grund, warum ich eine Suche mit direktem Vergleich der Zellwerte einer mit Vergleich der Determinanten vorziehe.

Fangen wir mal mit einem einfachen Algorithmus (tatsächlich dem naiven) an:

Code:

Sei haystack die Matrix, in der gesucht wird.
Sei needle die Matrix, nach der wir suchen.
Sei matches eine Liste von der Positionen, an denen Treffer gefunden wurden
  (implementiert als Liste von Paaren von Ganzzahlen).

FOR y_start IN [0 .. (haystack.höhe - needle.höhe)]
    FOR x_start IN [0 .. (haystack.breite - needle.breite)]
        FOR y IN [0 .. needle.höhe - 1]
            FOR x IN [0 .. needle.breite - 1]
                IF haystack[y_start + y][x_start + x] != needle[y][x]
                THEN GOTO :weiter
        matches.add(<y, x>)
        :weiter
RETURN matches

Der ist mit O(n⁴) wirklich langsam, aber es ist schon mal ein Anfang. Wenn wir uns jetzt den Boyer-Moore ansehen, dann haben wir zwei Heuristiken, die uns erlauben, bei Fehlern Teile der Matrix zu überspringen. Ich sehe gerade, daß ich keine Zeit mehr habe, das jetzt konkret zu erarbeiten, aber wenn man das Suchfenster anhand dieser Regeln zumindest auf der X-Achse verschiebt, kann man einiges an Aufwand einsparen.

Es müßte möglich sein, sich zu erarbeiten, ob man auch gleich mehrere Y-Zeilen überspringen kann, was natürlich den Aufwand deutlich senkt. Auch dafür habe ich jetzt leider keine Zeit mehr.

Auf jeden Fall kannst du vermeiden, für jede der (haystack.breite - needle.breite)*(haystack.höhe - needle.höhe) möglichen Positionen Vergleiche durchführen zu müssen.


PS: Verdammt, von nudel geninjat.

[dadie]

Heureka

Die Lösungs-Ideen sind gar nicht mal schlecht. Ich wollte unbedingt das ganze Zwei-Dimensional vergleichen. Aber wenn ich es erst einmal Ein-Dimensional überprüfe geht es wirklich einfacher. 666 sei aber beruhigt. Deine Beitrag hat mir ebenfalls einen Denk Anstoß gegeben ^^

[R.D.]

Ah verdammt Warum muss ich auch fernseh gucken. Boyer-Moore hätte ich auch gesagt (Aber nur, weil ich das erst vor kurzem gelernt habe xD)

@Jeez
Du springst! D: