Lazy (Non-Greedy) 매칭 — *? +? ??

? 추가로 quantifier 를 minimal-match

greedy → lazy 뒤집으려면 quantifier 에 ? 추가:

*? — 0 이상, 가능한 적게
+? — 1 이상, 가능한 적게
?? — 0 또는 1, 0 선호
{n,m}? — n 과 m 사이, n 선호

Lazy quantifier 는 최소 소비, 패턴 나머지 실패할 때만 늘림. Greedy 와 반대지만 같은 backtracking 기계.

HTML 재앙, 수정

Greedy .* 가 두 <p> 블록을 한 매칭으로 먹음. Lazy .*? 는 각각 따로 매칭 — 마지막 </p> 대신 첫 거에서 멈춤.

성능 노트

Lazy 가 무료 아냐. 엔진은 여전히 backtrack; 그냥 반대 방향 backtrack (줄이는 대신 늘림). 어떤 패턴은 lazy 가 빠르고 어떤 건 greedy 가 빠름. 더 큰 win 은 정확성 — lazy 가 보통 원하는 거 매칭.

Negated class 대안

종종 가장 깨끗한 수정은 lazy 도 greedy 도 아닌 negated class. <p>([^<]*)</p> 는 "< 가 아닌 거 다 캡처" — backtracking 없음, 놀람 없음. 트랙 8 에서 이게 ReDoS-safe 패턴의 비결임 보여줘.

Code

Lazy 가 greedy 재앙 수정·python

import re

html = '<p>first</p> <p>second</p>'

# Greedy — 잘못
re.findall(r'<p>.*</p>', html)
# ['<p>first</p> <p>second</p>']

# Lazy — 맞음
re.findall(r'<p>.*?</p>', html)
# ['<p>first</p>', '<p>second</p>']

# 더 좋음 — negated class (backtracking 없음)
re.findall(r'<p>[^<]*</p>', html)
# ['<p>first</p>', '<p>second</p>']

# 따옴표 문자열 — 같은 lesson
re.findall(r'"[^"]*"', '"a" "b" "c"')
# ['"a"', '"b"', '"c"']  — 깨끗하고 ReDoS-safe

Lazy (Non-Greedy) 매칭 — *? +? ??

? 추가로 quantifier 를 minimal-match

HTML 재앙, 수정

성능 노트

Negated class 대안

Code

External links

Exercise

Progress

댓글 0