Click here to Skip to main content
Click here to Skip to main content
Go to top

Boolean Retrieval Model

, 31 Jul 2012
Rate this:
Please Sign up or sign in to vote.
Information retrieval using boolean retrieval model

Introduction

Model is an idealization or abstraction of an actual process. Information Retrieval models can describe the computational process.

For example 

  1. how documents are ranked
  2. Note that how documents or indexes are stored is implemented.

The goal of information retrieval (IR) is to provide users with those documents that will satisfy their information need. Retrieval models can attempt to describe the human Process, such as the information need, interaction.

Retrieval model can be categorize as

  1. Boolean retrieval model
  2. Vector space model
  3. Probabilistic model 
  4. Model based on belief net

The Boolean model of information retrieval is a classical information retrieval (IR) model and is the first and most adopted one. It is used by virtually all commercial IR systems today.

Exact vs Best match

In exact match a query specifies precise criteria. Each document either matches or fails to match the query. The results retrieved in exact match is a set of document (without ranking).

In best match a query describes good or best matching documents. In this case the result is a ranked list of document. The Boolean model here I’m going to deal with is the most common exact match model.

Basic Assumption of Boolean Model
  1. An index term is either present(1) or absent(0) in the document
  2. All index terms provide equal evidence with respect to information needs.
  3. Queries are Boolean combinations of index terms.
    • X AND Y: represents doc that contains both X and Y
    • X OR Y: represents doc that contains either X or Y
    • NOT X: represents the doc that do not contain X
Boolean Queries Example

User information need: Interested to know about Everest and Nepal

User Boolean query: Everest AND Nepal

Implementation Part

Example of Input collection

Doc1= English tutorial and fast track

Doc2 = learning latent semantic indexing

Doc3 = Book on semantic indexing

Doc4 = Advance in structure and semantic indexing

Doc5 = Analysis of latent structures

Query problem: advance and structure AND NOT analysis

Boolean Model Index Construction

First we build the term-document incidence matrix which represents a list of all the distinct terms and their presence on each document (incidence vector). If the document contains the term than incidence vector is 1 otherwise 0.

Terms/doc Doc1 Doc2 Doc3 Doc4 Doc5
English  1 0 0 0 0
Tutorial 1 0 0 0 0
Fast 1 0 0 0 0
Track 1 0 0 0 0
Books 0 1 0 0 0
Semantic 0 1 1 1 0
Analysis 0 1 0 0 1
Learning 0 0 1 0 0
Latent 0 0 1 0 1
Indexing 0 0 1 1 0
Advance 0 0 0 1 0
Structures 0 0 0 1 1

So now we have 0/1 vector for each term. To answer the query we take the vectors for advance, structure and analysis, complement the last, and then do a bitwise AND.

Doc1 Doc2 Doc3 Doc4 Doc5
0 0 0 1 0
0 0 0 1 1 (AND)
0 0 0 1
1 0 1 1 0 (NOT analysis)
0 0 0 1 0  
      Doc4    
Hence Doc4 is retrieved here.

Diving into the code

Document tokenization and indexing

Tokenization is the task of chopping the input character sequence into pieces, called tokens. Here I have used termsCollection to store the retrieve tokens from the input document and HasSet collection type distinctTerm to create the index of tokens which ensures that the collection type contains only distinct terms .

//read all the text document on the specified directory
foreach (string file in Directory.EnumerateFiles("F:\\IR\\", "*.txt"))
{
    string contents = File.ReadAllText(file);
    String[] termsCollection = RemoveStopsWords(contents.ToUpper().Split(' '));
    foreach (string term in termsCollection)
    {
        //prepeare distinct terms collection
        //remove stop words
        if (!stopWords.Contains(term)) 
        {
            distinctTerm.Add(term);
        }
    }

    //add document and their terms collection
    documentCollection.Add(file, termsCollection.ToList());
    //add document and its content for displaying the search result
    documentContentList.Add(count, contents);
    count++;
}
Removing stop words

Most Search Engines do not consider extremely common words in order to save disk space or to speed up search results. These filtered words are known as 'Stop Words' here I have used generic collection stopWords which contains a list of stop word, to remove it from the document.

//removes all stop words
public static string[] RemoveStopsWords(string[] str)
{
    List<string> terms = new List<string>();
    foreach (string term in str)
    {
        if (!stopWords.Contains(term))
        {
            terms.Add(term);
        }
    }
    return terms.ToArray();
}
Term - Document Incidence matrix creation

If a term appears on a document than its term incidence vector is 1 else 0.

The GetTermDocumentIncidenceMatrix function returns the term document incidence matrix for all distinct terms which are stored on HashSet collection. I have used Dictionary collection type termDocumentIncidenceMatrix to store the term and its incidence vectors on each document.

//prepares Term Document Incidence Matrix
public static Dictionary<string, List<int>> GetTermDocumentIncidenceMatrix(HashSet<string> 
       distinctTerms,Dictionary<string,List<string>> documentCollection)
{
    Dictionary<string, List<int>> termDocumentIncidenceMatrix = 
                new Dictionary<string, List<int>>();
    List<int> incidenceVector = new List<int>();
    foreach (string term in distinctTerms)
    {
        //incidence vector for each terms
        incidenceVector = new List<int>();
        foreach(KeyValuePair<string ,List<string>> p in documentCollection)
        {
            
            if (p.Value.Contains(term))
            {
                //document contains the term
                incidenceVector.Add(1); 

            }
            else
            {
                //document do not contains the term
                incidenceVector.Add(0); 
            }
        }
        termDocumentIncidenceMatrix.Add(term, incidenceVector);

    }
    return termDocumentIncidenceMatrix;
} 
Retrieving incidence vector of individual term
//returns term incidence vector
public static List<int> GetTermIncidenceVector(string term)
{
    return termDocumentIncidenceMatrix[term.ToUpper()];
}
Query Processor

The string variable bitWiseOp holds the Boolean operator that exists on the query. Generally the term but is treated as semantically equivalent with Boolean AND operator. The collection previousTermIncidenceV and nextTermIncidenceV is used to hold the term incidence vector of each term that appears before and after the Boolean operator on the query.

//process the boolean query
public static List<int> ProcessQuery(string query)
{
    //query boolean operator
    string bitWiseOp = string.Empty; 
    string[] queryTerm = RemoveStopsWords(query.ToUpper().Split(''));
    //remove query term that doesnot appears on document collection
    FilterQueryTerm(ref queryTerm);
    List<int> previousTermIncidenceV = null;
    List<int> nextTermsIncidenceV = null;
    //holds the bitwise operation result
    List<int> resultSet = null;
    //On query X AND Y, X is previousTerm term and Y is nextTerm
    Boolean hasPreviousTerm = false; 
    Boolean hasNotOperation = false;
    foreach (string term in queryTerm)
    {
        //is a term
        if (!booleanOperator.Contains(term)&&!term.Equals("BUT"))
        {
            //query case: structure AND NOT analysis
            if (hasNotOperation) 
            {
                
                if (hasPreviousTerm)
                {
                    nextTermsIncidenceV = ProcessBooleanOperator("NOT", 
                      GetTermIncidenc eVector(term), nextTermsIncidenceV);
                }
                //query case: eg.NOT analysis
                else 
                {
                    previousTermIncidenceV = ProcessBooleanOperator("NOT", 
                      GetTermIncid enceVector(term), nextTermsIncidenceV);
                    resultSet = previousTermIncidenceV; 
                }
                hasNotOperation = false;
            }
            else if (!hasPreviousTerm)
            {
                previousTermIncidenceV = GetTermIncidenceVector(term);
                resultSet = previousTermIncidenceV;
                hasPreviousTerm = true; //
            }
            else
            {
                
                nextTermsIncidenceV = GetTermIncidenceVector(term);
            }
        }
        else if (term.Equals("NOT"))
        {
            //indicates that the  term in the next iteration should be complemented.
            hasNotOperation = true;
        }
        else
        {
            //'BUT' also should be evaluated as AND eg. structure BUT
            //NOT semantic should be evaluated as structure AND NOT semantic
            if (term.Equals("BUT")) 
            {
                bitWiseOp = "AND";
            }
            else
            bitWiseOp = term;
        }

        if (nextTermsIncidenceV != null && !hasNotOperation)
        {
            resultSet = ProcessBooleanOperator(bitWiseOp, 
                             previousTermIncidenceV, nextT ermsIncidenceV);
            previousTermIncidenceV = resultSet;
            hasPreviousTerm = true;
            nextTermsIncidenceV = null;
        }
    }

    return resultSet;
} 
Filter Query Term
private static void FilterQueryTerm(ref string[] str)
{
     List<string> _queryTerm = new List<string>();            
     foreach (string queryTerm in str) 
     {
         if (queryTerm.ToUpper().Equals("BUT") ||termDocumentIncidenceMatrix.ContainsKey(queryTerm.ToUpper()) ||booleanOperator.Contains(queryTerm))
            {
                    _queryTerm.Add(queryTerm);
                   
            }
      }
      str = _queryTerm.ToArray();
}
Processing Boolean operators
public static List<int> ProcessBooleanOperator(string op, 
          List<int> previousTermV,List<int> nextTermV)
{
    List<int> resultSet = new List<int>();
    if(op.Equals("NOT"))
    {
        foreach(int a in previousTermV)
        {
            if (a == 1)
            {
                resultSet.Add(0);
            }
            else
            {
                resultSet.Add(1);
            }
        }
    }
    else if (op.ToUpper().Equals("AND")) //bitwise AND operation
    {
        for (int a = 0; a < previousTermV.Count; a++)
        {
            if (previousTermV[a] == 1 && nextTermV[a] == 1)
            {
                resultSet.Add(1);
            }
            else
            {
                resultSet.Add(0);
            }
        }
    }
    else if (op.ToUpper().Equals("OR")) //bitwise OR operation
    {
        for (int a = 0; a < previousTermV.Count; a++)
        {
            if (previousTermV[a] == 0 && nextTermV[a] == 0)
            {
                resultSet.Add(0);
            }
            else
            {
                resultSet.Add(1);
            }
        }
    }
    return resultSet;
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Samir Kunwar
Software Developer
United States United States
Interested in Information Retrieval, Artificial Intelligence
research and programming.Programming is my passion,I enjoy programming for the same reasons that I enjoy reading great books.What I love about writing code is the nitpicking and problem solving.

Comments and Discussions

 
QuestionHow to run this code? PinmemberMember 109169231-Jul-14 4:42 
QuestionRe: Python code boolean retrieval model PinmemberJuan Pablo Perez F26-Sep-13 14:35 
QuestionHelp PinmemberMember 929051830-Jul-12 18:16 
AnswerRe: Help [modified] PinmemberSamir Kunwar31-Jul-12 8:14 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140926.1 | Last Updated 31 Jul 2012
Article Copyright 2012 by Samir Kunwar
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid