Regular Expression 종류, 동작 방식, 성능

 

Regular expressions by DALL·E 2

 

개발을 하다보면 Regular Expression을 사용할 일이 종종 생긴다.
패턴 매칭을 통해 String을 검증하기도 하고, 특정 패턴의 String을 검색하는 데에도 사용한다.

하지만 따로 공부를 하지 않다보니 매번 원하는 식을 찾는데에 시간이 걸렸다.
또한 내가 쓰는 패턴이 정확히 어떤 동작을 하는 것인지에 대한 이해도 부족했다.

그래서 정규식의 종류, 작동방식, 성능에 대해 알아보기로 했다.
한 번에 다 외우기보단 정리를 해두고 자주 보면서 익히면 생산성을 향상시켜줄 수 있을 것이다.

종류

1. Anchor

시작점과 끝점을 나타낸다.

^: 시작점
$: 끝점
\b: Word boundary; 문자(\w)와 문자가 아닌 것(\W)의 경계를 나타낸다.

2. Quantifier

원하는 패턴이 몇 번이나 나오는지에 대해 매칭한다.

2.1 Greedy Quantifier

일반적으로 Quantifier라고 하면 아래 표현들을 말한다.
2.2, 2.3의 Quantifier와 구분하여 Greedy Quantifier라고 부른다.
이름처럼, 최대로 매칭가능한 범위까지 매칭 후, 실패 시에 백트래킹을 통해 탐색한다.

*: 0개 이상
+: 1개 이상
?: 0 또는 1개 (optional)
{m}: m개
{m,}: m개 이상
{m,n}: m개 ~ n개

2.2 Lazy Quantifier

최소로 매칭되는 범위부터 매칭을 시작한다.
실패 시 범위를 늘려간다.

Greedy Quantifier + ? 형태
e.g. ??, *?

2.3 Possesive Quantifier

Greedy Quantifier와 같이 최대로 매칭가능한 범위까지 매칭한다.
하지만 Backtracking하지 않는다.
최대 매칭에서 패턴을 찾지 못할 경우 바로 실패하기 때문에 사용 시 주의하여야한다.

Greedy Quantifier + +
e.g. *+, {m,}+

3. Character Class

괄호안의 character 목록에 매칭한다.
^를 붙이면 괄호안의 character 목록이 아닌 경우에만 매칭한다.

e.g. [abcd], [^a-z]

4. Special Characters

\d: Digit; [0-9]와 동일
\D: Non-digit; [^0-9]와 동일
\w: Word; [a-zA-Z0-9_]와 동일
\W: Non-word; [^a-zA-Z0-9_]와 동일
\s: Whitespace; [ \t\r\n\v\f]와 동일
\S: Non-whitespace; [^ \t\r\n\v\f]와 동일

5. Group Matching

괄호안의 패턴과 매칭한다.
매칭된 그룹이 저장되어 필요 시 사용할 수 있다.

(abc): Capturing group; abc와 매칭하고 매칭된 부분을 저장함
(?:abc): Non-capturing group: abc와 매칭하지만, 저장하지는 않음.

6. Lookaround (Lookbehind/Lookahead)

괄호 안의 패턴이 X의 앞이나 뒤에 오는 경우의 X를 찾는다.
(positive; 오지 않는 경우는 negative)

Group matching과 달리, 괄호안에서 매칭된 내용에 대해서는 매치에 포함하지 않는다.

// positive lookahead
"XY".replace(/123X(?=Y)/, ""); // 123X

// group matching - Y도 매치에 포함됨.
"XY".replace(/123X(Y)/, ""); // 123

Lookahead

X(?=Y): positive; Y가 뒤따르는 X를 찾음.
X(?!Y): negative; Y가 뒤따르지 않는 X를 찾음.

Lookbehind

(>=Y)X: positive; Y가 앞에 오는 X를 찾음.
(>!Y)X: negative; Y가 앞서지 않는 X를 찾음.

7. Alternation

or 연산자처럼 alternation으로 이어진 패턴들에 대해 매칭한다.

(cat|dog|fish): cat 또는 dog 또는 fish에 매칭

동작 방식

정규식은 굉장히 단순해보이는 마법같은 도구이다.
하지만 내부에서 문자열과 패턴에 대해서 하나하나 맞춰보며 매칭을 판별한다.

실제로는 더욱 복잡하지만 간단히 아래와 같은 원리로 동작한다.

1. Sequential processing
   기본적으로 regex 엔진은 regex 패턴과 문자열을 왼쪽부터 오른쪽으로 한글자씩 소비한다.
2. Matching and consuming characters
   패턴에서 일반 문자토큰을 만난 경우, 문자열의 문자와 비교 후 맞으면 소비하고, 패턴과 문자열 모두 다음으로 이동한다.
3. Handling quantifier
   Quantifier와 만난 경우 regex 엔진은 매치되는 최대 범위까지 매칭한다.
4. Backtracking
   패턴과 문자열이 맞지 않아서 더 이상 진행할 수 없는 경우, 한 단계씩 undo하여 돌아온다.
   돌아온 자리부터 새로운 match를 찾는 것을 시작한다.
5. Alternation (|)
   |가 있다면 차례로 매칭해본다. 실패하면 백트랙한다.

성능

위 알고리즘에서 봤듯이 정규식도 탐색에 시간이 소요된다.
그러므로 정규식 사용시 패턴을 마구잡이로 사용하면 성능이슈가 생길 수 있다.

시간 복잡도

복잡하지 않은 경우 (선형 탐색): Linear time
복잡한 경우 (Backtracking): Exponential time

성능 이슈 피하기

백트래킹 유발을 피한다.

백트래킹은 시간 복잡도를 Exponential하게 만드니 주의가 필요하다.

1. Quantifier의 Nesting은 피한다. ex) (a*)*
2. Non-greedy(Lazy, Possesive) Quantifier로 대체가 가능한 경우 대체한다.
3. 가능성이 높은 후보를 alternation의 앞쪽에 배치하여 backtracking의 확률을 줄일 수 있다.
   e.g. dog 80%, cat 15%, eagle 5% 라면 (dog|cat|eagle)

패턴의 범위를 좁힌다.

1. anchor를 사용할 수 있는 경우 사용한다.
2. 어떤 character인지 알 경우에는 최대한 좁은 범위를 선언한다.
   e.g. . -> [a-z] -> [abcde]
3. word boundary를 활용한다.
   e.g. This is a dog.이란 문자열에서 is는 This의 i에서도 탐색을 시작한다.
   반면 \bis\b는 word boundary가 적용되어 뒤의 is에서만 탐색을 시작하면된다.

 

도움이 되는 사이트

https://regex101.com/ regex를 만들고 테스트해볼 수 있다. 작성한 regex에 대한 분석도 우측에 제공한다.