Czy istnieją jakieś dobre/interesujące analogi do wyrażeń regularnych w 2d?

Question

Czy istnieją jakieś dobre (lub co najmniej interesujące, ale błędne) analogi do wyrażeń regularnych w dwóch wymiarach?

W jednym wymiarze mogę napisać coś podobnego /aaac?(bc)*b?aaa/ aby szybko wyciągnąć regionu zmiennego b s i c s przy granicy z co najmniej trzech a s. Być może, co równie ważne, mogę wrócić miesiąc później i zobaczyć na pierwszy rzut oka, czego szuka.

jestem znalezieniem się pisania kodu niestandardowego do analogicznych problemów w 2D (niektóre znacznie bardziej skomplikowane/ograniczona) i byłoby miło mieć bardziej zwięzły i znormalizowany zapis, nawet jeśli muszę napisać silnik za to sam .

Drugi przykład może być nazwany "znajdź +". Celem jest zlokalizowanie kolumny 3 lub większej liczby a s, b w nawiasie za pomocą 3 lub większej liczby a s z trzema lub więcej a s poniżej. powinien pasować:

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

i może być zapisane jako [b^(a {3}) V (A {3})> (a {3}) < (a {3})] lub ..

Sugestie?

Answer 1

Nie będąc ekspertem od regex, ale znajdując problem interesujący, rozejrzałem się i znalazłem to interesujące blog entry. Zwłaszcza składnia używana do definiowania regexu 2D wygląda interesująco. Wiążący się z tobą artykuł może ci powiedzieć więcej niż ja.

Aktualizacja z komentarzem: Oto link do strony głównym autorem, gdzie można pobrać powiązany papier „Języki dwuwymiarowe”: http://www.mat.uniroma2.it/~giammarr/Research/pubbl.html

Answer 2

Wyrażenia regularne służą do modelowania wzorów w jednym wymiarze. Jak rozumiem, chcesz dopasować wzory w dwuwymiarową tablicę znaków.

Czy potrafisz używać wyrażeń regularnych? To zależy od tego, czy poszukiwana właściwość rozkłada się na komponenty, które można dopasować w jednym wymiarze, czy nie. Jeśli tak, możesz uruchamiać wyrażenia regularne w kolumnach i wierszach i szukać przecięć w zestawach rozwiązań z nich. W zależności od konkretnego problemu może to rozwiązać problem, lub może znaleźć obszary w twojej tablicy 2d, które prawdopodobnie będą rozwiązaniami.

Bez względu na to, czy Twój problem jest rozkładalny, czy nie, myślę, że napisanie niestandardowego kodu będzie nieuniknione. Ale przynajmniej brzmi to interesująco, więc praca powinna być przyjemna.

Answer 3

W gruncie rzeczy mówisz o spatial query language. Istnieje wiele możliwości, jeśli poszukujesz zapytań przestrzennych, zapytań geograficznych i zapytań graficznych. Część przestrzenna zazwyczaj sprowadza się do punktów, linii i obiektów w regionie, który ma inne dane atrybuty. Regiony mogą być określane jako wielokąty, odległość od punktu (np. Okręgi), odległość od elementu liniowego, np. Drogi, wszystkie punkty po jednej stronie liniowego elementu itp. Możesz wtedy uzyskać bardziej złożone zapytania, takie jak zestaw wszystkich najbliższych sąsiadów, najkrótszą ścieżkę, komiwojażera i tesselacje, takie jak diody Delaunay TIN i Voronoi.

Answer 4

Przyjemny problem.

Najpierw zadaj sobie pytanie, czy możesz ograniczyć wzór do wzoru "+", czy też musisz przetestować/dopasować również prostokąty. Na przykład, prostokąt od [bc] z a granicy a pasowałby prostokąt środkowy poniżej, ale również dopasować „+” kształt [c([bc]*a})v([bc]*a)>([bc]*a)<([bc]*a)] (w składni)

xxxaaaaaxxx 
yzyabcba12d 
defabcbass3 
oreabcba3s3 
s33aaaaas33 
k388x.egiee 

Jeśli można ograniczyć go do "+", wtedy twoje zadanie jest znacznie łatwiejsze. Jak powiedział ShuggyCoUk, parsowanie RE jest zwykle równoznaczne z DFSM - ale dla pojedynczego, szeregowego wejścia, które znacznie upraszcza.

W swoim silniku "RE +" będziesz musiał debugować nie tylko silnik, ale także każde miejsce, w którym wprowadzane są wyrażenia. Chciałbym, aby kompilator złapał wszelkie możliwe błędy. Biorąc pod uwagę, że można też użyć czegoś, co zostało wyraźnie cztery Re, jak:

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

Jednakże, w zależności od implementacji może to być kłopotliwe.

Co się tyczy silnika traversal - czy wzorce North/West pasują do RtL lub LtR? Może to mieć znaczenie, jeśli wzory pasują do siebie z lub bez chciwych podpasek.

Nawiasem mówiąc, myślę, że "^" w twoim przykładzie ma być jednym znakiem po lewej stronie, poza nawiasem.