검색엔진 : Boolean Model

Boolean Model은 정보검색(:12) 분야에서 가장 오래된 모델중 하나이며, 거의 대부분의 상용/비상용 정보검색 시스템이 채택하고 있는 모델이다. 불리언이라는 용어가 의미하는 바와 같이, 이 모델은 집합이론에 근거한 불리언 로직을 이용해서 질의어와 문서를 색인어의 집합으로 표현하는 모델이다. 불리언 모델의 단점을 보완한 Extended Boolean Model 이 있는데, 이와 구분하기 위해서 Pure Boolean Model 이라고 부르기도 한다.

불리언 모델은 사용자 쿼리로 부터 주어진 Term을 포함한 문서를 찾는다고 하면, 해당 문서가 Term을 포함하고 있는지 (true), 아닌지 (false)에 대한 정보만을 가지고 문서를 찾아낸다. 매우 단순하고 효율적이며 빠른 구현이 가능하지만, 문헌의 우선순위나 사용자 질의에 대한 가중치등을 부여할 수 없기 때문에, 사용자의 의도와 다른 결과물을 보여줄 확률이 매우 높다.

때문에 검색엔진을 구현하기 위한 모델로는 거의 사용되지 않고 있다. 대부분의 검색엔진은 Extend:::Boolean:::Model(:12)이나 Vector:::Space:::Model(:12)을 쓴다.

하지만 사용자 질의 처리를 위한 목적으로는 여전히 널리 사용되고 있다. SQL(:12)혹은 검색엔진에서의 사용자 입력등에 있어서 불리언 모델은 가장 쉽고 일반적으로 사용할 수 있다. 이 문서에서는 사용자 질의 처리의 관점에서 불리언 모델이 가지는 장점과 구현 방법에 대해서 알아보려고 한다.

불리언 모델은 매우 직관적이다. 검색질의어의 처리를 위해서 불리언 모델을 사용할 경우 해당 단어를 포함한다, 포함하지 않는다의 TRUE, FALSE로 단순화 시킬 수 있기 때문이다. 사용자 질의어를 처리하기 위해서 Boolean Model을 적용한 경우 Boolean Query라고 부른다. 물론 사용자 자연어에 좀더 가까운 사용자 질의어의 처리를 위해서 vector space model이나 확장 불리언 모델을 사용할 수도 있을 것이다. 실제 이러한 시도도 이루어 지고는 있지만, 지나치게 복잡하고, 들이는 비용에 비해서 얻을 수 있는 이득이 별로 없기 때문에 그리 대중화되지는 못하고 있는 실정이다.

이를테면 다음과 같은 질의어의 작성이 가능하다.

• "A"와 "B"를 모두 포함하는 문서의 검색

+A +B

• "A"를 포함하지만 "B"를 포함하지 않는 문서의 검색

+A -B

몇몇 대중적인 검색서비스에서 '자연어를 입력하고 이를 처리'할수 있음을 마케팅 포인트로 부각시킨 적도 있었지만, 결국 형태소 분석을 동원한 Boolean Query의 응용일 따름이였다. 예컨데, "세상에서 가장 좋은 검색엔진시스템" 이라고 사용자가 쿼리를 입력하였을 경우 아래와 같이 단순 Boolean Query로 변경해서 사용한다. 순전히 형태소분석기의 영역이라고 볼 수 있을 것이다.

Boolean Query는 단순하다는 장점을 가지지만, 너무 단순해서 사용자의 의도를 충분히 파악하기 힘들다는 점이 단점이 된다.

이 문제는 True, False 외에도 Level과 Priority를 줌으로써 어느 정도 해결할 수가 있다. 이 방식은 형태소 분석기와 밀접한 관계를 가진다.

예를 들어 사용자가 "정보검색엔진" 이라는 질의어를 만들었다고 가정을 해보자. 이 쿼리를 순전히 불리언 모델에 의해서만 표현한다면, "정보검색엔진"을 포함한 문서를 찾아라고 검색엔진에 알려줄 수 있을 것이다.

그러나 이 경우 하나의 단어를 완전히 포함한 TRUE 상태의 문서들만이 검색대상이 되므로, 검색되는 문서의 양이 극히 적게 될 것이다. 사실은 정보검색 이라든지 검색엔진과 같은 단어를 포함한 문서도 충분히 가치있는 문서가 있을 수 있는데, 모두 제외되어 버리는 것이다.

그렇다면, 형태소 분석기를 이용해서 사용자질의어를 다음과 같은 stack(:12) 구조로 세분화해서 넘겨줄 수 있을 것이다. 다음과 같은 간단한 스택구조로 표현할 수 있다.

이렇게 사용자 질의어를 형태소단위로 분류하면 다음과 같은 장점을 얻을 수 있다.

• 더 많은 문서를 검색해 낼 수 있다. - precision과 recall 을 적절히 조절할 수 있다 -

"정보검색엔진"을 모두 포함한 문서가 가장 좋은 문서일 확률이 높긴 하지만, 찾아낸게 100만개 문서중 5개 정도 문서라면, 그만큼 많은 좋은 문서를 놓치게 될 것이다. Recall(:12)이 너무 작아서 문제가 되는 경우다.

이 경우 "정보검색"을 포함한 문서까지 범위를 확대하게 되면, Recall을 높일 수 있을 것이고, 더 많은 문서를 검색해낼 수 있을 것이다.

• Level 에 따라 질의어에 가중치를 줄 수가 있다.

"정보검색엔진"을 포함한 문서는 1점, "정보검색"을 포함한 문서는 0.8점, "정보"를 포함한 문서는 0.7 점 하는 식이다. 이것은 우리의 직관과도 잘 맞아떨어지는 점이 있다. 정보검색 을 포함한 문서보다는 정보검색엔진을 모두 포함한 문서가 더 좋은 문서일 확률이 높기 때문이다.

• 검색 튜닝 포인트로의 활용

검색엔진을 만드는데, 가장 큰 넘어야될 산은 "문서의 양이 너무 많다"는 점일 것이다. 문서의 양이 많으면, 당연히 성능이 떨어질 수 밖에 없다. 1000만건의 문서에서, "A"라는 단어를 포함한 문서를 가져오는데 걸리는 시간이 3초라면 문제가 될 수 밖에 없을 것이다.

사용자가 "검색 엔진" 이라는 질의어를 선택했다고 보자. 검색을 포함한 문서가 500만건 엔진을 포함한 문서가 300만건 이라면, 이들 문서를 가져오고, score 연산을 해서 높은 점수의 문서가 위로 올라오게 하는 것만 해도 상당한 시간이 소비될 것이다.

이것을 "(검색엔진(검색)(엔진))"의 형식으로 표현했다고 가정해보자. 검색엔진을 포함한 문서는 당연히 더 적을 수 밖에 없을 것이다. "검색엔진"을 포함한 문서가 2000건 정도가 나왔다면, 검색 페이지 10개를 네비게이션할 수 있는 양이되므로, 굳이 "검색" 과 "엔진"을 모두 검사할 필요가 없을 것이다. 게다가 개개의 단어로 검색한 것 보다, 오히려 더 좋은 검색결과를 보장받을 수 있을 것이다. 800만건의 문서를 뒤져야 되는걸 2000건만 뒤지면 되니, 검색시간역시 크게 단축시킬 수 있을 것이다.

일단 형태소 분석기가 stack 형태로 표현된 단어들을 리턴한다고 가정을 해보자. 대부분의 형태소 분석기가 당연히 지원하고 있는 기능일 것이므로, 이렇게 가정한다고 해도 문제되진 않을 것이다.

이렇게 해서 넘어온 정보를 분석하는 프로그램은 비교적 간단하게 구현해낼 수 있을 것이다.

1. (를 만나면 depth++ 한다.
2. )를 만나면 depth-- 한다.
3. (와 )사이에 있는 것은 Term 이다.

테스트 결과