Processing Boolean Queries using C#

In the first post of this series, I explained how to produce an inverted index using C#. In the second post, I explained how to improve the tokenization process, using the Porter Stemming Algorithm. Now, I will share how to process boolean queries.

Inverted Index?

Within a  document collection, I assume that each document has a unique serial number (a documentId). During the index construction I simple assign successive integer to each new document.

The input to the indexing process is an enumeration of normalized tokens for each document.  The output is a dictionary where the keys are the tokens, and the values are lists of the documentIds of the documents which contains that token.

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<int>> _data = 
            new Dictionary<string, List>();

        internal void Append(string term, int documentId)
        {
            if (_data.ContainsKey(term))
            {
                _data[term].Add(documentId);
            }
            else
            {
                var postings = new List {documentId};
                _data.Add(term, postings);
            }

            _indexedDocuments.Add(documentId);
        }

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

The Query Abstraction

Given an inverted index, I want to be able to perform a query that results in all documents that meet the specified criteria.

In my implementation, the Query class is a base class and a factory.

using System.Collections.Generic;
using Tupi.Indexing;

namespace Tupi.Querying.Queries
{
    public abstract class Query
    {
        public abstract IEnumerable<int> Execute(InvertedIndex index);

        public static Query Term(string term) =>
            TermQuery.From(term);

        public static Query All(params string[] terms) =>
            AllQuery.From(terms);

        public static Query All(IEnumerable<int> queries) =>
            new AllQuery(queries);

        public static Query And(Query left, Query right) =>
            new AllQuery(left, right);

        public static Query Any(params string[] terms) =>
            AnyQuery.From(terms);

        public static Query Or(Query left, Query right) =>
            new AnyQuery(left, right);

        public static Query Not(Query innerQuery) 
            => new NotQuery(innerQuery);
    }
}

Use this abstraction to define queries is simple.

var query1 = Query.Or(
    Query.Term("csharp"),
    Query.And(
        Query.Term("Elemar"),
        Query.Term("inverted")
    )
);

var query2 = Query.Not(
    Query.And(
        Query.Term("Elemar"),
        Query.Term("inverted")
    )
);

Querying terms

Retrieving the list of documents containing a term is pretty simple. We just need to normalize the term and then check the dictionary.

using System;
using System.Collections.Generic;
using System.IO;
using Tupi.Indexing;

namespace Tupi.Querying.Queries
{
    public class TermQuery : Query
    {
        private readonly string _term;

        public TermQuery(string term)
        {
            _term = term;
        }

        public override IEnumerable<int> Execute(InvertedIndex index) 
            => index.GetPostingsFor(_term);

        public static Query From(string term) =>
            From(term, DefaultAnalyzer.Instance);

        public static Query From(string term, IAnalyzer analyzer)
        {
            using (var reader = new StringReader(term))
            {
                var tokenSource = new TokenSource(reader);
                tokenSource.Next();

                if (!analyzer.Process(tokenSource))
                {
                    throw new InvalidOperationException($"Could not generate a term from: {term}");
                }

                return new TermQuery(tokenSource.ToString());
            }
        }
    }
}

AND operator

Then AND implementation just intersects the results of two (or more) queries.

using System.Collections.Generic;
using System.Linq;
using Tupi.Indexing;

namespace Tupi.Querying.Queries
{
    public class AllQuery : Query
    {
        private readonly IEnumerable<Query> _queries;

        public AllQuery(IEnumerable<Query> queries)
        {
            _queries = queries;
        }

        public AllQuery(params Query[] queries)
        {
            _queries = queries;
        }

        public override IEnumerable<int> Execute(InvertedIndex index)
        {
            var postings = new List<List>();
            foreach (var query in _queries)
            {
                var l = query.Execute(index).ToList();

                if (!l.Any())
                {
                    return Enumerable.Empty();
                }

                postings.Add(l.ToList());
            }

            postings.Sort((l1, l2) => l1.Count.CompareTo(l2.Count));

            var results = postings[0];

            for (var i = 1; i < postings.Count; i++) { results = results.Intersect(postings[1]).ToList(); } return results; } public static Query From(params string[] terms) => 
            new AllQuery(terms.Select(TermQuery.From).ToList());
    }
}

OR operator

The OR implementation just merges the results of two (or more) queries.

using System.Collections.Generic;
using System.Linq;
using Tupi.Indexing;

namespace Tupi.Querying.Queries
{
    public class AnyQuery : Query
    {
        private readonly IEnumerable<Query> _queries;

        public AnyQuery(IEnumerable<Query> queries)
        {
            _queries = queries;
        }

        public AnyQuery(params Query[] queries)
        {
            _queries = queries;
        }

        public override IEnumerable<int> Execute(InvertedIndex index)
        {
            var results = Enumerable.Empty();
            return _queries.Aggregate(
                seed: Enumerable.Empty(),
                func: (current, query) => current.Union(query.Execute(index))
            );
        }

        public static Query From(params string[] terms) =>
            new AnyQuery(terms.Select(TermQuery.From).ToList());
    }
}

NOT operator

The NOT implementation returns all indexed documents, except the returned by the execution of the inner query.

using System.Collections.Generic;
using System.Linq;
using Tupi.Indexing;

namespace Tupi.Querying.Queries
{
    public class NotQuery : Query
    {
        private readonly Query _query;

        public NotQuery(Query query)
        {
            _query = query;
        }

        public override IEnumerable<int> Execute(InvertedIndex index) => 
            index.IndexedDocuments.Except(_query.Execute(index));
    }
}

Last words

In this post a shared how to implement boolean queries on an inverted index. I am pretty sure that there are a lot of improvement opportunities here. Please give me your recommendations in the comments.

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:

Nunca trabalhei em um circo, tampouco criei elefantes! Portanto, advirto que os “fatos” que lerá aqui foram relatados por amigos,...
In this post, I will show how to do your first steps with OpenCV quickly using Visual Studio 2017 and...
Há tempos que percebo em mim a ocorrência de um padrão recorrente. Não acho que ele seja exclusividade minha, mas,...
Tenho realizado uma série de apresentações, em conferências, onde compartilho um pouco das lições que tenho aprendido implementando microsserviços. Abaixo,...
Anualmente, como Microsoft MVP & RD, participo de uma conferência global, organizada pela Microsoft, na sede da empresa em Redmond....
As a consultant, I often need to work with the code that I do not know. I need to understand...

Curso Reputação e Marketing Pessoal

Masterclasses

01

Introdução do curso

02

Por que sua “reputação” é importante?

03

Como você se apresenta?

04

Como você apresenta suas ideias?

05

Como usar Storytelling?

06

Você tem uma dor? Eu tenho o alívio!

07

Escrita efetiva para não escritores

08

Como aumentar (e manter) sua audiência?

09

Gatilhos! Gatilhos!

10

Triple Threat: Domine Produto, Embalagem e Distribuição

11

Estratégias Vencedoras: Desbloqueie o Poder da Teoria dos Jogos

12

Análise SWOT de sua marca pessoal

13

Soterrado por informações? Aprenda a fazer gestão do conhecimento pessoal, do jeito certo

14

Vendo além do óbvio com a Pentad de Burkle

15

Construindo Reputação através de Métricas: A Arte de Alinhar Expectativas com Lag e Lead Measures

16

A Tríade da Liderança: Navegando entre Líder, Liderado e Contexto no Mundo do Marketing Pessoal

17

Análise PESTEL para Marketing Pessoal

18

Canvas de Proposta de Valor para Marca Pessoal

19

Método OKR para Objetivos Pessoais

20

Análise de Competências de Gallup

21

Feedback 360 Graus para Autoavaliação

22

Modelo de Cinco Forças de Porter

23

Estratégia Blue Ocean para Diferenciação Pessoal

24

Análise de Tendências para Previsão de Mercado

25

Design Thinking para Inovação Pessoal

26

Metodologia Agile para Desenvolvimento Pessoal

27

Análise de Redes Sociais para Ampliar Conexões

Lições complementares

28

Apresentando-se do Jeito Certo

29

O mercado remunera raridade? Como evidenciar a sua?

30

O que pode estar te impedindo de ter sucesso

Recomendações de Leituras

31

Aprendendo a qualificar sua reputação do jeito certo

32

Quem é você?

33

Qual a sua “IDEIA”?

34

StoryTelling

35

Você tem uma dor? Eu tenho o alívio!

36

Escrita efetiva para não escritores

37

Gatilhos!

38

Triple Threat: Domine Produto, Embalagem e Distribuição

39

Estratégias Vencedoras: Desbloqueie o Poder da Teoria do Jogos

40

Análise SWOT de sua marca pessoal

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.

Masterclass
15/07

Pare de dar a solução certa para o problema errado

Muita gente boa quebra a cabeça por dias tentando resolver o que não estava quebrado, simplesmente por tentar dar a resposta certa pro problema errado, mas precisa realmente ser assim?

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?