Development Tip

ASCII "이미지"에서 "수직"정규식 일치

yourdevel 2020. 12. 11. 20:24

ASCII "이미지"에서 "수직"정규식 일치

참고 : 이것은 최신 정규식 버전의 가능성에 대한 질문입니다. 다른 방법을 사용하여이 문제를 해결하는 가장 좋은 방법이 아닙니다. 이전 질문 에서 영감을 얻었 지만 정규식에 국한되지 않습니다.

문제

ASCII "이미지"/ art / map / string에서 다음과 같이 :

....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....

세 개의 간단한 수직선 형성을 찾고 싶습니다 X.

X
X
X

이미지의 줄 수는 가변적이며 각 줄 의 너비 도 가변적입니다.

질문 (들)

정규식 (PCRE / PHP, Perl, .NET 또는 유사)을 사용하면 다음을 수행 할 수 있습니다.

그러한 형성이 존재하는지 확인
그러한 포메이션의 수를 세거나 모두의 시작점과 일치합니다 (위의 예에서는 4 개).

질문 1에 대한 답변

첫 번째 질문에 답하려면 다음을 사용할 수 있습니다.

(?xm)                    # ignore comments and whitespace, ^ matches beginning of line
^                        # beginning of line
(?:
    .                    # any character except \n
    (?=                  # lookahead
        .*+\n            # go to next line
        ( \1?+ . )       # add a character to the 1st capturing group
        .*+\n            # next line
        ( \2?+ . )       # add a character to the 2nd capturing group
    )
)*?                      # repeat as few times as needed
X .*+\n                  # X on the first line and advance to next line
\1?+                     # if 1st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X .*+\n                  # X on the 2nd line and advance to next line
\2?+                     # if 2st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X                        # X on the 3rd line

Online demo

이 표현식은 Perl, PCRE, Java에서 작동하며 .NET에서 작동해야합니다.

표현식은 자체 참조 캡처 링 그룹과 함께 미리보기를 사용하여 미리보기가 반복 될 때마다 문자를 추가합니다 ( "계수"에 사용됨).

\1?+수단이 경우 \1일치 (또는 정의)를 소비하고 (안 철수 할) 다시 제공하지 않습니다. 이 경우 (?(1) \1 ). 정의 된 \1경우 일치를 의미 \1합니다.

polygenelubricants 는 어떻게 a ^ nb ^ n을 Java 정규식과 일치시킬 수 있습니까?에 대한 그의 답변 에서 역 참조로 이러한 종류의 예견을 매우 잘 설명합니다 . . (그는 역 참조 및 둘러보기와 관련된 Java 정규식에 대한 다른 인상적인 트릭에 대해서도 작성했습니다.)

질문 2에 대한 답변

일반 매칭

일치를 사용하고 일치 수에 대한 답변 (개수)을 요구하는 경우 질문 2 답변은 다음과 같습니다.

제한된 lookbehind를 가진 정규식 버전에서는 직접 해결할 수 없습니다 . Java 및 .NET과 같은 다른 버전도 가능합니다 (예 : m.buettner의 .NET 솔루션 ).

따라서 Perl 및 PCRE (PHP 등)의 일반 정규식 일치는이 경우이 질문에 직접 답할 수 없습니다.

(세미?) 증거

가변 길이 lookbehind를 사용할 수 없다고 가정합니다.

어떤 식 으로든 X.
이를 수행하는 유일한 방법은 그것들을 일치시키는 것이며, 가변 길이 lookbehinds를 사용할 수 없기 때문에 적어도 줄의 시작에서 일치를 시작해야합니다.
줄의 시작 부분에서 경기를 시작하면 한 줄에 최대 하나의 경기 만 얻을 수 있습니다.

한 줄에 여러 번 발생할 수 있으므로 모두 계산하지 않고 정답을 제공하지 않습니다.

길이 / 간접 솔루션

반면에 일치 또는 대체 결과의 길이로 답변을 수락하면 두 번째 질문 은 PCRE 및 Perl (및 기타 버전)에서 답변 할 수 있습니다 .

이 솔루션은 m.buettner의 멋진 "부분 PCRE 솔루션"을 기반으로하고 영감을 받았습니다 .

다음 표현식의 모든 일치 항목을으로 간단히 대체 $3하여 결과 문자열의 길이로 질문 2 (관심있는 패턴 수)에 대한 답을 얻을 수 있습니다.

^
(?:
    (?:                   # match .+? characters
        .
        (?=               # counting the same number on the following two lines
            .*+\n
            ( \1?+ . )
            .*+\n
            ( \2?+ . )
        )
    )+?
    (?<= X )              # till the above consumes an X
    (?=                   # that matches the following conditions
        .*+\n
        \1?+
        (?<= X )
        .*+\n
        \2?+
        (?<= X )
    )
    (?=                   # count the number of matches
        .*+\n
        ( \3?+ . )        # the number of matches = length of $3
    )
)*                        # repeat as long as there are matches on this line
.*\n?                     # remove the rest of the line

Perl에서 다음과 같이 작성할 수 있습니다.

$in =~ s/regex/$3/gmx;
$count = length $in;

Online demo

이 표현은 위의 질문 1에 대한 솔루션과 유사 X하며, 첫 번째 예측에서 일치하는 문자 를 포함하도록 일부 수정 하고 수량 자로 래핑하고 수량 자의 일치 수를 계산합니다.

직접 일치를 제외하고 이것은 (정규식 외에 추가 코드 현명한) 최대한 가깝고 질문 2에 대한 대답이 될 수 있습니다.

테스트 케이스

위 솔루션에 대한 일부 테스트 사례 및 결과. 숫자 답 (결과 문자열의 길이)을 보여주는 결과와 괄호 안에 대체 후 결과 문자열이 표시됩니다.

Test #0:
--------------------
X
X
X

result: 1 (X)


Test #1:
--------------------
..X....
..X....
..X....

result: 1 (.)


Test #2:
--------------------
..X.X..
..X.X..
....X..

result: 1 (.)


Test #3:
--------------------
..X....
..X....
...X...

result: 0 ()


Test #4:
--------------------
..X....
...X...
..X....

result: 0 ()


Test #5:
--------------------
....X..
.X..X..
.X.....

result: 0 ()


Test #6:
--------------------
.X..X..
.X.X...
.X.X...

result: 1 (.)


Test #7:
--------------------
.X..X..
.X..X..
.X..X..

result: 2 (.X)


Test #8:
--------------------
XXX
XXX
XXX

result: 3 (XXX)


Test #9:
--------------------
X.X.X
XXXXX
XXXXX
.X.X.

result: 5 (XXXXX)


Test #10:
--------------------
1....X.......
2..X..X...X....
3X.X...X..X.....
4X....XXXXXX.....
5X..XXX...........
6.....X..........
7.........X....X
8..X......X....X....
9..X......X....X....X...
A....X.....
B.X..X..
C.....
XXX
XXX
XXX
.

result: 8 (3458.XXX)

편집하다

다음 솔루션에는 두 가지 심각한 문제가 있습니다.

너무 많이 진행 XXX되기 때문에 같은 줄에서 시작하는 여러 시퀀스를 일치시킬 수 없습니다 pos.
두 번째 솔루션은 올바르지 않습니다. 두 개가 X서로 위에 있는 연속 된 행과 일치 합니다. 반드시 연속 3 개일 필요는 없습니다.

따라서 모든 upvotes (그리고 현상금) 중 하나의 가야한다 m.buettner 의 ' 포괄적 .NET 응답 또는 매혹적인 PCRE 응답 에서 Qtax 자신.

원래 답변

이것은 정규식에 Perl 코드를 포함하는 대답입니다. Perl 정규식은 코드를 사용하여 정규식 내에서 임의의 조건을 주장하거나 부분 정규식을 내보낼 수 있기 때문에 정규 언어 또는 컨텍스트없는 언어 일치에만 국한되지 않고 Chomsky 계층 구조에서 상위 언어의 일부와 일치 할 수 있습니다.

일치시키려는 언어는 다음과 같이 정규식 용어로 설명 할 수 있습니다.

^ .{n} X .*\n
  .{n} X .*\n
  .{n} X

n숫자는 어디에 있습니까 ? 이것은 상황에 맞는 언어의 표준 예인 a ⁿ b ⁿ c ⁿ 언어 와 일치하는 것만 큼 복잡 합니다.

첫 번째 줄을 쉽게 일치시키고 Perl 코드를 사용하여 다른 줄에 대한 정규식을 내보낼 수 있습니다.

    /^ (.*?) X
       (?: .*\n (??{"." x length($1)}) X){2}
    /mx

짧았 어! 그것은 무엇을합니까?

^ (.*?) X줄의 시작 부분에 고정되고, 가능한 한 줄 바꿈이 아닌 문자와 일치 한 다음 X. Xas 캡처 그룹 까지의 라인을 기억합니다 $1.
우리는 줄의 나머지 부분과 일치하는 그룹을 두 번 반복 한 다음 개행 문자와 같은 길이의 문자열과 일치하는 정규식을 삽입합니다 $1. 그 후에는 X.

이 정규식은 이제 X서로 위에 세 개가있는 모든 문자열과 일치합니다 .

이러한 모든 시퀀스 를 추출 하려면 멋지게 만들어야합니다. 시퀀스가 겹칠 수 있기 때문에

.X
XX
XX
X.

다음 경기가 시작되는 위치는 첫 번째 경기를 지나서는 안됩니다 X. lookbehind 및 lookahead를 통해이를 수행 할 수 있습니다. Perl은 일정한 길이의 lookbehind 만 지원하지만 \K유사한 의미를 제공 하는 이스케이프 기능이 있습니다. 그러므로

/^ (.*?) \K X
   (?=( (?: .*\n (??{"."x length($1)}) X ){2} ))
/gmx

세 개의 수직 항목의 모든 시퀀스와 일치합니다 X. 테스트 시간 :

$ perl -E'my$_=join"",<>; say "===\n$1X$2" while /^(.*?)\KX(?=((?:.*\n(??{"."x length($1)})X){2}))/gmx' <<'END'
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXX
===
X.X...X..X.....
X....XXXXXX.....
X
===
X....XXXXXX.....
X..XXX...........
.....X
===
..............X
..X...........X....
..X...........X

참고 : 이는 Perl 5, v10 이상에서 사용할 수있는 실험적 정규식 기능에 의존합니다. 코드는 v16 perl로 테스트되었습니다.

임베디드 코드가없는 솔루션

선을 보자

...X...\n
...X..\n

우리 ...는 각 줄의 앞부분이 같은 길이 라고 주장하고 싶습니다 . 기본 케이스를 사용하여 재귀를 수행 할 수 있습니다 X.*\n.

(X.*\n|.(?-1).)X

선의 시작 부분에 고정하면 두 개의 수직선을 일치시킬 수 있습니다 X. 두 줄 이상을 일치 시키려면 미리보기에서 재귀를 수행 한 다음 일치 위치를 다음 줄로 이동하고 반복해야합니다. 이를 위해 우리는 단순히 .*\n.

결과적으로 세 개의 수직 Xes가 있는 문자열과 일치 할 수있는 다음 정규식이 생성됩니다 .

/ ^
  (?:
    (?=( X.*\n | .(?-1). ) X)
    .*\n # go to next line
  ){2}
/mx

그러나 우리는 그러한 모든 시퀀스를 일치시키고 싶기 때문에 이것만으로는 충분하지 않습니다. 이를 위해 본질적으로 전체 정규식을 미리보기에 넣습니다. 정규식 엔진은 새 일치를 생성하기 위해 매번 위치를 전진시킵니다.

/ ^
  (?=
    (
      (?:
          (?= (X.*\n | .(?-1). ) X)
          .*\n # go to next line
      ){2}
      .* # include next line in $1
    )
  )
/mx

테스트 시간 :

$ perl -E'my$_=join"",<>; say "===\n$1" while /^(?=((?:(?=(X.*\n|.(?-1).)X).*\n){2}.*))/gmx' <<'END'
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
===
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
===
X....XXXXXX.....
X..XXX...........
.....X..........
===
..............X
..X...........X....
..X...........X....X...

따라서 이것은 임베디드 코드를 사용하는 솔루션과 마찬가지로 작동합니다. 즉, 각 라인 X그룹을 각 Xes 그룹이 아닌 수직 es 와 일치시킵니다. (사실이 솔루션은 임베디드 코드보다 나에게 더 취약 해 보입니다)

우선 : 훌륭한 질문입니다. 정규식 엔진을 한계까지 끌어들이는 것이 매우 유익하다고 생각합니다.

기본 .NET 솔루션

여러분은 코멘트에서 .NET으로 쉽게 할 수 있다고 말했지만 아직 대답이 없기 때문에 하나를 쓸 것이라고 생각했습니다.

.NET의 가변 길이 lookbehind 및 균형 그룹을 사용하여 질문 1과 2를 모두 해결할 수 있습니다. 대부분의 작업은 밸런싱 그룹에 의해 수행되지만 동일한 라인에서 시작하는 여러 일치 항목을 감지 할 수 있으려면 가변 길이 lookbehind가 중요합니다.

어쨌든 패턴은 다음과 같습니다.

(?<=                  # lookbehind counts position of X into stack
  ^(?:(?<a>).)*       # push an empty capture on the 'a' stack for each character
                      # in front of X
)                     # end of lookbehind

X                     # match X

(?=.*\n               # lookahead checks that there are two more Xs right below
  (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
  (?(a)(?!))          # make sure that stack 'a' is empty
  X.*\n               # match X and the rest of the line
  (?:(?<-b>).)*       # while we can pop an element from stack 'b', and consume
                      # a character
  (?(b)(?!))          # make sure that stack 'b' is empty
  X                   # match a final X
)                     # end of lookahead

이 패턴은 줄의 시작 부분을 일치시키기 RegexOptions.Multiline위해 와 함께 사용해야 ^합니다 (그리고 분명히 RegexOptions.IgnorePatternWhitespacefreespacing 모드가 작동하기 위해).

다음은 몇 가지 추가 설명입니다.

처음 X를 제외한 모든 것을 둘러보기에 넣음으로써 일치 항목이 겹치거나 같은 줄에서 시작하는 일치 항목도 문제가 없습니다. 그러나 lookbehind는 이러한 종류의 솔루션을 .NET으로 확실히 제한하는 가변 길이 여야합니다.

나머지는 균형 잡힌 그룹에 대한 좋은 이해에 의존합니다. 그 자체로 꽤 긴 답변을 만들기 때문에 여기에서 자세히 설명하지 않겠습니다 . ( 더 자세한 정보는 MSDN 및 이 블로그 게시물 참조 )

lookbehind는 일치 ^.*하므로 줄의 시작까지 모든 것이 있지만 모든 .빈 캡처를 stack에 푸시하여 스택 의 크기로 a우리의 위치를 계산합니다 X.

그런 다음 내다에있는 라인의 나머지 부분을 소모 후, 우리는 다시 단지 일치 .*하지만, 각 소비하기 전에 ., 우리는 스택에서 하나 개의 요소 팝업 a(한 번 실패 리드 a비어을)과에 빈 캡처를 밀어 b'우리가 돈 것을 ( t 세 번째 줄에 몇 개의 문자가 있어야하는지 잊어 버림).

전체 스택을 실제로 비우기 위해 (?(a)(?!)). 이것은 (?!)스택 a이 비어 있지 않은 경우 일치를 시도하는 조건부 패턴입니다 (그렇지 않으면 단순히 건너 뜁니다). 그리고 (?!)항상 실패하는 비어있는 부정적인 예견입니다. 따라서 이것은 단순히 " a비어 있지 않습니까? 실패. 그렇지 않으면 계속"으로 인코딩 됩니다.

이제 새 줄에서 정확한 양의 문자를 사용했음을 알았으므로 a X와 나머지 줄 을 일치 시키려고합니다 . 그런 다음 stack으로 동일한 프로세스를 다시 반복합니다 b. 이제 새 스택으로 푸시 할 필요가 없습니다. 이것이 작동하면 완료된 것입니다. b이 후 비어 있는지 확인 하고 세 번째 X.

마지막으로 최적화 관련 참고 사항 : 모든 반복이 원자 그룹으로 래핑되어있는 경우에도이 패턴은 여전히 작동합니다 (따라서 .NET에서 지원하지 않는 소유 한정자를 에뮬레이트 함)! 이것은 많은 역 추적을 절약 할 것입니다. 또한, 경우에 우리는 적어도 원자 그룹의 스택 터지는 한정사, 우리는 모두 제거 할 수 넣어 (?(...)(?!))검사 (이 만 경우에 필요할 때, 앞의 반복은 철수해야했다 경우).

완전한 .NET 솔루션

(가장 용감한 모험가 만이 나를 따라 내려 가려는 정말 어두운 동굴로 들어가야합니다 ...)

의견에서 논의했듯이이 솔루션에는 한 가지 단점이 있습니다. 즉, 겹치는 일치를 계산합니다. 예

..X..
..X..
..X..
..X..

첫 번째 줄과 두 번째 줄에 하나씩 두 개의 일치 항목을 제공합니다. 우리는 이것을 피하고 하나의 일치 만보고하고 싶습니다 (또는 6-8 X초가있는 경우 2 개, 9-11 초가있는 경우 3 개 등 X). 또한 1 일, 4 일, 7 일, ...에서 경기를보고하고 싶습니다 X.

우리는 우리의 요구 사항을 충족시키는 X다른 3의 정수 배수가 첫 번째 앞에 X오도록 요구함으로써이 솔루션을 허용하도록 위의 패턴을 조정할 수 있습니다 . 이를 확인하는 기본 아이디어는 이전과 동일한 스택 조작을 사용합니다 (단, 3 개의 스택을 찾은 후 X시작 위치에 도달하도록 3 개의 스택 사이를 이동하는 것을 제외하고 ). 이를 위해 우리는 룩 비하인드를 약간 조정해야합니다.

그래도 문제가 있습니다. .NET의 가변 길이 lookbehind는 RightToLeftMode패턴을 오른쪽에서 왼쪽으로 읽고 일치시키는 또 다른 .NET 고유 기능을 사용합니다 . 일반적으로 이것은 우리를 괴롭힐 필요가 없지만 이것을 균형 잡힌 그룹과 결합하면 불쾌한 놀라움 이 생길 수 있습니다 . 특히 캡처 스택이 어떻게 진화하는지 고려할 때 표현식을 오른쪽에서 왼쪽 (또는 아래에서 위로)으로 구성하고 읽어야합니다.

따라서 다음 식 (및 내 주석)을 읽을 때 가장 바깥 쪽 lookbehind의 끝에서 시작합니다 (조금 스크롤해야 함). 즉, 유일한 최상위 수준 바로 앞 X; 그런 다음 맨 위로 끝까지 읽으십시오. 그런 다음 lookbehind 후에 계속하십시오.

(?<=                  
  # note that the lookbehind below does NOT affect the state of stack 'a'!
  # in fact, negative lookarounds can never change any capturing state.
  # this is because they have to fail for the engine to continue matching.
  # and if they fail, the engine needs to backtrack out of them, in which
  # case the previous capturing state will be restored.
  (?<!                # if we get here, there is another X on top of the last
                      # one in the loop, and the pattern fails
    ^                 # make sure we reached the beginning of the line
    (?(a)(?!))        # make sure that stack 'a' is empty
    (?:(?<-a>).)*     # while we can pop an element from stack 'a', and consume
                      # a character
    X.*\n             # consume the next line and a potential X
  )
  # at this point we know that there are less than 3 Xs in the same column
  # above this position. but there might still be one or two more. these
  # are the cases we now have to eliminate, and we use a nested negative
  # lookbehind for this. the lookbehind simply checks the next row and
  # asserts that there is no further X in the same column.
  # this, together with the loop, below means that the X we are going to match
  # is either the topmost in its column or preceded by an integer multiple of 3
  # Xs - exactly what we are looking for.
  (?:

    # at this point we've advanced the lookbehind's "cursor" by exactly 3 Xs
    # in the same column, AND we've restored the same amount of captures on
    # stack 'a', so we're left in exactly the same state as before and can
    # potentially match another 3 Xs upwards this way.
    # the fact that stack 'a' is unaffected by a full iteration of this loop is
    # also crucial for the later (lookahead) part to work regardless of the
    # amount of Xs we've looked at here.

    ^                 # make sure we reached the beginning of the line
    (?(c)(?!))        # make sure that stack 'a' is empty
    (?:(?<-c>)(?<a>).)* # while we can pop an element from stack 'c', push an
                      # element onto 'a' and consume a character
    X.*\n             # consume the next line and a potential X
    (?(b)(?!))        # make sure that stack 'b' is empty
    (?:(?<-b>)(?<c>).)* # while we can pop an element from stack 'b', push an
                      # element onto 'c' and consume a character
    X.*\n             # consume the next line and a potential X
    (?(a)(?!))        # make sure that stack 'a' is empty
    (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
    X.*\n             # consume the next line and a potential X
  )*                  # this non-capturing group will match exactly 3 leading
                      # Xs in the same column. we repeat this group 0 or more
                      # times to match an integer-multiple of 3 occurrences.
  ^                   # make sure we reached the beginning of the line
  (?:(?<a>).)*        # push an empty capture on the 'a' stack for each
                      # character in front of X
)                     # end of lookbehind (or rather beginning)

# the rest is the same as before    

X                     # match X
(?=.*\n               # lookahead checks that there are two more Xs right below
  (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
  (?(a)(?!))          # make sure that stack 'a' is empty
  X.*\n               # match X and the rest of the line
  (?:(?<-b>).)*       # while we can pop an element from stack 'b', and consume
                      # a character
  (?(b)(?!))          # make sure that stack 'b' is empty
  X                   # match a final X
)                     # end of lookahead

RegexHero.net의 작업 데모.

이번에는 패턴과 함께 모든 설명을 제대로 산재했습니다. 따라서 위에서 권장 한 방식으로 패턴을 읽으면 필요할 때 바로 설명을 얻을 수 있습니다.

이제 그것은 짐승의 지옥이었습니다. 그러나 지금은 전체 사양을 충족하고 .NET의 정규식 풍미가 실제로 얼마나 강력한 지 보여줍니다. 그리고 이것은 매우 끔찍해 보이지만 (오른쪽에서 왼쪽으로) 이것은 PCRE (재귀 또는 기타 사용)와 유사한 솔루션보다 훨씬 쉽게 이해할 수 있다고 생각합니다.

Kobi가 아래 주석에서 언급했듯이, 결과가 단일 일치의 여러 캡처에서 발견된다는 것을 수락하면 약간 단축 될 수 있습니다 (예 : 7 X초 열이있는 경우 하나의 일치 만 얻지 만 특정 그룹에서 2 번 캡처). 메인 (예측) 파트를 1 회 이상 반복하고 이니셜을 캡처하여이를 수행 할 수 있습니다 X(모든 것을 미리보기에 넣음). 그런 다음 lookbehind는 Xs의 트리플을 계산할 필요 가 없지만 선행이 없는지 확인하기 만하면 X됩니다. 이것은 아마도 패턴의 크기를 반으로 줄일 것입니다.

부분 PCRE 솔루션

(마지막 해결책을 통해 용감한 모험가들이 나를 따라 갔다면 아마 다음 여행에서 미치광이들과 함께 남았을 것입니다 ...)

위의 솔루션이 PCRE와 어떻게 비교되는지에 대해 방금 말한 것을 증명하기 위해 PCRE에서 전체 문제를 원격으로 해결할 수있는 방법을 살펴 보겠습니다. 가변 길이 룩 비하인드 (lookbehind)와 밸런싱 그룹없이 더 열심히 일해야합니다.

Qtax (the OP)는 X자기 참조 그룹을 사용하여 첫 번째 질문 (문자열에 열이 포함되어 있는지 확인)에 대한 훌륭한 솔루션을 제공했습니다 . 이것은 매우 우아하고 컴팩트 한 솔루션입니다. 그러나 각 일치 항목은 줄의 X시작에서 열을 시작 하는 지점으로 이동 하고 일치 항목이 겹칠 수 없기 때문에 한 줄에 여러 일치 항목을 얻을 수 없습니다. 우리는 모든 것을 미리보기에 넣을 수 있지만 (실제로 일치하는 항목이 없도록) 두 개의 너비가 0 인 일치도 같은 위치에서 시작하지 않습니다. 따라서 후보 줄당 일치 항목이 하나만 표시됩니다.

그러나 PCRE로 질문 2의 첫 번째 부분을 해결하는 것이 실제로 가능합니다. 각 줄에서 시작하는 열 수를 계산하여 총 열 수를 계산합니다 X. 개별 일치 (이전 단락 참조)의 형태로이 개수를 얻을 수없고 개별 그룹 또는 캡처의 형태로이 개수를 얻을 수 없기 때문에 (PCRE는 .NET과는 달리 고정 된 제한된 개수의 캡처 만 제공하기 때문에) ). 대신 우리가 할 수있는 것은 일치하는 열의 수를 인코딩하는 것입니다.

방법은 다음과 같습니다. 각 행에 대해 시작하는 열이 있는지 확인합니다. 그렇다면 특정 캡처 그룹에 한 캐릭터를 포함합니다. 그런 다음 성공적인 일치를보고하기 전에 가능한 한 더 많은 열을 찾으려고합니다. 각 열은 특정 그룹에 문자를 추가합니다. 이를 통해 특정 캡처 길이의 각 줄에서 시작하는 열 수를 인코딩합니다.

실제로 정규식에서이 개념을 실현하는 것은 처음 들리는 것보다 훨씬 더 복잡합니다 (그리고 이미 꽤 복잡하게 들립니다). 어쨌든, 여기 있습니다 :

^                        
(?:(?|
  (?(5)(?![\s\S]*+\5))      
  (?!(?!)()()) 
  (?=
    (?:
      .                  
      (?=                
        .*+\n            
        ( \3? . )   
        .*+\n        
        ( \4? . )    
      )
    )*?              
    X .*+\n          
    \3               
    X .*+\n          
    \4               
  )
  ()
|
  (?(5)(?=[\s\S]*+\5)|(?!))
  (?:
    .
    (?=
      .*+\n
      ( \1? .)
      .*+\n
      ( \2? .)
    )
  )+?
  (?=
    (?<=X).*+\n
    (\1)         
    (?<=X).*+\n
    (\2)         
    (?<=X)     
  )
  (?=
    ([\s\S])   
    [\s\S]*
    ([\s\S] (?(6)\6))
  )
){2})+

(사실이 접근 방식을 단순화하는 방법에 대한 Qtax의 답변을 참조하십시오.이 접근 방식을 학문적 이유로 여기에 남겨 두겠습니다. 매우 진보되고 흥미로운 기술을 배울 수 있기 때문입니다. 종료.)

예, 주석이 없습니다. 어쨌든 아무도 실제로 읽지 않을 것이라고 생각했기 때문에 대신이 표현을 부분적으로 나누려고 노력할 것입니다 (하향식 접근 방식으로 갈 것입니다).

그래서 지옥에서 온 양파의 바깥층을 보자 :

^                        
(?:(?|
  checkForNextColumn
|
  countAndAdvance
){2})+

따라서 우리의 경기는 다시 줄의 시작 부분에 고정됩니다. 그런 다음 우리는 (?:...{2})+무언가를 짝수 반복한다는 것을 의미합니다. 그리고 그것은 두 개의 하위 패턴의 교대입니다. 이러한 하위 패턴은 위에서 언급 한 단계를 나타냅니다. 첫 번째는 현재 행에서 시작하는 다른 열이 있는지 확인하고, 두 번째는 카운트를 등록하고 첫 번째 하위 패턴의 다른 적용을 위해 엔진의 상태를 준비합니다. 따라서 두 번째 패턴에 제어가 제공됩니다. 첫 번째 패턴은 미리보기를 사용하여 다른 열을 확인하므로 너비가 0 인 패턴입니다. 이것이 내가 모든 것을 단순히 포장 할 수는 +없지만{2})+사물-그렇지 않으면 너비가 0 인 구성 요소가 한 번만 시도됩니다. 이는 .NET과 같은 패턴을 가진 무한 루프를 피하기 위해 거의 모든 엔진에서 적용되는 필수 최적화 (a*)+입니다.

한 가지 더 있습니다 (매우 중요한 세부 사항) : 나는 (?|...)교대로 사용 했습니다. 이러한 종류의 그룹화에서 각 대안은 동일한 그룹 번호로 시작합니다. 따라서에서 /(?|(a)|(b))/모두 a와 b그룹으로 포착 될 수있다 1. 이는 동일한 그룹을 수정할 수 있으므로 하위 패턴 간의 "통신"을 허용하는 중요한 트릭입니다.

어쨌든 ... 그래서 우리는이 두 개의 서브 패턴을 가지고 있습니다. 우리는 컨트롤이 그들 사이에서 실제로 번갈아 가도록하고 싶습니다. 따라서 일치하는 마지막 그룹이면 각 그룹이 실패합니다. 패턴을 그룹화 및 참조 마법으로 래핑하여이를 수행합니다.

^(?:(?|
  (?(5)(?![\s\S]*+\5))       # if group 5 has matched before make sure that
                             # it didn't match empty
  checkForNextColumn         # contains 4 capturing groups
  ()                         # this is group 5, match empty
|
  (?(5)(?=[\s\S]*+\5)|(?!))  # make sure that group 5 is defined and that it
                             # matched empty
  advanceEngineState         # contains 4 capturing groups
  (?=
    ([\s\S])                 # this is group 5, match non-empty
    [\s\S]*                  # advance to the end very end of the string
    ([\s\S] (?(6)\6))             # add a character from the end of the string to
                             # group 6
  )
){2})+

따라서 각 대안이 끝날 때 일치를 시작하기 위해이 대안에 대한 조건을 무효화합니다. 두 번째 대안의 끝에서 우리는 또한 6Qtax에서 설명한 기술을 사용하여 group에 문자를 포함 할 것 입니다. 이것이 계산 단계입니다. 즉, 그룹 6은 현재 행에서 시작하는 열 수만큼 문자를 포함합니다.

이제 checkForNextColumn실제로는 예견 내에서 Qtax의 솔루션이 될 것입니다. 하지만 한 번 더 수정해야하며이를 정당화하기 위해 advanceEngineState먼저 살펴 보겠습니다 .

Qtax의 솔루션이 행의 두 번째 열과 일치하도록 상태를 수정하는 방법에 대해 생각해 봅시다. 의견이 있다고 가정 해 보겠습니다.

..X..X..
..X..X..
..X..X..

두 번째 열을 찾고 싶습니다. 이는 첫 번째 바로 뒤 위치에서 일치를 시작하고 X그룹이 \1있고 각각 행 2와 3 \2의 처음 세 문자 ( ..X)로 이미 초기화되어 (비어있는 대신) 수행 될 수 있습니다.

이제이 작업을 수행해 보겠습니다 X. 열을 시작하는 다음 항목 을 포함하여 모든 항목을 일치시킨 다음 checkForNextColumn패턴 에 사용할 해당 줄 접두사로 두 그룹을 채 웁니다 . 이것은 다시 거의 Qtax의 패턴입니다. 단, Xin 을 세고 (직전에 멈추지 않고) 별도의 그룹에 캡처를 추가해야합니다. 그래서 여기 있습니다 advanceEngineState:

(?:
  .
  (?=
    .*+\n
    ( \1? .)
    .*+\n
    ( \2? .)
  )
)+?
(?=
  (?<=X) .*+\n
  (\1)        
  (?<=X) .*+\n
  (\2)        
  (?<=X)
)

참고 내가 설정하는 방법을 X추가 한 문자를 가고, lookbehinds에들, 그리고 효과적으로 최종의 내용을 복사하는 방법 \1에 \3와들 \2로를 \4.

우리가 지금과 같이 Qtax의 솔루션을 사용한다면 checkForNextColumn그룹을 사용하여 내다보기로 \3하고 \4대신 \1하고 \2, 우리가 수행해야합니다.

그러나 얼마나 우리가 이러한 그룹 만들 수 있죠 \3과 \4대신 \1과를 \2? 우리가 패턴 시작할 수 ()()엔진의 커서에 영향을주지 않고, 항상 일치합니다,하지만, 그러나 2로 그룹의 수를 증가,이 문제가 :이 재설정 그룹 1과 2빈 문자열에 경우에 우리는 두 번째 열을 찾을 수 있습니다,advanceEngineState일관성없는 상태가됩니다 (엔진의 글로벌 위치가 전진되었지만 계수 그룹이 다시 0이 됨). 따라서 우리는이 두 그룹을 패턴으로 만들고자하지만 현재 캡처하고있는 것에 영향을주지 않습니다. .NET 솔루션에서 이미 언급 한 것을 활용하여이를 수행 할 수 있습니다. 네거티브 룩 어라운드의 그룹은 캡처 된 콘텐츠에 영향을주지 않습니다 (엔진이 계속 진행하려면 룩 어라운드에서 역 추적해야하기 때문). 따라서 우리는 (?!(?!)()())패턴에 절대 사용되지 않는 두 세트의 괄호를 포함하기 위해 (패턴이 실패하지 않는 부정적 예측)을 사용할 수 있습니다. 이를 통해 그룹 3및 4첫 번째 하위 패턴에서 작업 할 수 있으며 그룹 1및2다음 반복의 두 번째 하위 패턴에 대해서는 변경되지 않습니다. 결론적으로 이것은 다음과 checkForNextColumn같습니다.

(?!(?!)()()) 
(?=
  (?:
    .                  
    (?=                
      .*+\n            
      ( \3? . )   
      .*+\n        
      ( \4? . )    
    )
  )*?              
  X .*+\n          
  \3               
  X .*+\n          
  \4               
)

대부분의 경우 실제로 정말 익숙해 보입니다.

그래서 이것이다. 일부 입력에 대해이를 실행하면 6열이 시작되는 각 행에 대해 하나의 캡처를 포함 하는 그룹이 제공 되며 캡처의 길이는 여기에서 시작된 열의 수를 알려줍니다.

예, 실제로 작동합니다 (라이브 데모).

이것은 (기본 .NET 솔루션과 같이) X길이 가 3 초 이상인 열을 초과 합니다. 전체 .NET 솔루션의 룩 비하인드 (lookbehind)와 유사한 방식으로 미리보기를 사용하여이 개수를 수정할 수 있다고 생각하지만 이것은 독자에게 연습으로 남겨 둡니다.

이 솔루션의 기본 문제가 이미 매우 복잡하고 솔루션이 부풀어 오르는 것은 약간 불행합니다 (줄의 75 %는 대부분 Qtax 솔루션의 복사본 일뿐입니다). 주변 프레임 워크에는 정말 흥미로운 기술과 교훈이 있기 때문입니다.

특정 매칭 / 카운팅 작업을 수행하는 여러 하위 패턴을 가질 수 있으며, 이들을 (?|...)번갈아 가며 반복 하여 상호 캡처 그룹을 통해 "통신" 하도록 할 수 있습니다.
너비가 0 인 대안을 .NET {2}에 모든 것을 넣기 전과 같이 유한 수량 자로 래핑하여 반복해서 수행하도록 강제 할 수 있습니다 +.
그룹 번호는 (캡처 된 내용에 영향을주지 않고) 하나의 하위 패턴에서 건너 뛸 수 있습니다 (?!(?!)())..
대체 입력시 확인되는 특정 그룹에서 무언가를 캡처하거나 아무것도 캡처하지 않음으로써 하위 패턴간에 제어를 전달할 수 있습니다.

이것은 매우 강력한 계산을 허용합니다 (PCRE가 실제로 Turing-complete라는 주장을 보았습니다). 이것은 확실히 생산적인 사용을위한 잘못된 접근 방식입니다. 그러나 여전히 그러한 해결책을 이해하고 시도하는 것은 문제 해결에있어 매우 도전적이고 보람있는 연습이 될 수 있습니다.

단일 "수직"패턴을 찾으려면 여기에 해결책이 있습니다. "수평"패턴도 일치 시키려면 별도의 일치로 시도하여 일치 위치가 겹치는 지 확인하십시오. 컴퓨터는 선이 무엇인지 알지 못합니다. 인간이 만든 임의적 인 것입니다. 문자열은 일부 문자가 줄 끝이라는 것을 나타내는 1 차원 시퀀스입니다.

#!/usr/local/perls/perl-5.18.0/bin/perl
use v5.10;

my $pattern = qr/XXX/p;

my $string =<<'HERE';
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
HERE


$transposed = transpose_string( $string );

open my $tfh, '<', \ $transposed;
while( <$tfh> ) {
    while( /$pattern/g ) {
        my $pos = pos() - length( ${^MATCH} );
        push @found, { row => $pos, col => $. - 1 };
        pos = $pos + 1; # for overlapping matches
        }
    }

# row and col are 0 based
print Dumper( \@found ); use Data::Dumper;

sub transpose_string {
    my( $string ) = @_;

    open my $sfh, '<', \ $string;

    my @transposed;
    while( <$sfh> ) {
        state $row = 0;
        chomp;
        my @chars = split //;

        while( my( $col, $char ) = each @chars ) {
            $transposed[$col][$row] = $char;
            }

        $row++;
        }

    my @line_end_positions = ( 0 );
    foreach my $col ( 0 .. $#transposed ) {
        $transposed .= join '', @{ $transposed[$col] };
        $transposed .= "\n";
        }
    close $sfh;

    return $transposed;
    }

질문 2에 대한 작업 솔루션

Perl / PCRE에서 완전히 가능합니다! :)

미안 해요, 난 조금 극단적으로 늦게 파티에,하지만 난 당신이 실제로 XXX 형성의 수를 셀 수 있음을 지적하고 싶습니다 발견; 즉, 글로벌 매치를 수행 할 때 포메이션 당 정확히 하나의 매치가 있도록 표현식을 구성합니다. 하지만 꽤 까다 롭습니다.

여기있어:

\A(?:(?=(?(3)[\s\S]*(?=\3\z))(?|.(?=.*\n(\1?+.).*\n(\2?+.))|.*\n()())+?(?<=X)(?=.*\n\1(?<=X).*\n\2(?<=X))(?=([\s\S]*\z)))(?=[\s\S]*([\s\S](?(4)\4)))[\s\S])+[\s\S]*(?=\4\z)|\G(?!\A|[\s\S]?\z)

regex101에 대한 조치

나는 그것에 대해 몇 가지 의견을 추가해야 할 것입니다! 여기에 관심이있는 분들을 위해 :

\A(?:
    (?=
        (?(3)[\s\S]*(?=\3\z))                   # Resume from where we ended last iteration

        (?|                                     # Branch-reset group used to reset \1
            .(?=.*\n(\1?+.).*\n(\2?+.))         # and \2 to empty values when a new line
            |                                   # is reached. ".*\n" is used to skip the
            .*\n()()                            # rest of a line that is longer than the
        )+?                                     # ones below it.

        (?<=X)(?=.*\n\1(?<=X).*\n\2(?<=X))      # Find a XXX formation

        (?=([\s\S]*\z))                         # Save the rest of the line in \3 for 
    )                                           # when we resume looking next iteration

    (?=[\s\S]*([\s\S](?(4)\4)))                 # For every formation found, consume another 
                                                # character at the end of the subject

    [\s\S]                                      # Consume a character so we can move on

    )+

[\s\S]*(?=\4\z)                                 # When all formations around found, consume
                                                # up to just before \4 at the subject end.

|

\G(?!\A|[\s\S]?\z)                              # Now we just need to force the rest of the 
                                                # matches. The length of \4 is equal to the 
                                                # number of formations. So to avoid overmatching,
                                                # we need to exclude a couple of cases.

나 무서워; 무슨 일이야??

기본적으로, 우리는 하나의 반복되는 비 포착 그룹에서 전체 주제를 통과하여 하나의 XXX 형성에서 다음 형성으로 이동합니다. 발견 된 각 포메이션에 대해 피사체 끝에있는 카운터에 다른 캐릭터를 붙입니다 (\ 4에 저장 됨). 극복해야 할 몇 가지 장애물이 있습니다.

한 번에 모든 것을 일치시키는 경우 어떻게 한 줄에서 다음 줄로 이동할 수 있습니까? 해결 방법 : 분기 재설정 그룹을 사용하여 새 줄이 나타날 때 \ 1 및 \ 2를 재설정하십시오.
끝에 작은 "\ nX \ nX \ nX"가있는 큰 ASCII 그리드가 있다면 어떨까요? 우리가 한 형성에서 다음 형성으로 주제를 소비하면 우리는 카운터로 먹기 시작할 것입니다. 해결책 : 한 번에 하나의 캐릭터 만 소비하고, 진형 추구 논리를 예견으로 감 쌉니다.
그러나 한 포메이션에서 다음 포메이션으로 소비하지 않는 경우 비 포획 그룹의 다음 반복을 다시 찾을 위치를 어떻게 알 수 있습니까? 솔루션 : 포메이션이 발견되면 해당 위치 에서 피사체 의 맨 끝까지 캐릭터를 캡처합니다 . 항상 참조 할 수있는 고정 지점입니다. 이것은 재귀없이 중첩 된 괄호 를 일치시키는 데 사용한 것과 동일한 트릭 이며, 실제로 순방향 참조의 힘을 보여줍니다.

이것은 많은 재미가 있었고 나는 이와 같은 더 많은 게시물을보고 싶습니다!

이미지를 회전 한 다음 XXX.

PHP를 사용하여 수직 패턴을 일치시키는 방법.

먼저 입력을 90 ° 회전시켜 보겠습니다.

// assuming $input contains your string
$input = explode("\n", $input);
$rotated = array();
foreach ($input as $line)
{
    $l = strlen($line);
    for ($i = 0; $i < $l; $i++)
    {
        if (isset($rotated[$i]))
            $rotated[$i] .= $line[$i];
        else
            $rotated[$i] = $line[$i];
    }
}
$rotated = implode("\n", $rotated);

결과

..XXX.....
..........
.XX....XX.
....X.....
X...X....X
.X.XXX....
..XX......
...X......
...X......
.XXX......
...X.....
.........
........
........
....XXX
.....
...
..
..
X
.
.
.

이제 이상하게 보일 수 있지만 이제는 간단하게 해결할 수 있기 때문에 실제로 더 가까워 preg_match_all()집니다.

if (preg_match_all('/\bXXX\b/', $rotated, $m))
var_dump($m[0]);

et voila :

array(4) {
  [0] =>
  string(3) "XXX"
  [1] =>
  string(3) "XXX"
  [2] =>
  string(3) "XXX"
  [3] =>
  string(3) "XXX"
}

동일한 수평 패턴도 일치 시키려면 회전되지 않은 입력에 동일한 표현식을 사용하면됩니다.

참고 URL : https://stackoverflow.com/questions/17039670/vertical-regex-matching-in-an-ascii-image

'Development Tip' 카테고리의 다른 글

Meteor의 백그라운드 작업 (0)	2020.12.11
HTML5에서 확인란을 선택하고 선택 취소하는 올바른 방법은 무엇입니까? (0)	2020.12.11
Xcode 5/6 : View Debugging이 항상 회색으로 표시됩니까? (0)	2020.12.11
Flask sqlalchemy 다 대다 데이터 삽입 (0)	2020.12.11
오류 : detectMultiScale 함수의 (-215)! empty () (0)	2020.12.11

현재글ASCII "이미지"에서 "수직"정규식 일치

yourdevel

ASCII "이미지"에서 "수직"정규식 일치

ASCII "이미지"에서 "수직"정규식 일치

문제

질문 (들)

질문 1에 대한 답변

질문 2에 대한 답변

일반 매칭

(세미?) 증거

길이 / 간접 솔루션

테스트 케이스

편집하다

원래 답변

임베디드 코드가없는 솔루션

기본 .NET 솔루션

완전한 .NET 솔루션

부분 PCRE 솔루션

질문 2에 대한 작업 솔루션

나 무서워; 무슨 일이야??

'Development Tip' 카테고리의 다른 글

'Development Tip'의 다른글

티스토리툴바

ASCII "이미지"에서 "수직"정규식 일치

ASCII "이미지"에서 "수직"정규식 일치

문제

질문 (들)

질문 1에 대한 답변

질문 2에 대한 답변

일반 매칭

(세미?) 증거

길이 / 간접 솔루션

테스트 케이스

편집하다

원래 답변

임베디드 코드가없는 솔루션

기본 .NET 솔루션

완전한 .NET 솔루션

부분 PCRE 솔루션

질문 2에 대한 작업 솔루션

나 무서워; 무슨 일이야??

'Development Tip' 카테고리의 다른 글

'Development Tip'의 다른글

관련글

티스토리툴바