소유적 수량자 — *+ ++ ?+ · RegEx Quest

소유적 수량자는 잡은 문자를 돌려주지 않아

*+, ++, ?+, {n,m}+는 처음에는 탐욕적 수량자처럼 가능한 만큼 소비해. 차이는 뒤의 패턴이 실패해도 이 수량자가 소비한 범위 안으로 백트래킹하지 않는다는 거야.

뒤 요소가 성공하려면 앞에서 잡은 문자를 돌려받아야 하는 패턴에는 쓰면 안 돼. 반대로 어떤 분할로도 결과가 달라지지 않는다고 확인한 자리에서는 불필요한 재시도를 줄일 수 있어.

실패 경로를 짧게 만들 수 있어

a+b를 aaaaaaa에 적용하면 a+가 문자를 하나씩 돌려주며 뒤의 b를 다시 시도해. a++b는 일곱 개의 a를 확정한 뒤 b가 없다는 사실을 확인하면 곧바로 실패해.

(a+)+b처럼 반복이 겹치면 같은 입력을 나누는 방법이 급격히 늘 수 있어. 안쪽을 (a++)+b로 고정하면 그 분할을 다시 시도하지 않으므로 이 형태의 파국적 백트래킹을 막을 수 있어. 다만 패턴의 의미가 유지되는지는 정상·실패·경계 입력으로 따로 증명해야 해.

지원 여부는 엔진과 버전에 따라 달라

PCRE, Java, Ruby 1.9 이상, Python 3.11 이상의 내장 re는 소유적 수량자를 지원해. JavaScript와 .NET은 이 문법을 지원하지 않고, Python 3.10 이하에서는 별도 regex 모듈을 사용할 수 있어. RE2는 백트래킹 엔진이 아니라서 이 문법이 필요하지 않아.

소유적 수량자를 지원하지 않는 백트래킹 엔진이라면 원자 그룹 (?>...)을 대안으로 검토할 수 있어. 원자 그룹은 트랙 8에서 자세히 다뤄.

Code

소유적 수량자와 원자 그룹·text

# Python 3.11+ 내장 re
import re
re.findall(r'a++b', 'aaaaaaa')  # [] — 돌려주지 않고 바로 실패
re.findall(r'(?>a+)b', 'aaaaaaa')  # [] — 원자 그룹도 같은 결과

# Java
Pattern.matches("a++b", "aaaaaaa")  // false, 백트래킹 시도 없음

# PHP/PCRE
preg_match('/a++b/', 'aaaaaaa')  // 0

# 큰 입력에서 성능 차이가 드러남
# 'a' * 30 + 'X' — 적대적 입력
# (a+)+ → 지수 시간, 분 단위로 멈출 수 있음
# (a++)+ → 선형 시간, 즉시 실패

소유적 수량자 — *+ ++ ?+

소유적 수량자는 잡은 문자를 돌려주지 않아

실패 경로를 짧게 만들 수 있어

지원 여부는 엔진과 버전에 따라 달라

Code

External links

Exercise

Progress

댓글 0