불리언 모델(boolean model)[1] 은 정보 검색 분야에서 사용되는 고전적인 모델로, 오늘날에도 많은 정보 검색 시스템에서 활용되고 있다.
정의
불리언 모델은 불 논리 및 전통적인 집합론을 기반으로 하여 검색 대상이 되는 문서들과 사용자의 질의를 모두 단어들의 집합으로 간주한다. 질의 단어들의 대상 문서내 포함 관계에 따라 문서의 검색 결과내 반영 여부가 결정된다. 이를 수학적으로 표현하면 다음과 같다.
다음과 같이 색인 단어들로 구성된 유한 집합이 있다.
- T = {t1, t2, ..., tj, ..., tm}
여기서 색인 단어란 문서의 특성이나 주제 등을 설명하는 단어 또는 문장(일반적으로 어간만 취한다고 가정)으로, 학술 논문의 주제어와 유사한 것이다.
또, 다음과 같이 문서들의 유한 집합이 있다.
- D = {D1, ..., Di, ..., Dn}, Di는 T의 멱집합의 원소
질의에 해당하는 불 논리식 Q는 다음과 같이 정의된다.
- Q = (Wi OR Wk OR ...) AND ... AND (Wj OR Ws OR ...),
- 이 때, Wi=ti, Wk=tk, Wj=tj, Ws=ts, 또는 Wi=NON ti, Wk=NON tk, Wj=NON tj, Ws=NONts
여기서 ti는 해당 단어 ti가 문서 Di에 포함되어 있다는 것을 의미하고, NON ti는 그 반대의 경우를 의미한다.
Q는 다음과 같이 정의될 수도 있다. 검색 연산은 다음과 같이 두 단계로 정의된다.
- 1. 단어 tj를 포함하는 문서 집합 Sj를 구한다.(Wj=NON tj일 경우 단어 tj를 포함하지 않는 문서 집합 Sj를 구한다)
- Sj = {Di|Wj element of Di}
- 2. 각 집합 연산에 해당하는 문서들이 질의 Q에 대한 응답으로 검색되며, 이는 다음과 같이 표현된다.
- UNION ( INTERSECTION Sj)
예제
다음과 같은 원본 문서 집합이 있다고 가정한다.
- O = {O1, O2, O3}
- O1 = Bayes' Principle: The principle that, in estimating a parameter, one should initially assume that each possible value has equal probability (a uniform prior distribution).
- O2 = Bayesian Decision Theory: A mathematical theory of decision-making which presumes utility and probability functions, and according to which the act to be chosen is the Bayes act, i.e. the one with highest Subjective Expected Utility. If one had unlimited time and calculating power with which to make every decision, this procedure would be the best way to make any decision.
- O3 = Bayesian Epistemology: A philosophical theory which holds that the epistemic status of a proposition (i.e. how well proven or well established it is) is best measured by a probability and that the proper way to revise this probability is given by Bayesian conditionalisation or similar procedures. A Bayesian epistemologist would use probability to define, and explore the relationship between, concepts such as epistemic status, support or explanatory power.
단어들의 집합 T가 다음과 같다.
- T = {t1 = Bayes' Principle, t2 = probability, t3 = decision-making, t4 = Bayesian Epistemology}
문서 집합 D가 다음과 같이 주어진다.
- D = {D1, D2, D3}
- D1 = {Bayes' Principle, probability}
- D2 = {probability, decision-making}
- D3 = {probability, Bayesian Epistemology}
질의 Q는 다음과 같다.
- Q = probability AND decision-making
검색이 이루어지는 순서는 다음과 같다.
- 1. 우선 다음과 같이 문서 Di의 집합 S1, S2가 구해진다(검색된다).
- S1 = {D1, D2, D3}
- S2 = {D2}
- 2. 이어서 질의 Q에 대한 응답으로 다음의 문서 Di가 구해진다.
- {D1, D2, D3} INTERSECTION {D2} = {D2}
- 이는 원본 문서 O2(D2에 해당)가 질의 Q에 대한 답이라는 것을 의미한다.
똑같은 표현식으로 구해지는 문서가 두 건 이상이라면 해당 문서들이 모두 검색된다. 불리언 모델에서 이러한 문서들은 구분이 불가능하다.(동일한 문서로 간주된다)
장점
단점
- 정확한 일치를 기준으로 검색할 경우 검색 결과로 얻어지는 문서가 너무 적어지거나 많아질 수 있음
- 문서들간의 중요도가 다름에도 결과 문서의 순위를 구분할 수 없음
- 질의를 불 표현식으로 변환하기 어려움
- 모든 단어의 가중치가 서로 동일함
- 정보 검색이라기보다는 데이터 검색에 가까움
자료 구조와 알고리즘
수학적 형식의 관점에서 볼 때 불리언 모델은 간단하다. 그러나 실용적인 관점에서 보면, 자료 구조 및 알고리즘과 관련한 몇 가지 문제들이 존재한다. 이러한 문제들에는 단어 선택 방법(수동/자동 선택 또는 모두), 어간 추출, 해시 테이블, 역색인 등이 있다.[2]
해시 집합
가능한 구현 방법 중 하나는 해시 집합을 이용하는 것이다. 이 경우 각각의 문서들은 모든 개별 단어를 포함하는 해시 테이블로 표현된다. 해시 테이블의 크기는 단어의 추가 및 삭제에 따라 실시간으로 증가 및 감소하기 때문에, 각 문서들이 훨씬 적은 메모리 공간을 차지하게 된다. 그러나 비트로 이루어진 벡터에 비해 더 복잡한 연산이 필요해지므로 성능은 저하된다. 최악의 경우 성능이 O(n)에서 O(n2) 수준까지 떨어질 수 있다. 평균적으로는 비트 벡터에 비해 성능이 크게 떨어지지는 않으며, 반면 메모리 공간 사용은 훨씬 더 효율적이다.
각주
- Lashkari, A.H.; Mahdavi, F.; Ghomi, V. (2009). “A Boolean Model in Information Retrieval for Search Engines”. 《ICIME '09. International Conference on Information Management and Engineering》. doi:10.1109/ICIME.2009.101.
