regexp-like library for matrix pattern search

Question

Is there a library (in any language) that can search patterns in matrixes like regular expressions work for strings ? Something like regular expresions for matrixes, or any matrix pattern search method ?

Okra

you mean like if the matrix is identity matrix/square matrix etc? – Abixah

no I mean if a matrix is a submatrix in another matrix, or if a shape is found in a matrix – Okra

What sort of matrix? Floating point? Is this matrix by chance an image? Is an approximate match ok? – Spook

I'm looking for exact match, is an integer rectangular matrix – Okra

Related #616229 – Okra

Answer 1

If you're not averse to using J, you can find out whether two matrices are equal by using the -: (match) operator. For example:

   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

One nice feature of the match operator is that you can use it to compare arrays of arbitrary dimension; if A is a 3x3x4 array and B is a 2x1 array, then A-:B returns 0.

To find out whether a matrix is a submatrix of another matrix, you can use the E: (member of interval) operator like so:

 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

The 1 at the top left of the result signifies that the part of Y that is equal to X has the given pixel as its upper left-hand corner. The reason for this is that there may be several overlapping copies of X embedded in Y, and only flagging the one pixel lets you see the location of every matching tile.

Misty

Answer 2

I found two things: gawk and a perl script.

It's a different problem because string regular expressions work (e.g., sed, grep) work line-by-line on one-dimensional strings.

Unless your matrices are one-dimensional (basically vectors), these programs and the algorithms they use won't work.

Good luck!

Gon

Answer 3

Just search rows of the pattern in each row of the input matrix using Aho-Corasick (time O(matrix size)). The result should be small enough to quickly join it into the final result.

Telford

Answer 4

I don't think there exists anything quite like regular expressions for dimensions higher than 1, but if you want to match an exact pattern instead of a class of patterns then I might suggest you read up on convolution (or rather Cross-correlation )

The reason being, there are many highly optimized library functions (eg. IPP) for doing this faster than you could ever hope to achieve on your own. Also this method scales to higher dimensions as well.

Also, this won't necessarily give you a "match", but rather a "peak" in a correlation map which will correspond to the match if that peak is equal to the sum of squared coefficients of the pattern you are searching for.

Spook