Phrase Queries and Positional Indexes in C#

This is another post about how to implement a basic Search Engine.

Previously, I explained:

In this post, I will share how to implement Phrase Queries and how to generate Positional Indexes using C#. The source code is available on my Github.

Phrase Queries?

From the “Introduction to Information Retrieval” book:

Many complex or technical concepts and many organization or product names are multiword compounds or phrases. We  would like to be able to pose a query such as “Stanford University” by threating it as a phrase do that a sentece in a document like “The Inventor Stanford Ovshinsky never went to university” is not a match.

To perform this kind of query in my search engine, I implemented a new Query concept: Distance.

[Fact]
void DistanceQueriesRespectsMaxDistance()
{
    var documents = new[]
    {
        "The Inventor Stanford Ovshinsky never went to university",
        "The Stanford University is in the heart of Northern California's dynamic Silicon Valley"
    };

    var index = new StringIndexer().CreateIndex(documents);
    var seacher = new Searcher(index);

    var query = Query.Distance(
        DefaultAnalyzer.Instance.AnalyzeOnlyTheFirstToken("Stanford"),
        DefaultAnalyzer.Instance.AnalyzeOnlyTheFirstToken("University"),
        maxDistance: 1
    );

    var results = seacher.Search(query);

    Assert.Equal(new[] { 1 }, results);
}

The idea is to match only documents where two terms appear close to each other in the text.

Positional Indexes?

To be able to support the Distance concept, I improved the Inverted Index data structure.

It is no longer sufficient to store simply lists of documents that contain individual terms (as we did in the previous posts). Now, for each term in the vocabulary, we will need to store, for each document, the positions of the term in the text.

var documents = new[]
{
    // 1    2  3    4   5    6    7     8   9    10  11    12
    "One item is just one item. Two items are other two items"
};

We have now the Posting class with the DocumentID and the Positions.

using System.Collections.Generic;
using System.Linq;

namespace Tupi.Indexing
{
    public class InvertedIndex
    {
        private readonly ISet _indexedDocuments = 
            new SortedSet();
        public IEnumerable<int> IndexedDocuments => _indexedDocuments;

        private readonly IDictionary<string, List> _data = 
            new Dictionary<string, List>();

        internal void Append(string term, int documentId, long position)
        {
            if (_data.ContainsKey(term))
            {
                var posting =
                    _data[term].FirstOrDefault(p => p.DocumentId == documentId);

                if (posting == null)
                {
                    posting = new Posting(documentId);
                    _data[term].Add(posting);
                }
            
                posting.Positions.Add(position);
            }
            else
            {
                var posting = new Posting(documentId);
                posting.Positions.Add(position);
                var postings = new List {posting};
                _data.Add(term, postings);
            }

            _indexedDocuments.Add(documentId);
        }

        public IEnumerable GetPostingsFor(string term) => !_data.ContainsKey(term) 
            ? Enumerable.Empty() 
            : _data[term];
    }

    public class Posting
    {
        public int DocumentId { get; }
        public IList Positions { get; } = new List(); 

        public Posting(int documentId)
        {
            DocumentId = documentId;
        }

        public static implicit operator int(Posting entry) => 
            entry.DocumentId;
    }
}

The Inverted Index, including positional information, needs more memory, but we have no choice if we want to provide support for Phrase Queries.

The Distance Query Implementation

To process a phrase query, we will need:

    • to access the inverted index entries for each distinct term in the query;
    • check if both terms are in a single document;
    • check that their positions of appearance in the document are compatible with the specified max distance.

Here is my implementation:

public class DistanceQuery : Query
{
    private readonly string _term1;
    private readonly string _term2;
    private readonly int _maxDistance;

    public DistanceQuery(string term1, string term2, int maxDistance)
    {
        _term1 = term1;
        _term2 = term2;
        _maxDistance = maxDistance;
    }

    public override IEnumerable<int> Execute(InvertedIndex index)
    {
        var postingsForTerm1 = index.GetPostingsFor(_term1).ToList();
        var postingsForTerm2 = index.GetPostingsFor(_term2).ToList();

        IEnumerable<Posting> lessFrequent;
        IEnumerable<Posting> moreFrequent;

        if (postingsForTerm1.Count() < postingsForTerm2.Count())
        {
            lessFrequent = postingsForTerm1;
            moreFrequent = postingsForTerm2;
        }
        else
        {
            lessFrequent = postingsForTerm2;
            moreFrequent = postingsForTerm1;
        }

        using (var p1 = lessFrequent.GetEnumerator())
        using (var p2 = moreFrequent.GetEnumerator())
        {
            var hasElementsP1 = p1.MoveNext();
            var hasElementsP2 = p2.MoveNext();
            while (hasElementsP1 && hasElementsP2)
            {
                if (p1.Current.DocumentId == p2.Current.DocumentId)
                {
                    var pp1 = p1.Current.Positions;
                    var pp2 = p2.Current.Positions;
                    for (var i = 0; i < pp1.Count; i++)
                    {
                        for (var j = 0; j < pp2.Count; j++)
                        {
                            if (Math.Abs(pp1[i] - pp2[j]) <= _maxDistance) 
                            { 
                                yield return p1.Current.DocumentId; 
                                break; 
                            } 
                            if (pp2[j] > pp1[i])
                            {
                                break;
                            }
                        }
                    }

                    hasElementsP1 = p1.MoveNext();
                    hasElementsP2 = p2.MoveNext();
                }
                else if (p1.Current.DocumentId < p2.Current.DocumentId)
                {
                    hasElementsP1 = p1.MoveNext();
                }
                else
                {
                    hasElementsP2 = p2.MoveNext();
                }
            }
        }
    }
}

Until now, we were using .NET Enumerable’s implementation of the Intersect algorithm. This one is based on the algorithm proposed in the book.

Let’s see the next steps…

Compartilhe este insight:

Elemar Júnior

Sou fundador e CEO da EximiaCo e atuo como tech trusted advisor ajudando diversas empresas a gerar mais resultados através da tecnologia.

Elemar Júnior

Sou fundador e CEO da EximiaCo e atuo como tech trusted advisor ajudando diversas empresas a gerar mais resultados através da tecnologia.

Mais insights para o seu negócio

Veja mais alguns estudos e reflexões que podem gerar alguns insights para o seu negócio:

Neste post, compartilho seis benefícios gerados por um bom projeto de Arquitetura de Software.  Cada um desses benefícios ajuda a...
Crescer implica, invariavelmente, em aumentar a produtividade, ou seja, na melhoria da relação entre a capacidade de gerar valor e...
Há pouco menos de um ano, aceitei o desafio de liderar o time de tecnologia e estratégia de negócios da...
Em tempos onde tanta gente parece saber muito sobre tanta coisa, é interessante resgatar o pensamento da polêmica professora Marilena...
In the previous post, I shared an example of how containers could help us to make the code clearer about...
If you ask me one tip to improve the performance of your applications, it would be: Design your objects to...

Inscrição realizada com sucesso!

No dia da masterclass você receberá um e-mail com um link para acompanhar a aula ao vivo. Até lá!

A sua subscrição foi enviada com sucesso!

Aguarde, em breve entraremos em contato com você para lhe fornecer mais informações sobre como participar da mentoria.

Crie sua conta

Preencha os dados para iniciar o seu cadastro no plano anual do Clube de Estudos:

Crie sua conta

Preencha os dados para iniciar o seu cadastro no plano mensal do Clube de Estudos:

× Precisa de ajuda?