검색엔진 : Density based model

공개 검색엔진(:12) Lucene(:12)은 다양한 현대적인 검색모델을 지원하고 있으며, 학습용도 혹은 상업적인 용도 모두에 사용할 수 있다. 여기에서는 루신이 사용하는 모델중 Density based model에 대해서 알아보도록 하겠다.

루신은 vector:::space:::model(:12)기반으로하는 검색엔진(:12)이며, Document:::Term:::Weight(:12)의 계산을 위해서 TF(:12) - IDF(:12)을 사용하고 있다. 상당히 좋은 모델이긴 하지만 몇 가지 문제를 가지고 있다. 예를 들어 아래와 같은 3개의 문장을 포함한 문서가 있다고 가정해 보자.

• A : 구글 검색엔진 ... 그래서 ... 이러한 특징을 ... ... ... ... .. 이다.
• B : 구글은 최근 ... ... 하는 과정에서 ... 검색엔진을 ... .. ... 했다.
• C : 오늘 ... 검색을 해봤더니 ... ... 구글에서 ... ... 엔진은 역시 벤츠.

검색어는 구글 검색 엔진 이라고 가정해보자. 3문서 모두다 "구글 검색 엔진"을 포함하고 있으며, TF(:12)도 모두 1이다. IDF(:12)도 동일하다고 할 수 있으므로, 다른 조건이 같다면 A, B, C 는 모두 동일한 문서유사도를 가지게 될 것이다. 그러나 여러분은 각 문서의 유사도가 다르다는 것을 알고 있다. 인간은 내용을 모두 읽어보지 않더라도 A > B > C 순으로 문서가 유사하다는 것을 알아낼 수 있다. 바로 Term의 발생밀도를 가지고 예측을 하는 것이다.

A 번 문서는 "구글 검색 엔진"이 모두 동일한 위치에서 높은 밀도로 발생했으며, C 번 문서는 각각 다른 장소에서 낮은 밀도로 발생하고 있다. 그렇다면 A 문서가 더 높은 값을 가지도록 계산요소를 포함시킬 수 있을 것이다. 이러한 아이디어에서 만들어진 모델이 Density based model 이다. 단어의 발생위치를 기준으로 계산하는 특성 때문에 Proximity model이라고 부르기도 한다.

일반적인 공식은 다음과 같으며 Density Distance N-Gram Model을 위한 공식이다.

attachment:distence.png

X와 Xmax의 거리가 증가함에 따른 감소 그래프는 대략 다음과 같을 것이다. 그래프는 gnupolot(:12)를 이용해서 생성했다.

attachment:dweight.png

공식에서는 x와 x_max의 거리값만을 가지고 계산을 하고 있지만, Lucene에서는 쿼리내의 모든 Term의 위치에 따른 연산을 수행한다. Lucene의 이 방식을 사용하면 검색품질을 높은 수준으로 끌어올릴 수 있지만 너무 느리다라는 결정적인 단점을 가진다.

이 모델을 적용하려면 tokenizing(:12)된 문서를 얻어내고, 모든 Term에 대해서 Term의 위치정보를 가지고 있어야 한다. 그리고 사용자 쿼리에 포함된 Term의 갯수만큼 loop를 돌면서 값을 계산해 내야 한다. 사용자 쿼리어에 포함된 Term이 많을 수록, 그리고 Term이 문서에서 여러번 등장할 수록 급격하게 연산횟수가 늘어남을 예상할 수 있을 것이다.

시간이 별로 중요하지 않은 내부검색용이라면 모르지만 상용으로 사용하고자 할경우 이 모델을 그대로 적용시키기엔 무리가 따를 것이다. 그렇다고 Density Distance N-Gram Model의 오리지날 공식을 그대로 사용하면, 좀더 빠르겠지만 결과가 만족스럽지 못할 것이다.

결국 성능과 검색품질 모두를 어느정도 만족하는 변형된 모델을 사용해야 할것이다. 이 방법은 관심이 있다면 한번 고민해 보기 바란다.