RegEx에서 3개 이하의 고유 문자가 포함된 줄을 어떻게 찾나요?

StackOverflow https://stackoverflow.com/questions/1418966

문제

나는 큰 텍스트 파일을 반복하면서 3개 이하의 문자가 포함된 줄을 찾고 있습니다(그러나 이러한 문자는 무한정 반복될 수 있습니다).나는 이것을 수행하는 가장 좋은 방법이 일종의 정규식이라고 가정합니다.

모든 도움을 주시면 감사하겠습니다.

(도움이 된다면 PHP로 스크립트를 작성하고 있습니다.)

도움이 되었습니까?

해결책

아마도 이것이 효과가 있을 것입니다:

preg_match("/^(.)\\1*(.)?(?:\\1*\\2*)*(.)?(?:\\1*\\2*\\3*)*$/", $string, $matches);
// aaaaa:Pass
// abababcaaabac:Pass
// aaadsdsdads:Pass
// aasasasassa:Pass
// aasdasdsadfasf:Fail

설명:

/
 ^                 #start of string
 (.)               #match any character in group 1
 \\1*              #match whatever group 1 was 0 or more times
 (.)?              #match any character in group 2 (optional)
 (?:\\1*\\2*)*     #match group 1 or 2, 0 or more times, 0 or more times 
                   #(non-capture group)
 (.)?              #match any character in group 3 (optional)
 (?:\\1*\\2*\\3*)* #match group 1, 2 or 3, 0 or more times, 0 or more times
                   #(non-capture group)
 $                 #end of string
/

추가된 혜택, $matches[1], [2], [3] 원하는 세 문자가 포함됩니다.정규식은 첫 번째 문자를 찾은 다음 이를 저장하고 해당 문자가 아닌 다른 문자가 발견될 때까지 일치시키고 두 번째 문자로 포착하여 해당 문자 중 하나와 최대한 많이 일치시키고 세 번째 문자를 포착한 다음 일치가 실패하거나 문자열이 끝나고 테스트가 통과할 때까지 세 가지 모두와 일치합니다.

편집하다

이 정규 표현식은 구문 분석 엔진 및 역추적 작동 방식으로 인해 훨씬 ​​더 빨라집니다. 설명은 bobince의 답변을 읽어보세요.

/^(.)\\1*(?:(.)(?:\\1|\\2)*(?:(.)(?:\\1|\\2|\\3)*)?)?$/

다른 팁

아이들을 위한 정규식 최적화 재미있는 시간 운동!gnarf의 정규식을 출발점으로 삼아:

^(.)\1*(.)?(?:\1*\2*)*(.)?(?:\1*\2*\3*)*$

나는 여기에 중첩되고 연속적인 *가 있다는 것을 알았습니다. 이로 인해 많은 역추적이 발생할 수 있습니다.예를 들어 'abcaaax'에서는 'a'의 마지막 문자열을 길이 3의 단일 \1*, 길이 2의 \1*, 단일 \1, \1 다음에 길이 2로 일치하도록 시도합니다. \1* 또는 세 개의 단일 일치 \1입니다.이 문제는 문자열이 길면 훨씬 더 악화됩니다. 특히 정규 표현식으로 인해 \1이 \2와 동일한 문자가 되는 것을 막을 수 없는 경우에는 더욱 그렇습니다.

^(.)\1*(.)?(?:\1|\2)*(.)?(?:\1|\2|\3)*$

이는 Python의 PCRE matcher에서 테스트하여 원본보다 두 배 이상 빠릅니다.(PHP에서 설정하는 것보다 빠릅니다. 죄송합니다.)

이건 아직 문제가 있는 것 같아요 (.)? 아무 것도 일치하지 않고 나머지 경기를 계속할 수 있습니다. \1|\2 일치하는 \2가 없더라도 \1과 일치하므로 해당 항목을 도입하려는 역추적 가능성이 있습니다. \1|\2 그리고 \1|\2|\3 일치하는 결과를 얻을 수 없는 이전 조항.이 문제는 이동을 통해 해결될 수 있습니다. ? 후행 절 전체에 대한 선택 사항:

^(.)\1*(?:(.)(?:\1|\2)*(?:(.)(?:\1|\2|\3)*)?)?$

이번에도 두 배나 빨랐습니다.

\1, \2 및 \3 중 하나라도 동일한 문자일 수 있어 표현식이 일치하지 않을 때 잠재적으로 더 많은 역추적을 일으킬 수 있다는 잠재적인 문제가 여전히 있습니다.이전 문자와 일치하지 않도록 부정 예측을 사용하여 이를 중지합니다.

^(.)\1*(?:(?!\1)(.)(?:\1|\2)*(?:(?!\1|\2)(.)(?:\1|\2|\3)*)?)?$

그러나 Python에서는 무작위 테스트 데이터를 사용하여 이로 인해 속도가 크게 향상되는 것을 느끼지 못했습니다.귀하의 마일리지는 테스트 데이터에 따라 PHP에서 달라질 수 있지만 이미 충분할 수도 있습니다.소유격 일치(*+)가 여기에서 사용 가능했다면 도움이 되었을 것입니다.

읽기 쉬운 Python 대안보다 더 나은 성능을 발휘하는 정규식은 없습니다.

len(set(s))<=3

PHP의 유사한 방법은 아마도 다음과 같습니다. count_chars:

strlen(count_chars($s, 3))<=3

속도를 테스트하지는 않았지만 정규식보다 더 빠르고 읽기에도 훨씬 좋을 것으로 기대합니다.

그래서 기본적으로 저는 정규식을 다루느라 시간을 완전히 낭비했습니다.시간을 낭비하지 말고 정규식을 사용하기 전에 먼저 간단한 문자열 방법을 찾으십시오!

다운 투자의 위험에 처해, 정기적 인 표현 이이 상황을 처리하기위한 것이 아니라는 것을 제안 할 것입니다.

캐릭터 나 캐릭터 세트와 일치 할 수는 있지만 세트의 캐릭터가 이미 더 일치하는 것을 제외한 것으로 밝혀진 세트의 캐릭터를 기억할 수는 없습니다.

나는 당신이 캐릭터 세트를 유지하고, 새로운 라인으로 시작하기 전에 그것을 재설정하고, 줄을 넘어가는 동안 요소를 추가하는 것이 좋습니다. 세트의 요소 수가 3을 초과하자마자 현재 선을 떨어 뜨리고 다음 선으로 진행합니다.

저에게 - 공정한 정규 표현 지식을 가진 프로그래머로서 이것은 Regexp 만 사용하는 데 문제가 될 수있는 문제와는 다릅니다.

해시 맵/배열 데이터 구조 키 : 문자 값 : 큰 텍스트 파일을 계산하고 반복하여 각 줄에 대한 맵을 재건해야 할 것입니다. 각각의 새로운 문자에서 이미 인정 된 문자 수가 2인지 확인하십시오. 그렇다면 현재 선을 건너 뛰십시오.

그러나 한 명의 Mad Regexp 해커가 해결책을 제시 할 경우 놀라게되고 싶어합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top