The (standard) Boolean model of information retrieval (BIR) is a classical information retrieval (IR) model and, at the same time, the first and most-adopted one. It is used by many IR systems to this day. The BIR is based on Boolean logic and classical set theory in that both the documents to be searched and the user's query are conceived as sets of terms (a bag-of-words model). Retrieval is based on whether or not the documents contain the query terms.

Definitions

An index term is a word or expression, which may be stemmed, describing or characterizing a document,  such as a keyword given for a journal article. Letbe the set of all such index terms.

A document is any subset of . Letbe the set of all documents.

A query is a Boolean expression  in normal form:where  is true for  when . (Equivalently,  could be expressed in  disjunctive normal form.)

We seek to find the set of documents that satisfy .  This operation is called retrieval and consists of the following two steps:

 1. For each  in , find the set  of documents that satisfy :2. Then the set of documents that satisfy Q is given by:

Example

Let the set of original (real) documents be, for example

 

where

 = "Bayes' principle: The principle that, in estimating a parameter, one should initially assume that each possible value has equal probability (a uniform prior  distribution)."

 = "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."

 = "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."

Let the set  of terms be:

Then, the set  of documents is as follows:

 

where 

Let the query  be:

Then to retrieve the relevant documents:
 Firstly, the following sets  and  of documents   are obtained (retrieved):
 Finally, the following documents  are retrieved in response to  
This means that the original document  (corresponding to ) is the answer to .

Obviously, if there is more than one document with the same representation, every such document is retrieved. Such documents are indistinguishable in the BIR (in other words, equivalent).

Advantages 

 Clean formalism
 Easy to implement
 Intuitive concept
 If the resulting document set is either too small or too big, it is directly clear which operators will produce respectively a bigger or smaller set.
It gives (expert) users a sense of control over the system. It is immediately clear why a document has been retrieved given a query.

Disadvantages 

 Exact matching may retrieve too few or too many documents
 Hard to translate a query into a Boolean expression
 All terms are equally weighted
 More like data retrieval than information retrieval
 Retrieval based on binary decision criteria with no notion of partial matching
 No ranking of the documents is provided (absence of a grading scale)
 Information need has to be translated into a Boolean expression, which most users find awkward
 The Boolean queries formulated by the users are most often too simplistic
 The model frequently returns either too few or too many documents in response to a user query

Data structures and algorithms 

From a pure formal mathematical point of view, the BIR is straightforward. From a practical point of view, however, several further problems should be solved that relate to algorithms and data structures, such as, for example, the choice of terms (manual or automatic selection or both), stemming, hash tables, inverted file structure, and so on.

Hash sets 

Another possibility is to use hash sets. Each document is represented by a hash table which contains every single term of that document. Since hash table size increases and decreases in real time with the addition and removal of terms, each document will occupy much less space in memory. However, it will have a slowdown in performance because the operations are more complex than with bit vectors. On the worst-case performance can degrade from O(n) to O(n2). On the average case, the performance slowdown will not be that much worse than bit vectors and the space usage is much more efficient.

Signature file 
Each document can be summarized by Bloom filter representing the set of words in that document, stored in a fixed-length bitstring, called a signature.
The signature file contains one such superimposed code bitstring for every document in the collection.
Each query can also be summarized by a Bloom filter representing the set of words in the query, stored in a bitstring of the same fixed length.
The query bitstring is tested against each signature.

The signature file approached is used in BitFunnel.

Inverted file 

An inverted index file contains two parts:
a vocabulary containing all the terms used in the collection,
and for each distinct term an inverted index that lists every document that mentions that term.

References 

 

Mathematical modeling
Information retrieval techniques
불리언 모델(boolean model) 은 정보 검색 분야에서 사용되는 고전적인 모델로, 오늘날에도 많은 정보 검색 시스템에서 활용되고 있다.

정의
불리언 모델은 불 논리 및 전통적인 집합론을 기반으로 하여 검색 대상이 되는 문서들과 사용자의 질의를 모두 단어들의 집합으로 간주한다. 질의 단어들의 대상 문서내 포함 관계에 따라 문서의 검색 결과내 반영 여부가 결정된다. 이를 수학적으로 표현하면 다음과 같다.

다음과 같이 색인 단어들로 구성된 유한 집합이 있다.

 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에 대한 답이라는 것을 의미한다.

똑같은 표현식으로 구해지는 문서가 두 건 이상이라면 해당 문서들이 모두 검색된다. 불리언 모델에서 이러한 문서들은 구분이 불가능하다.(동일한 문서로 간주된다)

장점 
 간결한 형식
 구현이 용이
 직관적 개념

단점 
 정확한 일치를 기준으로 검색할 경우 검색 결과로 얻어지는 문서가 너무 적어지거나 많아질 수 있음
 문서들간의 중요도가 다름에도 결과 문서의 순위를 구분할 수 없음
 질의를 불 표현식으로 변환하기 어려움
 모든 단어의 가중치가 서로 동일함
 정보 검색이라기보다는 데이터 검색에 가까움

자료 구조와 알고리즘 
수학적 형식의 관점에서 볼 때 불리언 모델은 간단하다. 그러나 실용적인 관점에서 보면, 자료 구조 및 알고리즘과 관련한 몇 가지 문제들이 존재한다. 이러한 문제들에는 단어 선택 방법(수동/자동 선택 또는 모두), 어간 추출, 해시 테이블, 역색인 등이 있다.

해시 집합 
가능한 구현 방법 중 하나는 해시 집합을 이용하는 것이다. 이 경우 각각의 문서들은 모든 개별 단어를 포함하는 해시 테이블로 표현된다. 해시 테이블의 크기는 단어의 추가 및 삭제에 따라 실시간으로 증가 및 감소하기 때문에, 각 문서들이 훨씬 적은 메모리 공간을 차지하게 된다. 그러나 비트로 이루어진 벡터에 비해 더 복잡한 연산이 필요해지므로 성능은 저하된다. 최악의 경우 성능이 O(n)에서 O(n2) 수준까지 떨어질 수 있다. 평균적으로는 비트 벡터에 비해 성능이 크게 떨어지지는 않으며, 반면 메모리 공간 사용은 훨씬 더 효율적이다.

각주 

 

정보 검색 기술
수학적 모델링