Atomic 그룹 — (?>...)

'commit 후 뒤돌아보지 않기' 그룹

Atomic 그룹 (?>...) 가 일반 그룹처럼 매칭, BUT 한 번 성공하면 엔진이 backtrack 거부. 소비한 게 lock in. 엔진이 전진; 패턴 나머지 실패해도 atomic 그룹 안 대안 시도 X.

왜 중요

루프 안 backtracking 이 모든 catastrophic 정규식 성능의 출처. (\w+)*X 가 끝에 X 없는 긴 word 글자 문자열에 대해 \w+ iteration 사이 입력의 가능한 모든 split 시도 — 지수적.

안 그룹을 atomic 으로: (?>\w+)*X. 이제 \w+ 가 가능한 만큼 잡으면 엔진이 글자 돌려주려 시도 X. 즉시 실패, linear time.

엔진 지원

Python re: Python 3.11 부터 atomic 그룹 추가. 옛 버전: third-party regex 설치.
PCRE, Perl, Java, Ruby, .NET: 지원.
JavaScript: 미지원 (아직).
RE2/Go: Backtrack 자체 안 해서 atomic 그룹 필요 X.

멘탈 모델

Atomic 그룹이 엔진에게 "이거 매칭한 후 second-guess X" 알려주는 방법. 패턴 안 섹션이 첫 거 실패면 유효한 대체 매칭 없을 때마다 사용 — "숫자 하나 이상," "word 글자 하나 이상," "이 줄 나머지" 같은 거에 거의 항상.

Code

Atomic 그룹 vs vanilla·python

import re

# Vanilla — 엔진이 (\w+)* 안 backtrack
# 이게 canonical ReDoS 모양
# re.search(r'(\w+)*X', 'a' * 30)  # 여러 초 hang

# Atomic — (?>\w+) 안 backtrack 거부
# Python 3.11+
import sys
if sys.version_info >= (3, 11):
    re.search(r'(?>\w+)*X', 'a' * 30)  # 즉시 실패

# 실전: 줄 끝까지 추출, backtracking 없이
# Vanilla
re.match(r'(\w+)\s+(\w+)', 'hello world')

# Atomic — 같은 결과, 적대적 입력에 더 빠름
if sys.version_info >= (3, 11):
    re.match(r'(?>\w+)\s+(?>\w+)', 'hello world')

# 패턴의 다음 거가 실패할 때 atomic 이 크게 win
# 'kg' 따라오는 숫자 매칭, 나쁜 입력에 빠르게 실패
for _ in range(100000):
    re.search(r'\d+kg', '1234567890123456789' * 100)  # backtracking 으로 느림
# vs
if sys.version_info >= (3, 11):
    for _ in range(100000):
        re.search(r'(?>\d+)kg', '1234567890123456789' * 100)  # 빠름

Atomic 그룹 — (?>...)

'commit 후 뒤돌아보지 않기' 그룹

왜 중요

엔진 지원

멘탈 모델

Code

External links

Exercise

Progress

댓글 0