regexp-come libreria per ricerca del modello a matrice

Question

C'è una libreria (in qualsiasi lingua) che può cercare i modelli in matrici come regolare lavoro espressioni per le stringhe? Qualcosa di simile esprimono tutti regolari per matrici, o qualsiasi metodo di ricerca del modello a matrice?

Answer 1

Se non sei contrario a utilizzare J, è possibile scoprire se due matrici sono uguali utilizzando l'operatore -: (match). Ad esempio:

   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

Una caratteristica dell'operatore partita è che si può utilizzare per confrontare le matrici di dimensione arbitraria; se A è una matrice 3x3x4 ed B è una matrice 2x1, poi ritorna A-:B 0.

Per scoprire se una matrice è una sottomatrice di un'altra matrice, è possibile utilizzare il E: (membro della dell'intervallo) Operatore in questo modo:

 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

Il 1 in alto a sinistra del risultato significa che la parte di Y che è uguale a X contiene il pixel dato come l'angolo superiore sinistro. La ragione di questo è che ci possono essere più sovrapposizione copie di X incorporati in Y, e solo segnalando l'un pixel permette di vedere la posizione di ogni tegola di corrispondenza.

Answer 2

ho trovato due cose: gawk e un perl script.

E 'un problema diverso, perché stringa regolare le espressioni di lavoro (ad esempio, sed, grep) lavoro di linea per linea su stringhe unidimensionali.

A meno che le vostre matrici sono unidimensionale (in pratica vettori), questi programmi e gli algoritmi utilizzati non funzionerà.

In bocca al lupo!

Answer 3

Basta cercare righe del modello in ciascuna riga della matrice di ingresso utilizzando Aho-Corasick (tempo O (dimensione della matrice)). Il risultato dovrebbe essere abbastanza piccolo per unire rapidamente nel risultato finale.

Answer 4

Non credo esista niente di simile espressioni regolari per le dimensioni superiori a 1, ma se si desidera far corrispondere un modello esatto, invece di una classe di modelli, allora potrei suggerire di leggere su circonvoluzione (o meglio Cross-correlazione )

La ragione è che, ci sono molte funzioni di libreria altamente ottimizzati (ad es. IPP) per fare questo più velocemente di quanto si potrebbe mai sperare di raggiungere da soli. Anche questo metodo scale dimensionali superiori pure.

Inoltre, questo non necessariamente dare un "match", ma piuttosto un "picco" in una mappa di correlazione che corrisponderà alla partita se tale picco è uguale alla somma dei coefficienti quadrati del modello si sta cercando per.