The term vocabulary and postings lists

inverted index 생성 방법

1. 문서 수집
2. 텍스트 토큰화
3. 토큰에 대한 언어 분석
4. 위에서 분석된 토큰에 대한 인덱스

위에서 텍스트 토큰을 했을 경우, 해당 텍스트를 분석해야 한다. 그런데, 간단해 보이는 여기에서 큰 문제가 발생한다.

예를 들어서, 위의 과정 2,3은 화이트 스페이스 단어로 토큰을 나눈다거나 쉽게 생각할 수 있다.

하지만, 우리 앞을 가로막는 것은 토큰의 인식 방법이나, 문서 인코딩이 문제가 될 수 있다.

예를 들어서, 같은 “문서” 라는 단어지만, euc-kr, UCS2, utf-8 모두 값이 다르다. –_- 즉, 중간에 이런것에 대해서 맞춰주는 뭔가가 필요하다는 거다. 예를 들어, 1차적으로 모두 유니코드로 변경한다든지…

그리고 입력 단어가, 좌->우 가 아니라, 우->좌 가 된다든지, 등의 문제가 생긴다.

위에는 책에서 예를 들었던 부분…

이런 부분에서만 아니라, 또한 이런 부분도 나온다. PDF, HWP, Office 계열의 경우에는 인코딩 되어 있으므로 바로 분석이 되지 않는 경우도 있을 수 있다.

2장의 주 내용은 거의 제목처럼 Term( 일종의 토큰 ) 을 어떻게 나누고 처리할 것인가? 이다.

여기서 처리도, 타입을 나누는 방법 이런것이 아니라, 단어를 저장할 때, type 정보를 같이 저장한다든지

(즉, 단어, 동사, 명사, 형용사 등의 형태소 정보?)

그리고 O’Neill 같은 단어가 있을 때,

neill

oneill

o’neill

o’ neill

o neill 등 어떤식으로 색인을 잡을 것인가도 고민해야 할 문제이다.

그리고 불용어 들은 어떻게 처리할 것인지?

a an and are as at be by for from

has he in is it its of on that the

to was were will with 등은 색인의 가치가 없는 단어인 것이다. (나오기는 엄청 나온다.)

또한 단어의 단,복수 아니면, 대소문자 구분 등 에 대해서도 색인을 어떻게 할 것인가 고민해야 한다

예를 들어, Windows 라고 쿼리가 올 경우, Windows, windows window 를 모두 매치시킬것인가

말것인가 등의 문제이다. C.A.T. 를 CAT 로 볼것인가? cat 로 볼것인가 등등도 문제가 될 수 있다.

2장에서는 이런 문제거리 들에 대해서 기본적으로 던져준다.

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이 붙었을 경우에는 어떻게 검색하는 것이 좋을까? 이장에서는 이런 의문을 들게

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