Boolean Retrieval

 Introduction to Information Retrieval 의 1장은 boolean retrieval 이다.

 

실제로 현재 1~2장을 재미삼아 번역하신 분(http://danamoni.tistory.com/) 도 계시고 여기는 그냥 내가

공부하고 이해한 정도만 내용을 올려볼려고 한다. 기록하지 않으면 까먹는 법이니……

 

사실 이게 지금 4번째 1장 내용을 올리는 중이다. 젠장 계속 날라간다. ㅎㅎㅎ

 

Boolean Retrieval의 핵심은 말 그대로 Boolean 연산을 통해서 해당 문서를 찾아내는 것이다. 그럼

무엇을 이용해서 불린 연산을 하게되는 것인가? 바로 단어다. “정보”, “검색” 등의 키워드로 우리가

일반적으로 사용하는 검색은 보통 그 기초는 불린 검색이라고 보면 된다.

 

 불린 연산에는 AND, OR, NOT 등을 이용하는 검색을 생각하면 된다.

 

1장의 내용은 위의 불린 연산에 적합한 자료구조와 그것을 이용해서 어떻게 효율적으로 문서를 검색할

것인지를 설명하고 있다.

 

 그럼 단어들의 AND, OR, NOT 연산을 통해서 찾을려면 어떤 자료구조가 가장 빠를까?

해당 단어들이 서로 같은 페이지에 있는지 매트릭스로 표현하면 바로 찾아지지 않을까? 각각의 키워드가

x,y 축 인덱스로 어떻게 변형할 수 있을까는 넘어가도록 하자.(필자는 이런거 잘 모른다.)

 

사용자 삽입 이미지

 

 위의 형태로 이렇게 매트릭스로 만들어 놓으면 바로 해당 단어와 다른 단어가 연결되어 있는지 쉽게 찾을 수 있다. 그런데 -_- 사실 위와 같은 형태는 바로 단점이 들어난다. 각각의 단어들의 관계를 위와 같은

형태로 나타내면, 엄청난 공간이 필요하다. 즉 무한대의 공간이 없는 이상 힘들다라는 -_-,

 

 그럼 여기서 누군가 그럼 Sparse Matrix 를 쓰면 되잖아요 라고 물어보신다면 -_-

답변은 빙고이다. 그래서 위와 같은 형태를 Sparse matrix 형태로 표현하는 것이 위의 개선 방법이다.

뭐, 그리고 그걸 조금 더 발전 시켜서, Inverted Index 라는 것이 나오게 된다. 즉 페이지에 들어있는 단어

형태로 표현하는 것이 아니라, 검색시 편하게 단어가, 어느 페이지에 나오는지를 따로 기록하는 것이다.

 

사용자 삽입 이미지 

대충 표현하면 위와 같다.

 

 기본적으로 불린 검색이든 뭐든, 해당 검색어가 어디에 위치하는 가를 보여주기 위해서는 보통 위의 방식을 쓴다.

 

 그리고 위와 같은 형태로 자료를 저장하는 방법으로 다음과 같은 진행 과정을 거친다.

 

사용자 삽입 이미지

 

위와 같이 문서 1을 단어별로 분리하고 해당 단어들에 대해서 문서 2와 같은 형태로 Inverted Index를 만들어

주는 것이다.

 

 이때, 단어는 Stemming 이라는 것을 하게 되는데, 영어 단어나 한국어의 경우, 어간 어미를 분리해서 어간만 저장하면, “먹었다”. “먹다” 같은 경우에 먹다로 통합 검색이 가능해지는 것이다.

 

 그런데 위와 같은 형태로 저장하면 끝일까? 당연히 아니다. 1장의 목표는 불린 검색에 적합한 자료구조와 검색 방법을 정하는 것이라고 앞에 설명했다. 그렇다면, 적합한 자료구조는 위와 같이 정했다고 보고 적합한 알고리즘은 과연 무엇일까?

 

 책에서는 Merge 라고 하고 있다. 예를 들어,

“정보” – 1,2,3,4,5,6,7,8,10,20,30

“검색” – 2, 10, 30, 40, 50 이렇게 문서에 나타날때

정보 & 검색은 어떻게 찾는 것이 좋을까?

작은 쪽을 큰 쪽에 계속 대입해 보는 방법이 있을 수 있고, 뒤의 데이터는 정렬되어 있을 경우 Binary Search

로 금방 찾을 수 있긴 하다. 그러나 사실 이것보다는 각각이 모두 정렬 되어 있으므로

 

Merge Sort 형태로 비교해서 검사를 하면 가장 짧은 시간에 끝낼 수 있지 않을까? 아이템이 n개라면

최대 n 번 정도로 검색이 가능하던가?(BigO는 항상 어렵다.)

 

조건이 몇개 더 늘어날수록 더 빨라질 수도 있을 것 같다. 그런데 개인적으로 드는 의문은 더 빠를 방법은

없을까?, 조건에 NOT이 붙었을 경우에는 어떻게 검색하는 것이 좋을까? 이장에서는 이런 의문을 들게

해준다. -_- 해결은 스스로!!!