REGEXP similar a la biblioteca para la búsqueda patrón de matriz

Question

¿Hay una biblioteca (en cualquier idioma) que se pueden buscar patrones en matrices como el trabajo de las expresiones regulares para las cadenas? Algo así como expresiones regulares para matrices, o cualquier método de búsqueda patrón de la matriz?

Answer 1

Si no está en contra de usar J, se puede averiguar si dos matrices son iguales usando el operador -: (partido). Por ejemplo:

   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 característica interesante del operador partido es que se puede usar para comparar matrices de dimensión arbitraria; si A es una matriz 3x3x4 y B es una matriz de 2x1, a continuación, vuelve A-:B 0.

Para saber si una matriz es una submatriz de la otra matriz, puede utilizar la E: (miembro de intervalo) operador de este 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

El 1 en la parte superior izquierda de las significa resultado de que la parte de Y que es igual a X tiene el píxel dado como su esquina superior izquierda. La razón de esto es que puede haber varias copias de X incrustados en Y se solapan, y sólo marcar el un píxel le permite ver la ubicación de cada ficha coincidente.

Answer 2

He encontrado dos cosas: gawk y una perl guión.

Es un problema diferente porque la cadena de las expresiones regulares (por ejemplo, sed, grep), línea por línea de trabajo en las cuerdas de una sola dimensión.

A menos que sus matrices son unidimensionales (básicamente vectores), estos programas y los algoritmos que utilizan no funcionará.

Buena suerte!

Answer 3

Sólo la búsqueda filas del patrón en cada fila de la matriz de entrada utilizando Aho-Corasick (tiempo O (tamaño de la matriz)). El resultado debe ser lo suficientemente pequeño como para unirse rápidamente en el resultado final.

Answer 4

No creo que exista algo como expresiones regulares de dimensiones superiores a 1, pero si desea hacer coincidir un patrón exacto en lugar de una clase de patrones entonces yo podría sugerir que lea sobre convolución (o más bien Cross-correlación)

La razón es que, hay muchas funciones de biblioteca altamente optimizados (por ejemplo. IPP) para hacer esto más rápido de lo que jamás podría aspirar a lograr por su cuenta. También este método escalas a dimensiones más altas también.

Además, esto no necesariamente le dan una "coincidencia", sino más bien un "pico" en un mapa de correlación que se corresponderá con el partido si ese pico es igual a la suma de los coeficientes al cuadrado del patrón que está buscando para.