탐욕적 수량자, 또는 욕심쟁이(greedy) 수량자라고도 한다. 이와 반대되는 것은 게으른(lazy) 수량자이다. 수량자에 대해서는 이전에 잠깐 언급했었다. 말 그대로 몇 개를 선택할지 결정하는 것으로 *, +, ?, {n}, {n,}, {n,m}등이 있다. 이런 수량자는 기본적으로 탐욕적(greedy) 수량자이다. 그렇다면 탐욕적이란 의미가 수량자에 어떻게 적용되는지 알아보자.
여기서 탐욕적이라 함은 백트래킹(backtracking)1 알고리즘을 사용한다. 설명하자면 우선 정규 표현식을 검사할 문자열에서 전체를 한 덩어리로 보고 정규표현식과 매치되는지를 검사한다. 만약 매치되지 않는다면 끝에서 한 문자를 뺀후 다시 검사한다. 이렇게 뒤에서 하나씩 빼가면서 맞을 때 까지 검사해 나간다.
탐욕적 수량자 *
이렇게 정규표현식과 매치되는 가장 큰 덩어리를 찾으려고 하기 때문에 탐욕적이라고 이름지었다. 설명만으로는 감이 안올 수 있겠다. 하지만 예제를 보면 쉽게 이해할 수 있다.
위 정규 표현식에 매칭되는 문자열은 사실 여러 개가 있을 수 있다. "Apple" 또는 "Orange" 등이 있을 수 있지만 중간에 "(이중 따옴표)는 무시된 채 가장 끝에있는 "(이중 따옴표)가 매칭된다. 즉 중간에 있는 "(이중 따옴표)들은 단순한 문자(.*에 의해)로 매칭된 것이다. 이런 현상은 앞에서 말했듯이 백트래킹(backtracking) 방식으로 문자열을 매칭시키기 때문이다. 따라서 탐욕적 매칭에 대해 모른다면 당황할 수도 있겠다.
위와 같이 탐욕적 방식으로 문자열을 찾을 목적도 있겠지만 일반적으로 원래의 의도는 "Apple"이나 "Orange"을 찾는 것일 것이다.
게으른 수량자 *?
일반적인 의도?에 맞는 정규표현식은 게으른(lazy) 수량자를 사용하면 되겠다. 게으른 수량자는 단순하게 ?를 탐욕적 수량자의 뒤에 붙여주면 된다.
게으른 수량자는 단순히 앞에서부터 순서대로 정규표현과 매치되는지 찾아간다. 이런 특성으로 탐욕적 수량자와 문자의 검사량에 차이가 난다. 원본 문자열의 길이가 길면 길수록 탐욕적 수량자는 더 많은 일을 할 수 밖에 없다. 단 매칭 되는 문자열이 문자열 전체 하나만 있을 경우는 탐욕적 수량자가 효율적일 수 있겠다.(이런 경우는 일반적이지는 않지만..)
탐욕적 수량자 {m, }
{m,}는 m번 이상이 된다. 여기서 m이 0이되면 *와 동일한 의미다.
이 밖에 몇가지 까다로운 경우가 있지만 일반적으로 이정도만 알고 있어도 충분하다.
- 위키백과 참조 - 한정 조건을 가진 문제를 풀려는 전략, 퇴각검색이라고도 한다. [본문으로]