본문 바로가기
프로그래밍 놀이터/안드로이드, Java

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

by 돼지왕 왕돼지 2020. 2. 27.
반응형

[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 을 나누어 실행하는 것은 성능 저하를 일으킬 수 있다.





반응형

댓글