정규식 대체의 복잡성

Question

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

편집하다:나는 파이썬으로 일합니다.하지만 가장 널리 사용되는 언어/도구(java, perl, sed)에 대해 일반적으로 알고 싶습니다.

Answer 1

순전히 이론적인 입장에서:

내가 익숙한 구현은 정규식을 인식하는 결정적 유한 자동화 장치를 구축하는 것입니다.이는 표준 알고리즘을 사용하여 O(2^m)으로 수행됩니다. m은 정규식의 크기입니다.이것이 구축되면 이를 통해 문자열을 실행하는 것은 문자열 길이에서 선형입니다. O(n), n은 문자열 길이입니다.문자열에서 발견된 일치 항목의 대체는 상수 시간이어야 합니다.

그래서 전체적으로 O(2^m + n)이라고 가정합니다.

Answer 2

관심을 가질 만한 기타 이론적 정보.

명확성을 위해 정규식에 대한 표준 정의를 가정합니다.

http://en.wikipedia.org/wiki/Regular_언어

형식언어이론에서실제로, 이것은 유일한 건축 자재는 알파벳 기호, 연결 연산자, 교대 및 클라인 폐쇄 및 단위 및 제로 상수 (그룹 이론적 이유로 나타나는)라는 것을 의미합니다.일반적으로 스크립팅 언어의 일상적인 연습에도 불구 하고이 용어를 과부하시키지 않는 것이 좋습니다.

O (| r | | t |) 시간 및 o (| r |) 공간의 입력 텍스트 t를 일치하는 문제를 해결하는 NFA 구조가 있습니다. 길이 함수입니다.이 알고리즘은 Myers에 의해 더욱 개선되었습니다.

http://doi.acm.org/10.1145/128749.128755

자동화 노드 목록과 Four Russians 패러다임을 사용하여 시간 및 공간 복잡도 O(|r| |t| / log |t|)를 해결합니다.이 패러다임은 온라인이 아닌 획기적인 논문을 쓴 4 명의 러시아 남자의 이름을 따서 명명 된 것 같습니다.그러나 패러다임은 이러한 계산 생물학 강의 노트에 설명되어 있습니다.

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

나는 성명 대신 저자의 숫자와 국적에 따라 패러다임을 지명하는 것이 재미 있음을 알았습니다.

뒷면 reference가 추가 된 정규 표현식의 일치 문제는 NP- 완성이며 AHO가 입증했습니다.

http://portal.acm.org/citation.cfm?id=114877

이는 고전적인 NP-완전 문제인 꼭지점 덮개 문제를 축소한 것입니다.

정규 표현식과 역사가와 일치하기 위해 결정적으로 역 추등을 일치시키기 위해 (Perl Regex 엔진과 달리) 역 추적을 사용하여 R의 변수에 할당 할 수있는 입력 텍스트 T의 가능한 하위 단어를 추적 할 수 있습니다.r의 하나의 변수에 할당 할 수있는 O (| t |^2) 서브 워드 만 있습니다.R에 n 변수가 있으면 o (| t |^2n) 가능한 할당이 있습니다.변수에 대한 하위 문자열의 할당이 고정되면 문제는 일반 정규식 일치로 줄어 듭니다.따라서 정규 표현을 등받이와 일치시키는 최악의 복잡성은 O (| t |^2n)입니다.

그러나, 뒷면을 포함한 정기적 인 표현은 아직 완전한 수분이없는 Regexen이 아닙니다.

예를 들어 다른 연산자와는 별도로 "신경 쓰지 않는"기호를 가져 가십시오.패턴 세트가 입력 텍스트와 일치하는지 여부를 결정하는 여러 다항식 알고리즘이 있습니다.예를 들어 Kucherov와 Rusinowitch는

http://dx.doi.org/10.1007/3-540-60044-2_46

패턴을 단어 w_1@w_2@...@w_n으로 정의합니다. 여기서 각 w_i는 단어(정규 표현식 아님)이고 "@"는 w_i 중 하나에 포함되지 않은 가변 길이 "상관 없음" 기호입니다.그들은 입력 텍스트 t와의 패턴 p에 일련의 패턴 p와 일치하기위한 o ((| t | + | p |) log | p |) 알고리즘을 도출합니다. 텍스트의 길이, | p | P의 모든 단어의 길이입니다.

이러한 복잡성 측정이 어떻게 결합되는지, 그리고 뒷면 표현, "신경 쓰지 말아라"및 실용적인 정규 표현의 기타 흥미로운 특징에 대한 일치 문제의 복잡성 측정 값을 아는 것은 흥미로울 것입니다.

아아, 나는 Python에 대해 한 마디도 말하지 않았습니다 ...:)

Answer 3

정규식으로 정의한 내용에 따라 다릅니다.연결 연산자, 대체 연산자, Kleene-star 연산자를 허용하면 실제로 시간은 다음과 같습니다. O(m*n+m), 어디 m 정규식의 크기이고 n 문자열의 길이입니다.NFA를 구성하여 이를 수행합니다(즉, 선형적임). m), 그런 다음 현재 상태 집합을 유지하고 업데이트하여 시뮬레이션합니다( O(m)) 모든 입력 문자에 대해.

정규식 구문 분석을 어렵게 만드는 사항:

• 괄호 및 역참조:앞서 언급한 알고리즘을 사용하면 캡처가 여전히 괜찮지만 복잡도가 높아져 실행 불가능할 수 있습니다.역참조는 정규식의 인식력을 높이고 난이도도 좋습니다.
• 긍정적인 예측:는 교차점의 또 다른 이름일 뿐이며, 이는 앞서 언급한 알고리즘의 복잡성을 증가시킵니다. O(m^2+n)
• 부정적인 예측:자동인형 제작에 대한 재앙(O(2^m), 아마도 PSPACE-완전).하지만 다음과 같은 방식으로 동적 알고리즘을 다루는 것은 여전히 ​​가능해야 합니다. O(n^2*m)

구체적인 구현을 통해 상황이 좋아질 수도 있고 나빠질 수도 있습니다.경험상 간단한 기능은 충분히 빠르고 모호하지 않아야 합니다(예:같지 않은 a*a*) 정규 표현식이 더 좋습니다.

Answer 4

theprise의 답변을 자세히 살펴보면, 자동 장치 구성의 경우 O(2^m)이 최악의 경우이지만 실제로는 정규 표현식의 형식에 따라 다릅니다(단어와 일치하는 매우 간단한 표현식의 경우 O( m) 예를 들어 크누스-모리스-프랫(Knuth-Morris-Pratt) 알고리즘).

Answer 5

구현에 따라 다릅니다.어떤 언어/도서관/수업?최상의 경우가 있을 수 있지만 구현의 기능 수에 따라 매우 구체적입니다.

Answer 6

DFA 대신 비결정적 유한 자동 장치를 구축하면 속도를 위해 공간을 교환할 수 있습니다.이는 선형 시간으로 탐색될 수 있습니다.물론 최악의 경우에는 O(2^m) 공간이 필요할 수 있습니다.나는 그 절충안이 그만한 가치가 있다고 기대합니다.

Answer 7

일치 및 대체 후에는 그룹화 및 역참조를 의미합니다.

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

이는 (몇 가지 다른 이론적 정보와 결합하여) 일치 및 대체에 정규식을 사용하는 것이 NP 완전하다는 것을 의미합니다.

이는 그룹화 개념이 없는 정규 표현식의 공식적인 정의와 다르며 다른 답변에서 설명한 대로 다항식 시간에 일치합니다.