RegExp-ähnliche Bibliothek für Suchmatrixmuster

Question

Gibt es eine Bibliothek (in jeder Sprache), die Muster in Matrices wie reguläre Ausdrücke Arbeit für Strings suchen? So etwas wie regelmäßige expresions für Matrices, oder jede Matrixmuster Suchmethode?

Answer 1

Wenn Sie mit J nicht abgeneigt sind, können Sie herausfinden, ob zwei Matrizen gleich sind durch den -: (Spiel) Operator. Zum Beispiel:

   X =: 4 3 $ i.12
   X
0  1  2
3  4  5
6  7  8
9 10 11
   Y =: 4 3 $ (1+i.12)
   Y
 1  2  3
 4  5  6
 7  8  9
10 11 12
   X -: X
1
   X -: Y
0

Ein nettes Feature des Spiels Betreiber ist, dass Sie es Arrays beliebiger Dimension vergleichen können; wenn A ein 3x3x4-Array ist und B ist ein 2x1-Array, dann A-:B kehrt 0.

Um herauszufinden, ob eine Matrix eine Untermatrix einer anderen Matrix ist, können Sie die E: verwenden (Mitglied des Intervalls) Operator wie folgt:

 X =: 2 2 $ 1 2 4 5  
   X
1 2
4 5
   Y =: 4 3 $ (1+i.12)
   Y
 1  2  3
 4  5  6
 7  8  9
10 11 12
   X E. Y
1 0 0
0 0 0
0 0 0
0 0 0

1 an der Oberseite des linken Ergebnis bedeutet, dass der Teil von Y zu X, die gleich ist wie das gegebene Pixel seiner obere linke Ecke. Der Grund dafür ist, dass es in Y eingebetteten Kopien von X überlappen mehrere sein kann, und nur das Markieren das ein Pixel Hier können Sie den Standort jeder passenden Fliese zu sehen.

Answer 2

fand ich zwei Dinge: gawk und ein perl Skript.

Es ist ein anderes Problem, weil String regulären Ausdrücken arbeiten (zum Beispiel sed, grep) Arbeit line-by-line auf eindimensionale Strings.

Es sei denn, Ihre Matrizen sind eindimensionale (im Grunde Vektoren), diese Programme und die Algorithmen sie verwenden, funktionieren nicht.

Viel Glück!

Answer 3

Just Suchzeilen des Musters in jeder Zeile der Eingangsmatrix unter Verwendung von Aho-Corasick (Zeit O (Matrixgrße)). Das Ergebnis sollte klein genug sein, um schnell in das endgültige Ergebnis kommen.

Answer 4

Ich glaube nicht, dass es etwas ganz wie reguläre Ausdrücke für Dimensionen höher als 1 vorhanden ist, aber wenn Sie ein genaues Muster übereinstimmen sollen statt einer Klasse von Mustern, dann könnte ich vorschlagen, dass Sie auf Faltung lesen (oder eher Kreuzkorrelation )

Der Grund dafür ist, gibt es viele hoch optimierte Bibliotheksfunktionen (z. B. IPP), dies zu tun schneller, als Sie jemals auf eigene Faust zu erreichen hoffen konnte. Auch diese Methode Skalen auf höhere Dimensionen als auch.

Auch wird, ist dies nicht unbedingt gibt Ihnen eine „Übereinstimmung“, sondern einen „Peak“ in einer Korrelationskarte, die mit dem Spiel entsprechen, wenn die Spitze auf die Summe der quadratischen Koeffizienten des Musters Sie suchen gleich für.