Boolean 정보 검색 요약

[1] Introduction to information Retrieval

정보검색(IR: Information Retrieval)은 거대한 정보 집합에서 요구하는 정보에 맞는 비정형적인 데이터를 찾는 것이다. 보통 찾고자하는 데이터는 문서이다. 정보검색에는 웹 검색 이외의 전자 메일 검색, 기업 지식 검색, 법률 정보 검색 등 다양한 분야가 있다.

정보검색에서의 Collection의 의미는 검색 대상이 되는 문서의 집합으로 정적인 것으로 생각하며, 정보검색의 목표는 사용자가 요구하는 정보와 관련된 정보로 문서를 검색하고 작업할 수 있도록 하는 것이다. 검색된 문서의 적합도를 판단하는데 있어서 Precision(반환된 결과 중 정보 요구에 적합한 비율)와 Recall(Collection에 포함된 적합 문헌 중 시스템에 의해 반환된 적합 문헌이 차지하는 비율)을 지표로 사용한다.

[2] Term-Document Incidence Matrices

Term-Document Matrices는 행이 용어, 열이 문서인 행렬로, 해당 용어가 문서 내에 포함되면 원소를 1로 표시하고, 용어가 포함되어있지 않다면 0으로 표시한다. 이를 통해 각 용에 대하여 [0,1]로 구성된 벡터를 구할 수 있으며, 이러한 벡터 값들은 boolean 질의에서 각 비트연산에 맞게 연산되며 문서들을 검색한다.

Boolean 검색 모델은 용어들을 Boolean 논리식 형태로 모든 질의를 작성할 수 있고, 질의식을 구성하는 용어들은 AND, OR, NOT 연산자로 결합이 된다.

큰 데이터를 기반으로 만들어진 Term-Document Matrix의 경우 항의 수가 매우 크기 때문에 컴퓨터 메모리에 적재하여 관리하기에는 어렵다. 하지만 이러한 행렬은 희소하기 때문에 0이 아닌 값을 가지는 항이 매우 적으므로, 1을 갖는 항들만 기록하는 것이 훨씬 더 좋은 방법이며, 이러한 방법이 역색인(Inverted Index)이다.

[3] The Inverted Index

사용자 검색에 따른 문서를 반환하기 위해서는, 용어를 포함하는 문서들의 집합을 저장하여 관리해야한다. 고정 크기의 배열을 사용할 경우, 문서의 수가 추가 또는 삽입됨에 따라 배열의 원소들이 이동을 해야 하므로, 가변 크기의 배열을 사용하는 것이 좋으며 이러한 배열을 Posting이라고 부른다. 디스크는 지속적으로 기록되는 것이 일반적이기 때문에 가장 좋으며, 메모리의 경우는 링크리스트 또는 가변길이 배열을 사용할 수 있으므로 문서들의 정보를 기록하기에 적합하다.

역색인을 생성하기 위해서는 우선 모든 문서는 고유의 번호로 색인이 되어있어야 한다. 이후 문헌을 토큰 처리하여 각 문헌을 토큰 목록으로 만든다. 자연어 전처리 과정을 수행한 다음, 색인어가 될 정규화 토큰 목록을 (정규화 토큰, 문서 색인번호)의 형태로 생성한다. 이후 정규화토큰과 문서 번호로 정렬을 하며, 이로 인해 이후 용어에 따른 역색인 리스트는 색인이 추가되어도 정렬을 유지한다. 교집합 연산은 두 용어를 포함하는 문서를 빨리 찾을 수 있는 연산으로, Posting 목록에 대한 교집합 연산은 병합 알고리즘을 통해 효과적으로 수행 할 수 있으며(반드시 Posting목록이 정렬되어있어야 함), 각 목록의 길이가 x, y라고 할 때 O(x+y)의 수행시간을 가진다.

[4] Phrase Queries and Positional indexes

biword indexes는 텍스트내의 용어의 쌍을 색인화 하는 것으로, 2개의 용어를 가진 질의어를 즉시 처리할 수 있다. 긴 구문의 경우 해당 구문을 분리하여 boolean 연산을 통해 검색이 가능하다. 하지만 biword index의 경우 문서가 없다면, 해당 질의어가 구문을 포함하고 있는지 여부를 알 수 없기 때문에 오탐지의 문제점을 갖고 있다. 따라서 표준 색인 방법으로는 한계점을 갖고 있어 복합적으로 사용되어야 한다. 이를 해결하기 위해 Positional indexes를 사용하는데 이는 각 토큰에 저장되어있는 용어들의 위치를 이용한 것으로, 각 용어들에 대해 역 색인 항목을 추출하고, 문서 위치정보를 바탕으로 모두 열거한 다음 병합 알고리즘을 통해 각 용어들이 포함된 문서 정보를 검색할 수 있다.