[regex] 정규식의 성능을 개선해보자.

[regex] 정규식의 성능을 개선해보자.

https://www.javaworld.com/article/2077757/optimizing-regular-expressions-in-java.html

Java pattern-matching engine and backtracking

-

java.util.regex package 는 Nondeterministic Finite Automation(NFA) 라 불리는 pattern-matching engine 을 사용한다. (2007년 글로 지금은 NFA 를 사용하지 않을 수도 있다.)

NFA 는 nondeterministic 이라 불리는데, 주어진 string 에 대해 regex 를 match 할 때 각각의 char 들이 regex 의 다른 파트에 대해 여러번 check 될 수 있기 때문이다. ( 돼왕 : 이해가 잘 안 된다면 글을 끝까지 읽어보자 )

이 방식은 .NET, PHP, Perl, Python, Ruby 등에서 광범위하게 사용되는 방식이다.

이 방식이 여러 종류의 quantifier 와 lookaround 와 같은 특별한 기능도 가능하게 한다.

-

NFA 는 backtracking 을 사용한다.

pattern-matching engine 은 실패에 도달하기 전까지 모든 가능성에 대해 시도한다.

더 빠른 이해를 위해 다음 예를 보자.

input string : scared

regex : "sc(ored|ared|oring)x"

처음 엔진은 sc 를 찾는다.  

그 다음 다음 순서로 sc 다음의 char 들을 평가한다. ored, ared, oring.

ored 를 선시도하며 매칭되지 않는다.

그 다음 ared 가 매칭될 테니 그 다음인 x 를 평가한다. 

x 가 없기 떄문에 그 다음인 oring 을 평가한다.

모든 | 된 녀석들이 매칭되지 않았기 때문에, engine 은 다음 sc 를 찾는다.

다음 sc 가 없기 때문에 fail 이 된다.

( 돼왕 : 위에서 설명한 nondeterministic, char 들의 여러번 평가가 이에 해당한다. )

Optimization tips for backtracking

-

regex 의 최적화 팁 중 중요한 분야가 바로 backtracking 횟수를 최소화하는 것이다.

-

Java 의 패턴 매칭 엔진은 backtracking 최소화에 대한 몇 가지 최적화 로직을 가지고 있다.

그러나 엔진에 완전 전적으로 의존할 수만은 없다.

-

regex 는 생각보다 오래 걸릴 수 있다.

그래서 실패하는 케이스에 대해 성능 측정을 해봐야 한다. 그리고 이 중 "거의 매칭되지만 아쉽게 매칭되지 않음" 을 하는 것이 가장 좋다.

( 돼왕 : backtracking 횟수 줄이는 방법은 쭉 읽어보면 나온다. )

Simple ways to optimize regular expressions

-

regex 를 한번 초과해서 사용한다면, pattern 을 compile 해서 사용하라.

Pattern.matches() 대신 Pattern.compile() 을 사용하란 말이다.

Pattern.matches() 는 호출될 때마다 compile 을 수행한다고 보면 된다.

그리고 Matcher object 도 reset 을 통해 재사용하는 것이 좋다.

-

(X | Y | Z) 와 같은 alternation regex 는 느리기로 이미 소문이 나있다.

저 방식을 써야 한다면 더 자주 등장할 것 같은 녀석은 앞에 배치하는 것이 좋다.

또한 더 구체화된 패턴을 사용하는 것이 좋다.

(abcd|abef) 대신 ab(cd|ef) 와 같이 사용하는 것이 더 좋다.

후자 방식으로는 NFA 가 ab 에 대해 다시 매칭하지 않을 것이기 때문이다.

regex 로 모든 것을 푸는 것이 멍청한 방법일 수도 있다.

String.indexOf() 로 X, Y, Z 를 찾는 것이 훨씬 빠를 수 있다.

-

Capturing group 은 사용할 때마다 약간의 성능 저하를 가져온다.

capturing 이 꼭 필요하지 않다면 non-capturing group 을 사용하는 것이 좋다.

예를 들면 (X) 대신 (?:X) 를 사용하는 것이 좋다.

Let the engine do the work for you

-

java 의 regex engine 은 regex 를 compile 할 때 여러 가지 방법으로 최적화를 시도한다.

예를 들어 regex 가 input string 중 반드시 포함된다면 engine 은 그 string 을 먼저 search 한다.

또한 전체 expression 이 절대 매칭될 수 없다거나 하면, 해당 string 에 대한 regex 을 실제 check 하지 않고 fail 을 뱉어낸다.

-

engine 이 input string 의 length 를 regex 가 기대하는 length 기준으로 체크하는 것이다.

예를 들어 \d{100} 이라고 되어있는데, input string 이 100 length 가 안 된다면 engine 은 regex 를 돌려보지 않고 바로 fail 을 뱉는다.

-

복잡한 regex 를 사용할 때면 regex engine 이 최적화를 할 수 있는 방향으로 작성하는 것이 좋다.

예를 들어 필수 string 을 grouping 이나 alternation 에 숨기지 않는 것이 좋다.

그리고 가능하다면 길이를 명시해주는 것이 좋다.

Optimizing greedy and reluctant quantifiers

-

* 나 + 와 같은 greedy quantifier 는 가능한한 많은 char 가 매칭되는 방향으로 match 를 찾는다.

심지어 최대한 매칭을 한 후 나머지 regex 의 매칭을 할 char 가 없어도 말이다.

따라서 greedy quantifier 의 경우 backtracking 을 하게 되고, overall match 가 찾아지거나 fail 이 될때까지 backtracking 을 계속한다.

reluctant(or lazy) quantifier 는 가능한한 적은 char 가 매칭되는 방향으로 match 를 찾는다.

-

만약 찾고자 하는 char 가 string 의 마지막부에 있다면 greedy quantifier 를 사용하는 것이 좋다. (ex) .*a)

만약 찾고자 하는 것이 string 의 초반부에 있다면 lazy quantifier 를 사용하는 것이 좋다. (ex) .*?a)

-

regex 를 더 정밀하게 쓰는 것이 좋다.

예를 들어 두개의 a 사이의 char 들을 구하는 것이라면 a(.*)a 대신 a([^a]*)a 를 사용하는 것이 좋다.

Possessive quantifiers and independent grouping

-

Possessive quanifier 와 independent grouping 은 regex 를 최적화하는데 아주 유용한 녀석들이다.

가능한한 이 녀석을 사용하는 것이 엄청난 성능 향상을 가져오곤 한다. ( backtracking 하지 않지 않는다. )

Possessive quantifier 는 추가 + 사인으로 마킹된다. 

예를 들어 X?+, X*+, X++ 이다.

independent grouping 은 (?>X) 이다. ( 돼왕: 이 녀석은 non-capturing & possessive 로 작동한다. )

-

두개의 operator 는 모두 backtracking 동작을 disable 시킨다.

backtracking 을 disable 시키기 때문에 regex 를 fail 로 몰고가기도 하기 때문에, 정확히 이해하고 써야 한다.

A note about the StackOverflowError

-

가끔 Pattern class 가 StackOverflowError 를 던지곤 한다.

이것은 Java 1.4 부터 있어온 버그이며, won't fix 로 결정난 상태이다.

이 에러는 Pattern 클래스가 regex 를 compile 하여 match 를 수행할 때 실행될 small program 으로 만들 때 발생한다.

이 small program 은 보통 recursive 하게 발생하며, 너무 많은 recursive 가 발생하면 이 에러가 발생하는 것이다.

그리고 이것이 발생하는 경우는 주로 alternation 을 사용한 경우이다.

-

만약 이 에러를 마딱뜨린다면, regex 를 다시 쓰거나, 여러개의 sub-expression 을 나누어 실행하도록 해야 한다.

sub-expression 을 나누어 실행하는 것은 성능 저하를 일으킬 수 있다.

alternation regex, backtracking, backtracking optimization, capturing group, greedy quantifier, greedy quantifier backtracking, java nfa, java pattern matching engine, java regex, lazy quantifier, lookaround, minimize backtracking, nfa backtracking, non-capturing, non-capturing group, nondeterministic finite automation, Optimizing greedy and reluctant quantifiers, pattern matching engine, pattern matching engnine, pattern StackOverflowError, Pattern.compile, possesive quantifier, Possesive quantifiers and independent grouping, possessive quantifier, quantifier, regex backtracking, regex compile, regex engine optimization, regex is not silver bullet, regex pattern compile, regex performance, regex performance improvement, regex StackOverflowError, regexp backtracking, reluctant quantifier, sub expression, [regex] 정규식의 성능을 개선해보자.