¿Hay algún análogo bueno/interesante a las expresiones regulares en 2d?

Question

¿Existen buenos (o al menos interesantes pero defectuosos) análogos para las expresiones regulares en dos dimensiones?

En una dimensión que puedo escribir algo como /aaac?(bc)*b?aaa/ para tirar rápidamente una región de alternar b s y s c con un borde de al menos tres a s. Quizás lo más importante es que puedo volver un mes después y ver de un vistazo lo que está buscando.

Me encuentro escribiendo código personalizado para problemas análogos en 2d (algunos mucho más complicados/restringidos) y sería bueno tener una notación más concisa y estandarizada, incluso si tengo que escribir el motor detrás de él mismo .

Un segundo ejemplo podría llamarse "encontrar el +". El objetivo es ubicar una columna de 3 o más a s, una b entre corchetes por 3 o más a s con tres o más a s más abajo. Debe coincidir:

..7...hkj.k f 
7...a h o j 
----a-------- 
j .a,g- 8 9 
.aaabaaaaa7 j 
k .a,,g- h j 
hh a----? j 
    a hjg 

y podría ser escrito como [b^(a {3}) v (a {3})> ({3} un) < (a {3})] o ..

Sugerencias?

Answer 1

Al no ser un experto en expresiones regulares, pero al encontrar el problema interesante, miré a mi alrededor y encontré este interesante blog entry. Especialmente la sintaxis utilizada allí para definir la expresión regular 2D parece atractiva. El documento vinculado allí podría decirle más que a mí.

actualización de comentario: Aquí está el enlace a la página del autor principal donde se puede descargar el documento vinculado "idiomas de dos dimensiones": http://www.mat.uniroma2.it/~giammarr/Research/pubbl.html

Answer 2

Las expresiones regulares están diseñadas para modelar patrones en una dimensión. Según lo entiendo, quieres unir patrones en una matriz bidimensional de caracteres.

¿Se pueden usar expresiones regulares? Eso depende de si la propiedad que está buscando se puede descomponer en componentes que pueden coincidir en una dimensión o no. Si es así, puede ejecutar sus expresiones regulares en columnas y filas, y buscar intersecciones en los conjuntos de soluciones de esos. Dependiendo del problema particular que tenga, esto puede resolver el problema o puede encontrar áreas en su matriz 2D que probablemente sean soluciones.

Si su problema es descomponible o no, creo que escribir un código personalizado será inevitable. Pero al menos parece un problema interesante, por lo que el trabajo debe ser agradable.

Answer 3

Básicamente está hablando de un spatial query language. Hay muchos por ahí si busca consultas espaciales, consultas geográficas y consultas gráficas. La parte espacial generalmente se reduce a puntos, líneas y objetos en una región que tienen otros atributos dados. Las regiones se pueden especificar como polígonos, la distancia desde un punto (por ejemplo, círculos), la distancia desde una característica lineal como una carretera, todos los puntos a un lado de una entidad lineal, etc. Puede acceder a consultas más complejas como establecer de todos los vecinos más cercanos, el camino más corto, vendedor ambulante y teselaciones como los diagramas de Delaunay y los diagramas de Voronoi.

Answer 4

Buen problema.

Primero, pregúntate si puedes restringir el patrón a un patrón "+", o si necesitarías probar/hacer coincidir rectángulos también. Por ejemplo, un rectángulo de [bc] con a frontera de a podría coincidir con el rectángulo central abajo, sino que también coincida con forma de "+" del [c([bc]*a})v([bc]*a)>([bc]*a)<([bc]*a)] (en su sintaxis)

xxxaaaaaxxx 
yzyabcba12d 
defabcbass3 
oreabcba3s3 
s33aaaaas33 
k388x.egiee 

Si se puede limitar a un "+" luego su tarea es mucho más fácil. Como dijo ShuggyCoUk, el análisis de un RE suele ser equivalente a un DFSM, pero para una sola entrada serial que simplifica mucho las cosas.

En su motor "RE +", tendrá que depurar no solo el motor, sino también cada lugar en el que se ingresan las expresiones. Me gustaría que el compilador capte los errores que pueda. Teniendo en cuenta esto, también se podría utilizar algo que era explícitamente cuatro de RE, como:

REPlus engine = new REPlus('b').North("a{3}") 
    .East("a{3}").South("a{3}").West("a{3}"); 

Sin embargo, dependiendo de la implementación esto puede ser engorroso.

Y con respecto al motor transversal: ¿los patrones Norte/Oeste coincidirían con RtL o LtR? Podría importar si los patrones coinciden de forma diferente con o sin sub-partidas codiciosas.

Incidentalmente, creo que el '^' en su ejemplo se supone que es un carácter a la izquierda, fuera del paréntesis.