카테고리 없음

Regex Performance - 2021.05.02

지우개발자 2022. 4. 17. 04:33

2021.05.02

이 글은 정규 표현식의 성능에 대해 조사한 글 입니다.

정규표현식의 성능

정규표현식은 문자열을 매치할때 원하는 문자를 빠르게 찾을수 있도록 고안된 하나의 문법이다. 우리는 프로그래밍을 할 때 이를 활용해서 원하는 형식의 문자열을 빠르고 간편하게 찾을 수 있다. 하지만 대부분 정규 표현식의 정확성에는 관심이 있지만 성능면에서 고려해보지는 않았을 것이다. 정규표현식은 성능 면에서 과연 빠를까? 도대체 어떤 원리로 문자열을 탐색해 나가는 것일까? 이 글에서 기본적인 정규 표현식의 기본적인 문법은 다루지 않도록 하고 정규표현식의 매칭 방법과 성능 향상에 대해서만 다뤄보도록 하겠다.

정규표현식의 알고리즘

여기 abc 문자열을 찾고자 하는 정규 표현식 /abc/ 가 있다. 정규표현식은 기본적으로 소거법을 이용해 문자열을 찾는다. 즉 자신이 갖고 있는 문자열중 앞 문자부터 하나씩 소거해, 가장 마지막 문자열까지 모두 소거 됐을 때 해당 문자열을 찾았다고 해석한다.

예를 들어 주어진 문자열이 ababc 이고 정규 표현식이 /abc/ 라면 문자열의 첫 글자인 a 에 대해 정규표현식은 자신이 갖고 있는 a 를 소거한다. 그렇다면 현재 남은 문자는 /bc/ 가 될 것이다. 이어서 b 를 만났을 때 정규 표현식은 자신이 갖고있는 b 를 소거하고 /c/ 만 남게된다. 다음 문자열인 a 를 만났을 때 정규표현식 /c/ 와 매칭되지 않기 때문에 정규 표현식은 자신이 갖고있던 문자열들을 다시 복구 시킨다. 즉 남은 문자열은 다시 /abc/ 가 된다. 찾고자 하는 문자열의 첫 글자인 a 에 대해 일치하지 않았으니 두번째 문자인 b 부터 또 다시 이 조건을 반복한다.

정규표현식의 탐색 방법을 알고 있어야 정규 표현식의 성능을 개선 할 수 있다. 정규 표현식의 매칭 방법중 가장 성능을 떨어트리는 부분이 백트래킹이다. 위의 예시로 보면 정규 표현식은 앞 문자열인 ab 까지 문자열을 찾았고, 그 이후 문자가 또 다시 a 가 나왔기 때문에 다시 두번째 문자열인 b 부터 탐색하고 있다. 즉 탐색된 문자열의 인덱스로 보자면 0 -> 1 -> 2 -> 1 순서이고 2 -> 1 로 다시 돌아가 탐색하는 과정을 백트래킹이라 부른다. 이 부분을 유의하며 앞으로의 성능 개선 방법을 보면 좋을것 같다.

탐욕적 수량자

정규표현식의 표현 연산자중 문자의 Quantity를 나타내는 수량자 +, *, ?, {1}...가 있다. 이중 +, * 수량자는 탐욕적 수량자(greedy)라고 불린다.

예를 들어 /.*foo/ 라는 정규표현식으로 문자열 xfooxxxxfoo 를 찾는다면 매치된 문자열은 xfooxxxxfoo 모두 찾게된다.

정규표현식 디버거를 이용하면 아래와 같은 과정으로 문자열을 탐색한다.

보이는것과 같이 모든 문자열을 찾은 후에 뒤부터 문자열을 추리는 백트래킹 과정이 있다. 이 과정에서 불 필요한 연산이 많이 발생되기 때문에 탐욕적 수량자는 주의해서 써야한다. 찾고자 하는 마지막 문자열이 뒤쪽에 있을때 사용하는것이 가장 좋다.

게으른 수량자

그렇다면 위의 상황에서 앞의 xfoo 를 찾고싶다면 어떤 연산자를 써야할까?

reluctant quantifier ? 를 탐욕적 수량자 뒤에 사용하면 된다.

/.*?foo/ 는 문자열 xfooxxxxfoo 에 대해 문자열 xfoo 를 찾는다.

이 또한 우선 디버거 창을 이용해 살펴보자.

보시다시피 백트래킹을 하지 않고 앞쪽 문자열부터 탐색하는것을 알 수 있다. 이 게으른 연산자는 수량자로 매 문자열을 탐색할때 마다 자신의 바로 뒤쪽 문자열 f 를 수시로 확인한다. 따라서 찾고자 하는 문자열이 앞쪽에 있다면 게으른 연산자를 사용하는것이 좋다.

Possessive quantifier

마땅한 한글 이름이 없어서 영어로 표현한다. possessive 는 기본적을 탐욕적 수량자와 같다. 하지만 백트래킹 과정이 없다. 탐욕적 수량자는 수량자로 문자열을 모두 찾으면 자신의 문자열을 양보하면서 백트래킹 과정을 거치지만 possessive는 자신이 찾은 문자열을 절대 양보하지 않는다. 표현법은 수량자 뒤에 + 기호를 붙히면 된다.

/.*+foo/ 라는 정규표현식이 xfooxxxxfoo 를 만나면 undefined 를 반환한다.

디버거 창을 통해 먼저 살펴보자.

정규표현식 .*+ 가 모든 문자열을 가져갔고 이후 나올 f 와 매칭되는 문자열은 남아있지 않기 때문에 즉시 탐색이 종료되고 undefined 가 반환된다. 백트래킹이 없다는것은 성능상 강력한 이점이 있지만 주의해서 사용해야 한다.

non-capturing group

정규 표현식의 그룹매칭은 /(ab)(cd)/ 와 같은 방식으로 사용한다. 문자열 abcd 매치에 사용하면 두 그룹 ab 와 cd 를 찾는다. 이 때 ab 는 찾을때만 사용하고 결과값으로 받고 싶지는 않다면 non-capturing group 을 사용하면 된다. 표현 방법은 (?:) 이다. (?:ab)(cd) 처럼 사용하면 된다. 캡쳐링은 사용할때마다 약간의 성능 저하가 있기 때문에 매칭할때만 필요한 문자열은 논 캡쳐링 그룹을 사용해주면 좋다.

그 외 미세 팁들

  • 빠른 undefined를 반환하기 위해 정규표현식은 최대한 정확하게 적어주는것이 좋다. 예를 들면 정규표현식으로 찾고자 하는 문자열의 최대길이를 지정해 주면 해당 길이보다 긴 문자열이 들어왔을때 비교를 실시하지 않고 빠른 undefined가 반환된다. 또한 startwith ^ endwith $ 연산자도 활용한다면 역시 매치하지 않을때 빠른 undefined를 반환한다. 이는 각 언어의 컴파일러마다 조금씩 다르다.
  • abbba 문자열에서 bbb를 찾고싶을 때 a.*?a 보다 a[^a++]a 처럼 보다 구체적으로 적어주는것이 성능상 좋다.
  • or 연산자는 무조건 백트래킹을 유발하기 때문에 주의해서 사용한다. 예를들면 (abcd|abef) 보다는 ab(cd|ef) 처럼 최대한 적은 부분만을 비교해 사용하는것이 좋다.

마치며

정규표현식은 편리한 도구일뿐 성능을 보장해 주진 않는다. 실제로 많은 양의 문자열을 잘못된 정규표현식을 사용해 매칭한다면 성능은 눈에 띌 정도로 나쁘다. 따라서 정규표현식을 사용할 때 정확하게 매칭 하는것도 중요하지만, 구체적인 정규표현식을 사용해 성능 또한 고려하는것이 바람직하다.

참고한 글

Performance of Regular Expressions

 

Performance of Regular Expressions

You have probably used regular expressions at least once, but have you ever thought about their performance? My experience shows that most…

medium.com

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

 

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

[regex] 정규식의 성능을 개선해보자. https://www.javaworld.com/article/2077757/optimizing-regular-expressions-in-java.html Java pattern-matching engine and backtracking - java.util.regex package 는 N..

aroundck.tistory.com

regex debugger

https://regex101.com/

 

regex101: build, test, and debug regex

Regular expression tester with syntax highlighting, explanation, cheat sheet for PHP/PCRE, Python, GO, JavaScript, Java, C#/.NET.

regex101.com