Boolean Search, Queries, Index and Inverted Index

 

Boolean Search

 

Boolean Search (불리언 검색)은 검색어가 찾고자 하는 문서에 있다면 1, 없으면 0으로 판단하는 단순한 알고리즘이다.

스탠포드의 CS276 수업에서의 자료인 Figure 1을 예로 들면 다음과 같다.

 

Figure 1. Boolean Search Example

 

 

우선 찾고자 하는 문서(Document)는 연극이며 Term은 여기서는 사람이름이다.

그리고 우리가 찾고자 하는 정보인 query (쿼리, 질의)는 Brutus AND Caesar BUT NOT Calpurnia다.

즉, 연극 중에서 Brutus와 Caesar가 등장하지만 Calpurnia가 등장하지 않는 것을 찾고자 하는게 목적이다.

 

Figure 1에 나온 term-document incidence matrix는 가로 row는 term (용어)이며 세로 column은 개별 연극 작품이다.

이때 matrix의 cell이 1이면 해당 극작품이 해당 용어를 포함하고 있다는 뜻이고 0은 포함하지 않는단 뜻이다.

 

Figure 1. Boolean Search Example Answers

 

따라서, Brutus와 Caesar가 모두 포함된 작품인 Antony and Cleopatra, Julius Caesar, Hamlet 중에서 Calpurnia가 포함되지 않은 문서(연극)인 Antony and Cleopatra과 Hamlet이 쿼리에 대한 정답으로 주어져야 한다.

 

Index (색인)

 

색인은 Doc 1: Text 1, Doc2: Text 2,... 처럼 문서 자체에 순서와 이름을 할당하고 그 내용을 순차적으로 본다고 이해했다.

따라서 색인을 이용한 검색은 Doc 1의 내용인 Text 1에 대해서 쿼리에 대해 검색하고 그 결과를 도출하고,

Doc 1에 대해서 완료 된 다음 Doc 2의 Text 2에 대해서 수행하는 등의 검색을 수행하게 된다.

문서들의 내용이 짧다면 모를까 길다면 굉장히 비효율적인 검색방법이 된다.

따라서, 문서를 기준으로 색인을 하지 않고 키워드, term을 기준으로 색인을 수행한 역색인을 검색에 사용하게 된다.

 

 

Inverted Index (역색인)

역색인은 Doc 1: Text 1,... 과는 다르게 Term 1: Doc 1, Doc 3, Doc 5, Term 2: Doc 2, Doc 5, Term 3: Doc 1, Doc 6, ...

이런식으로 term을 기준으로 수행한 색인이다. 

 

검색을 수행할 때 주어진 쿼리를 term 단위로 분리하여 비교하기 때문에 굉장히 빠르게 검색할 수 있다.

 

역색인의 과정은 아래의 Figure 3과 같다.

 

Figure 3. Inverted Index Construction

 

 

1. 우선 역색인을 수행할 문서들을 준비한다.
2. Tokenizer로 문서의 텍스트들을 tokens (위에서 언급한 terms)로 분해한다
3. Linguistic modules로 tokens를 수정한다 (stemming, lemmatization, lower case로 변환 등등)
4. Indexer로 역색인을 수행한다

Figure 4. Initial Stage of Text Processing

 

Figure 4에서는 text processing에 대해서 설명하는데 이는 딥러닝 분야의 NLP preprocessing과 유사하다.

 

1. 주어진 텍스트를 의미의 단위인 token 단위로 쪼갠다.
2. 그 다음 U.S.A.를 USA로 변환하거나 대문자를 소문자로 모두 변환하는 등의 normalization을 수행한다.
3. stemming (어간추출)이나 lemmatization (표제어추출) 등으로 단어의 형태를 통일시킨다. 먹다라는 단어를 예로 들면 "먹다, 먹-", 등의 내용을 모두 통일하게 일관적인 결과를 도출할 수 있다.
4. Stop words를 제거한다. 영어의 the, a, to, of 등의 빈번하게 등장하지만 의미 없는 단어들을 제거한다.

 

 

Figure 5. Tokenizing Sequences (documents)

 

Figure 5에서는 문서들을 token 단위로 쪼갠 다음 term과 해당 term이 나온 문서를 table 형태로 만들었다.

 

 

Figure 6. Sort by Terms

 

 

Figure 5에서 만든 테이블을 term을 기준으로 하여 오름차순으로 정렬한다. 즉 사전과 같은 형태로 정렬한다.

 

Figure 7. Dictionary and Postings

 

Figure 7에서는 Figure 6에서 정렬한 table을 딕셔너리 형태로 변경한 다음 posting list와 연결한다.

딕셔너리의 key는 term이고 value는 term frequency다. Term frequency 전체 문서 집단인 corpus에서 등장한 해당 term의 회수다. 다양한 형태로 구현이 가능하겠지만 여기서는 해당 딕셔너리에서 postings lists를 포인터를 활용해서 접근한다.

 

보다 색인과 역색인에 대해서는 아직 이해가 부족하므로, 자세한 내용은 레퍼런스에 있는 3개의 블로그를 참조하면 좋을듯하다.

 

 

Types of Queries

이번에는 여러 쿼리 종류를 살펴본다.

 

Exact Query

 

정확한 쿼리는 위의 Figure 1에서와 같은 쿼리다. 즉 정확하게 일치하는 결과만 반환한다.

이는 정확성을 담보하지만 오타를 낸다거나, 유의어가 쓰인 상황에서는 원활하게 작동하지 못한다.

 

 

Phrase Query

 

구를 활용한 쿼리로, stanford university라는 질의를 넣었을 때 Boolean search의 경우 I went to university at Stanford와 stanford university. 라는 문장은 매칭하지 못하게 된다. 

 

Wildcard Query

 

와일드 카드 질의는 쿼리에 있어서의 정확성을 어느정도 완화한 쿼리다.

 

MS Access에서 나온 예시를 통해 살펴보자.

 

wh*과 같은 와일드 카드 질의의 경우 what, white, why 등을 찾고 awhile, watch 등은 찾지 않습니다

 

즉 wh로 시작하는 단어들을 찾게 된다.

 

 

 

References:

최신정보검색론 (Manning 외 2인)

[업스테이지] AI 실전 학습 - Information Retrieval

Stanford CS276: Information Retrieval and Web Search

https://blog.naver.com/mbhaen94/222580240872

https://steady-coding.tistory.com/581

https://blog.naver.com/youngfem/223386846500

https://wikidocs.net/21707

https://support.microsoft.com/ko-kr/topic/%EC%99%80%EC%9D%BC%EB%93%9C%EC%B9%B4%EB%93%9C-%EB%AC%B8%EC%9E%90%EC%9D%98-%EC%98%88-939e153f-bd30-47e4-a763-61897c87b3f4