Ci sono degli analoghi buoni/interessanti alle espressioni regolari in 2d?

Question

Esistono degli analoghi buoni (o almeno interessanti ma imperfetti) alle espressioni regolari in due dimensioni?

In una dimensione posso scrivere qualcosa di simile /aaac?(bc)*b?aaa/ per tirare rapidamente una regione in cui si alternano b s e c s con un bordo di almeno tre a s. Forse altrettanto importante, posso tornare un mese dopo e vedere a colpo d'occhio cosa sta cercando.

Mi sto ritrovando a scrivere codice personalizzato per problemi analoghi in 2d (alcuni molto più complicati/limitati) e sarebbe bello avere una notazione più concisa e standardizzata, anche se devo scrivere il motore dietro di esso .

Un secondo esempio potrebbe essere chiamato "trova il +". L'obiettivo è individuare una colonna di 3 o più a s, un tra parentesi da 3 o più a s con tre o più a s di seguito. Deve corrispondere:

..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 

e potrebbe essere scritto come [b^(a {3}) v (una {3})> (un {3}) < (un {3})] o ..

Suggerimenti?

Answer 1

Non essendo un esperto di regex, ma trovando il problema interessante, mi sono guardato intorno e ho trovato questo interessante blog entry. Soprattutto la sintassi utilizzata per definire la regex 2D sembra interessante. La carta collegata lì potrebbe dirti più di me.

Aggiornamento da commento: Ecco il link alla pagina dell'autore primario dove è possibile scaricare il documento collegato "linguaggi bidimensionali": http://www.mat.uniroma2.it/~giammarr/Research/pubbl.html

Answer 2

Le espressioni regolari sono progettate per modellare modelli in una dimensione. A quanto ho capito, vuoi abbinare i pattern in una matrice bidimensionale di caratteri.

È possibile utilizzare le espressioni regolari? Dipende se la proprietà che stai cercando è scomposta in componenti che possono essere abbinati in una dimensione o meno. In tal caso, è possibile eseguire le espressioni regolari su colonne e righe e cercare le intersezioni tra i set di soluzioni. A seconda del problema specifico che hai, questo può risolvere il problema oppure potrebbe trovare aree nel tuo array 2d che potrebbero essere soluzioni.

Se il problema è scomposto o meno, penso che scrivere un codice personalizzato sarà inevitabile. Ma almeno sembra un problema interessante, quindi il lavoro dovrebbe essere piacevole.

Answer 3

Stai parlando essenzialmente di un spatial query language. Ci sono molte cose fuori se cerchi query spaziali, query geografiche e query grafiche. La parte spaziale generalmente scende a punti, linee e oggetti in una regione che ha altri attributi dati. Le regioni possono essere specificate come poligoni, distanza da un punto (es. Cerchi), distanza da una caratteristica lineare come una strada, tutti i punti su un lato di una caratteristica lineare, ecc ... È quindi possibile entrare in query più complesse come set di tutti i vicini più vicini, percorso più breve, commesso viaggiatore e tessellazioni come TIN di Delaunay e diagrammi di Voronoi.

Answer 4

Bel problema.

Prima di tutto, chiedetevi se è possibile vincolare il modello a un motivo "+" o se è necessario testare/abbinare i rettangoli anche. Per esempio, un rettangolo di di [bc] con a bordo di a sarebbe abbinare il rettangolo centrale in basso, ma sarebbe anche corrispondere una forma a "+" di [c([bc]*a})v([bc]*a)>([bc]*a)<([bc]*a)] (nella sintassi)

xxxaaaaaxxx 
yzyabcba12d 
defabcbass3 
oreabcba3s3 
s33aaaaas33 
k388x.egiee 

Se è possibile vincolare a un "+", quindi il tuo compito è molto più facile. Come diceva ShuggyCoUk, l'analisi di un RE è solitamente equivalente a un DFSM, ma per un singolo input seriale che semplifica notevolmente le cose.

Nel tuo motore "RE +", dovrai eseguire il debug non solo del motore, ma anche di ogni posto in cui sono inserite le espressioni. Mi piacerebbe che il compilatore catturasse tutti gli errori possibili. Dato che, si potrebbe anche usare qualcosa che è stato esplicitamente quattro RE di, come:

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

Tuttavia, a seconda dell'implementazione questo può essere ingombrante.

E per quanto riguarda il motore trasversale, i modelli Nord/Ovest corrispondono a RtL o LtR? Potrebbe importare se i modelli coincidono in modo diverso con o senza avidi sottotitoli.

Per inciso, penso che il "^" nel tuo esempio debba essere un carattere a sinistra, al di fuori della parentesi.