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




정규 표현식의 복잡성 (5)

나는 이것에 대한 답을 어디에도 가지지 않았다. Regex 일치 및 대체의 런타임 복잡성은 무엇입니까?

편집 : 나는 파이썬에서 작동합니다. 그러나 일반적으로 가장 대중적인 언어 / 도구 (java, perl, sed)에 대해 알고 싶습니다.


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


순전히 이론적 입장에서 :

내가 잘 알고있는 구현은 정규식을 인식 할 수있는 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 완성이라는 것을 의미합니다.

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





complexity-theory