Regular Expressions
역 추적

Backtracking의 원인은 무엇입니까?

일치 항목을 찾으려면 정규식 엔진이 문자를 하나씩 사용합니다. 부분 일치가 시작되면 엔진은 시작 위치를 기억하므로 다음 문자가 일치하지 않을 경우 다시 돌아갈 수 있습니다.

• 경기가 완료되면 역 추적이 없습니다.
• 일치가 완료되지 않은 경우 엔진은 전체 일치 항목을 찾기 위해 문자열을 역 추적합니다 (예전 테이프를 되감습니다).

예를 들어 : abc123def 문자열에 대한 \d{3}[az]{2} 는 다음과 같이 탐색됩니다.

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does match \d (third one)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

이제 regex를 같은 문자열 ( abc123def )에 대해 \d{2}[az]{2} abc123def .

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does not match [a-z]
abc123def
    ^ BACKTRACK to catch \d{2} => (23)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

역 추적은 왜 함정이 될 수 있습니까?

regex 엔진은 모든 경로를 탐색하려고하기 때문에 선택적 양수 또는 대체 구조로 인해 역 추적이 발생할 수 있습니다. aaaaaaaaaaaaaa 에 대해 정규식 a+b 를 실행하면 일치하는 항목이 없으므로 엔진에서 매우 빨리 찾을 수 있습니다.

하지만 (aa*)+b 정규 표현식을 변경하면 조합 수는 매우 빠르게 증가하고 대부분의 (최적화되지 않은) 엔진은 모든 경로를 탐색하려고 시도 할 것이며 영원을 찾아 일치를 찾거나 제한 시간 초과. 이를 치명적인 역 추적 이라고합니다.

물론 (aa*)+b 는 초보자 오류 인 것처럼 보일 수 있지만 여기에 요점을 설명하기 위해 나와 있습니다. 때로는 똑같은 문제가 있지만 더 복잡한 패턴으로 끝나기도합니다.

catgerophic backtracking의 더 극단적 인 경우는 정규식 (x+x+)+y (아마 여기 또는 여기 에서 본 것)에서 발생합니다. x 및 그 밖의 다른 것을 포함하는 문자열을 찾아내는 기하 급수적 인 시간이 필요합니다. xxxxxxxxxxxxxxxxxxxx )이 일치하지 않습니다.

어떻게 피하는가?

되도록 구체적으로 가능한 한 경로를 줄이십시오. 일부 정규식 matchers는 Thkpson NFA를 기반으로하기 때문에 awk 또는 grep 포함 된 것과 같은 역 추적에 취약하지 않습니다.