Information Retrieval Lecture Study
Boolean retrieval : query 와 boolean 연산으로 검색을 하는 것
Inverted Index
특정 단어가 어떤 문서에 있는지 찾고 싶다.
만약 아래와 같이 데이터 구조가 만들어져 있다면 각 문서에 단어가 있는 지 순회를 돌아야함.
그래서 term: {doc_id1, doc_id2, …, doc_idn} 형태로 구성된 inverted index 약간 책 뒤에 있는 단어마다 몇 페이지에 있는 지 알려주는 부록 같은 형태로 구성한다.
| 단어 (Term) | 문서 빈도 (Doc. Freq.) | 포스팅 리스트 (Postings lists) |
|---|---|---|
| ambitious | 1 | 2 |
| be | 1 | 2 |
| brutus | 2 | 1 2 |
| caesar | 2 | 1 2 |
| capitol | 1 | 1 |
| did | 1 | 1 |
| … | … | … |
만약 doc_id 마다 1/0으로 표기하면 sparse 하기 때문에 손해임.
비트로 표기하면 boolean retrieval 하기 편하지만 메모리 낭비가 심하다.
Inverted Index boolean query
기본적으로 two-pointer 형식으로 한다.
AND (Intersection)
두 posting list를 앞에서부터 동시에 순회하며 같은 doc_id만 수집한다.
INTERSECT(p1, p2):
answer ← []
while p1 ≠ nil and p2 ≠ nil do
if docID(p1) = docID(p2) then
answer.append(docID(p1))
p1 ← next(p1)
p2 ← next(p2)
else if docID(p1) < docID(p2) then
p1 ← next(p1)
else
p2 ← next(p2)
return answer