1. Boolean Retrieval

 

 

정보검색(Information Retrieval, IR)은 거대한 collection들에서 정보 필요를 만족시키는 비구조화된 특성의 물질을 찾는 것이다.

 

원문

Information Retrieval is finding material(usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers)

 

Boolean Retrieval

• 불린(Boolean) 모델은 정보검색 시스템의 가장 간단한 모델이다.
• 쿼리와 불린 표현들
• 검색엔진은 이 불린식을 만족하는 모든 문서를 반환한다.

구글은 불린 모델을 쓸까?

• 쿼리를 w1 AND w2 AND... AND wn 방식으로 사용
• wi에는 이러한 것들을 포함하지 않는다.
  • anchor text(to, on, with, at, 은/는, 이/가, 을/를)
  • 페이지는 엄청난 wi들을 가지고 있음
  • 쿼리가 길다.
  • 불린식은 매우 적은 hits를 생성한다.
• 간단한 불린 vs. 결과 집합 랭킹
  • 특수한 명령 아니면 불린 검색은 매칭된 문서만 반환
  • 구글(그리고 좋게 설계된 불린 엔진들)은 결과 집합을 랭크시킴. good hits가 많음.

 

Term-Document Incidence Matrix

 

 

위와 같은 형태를 Term-Document incidence matrix라고 한다.

첫번째 열에 term들이 나열되고,(이들을 dictionary, 사전이라고 한다.)

첫번째 행에는 document들이 id로 나열된다.

한 행은 incidence vector(사건 벡터)라고 칭하며, 1인 값은 그 document에 해당 term이 존재함을 의미한다.

 

이것을 이용하여 term1, term3을 검색하면 두 term의 incidence vector를 AND 연산하여 그 결과를 보면 된다.

Not 연산은 vector의 값들을 뒤집으면 된다.

 

Bigger Collection 에서는?

• 보통 N=10^6 개의 document가 있고, 각기 1,000개의 토큰을 가지고 있음=>총 10^9개의 토큰.(Billion 단위)
• 토큰당 평균 6바이트=>document collection의 크기가 6*10^9=6GB
• term의 갯수가 약 M=500,000개(50만개).(한글도 비슷)
• 이게 메모리 적재는 당연히 안되고.
• 공간 낭비가 심하다.(전체 행렬에서 1의 갯수가 billion이상으로 나오지 않기 때문.)
• 이를 위해 Linked List 형태로.

 

Inverted Index

 

• Dictionary는 동일.
• 오른쪽의 숫자는 해당 term이 존재하는 docID를 오름차순으로 정렬해둔 것으로 postings라고 부름.

 

만드는 방법(!시험 출제가능성 80~90%)

• collection들을 index로 만든다.
• text를 토큰화하여 document를 토큰의 리스트로 만든다.
• 언어적 전처리를 한다. 토큰들을 일반형으로 바꾼다.
• 그리고 그 토큰들을 이용하여 postings를 만들고.
• postings를 정렬한다.
• postings를 list로 만든다.

검색하는 방법

• 해당 term을 dictionary에서 찾고, 그 posting을 찾는다.
• 두 리스트를 Intersect한다.
• Intersect는(AND)
  • 한쪽 리스트가 끝날 때까지 반복
  • 양쪽이 다르면, 번호가 작은 쪽을 다음 posting으로
  • 양쪽이 같으면, 하나를 넣고 양쪽을 모두 다음 posting으로.

 

쿼리 최적화

• 리스트가 짧은 순서로 intersection 진행.