검색이란?

• 대량의 문서 집합에서 "특정" 키워드가 포함된 문서를 찾아내는 것

• 조건 : 모두 찾아 내어야 함, 더 적합것이 먼저 나와야 함

검색의 성능평가 요소

• Recall : 모두 나와야 하는 것 중에 검색 결과에 포함된 것의 비율(재현률)
• Precision : 검색결과에 포함된 것 중에 제대로 나온 것의 비율(정확률)

실시간 검색의 문제점(속도가 느리다)을 보완하기 위해 검색 속도 향상을 위해서 무언가의 장치(역색인)를 구축하는 것이 필요합니다.

색인

• 빠른 검색을 위하여 문서에서 검색의 될 만한 것(Lexicon)들의 존재여부와 위치(positing)를 미리 추출하여
빠른 탐색 자료구조를 구축하여 놓는 것을 말함.

Collection내의 단어의 개수가 n이라고 하고 전체 Collection 에서 나타난 단어의 개수가 m이라고 한다면,
Linear Search의 경우 O(N), Indexed Search의 경우 O(log M)이다. N >> M

100만건 Collection과 관련된 숫자
• 파일의 크기 : 3GB, 3K/doc
• 색인어 총 추출 개수 : 3억개, { (Kwd, docid, tokenid) } 6.5 GB
• 색인어-DocID UNIQ 개수 : 180M (179,759,835개) { (Kwd, docid) }
• 색인어 UNIQ 개수 : 700만개, { (Kwd) } 151 MB
• 형태소 분석 시간 : 80 min
• 3억개 소팅시간 : 60 min

역색인 구축과정

역색인

• 어떠한 키워드가 주어졌을때에, 어떠한 문서에서 나타났는지를 알려주는 자료구조

쉽게 말해서 색인이 문서들에서 키워드를 뽑아내는 과정이라면 역색인은 어떠한 키워드에대해 요청(찾아달라고)이 들어왔을때 그 뽑아낸 키워드들을 바탕으로 그 키워드가 포함된 문서를 찾아내는 것입니다.

역색인 구축의 과정

1. 원문에서 색인어를 추출한다. { (docid, tokenid, kwd) }
2. 원문에서 각 문서당 색인어수를 센다. { (docid, kwd count) }
3. 키워드 순서로 정렬한다. { (kwd, docid, tokenid) }
4. 키워드당 역색인 벡터를 만든다. ( Lexicon, Posting )
5. 역색인 벡터를 압축한다.
6. 키워드당 검색 순위를 미리 만든다.
7. Lexicon을 Hashing, Btree, TRIE등의 자료구조로 색인한다.
8. 키워드가 요청되면 열심히 찾는다.


이 작업이 평소에 선행되어야만 질의 요청시 빠른 시간내에 원하는 답을 제공할 수 있음.

(출처 : http://kulkulkul.tistory.com/ )


Inverted Index를 만들기 위해서 모든 문서들의 집합을 분석한다. 분석하는 과정에서 Stopword List에 있는 단어들은 제거한다. Stopword List는 일반적으로 매우 자주 나타나는 단어들의 집합으로 주로 조사, 전치사, 대명사 등을 포함한다. Stopword를 제거한 후, 각 문서가 포함하는 모든 단어들에 대해서 거꾸로 각각의 단어에 대해서 그들을 포함하는 문서들의 ID와 매핑시켜준다. 이런 식의 자료구조를 만들게 되면, 특정 질의어가 입력되었을때 그 질의어를 포함하는 문서들의 집합을 효율적으로 찾아낼 수 있게 된다.


inverted index를 사용하게 되면 질의에 대한 빠른 응답이 가능하다. 인덱싱이 되어있지 않은 경우에는 질의가 들어오면 직접 파일을 읽으면서 검색을 하게 되지만, 인덱싱이 되어있다면 인덱스 데이터베이스의 inverted index 구조를 사용하여 단어가 나타나는 문서를 빨리 찾아낼 수 있다. 따라서 인덱싱이 되어있다면 속도가 훨씬 빠르지만, 마지막으로 인덱싱을 한 후에 파일이 없어지거나 새로 생기거나 내용이 바뀌었다면 정확한 검색을 할 수 없게 된다. (출처 : http://goodwillstore.tistory.com/4 )

'LaKE LAB > 이론' 카테고리의 다른 글

불리안 모델과 벡터모델 (Boolean and Vector Model)  (0) 2012.03.26
Inverted Index (역색인)  (0) 2012.03.14
Posted by 기얏토