Xapian: a search engine library

CSC263

1. Install

Xapian needs two external libraries.

  • uuid. On ubuntu, it can be installed using
apt-get install uuid-dev
  • zlib. Ubuntu comes with zlib installed by default.

To compile the Xapian library, do the following:

  • Download Xapian core source code
  • Extract the xapian core source tree to a directory: tar -xf xapian-core-1.4.14.tar.xz XAPIAN_DIR Call it XAPIAN_DIR.
  • Make
cd XAPIAN_DIR
./configure
make

If no error occurred, you should see the file:

XAPIAN_DIR/.libs/libxapian.a

which is the static library we need to build programs using Xapian.

2. Compiling your program

Suppose your program is called myprog.cc which makes use of APIs from the Xapian library.

The following shell command compiles and links the executable from the source code:

c++ myprog.cc `xapian-config --libs --cxxflags` -o myprog

Defines the paths to look for include headers and libraries.

Defines the libraries to be used: xapian, zlib and uuid.

Compiles and links the source code.

3. The Xapian API by example

All xapian api are under the namespace Xapian:: which is imported by:

#include <xapian.h>

3.1. Indexing documents

First, we need to start with opening a writable database.

char *dbname = "...";
Xapian::WritableDatabase db(dbname, Xapian::DB_CREATE_OR_OPEN);

Note the flag Xapian::DB_CREATE_OR_OPEN will create a directory called dbname if it does not already exist.

Xapian stores documents in a database.

A document object is created by:

Xapian::Document doc;

Documents can store several types of information:

  1. terms: Terms are words by which a search engine can find the document. Typically, we will need to break down a text into a collection of terms, and populate a document object with these terms.
  2. values: Values are user defined data that can be associated with the document. Examples of the values suitable to be stored in a document are: document creation date, access control flags on the document, and the original text which is the source of the terms of the document.

Documents can add terms which are references to c++ strings.

#include <string>
...

std::string term = "hello";
doc.add_term(term);

The reason that references are used is the considerations for efficiency. In a practical scenario, the text database may contain hundreds of millions of terms. The Xapian::Document.add_term(std::string &) function accepts a reference to avoid the additional memory copy for each of the terms added to the documents of the database.

Documents have special slots to hold values. The slots are labeled by integers starting at 0. Each slot can hold a value of type (std::string &).

Values can be added as:

doc.add_value(0, string("hello"));
doc.add_value(1, string("world"));

Documents populated with terms and values can be written to a writable database by:

db.add_document(doc);

The Xapian::WritableDatabase::add_document does several things under the cover:

  • It inserts the terms into a global dictionary of words. This dictionary is implemented using a B+ tree data structure.
  • It inserts the document ID into the inverted list of all the terms that belongs to that document.
  • It stores the document values into a structured database.

The db.add_document(...) calls write the data asynchronously in units of transactions. This means that the documents are not immediately added to the database unless the database issues a commit explicitly.

db.commit()

A commit will flush the buffer causing one or more disk I/O. A good practice is to commit for every batch of documents added to the database, which a batch size of 1000 is reasonable.

Typically, we have a loop iterating over a collection of text segments. For example, each web page fetched by a crawler will be a text segment.

While we can choose to abstract each text segment as a separate document, in practice, we would like to reuse a single document object to store the text segments.

A document can be reused by clearing the terms and values of a document:

doc.clear_terms();
doc.clear_values();

Here is a complete sample program that creates two documents.

#include <xapian.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include "common.h"

using namespace std;

int main(int argc, char **argv) {
    if(argc < 2) {
        cerr << "Usage: <idxname>" << endl;
        exit(0);
    }

    char *idxname = argv[1];
    Xapian::WritableDatabase db(idxname, Xapian::DB_CREATE_OR_OPEN);
    Xapian::Document doc;

    vector<string> words;
    words.push_back("hello world again and again");
    words.push_back("a brave new world world");

    long lineno = 0;
    for(vector<string>::iterator it = words.begin(); 
                                 it != words.end(); 
                                 it++, lineno++) {
        cout << "line " << lineno << ": ";
        string &s = *it;

        // perform tokenization
        vector<string> tokens;
        word_tokenize(s, &tokens);

        // populate the document
        // value[0] will be the original line
        doc.clear_terms();
        doc.clear_values();
        doc.add_value(0, string(s));
        // document is the bag of terms
        for(vector<string>::iterator it_token=tokens.begin(); 
            it_token != tokens.end(); 
            it_token++) {
            string &token = *it_token;
            cout << token << " ";
            doc.add_term(token);
        }
        cout << endl;
        db.add_document(doc);
        if(lineno % 1000 == 0) {
            db.commit();
        }
    }
}

3.2. Querying documents

Querying documents from a Xapian database involves two steps:

  1. build a query from terms with boolean flags.
  2. execute the query and collect the matched documents.

We need to create a Xapian database object for reading an existing database.

Xapian::Database db("mydatabase");

A query is a sequence of pairs of the form:

(term, flag), (term, flag), ...

where the terms are std::string, and flags are one of;

  • Xapian::Query::OP_AND
  • Xapian::Query::OP_OR

NOTE: More flags and more complex Xapian query structures are possible.

The following code builds a query consisting of strings from a std::vector<string>, and all the term flags are Xapian::Query::OP_OR.

std::vector<string> terms = ...;
Xapian::Query query(
    Xapian::Query::OP_OR,
    terms.begin(),
    terms.end()
);

The query constructed will look for documents that match as many terms from terms as possible. More specifically, Xapian utilizes a variantion on TFIDF weighting scheme, known as the BM25 to assign weights on terms. The OR-query terms try to maximize the total BM25 weight of matched terms.

A searcher object, known as the enquire object, is responsible for scanning through the inverted list, and return the top-$k$ matched documents from the best matched to the worst matched.

The following code fetches the top 10 matched documents from a database and prints the first value stored in the document.

Xapian::Database db = ...;
Xapian::Query query = ...;

Xapian::Enquire enquire(db);
enquire.set_query(query);

Xapian::MSet matches = enquire.get_mset(0, 10); 
printf("mset size is %d\n", matches.size());

for(Xapian::MSetIterator match = matches.begin(); 
    match != matches.end();
    match ++)                                     
{

    Xapian::Document doc = i.get_document();

    std::string value0 = doc.get_value(0);
    cout << value0 << endl;
}

Xapian::MSet stores the top-10 matches in a ranked order.

Xapian::MSetIterator is used to walk through the matched documents.