정규 표현 식 독서 노트 에 정통 (2)

DFA VS NFA
DFA: 유한 자동 기 를 확정 합 니 다.하나의 입력 에 하나의 이동 상태 만 있 습 니 다.
NFA: 불확실 한 자동 동기.하나의 입력 에 대해 여러 개의 이동 상 태 를 가 질 수 있다.
DFA 의 예:
패턴 문자열 이: abc | abcdef 라면, 일치 하 는 문자열 이 abcdef 이면, DFA 에 서 는 항상 가능 한 모든 일치 성 을 시도 합 니 다.
우선 abc 의 a 로 일치 하고 만족 을 발견 합 니 다.또한 abcdef 의 a 로 일치 하고 발견 도 만족 합 니 다.이 때 는 일치 하 는 문자열 두 개 를 동시에 유지 합 니 다.
이어서 bc 와 일치 합 니 다.
문자 d 까지.이 때 왼쪽 abc 가 일치 하지 않 기 때문에 왼쪽 모드 는 일치 하지 않 는 것 으로 기 록 됩 니 다.오른쪽 abcdef 모드 문자열 은 일치 합 니 다.
이렇게 하면 오른쪽 abcdef 모드 문자열 로 남 은 문자 와 일치 합 니 다.
DFA 는 항상 모든 패턴 과 일치 하려 고 시도 하고 가장 긴 일치 입 니 다.
NFA 로 일치 하면 가장 먼저 일치 하 는 전략 을 사용 합 니 다.
abc 문자열 이 abcdef 와 일치 하면 일치 가 성공 했다 고 생각 하고 오른쪽 abcdef 로 남 은 문자 와 일치 하지 않 습 니 다.
다음 python 코드 는 NFA 의 일치 정책 을 사용 한 것 을 확인 할 수 있 습 니 다.

import re
p=re.compile(r'(abc)|(abcdef)')
s='abcdef'
m=p.match(s)
print m.groups()

출력 합 니 다 ('abc', None).
DFA 의 특징: 거 슬러 올 라 가지 않 고 속도 가 매우 빠르다.그러나 그룹 을 캡 처 할 수 없 기 때문에 지원 하 는 패턴 의 복잡 도 에 한계 가 있 습 니 다.
NFA 의 특징: 기능 이 강하 고 매우 복잡 한 모델 을 지원 할 수 있다.그러나 역 추적 이 있 기 때문에 속 도 는 패턴 자체 에 따라 결정 된다.불합리한 모델 은 대량의 역 추적 을 초래 하여 성능 저 하 를 초래 할 수 있다.
현재 대부분의 정규 표현 식 은 python, java. util. regex,. NET 등 NFA 입 니 다.일부 오래된 실현 은 awk 실 용 DFA 와 같다.
일치 우선 VS 무시 우선
일치 우선 순위: *
무시 우선: *?
경로 에서 파일 이름 가 져 오기:
두 가지 경로 방식: / usr / bin / gcc 또는 C: \ Windows \ Messenger 이 므 로 모델 은 두 가지 와 관련 됩 니 다. 여기 서 이전 자 를 예 로 들 수 있 습 니 다.
두 가지 생각 이 있다.
1. 처음부터 일치 합 니 다. 이런 사 고 는 본질 적 으로 마지막 '/' 전의 문 자 를 모두 없 애고 싶 습 니 다.perl 로 다음 과 같이 쓸 수 있 습 니 다:
$f =~ s{^.*/}{};
마지막 / 을 포함 한 모든 문 자 를 ^. * / 이 모드 로 일치 시 키 는 것 입 니 다.
2. 끝 에서 부터 일치 하 는 생각 은 뒤에서 앞으로 찾 아 만 나 거나 멈 추 기 를 바 라 는 것 이다.
이때 우 리 는 다음 과 같은 모드 로 일치 할 수 있다.
[^ /] * $, 그리고 그룹 포획 을 사용 하면 됩 니 다.
분석: 어떤 사고 든 일치 하 는 우선 순위 가 있다 는 것 은 역 추적 이 있다 는 것 을 의미한다.따라서 NFA 의 경우 성능 이 특별히 좋 지 않다.