/ coursework

IIR : 불리언 검색 (Boolean Retrieval)

정보 검색(Information Retrieval)

정보 검색는 수집·축적한 다량의 정보를 정리하고 구조화 되지 않은 임의의 대용량 정보에서 이용자의 정보요구에 적합한 정보를 탐색하여 찾아주는 것을 말한다. 단순 검색(ad hoc retrieval) 작업을 다루는 시스템 개발이 목적이다.

grep

셰익스피어 희곡 전집 중 'Brutus AND Caesar AND NOT Calpurnia'에 해당하는 희곡 문서를 찾는다고 해보자. 첫 장부터 모든 문장을 차례로 읽어가며 조건문 쿼리에 만족하는 문장을 찾는 방법이 바로 생각날 것이다. 순차적으로 하나씩 훑어나가는 과정(linear)을 "grepping through text"라고 말하는데, 리눅스 명령어인 grep 이후에 등장한 표현이다. (grep은 파일에서 특정한 패턴(문자열)을 찾는 명령어로 정규표현식으로 문자열을 검색하고 추출할 때 사용한다)

그러나 grep은 대용량 데이터의 경우 수행 속도가 매우 느리며, 'find the word Romans near countryman'(countryman 와 가까이에 있는 Romans를 찾아라)'와 같은 오퍼레이션을 수행할 수 없다.

Boolean Retrieval

불리안 검색 모델에서 검색문(query 또는 need representation)은 단어의 불리안 로직(AND, OR, NOT)으로 표현되고, 문서 또는 색인(index 또는 text/document representation)은 단어들의 집합으로 간주된다. 문서(document)는 검색 시스템을 형성하는 구성 요소(unit)이다. 그룹핑된 문서 집합은 콜렉션(collection), 코퍼스(corpus, 말뭉치, 텍스트의 본문을 말함)라고도 한다.

한 단어집은 색인어의 집합으로 표현되어 단어/색인어가 해당 문서 출현하면 "1" 값을 가지며, 출현하지 않으면 "0" 값을 가지게 된다. 이를 incidence matrix term(단어 근접 행렬) 또는 document-term matrix라고 한다.

아래 4개의 문서가 있다고 해보자.

[Figure 1]
Doc 1 Breakthrough drug for schizophrenia
Doc 2 new schizophrenia drug
Doc 3 new approach for treatment of schizophrenia
Doc 4 new hopes for schizophrenia patients

각 문서 내 문장을 토큰화 시킨 후 색인화 작업을 거쳐 만든 term-document incidence matrix 아래와 같다.

[Figure 2] Term-document incidence matrix / incidence vectors(발생 빈도 벡터)

term doc1 doc2 doc3 doc4
approach 0 0 1 0
breakthrough 1 0 0 0
drug 1 1 0 0
for 1 0 1 1
hopes 0 0 0 1
new 0 1 1 1
of 0 0 1 0
patients 0 0 0 1
schizophrenia 1 1 1 1

term-document incidence matrix은 벡터 열로 변환할 수 있고 부울 연산자로 계산 가능하다.

몇가지 쿼리 연산을 해보자. 검색 질의가 schizophrenia AND drug(schizophrenia와 drug를 포함하는 문서를 찾아라)라면 schizophrenia = [1, 1, 1, 1], drug = [1, 1, 0, 0]이 된다. AND 연산을 하면 [1 1 0 0] 이므로 doc1, doc2를 반환한다.

이번에는 for AND NOT(drug OR approach) 연산을 해보자.

term doc1 doc2 doc3 doc4
drug 1 1 0 0
approach 0 0 1 0
(drug OR approach) 1 1 1 0
NOT (drug OR approach) 0 0 0 1

먼저 drug OR approach를 계산하면 [1, 1, 1, 0]이 나오고, 이를 NOT연산을 하면 [0, 0, 0, 1]이 된다.

term doc1 doc2 doc3 doc4
for 1 0 0 1
NOT(drug OR approach) 0 0 0 1
For AND NOT(drug OR approach) 0 0 0 1

for과 AND 연산을 하면, [0, 0, 0, 1] 이 되므로 doc4 문서를 반환한다.

불리언 정보검색모델은 메모리 용량에 심각한 문제를 야기한다. 예를 들어 총 문서가 백 만개이고 색인어가 백 개라면 단어 당 평균 6byte임을 감안했을 때 총 용량은 무려 6GB가 넘는다.

또한 벡터로 표현하면 의미없는 데이터 ‘0’이 많아져 희소 행렬이 생긴다. 매트릭스에는 1보다 0이 훨씬 더 많게 되어 필요없는 데이터 '0'은 버리고, '1'에 대해서만 표시하는 것이 역 색인(Inverted index)이다.

불리안 모델에 가중치를 단어에 부여하지 않는다. 단어가 가지는 값은 "1"이거나 "0"으로 그 집합의 멤버인가 아닌가만 존재하는 것이다.

inverted index

[Figure 3]

term DF(document frequency)
approach 1
...
for 3 1 3 4

정보 검색에서 역 색인(inverted index, 또는 역 파일(inverted file))은 단어가 포함된 문서만 인덱싱하는 방법이다. 낱말이나 숫자와 같은 내용물로부터의 매핑 정보를 데이터베이스 파일의 특정 지점이나 문서 또는 문서 집합 안에 저장하는 색인 데이터 구조로 용어 사전(dictionary of terms)라고 말한다.

색인 파일은 포스팅(posting)이라고 하는데 각 용어마다 해당 단어가 등장하는 문서가 저장되어 출현 문서 위치를 매핑해주기 때문이다. 색인 시 색인어와 포스팅은 자모순으로 배열된다. 포스팅 값은 고유한 문서 ID 번호이다.

역 색인은 아래와 같은 정렬 및 그룹화 단계를 거친다.

  1. 색인 대상 문서를 수집한다.
  2. 문서를 토큰 처리(단어로 분절)하여 각 문서를 토큰 목록으로 변환한다.
  3. 자연어 전처리를 수행한 다음, 색인어가 될 정규화 토큰의 목록을 생성한다.
  4. 역색인을 생성하고, 단어집과 포스팅으로 구성되는 역색인을 생성하여 각 단어가 출현하는 문서를 색인한다.

토큰(token)과 정규화 토큰(normalizaed token)은 단어와 거의 유사한 것으로 간주한다. 컬렉션 내에서 각 문서는 식별자(docID 번호)를 갖고 있으며 목록은 단어(key)-문서(value) 쌍으로 구성한다.

이 데이터 테이블은 DF(문서 빈도, document frequency)를 결정할 때 사용된다.

[Figure 3]의 역 색인 테이블이다.

[Figure 4]
'approach': ['doc3'],
'breakthrough': ['doc1'],
'drug': ['doc1', 'doc2'],
'for': ['doc1', 'doc3', 'doc4'],
'hopes': ['doc4'],
'new': ['doc2', 'doc3', 'doc4'],
'of': ['doc3'],
'patients': ['doc4'],
'schizophrenia': ['doc1', 'doc2', 'doc3', 'doc4'],
'treatment': ['doc3'],

이제 검색 질의에 불리언 연산자를 넣어 검색할 수 있다.

approach AND schizophrenia은 아래와 같은 단계로 수행한다. AND 연산자이므로
approach의 포스팅과 schizophrenia의 포스팅의 교집합을 찾으면 된다.

  1. 사전에서 approach의 위치를 확인한다.
  2. approach와 관련된 포스팅을 검색한다.
  3. 사전에서 schizophrenia 위치를 확인한다.
  4. schizophrenia에 해당하는 포스팅을 검색한다.
  5. 두 포스팅 목록의 교집합을 구한다.

'approach': ['doc3'] 'schizophrenia': ['doc1', 'doc2', 'doc3', 'doc4'] 의 교집합은 doc3 다.

boolean query

교집합(intersection) 연산은 두 단어를 모두 포함하는 문서를 빨리 찾는 것이 목적이다. 병합 알고리즘(intersect algorithm)을 이용해 포스팅 리스트의 교집합을 구하는 방법은 단순하지만 효과적이다.

intersect algorithm

  • p1 AND p2
INTERSECT_AND(p1, p2)
 answer = []
 while p1 ̸= nil and p2 ̸= nil
 do if docID(p1) = docID(p2)
     then Add(answer, docID(p1))
         p1 ← next(p1)
         p2 ← next(p2)
     else if docID(p1) < docID(p2)
         then p1 ← next(p1)
     else 
         then p2 ← next(p2)
 return answer

p1, p2 두 리스트가 비어 있지 않을 때, p1과 p2의 docID가 서로 같으면 결괏값에 저장하고 엘레먼트로 포인터를 옮긴다. 그렇지 않으면 두 값 중 작은 쪽으로 인덱스로 포인터를 옮긴다. 그 다음 엘리먼트가 없을 때 까지 이를 반복한다.

  • p1 OR p2
INTERSECT_OR(p1, p2)
answer = []
while p1 != NIL or p2 != NIL
  if p1 = NIL
     then ADD(answer,docID(p2))
       p2 ← next(p2)
  else if p2 = NIL
    then ADD(answer,docID(p1))
       p1 ← next(p1)
  else if docID(p1) < docID(p2)
    then ADD(answer, docID(p1))
      p1 ← next(p1)
  else if docID(p1) >docID(p2)
    then ADD(answer, docID(p2))
      p2 ← next(p2)
  else if docID(p1) = docID(p2)
    then ADD(answer, docID(p1))
      p1 ← next(p1)
      p2 ← next(p2)
return answer

p1 리스트가 비어있으면(p1 = NIL), p2가 가리키는 docID를 추가하고 그 다음 인덱스로 포인터를 옮기고 결괏값(answer)에 저장한다. 반대로 p2 리스트 전체가 비어있으면(p2 = NIL) p1의 docID를 결과값에 저장하고, 그 다음인 안덱스로 포인터를 옮긴다. p1의 docID가 p2보다 작을 경우(docID(p1) < docID(p2)), p1 값을 결괏값에 저장하고, p1의 포인터를 이동한다. 반대로 p1의 docID가 p2보다 크면(docID(p1) > docID(p2)), p2 값을 결과값에 저장하고, p2 포인터를 이동한다. 마지막으로 docID가 서로 일치하면p1의 docID를 결괏값에 저장하고, 두 리스트 모두 포인터를 이동시킨다.

  • 시간 복잡도
    • p1 AND NOT p2 검색어 질의는 각 포스팅 길이가 x, y일 때 O(x+y)이다. 첫 번째 p1 포스팅 목록을, 두 번째 p2 포스팅 목록에 해당하지 않는 문서를 수집하기 때문이다.

    • p1 OR NOT p2 검색어 질의는 전체 포스팅 목록의 길이가 아니라 총 문서 수(N)가 되므로 O(N)이 된다.