Regex Performance - 2021.05.02

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

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

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

regex debugger

https://regex101.com/

regex101: build, test, and debug regex