regex - 추출 - 정규표현식 특수문자

구현에 따라 다릅니다. 어떤 언어 / 도서관 / 수업입니까? 가장 좋은 경우가있을 수 있지만 구현의 기능 수에 따라 매우 다를 수 있습니다.

순전히 이론적 입장에서 :

내가 잘 알고있는 구현은 정규식을 인식 할 수있는 Deterministic Finite Automaton을 만드는 것입니다. 이것은 표준 알고리즘을 사용하여 정규 표현식의 크기 인 O (2 ^ m)에서 수행됩니다. 일단 이것이 빌드되면 문자열을 통해 문자열을 실행하는 것은 문자열의 길이에 선형입니다. - O (n), n은 문자열 길이입니다. 문자열에서 찾은 일치 항목의 대체 항목은 일정한 시간이어야합니다.

전반적으로 O (2 ^ m + n)라고 가정합니다.

DFA 대신에 비 결정적 유한 유한 자동 기계를 구축하여 공간을 자유롭게 교환 할 수 있습니다. 이것은 선형 시간에 통과 할 수 있습니다. 물론, 최악의 경우 이것은 O (2 ^ m) 공간을 필요로 할 수 있습니다. 그만한 가치가 있다고 생각합니다.

당신이 정규식으로 정의한 것에 달려 있습니다. 연결 연산자, 대체 및 클라인 스타를 허용하면 실제로 시간은 O(m*n+m) 일 수 있습니다. 여기서 m 은 정규식의 크기이고 n 은 문자열의 길이입니다. 여러분은 NFA ( m 은 선형 임)를 구성한 다음, 입력 상태를 유지하면서 O(m) 업데이트하여 시뮬레이션합니다.

정규식 파싱을 어렵게 만드는 것들 :

• 괄호와 역 참조 : 위에서 언급 한 알고리즘을 사용하면 캡처는 여전히 괜찮은 편이지만 복잡도가 높아져서 실행하기가 어려울 수 있습니다. 역 참조는 정규 표현식의 인식력을 높이고 그 난이도는 높습니다.
• 긍정적 인 look-ahead : 교차점에 대한 또 다른 이름으로, 앞서 언급 한 알고리즘의 복잡성을 O(m^2+n)
• negative look-ahead : 오토 마톤 ( O(2^m) , 아마도 PSPACE-complete)을 구성하기위한 재앙. 그러나 O(n^2*m) 와 같은 것으로 동적 인 알고리즘을 다루는 것은 여전히 ​​가능해야합니다.

구체적인 구현에서는 상황이 더 좋아 지거나 악화 될 수 있습니다. 엄지 손가락의 규칙으로, 간단한 기능은 충분히 빠르며 모호하지 않습니다 (예 : a*a* 와 같지 않음) regexes가 더 좋습니다.

일치 및 대치가 완료된 경우 그룹화 및 역 참조를 의미합니다.

다음은 그룹화와 역 참조를 사용하여 NP 완전한 문제를 해결할 수있는 펄 예제입니다 : http://perl.plover.com/NPC/NPC-3SAT.html

이것은 (다른 이론적 인 가벼운 비트와 결합하여) 매칭과 대체를 위해 정규 표현식을 사용하는 것이 NP 완성이라는 것을 의미합니다.

이것은 그룹화 개념이없는 정규 표현식의 공식 정의와 다르고 다른 답변에서 설명한대로 다항식 시간과 일치한다는 점에 유의하십시오.