정규표현식의 최소일치(non-greedy match)

   정규 표현식에서 최소 일치 (non-greedy match)는 주어진 조건이 만족되는 최초의 위치까지를 일치하는 것으로 간주함을 의미한다. 정확한 의미는 예제를 살펴 보면 더 확실해 진다. 우선 vim에서의 사용법을 살펴 보고, 후에 python에서의 사용 예를 살펴 본다.

  python 이나 vim 에서 정규표현식을 사용할 때 점 한 개(.)는 '모든 문자'를 의미하게 된다. 예를 들면 vim에서

/line.\+$

를 하면 각 줄에서 line 이란 문자열이 나타나는 곳에서부터 아무 문자(.)나 아무 개수(\+)나 나오고 줄 끝($)까지 를 찾는다는 의미이다. 그래서 다음과 같은 결과를 얻는다.

'line'이란 문자열이 나타난 곳에서부터 줄 끝까지가 match 된 것을 알 수 있다.

그 원리를 도식적으로 설명하자면 다음과 같다.

문제는 .\+ 을 사용하여 특정 조건으로 감싸는 모든 글자를 선택하고자 할 때 나타난다. 즉,

<a href="1.html">앞으로</a><br/><a href="2.html">다음으로</a>

과 같은 내용이 한 줄에 다 있다고 했을 때

<a href=".\+">

를 하게 되면 다음과 같은 결과를 얻게 된다.

<a href="1.html">앞으로</a><br/><a href="2.html">다음으로</a>

즉, 위에서 href=" 뒤에 아무 글자나 오고, "> 로 닫히는 부분은 위처럼 2.html 까지가 선택이 된다. 이것은 최대일치(greedy match^[각주:1]), 즉, 조건이 만족되는 곳의 끝까지를 일치하는 것으로 간주했기 때문인데, 만약 1.html 을 뽑아 내려는 의도였다면 적당하지 않다. 이렇게, 즉, 원하는 조건에 일치되는 최소 영역까지만 일치하는 것으로 간주하고자 할 때 최소 일치를 사용해야 한다. 즉, pattern

<a href=".\+">

는 a href=" 에서 시작해서 아무 글자나 아무 개수가 나오고 "> 가 나오는 곳 까지이므로,

<a href="1.html">앞으로</a><br/><a href="2.html">다음으로</a> 에 맞기도 하고,
<a href="1.html">앞으로</a><br/><a href="2.html">다음으로</a> 에 맞기도 한다.

위처럼 두 곳에 맞을 수 있는데, pattern 이 맞는 최초의 위치까지만을 일치하도록 하는 것이 바로 최소 일치이다. 이러한 최소일치(non-greedy match)는 vim 에서는  \{-} 를, python 에서는 .*? 를 사용하게 된다.

위는 줄의 처음부터 아무 글자나 나오고 첫 tab 이 나오는 곳까지를 찾는 장면이다. 이것은 사실 파일에서 tab 으로 컬럼을 구분한다고 할 때 첫 번째 컬럼을 삭제하기 위해 미리 테스트 해 본 것인데 그 구체적 의미는 다음과 같다.

\^.\{-}\t : \ 는 vim 에서 찾기 명령을 위한 특수 문자.    
\^.\{-}\t : ^ 는 줄의 처음을 나타내는 특수 문자.   
\^.\{-}\t : . 은 모든 문자에 대한 일치를 나타내는 특수 문자. 아무 문자나 상관없다는 얘기.   
\^.\{-}\t : \{-} 는 최소 일치를 의미하는 문자열.    
\^.\{-}\t : tab 을 의미.    
\^.\{-}\t : 합하면 아무 문자나 여러 개가 오다가 tab 이 나오는 첫 번째 위치.    
\^.\{-}\t : 줄의 처음부터 시작해서 아무 문자나 아무 개수가 나오다 tab 이 나오는 첫 번째 위치.  

위처럼 잘 찾아지니 원래 하려던 작업, 즉 첫 번째 컬럼을 없애고자 한다면 다음과 같은 명령어를 사용하면 된다.

:%s/^.\{-}\t//g

즉, 줄의 처음부터 시작해서 아무 문자나 아무 개수나 나오다가 첫 번째 tab 이 나오는 위치까지를 공백으로 치환하면 되는 것이지. vim 에서 치환을 의미하는 %s는 다음의 형식을 따른다.

:%s/pattern1/pattern2/option

즉, pattern1 을 pattern2 로 바꾸고, option 을 뒤에 주고. 위에서는 최소 일치된 pattern1 을 아무것도 아닌 것, 즉 / 과 / 사이에 아무것도 없으니 pattern1 을 아무것도 아닌 것으로 바꾸는 것이 되고, 결과적으로 pattern1 을 삭제하는 효과를 갖는다. option 으로 준 g 는 global 을 의미하는 것으로, 현재 파일 내의 '모든 곳'에서 이와 같은 치환 작업을 하도록 명령한다.


지금까지는 vi 에서의 사용 예였고, python 에서의 사용 예를 살펴 보면 다음과 같다.

[adnoctum@bioism batch_pubmed]$ grep -P "\.\*\?" *.py
get_pubmed_search_by_keyword.py:                m = re.search('<Id>(.*?)</Id>',line);
get_pubmed_search.py:           m = re.search('<Id>(.*?)</Id>',line);
get_pubmed_search_with_gene_name.py:            m = re.search('<Id>(.*?)</Id>',line);
get_related_pmid.py:            m = re.search('<Id>(.*?)</Id>', line);
get_title_from_pubmed_reform.py:                m = re.search('<b>(.*?)</b>', line);
makefile.py:            m = re.search('#include <(.*?)>$',line);
makefile.py:            m = re.search('#include <(.*?)>$',line);
xmltoflatfile.py:               m = re.search('<MedlineCitation .*?>',line);
xmltoflatfile.py:               m = re.search('<Article .*?>',line);
xmltoflatfile.py:               m = re.search('<JournalIssue .*?>',line);
xmltoflatfile.py:               m = re.search('<AuthorList .*?>',line);
xmltoflatfile.py:                       m = re.search('<Volume>(.*?)</Volume>',line);
xmltoflatfile.py:                       m = re.search('<PMID .*?>(.*?)</PMID>',line);
xmltoflatfile.py:                       m = re.search('<LastName>(.*?)</LastName>',line);
xmltoflatfile.py:                       m = re.search('<ForeName>(.*?)</ForeName>',line);
xmltoflatfile.py:                       m = re.search('<Affiliation>(.*?)</Affiliation>',line);
xmltoflatfile.py:                       m = re.search('<MedlinePgn>(.*?)</MedlinePgn>',line);
xmltoflatfile.py:                       m = re.search('<Title>(.*?)</Title>',line);
xmltoflatfile.py:                       m = re.search('<Year>(.*?)</Year>',line);
xmltoflatfile.py:                       m = re.search('<Month>(.*?)</Month>',line);
[adnoctum@bioism batch_pubmed]$

grep 을 써서, 개인적으로 python script 를 의미하기 위한 확장자^[각주:2] *.py 파일에서 최소 일치인 .*? 가 쓰인 예를 찾기 위해서 위처럼 해보면 된다. 재미있는 예를 하나 보면,

m = re.search('<PMID .*?>(.*?)</PMID>',line);

이 부분인데, 이 경우는

<PMID version="1">12343322</PMID>

와 같은 경우처럼 version 명이 앞에 있을 때조차도 <PMID> tag 로 감싸인 실제 PMID인 12343322 를 뽑아 내기 위해 이렇게 사용되었다. 즉, <PMID .*?> 에 의해 첫 번째 > 가 나오는 곳에서 이곳의 .*? 는 끝났을 것이다. 그 이후 다시 .*? 에 의해 정확히 우리가 원하는 PMID 12343322 가 일치가 되겠지, 곧바로 </PMID> 에 걸리게 되니까. (.*?) 처럼 ( ) 가 쓰인 이유는 이렇게 일치된 문자열을 변수로 저장해서 나중에 뽑아 사용하기 위한 python re 모듈의 사용법 때문이다.

1. greedy 라는 단어 때문에 '탐욕적' 이란 말이 사용되는데, 흠, ㅋ, 좀 이상하다. 난 최대일치 라는 말을 사용. [본문으로]
2. 위는 리눅스에서의 사용 예이고, 리눅스에서는 파일 확장자가 의미가 없다. [본문으로]