Processing boolean queries on inverted indexes in C#

Elemar Júnior

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:

Comentários

Participe deixando seu comentário sobre este artigo a seguir:

Subscribe
Notify of
guest
0 Comentários
Inline Feedbacks
View all comments

AUTOR

Elemar Júnior
Fundador e CEO da EximiaCo atua como tech trusted advisor ajudando empresas e profissionais a gerar mais resultados através da tecnologia.

NOVOS HORIZONTES PARA O SEU NEGÓCIO

Nosso time está preparado para superar junto com você grandes desafios tecnológicos.

Entre em contato e vamos juntos utilizar a tecnologia do jeito certo para gerar mais resultados.

Insights EximiaCo

Confira os conteúdos de negócios e tecnologia desenvolvidos pelos nossos consultores:

Arquitetura de Dados

Insights de um DBA na análise de um plano de execução

Especialista em performance de Bancos de Dados de larga escala
Arquitetura de Software

Estratégias para modernização do legado

Desenvolvedor .NET/NodeJs e especialista em Kafka com experiência em startups e grandes empresas
Infraestrutura e Nuvem

Migração para a nuvem, mais do que mudança tecnológica, implica em mudança da cultura organizacional

Engenheiro de nuvem, arquiteto de software e especialista em Containers e Devops

Acesse nossos canais

Simplificamos, potencializamos e aceleramos resultados usando a tecnologia do jeito certo

EximiaCo 2022 – Todos os direitos reservados

0
Queremos saber a sua opinião, deixe seu comentáriox
()
x

Processing boolean queries on inverted indexes in C#

Para se candidatar nesta turma aberta, preencha o formulário a seguir:

Condição especial de pré-venda: R$ 14.000,00 - contratando a mentoria até até 31/01/2023 e R$ 15.000,00 - contratando a mentoria a partir de 01/02/2023, em até 12x com taxas.

Tenho interesse nessa capacitação

Para solicitar mais informações sobre essa capacitação para a sua empresa, preencha o formulário a seguir:

Tenho interesse em conversar

Se você está querendo gerar resultados através da tecnologia, preencha este formulário que um de nossos consultores entrará em contato com você:

O seu insight foi excluído com sucesso!

O seu insight foi excluído e não está mais disponível.

O seu insight foi salvo com sucesso!

Ele está na fila de espera, aguardando ser revisado para ter sua publicação programada.

Tenho interesse em conversar

Se você está querendo gerar resultados através da tecnologia, preencha este formulário que um de nossos consultores entrará em contato com você:

Tenho interesse nessa solução

Se você está procurando este tipo de solução para o seu negócio, preencha este formulário que um de nossos consultores entrará em contato com você:

Tenho interesse neste serviço

Se você está procurando este tipo de solução para o seu negócio, preencha este formulário que um de nossos consultores entrará em contato com você:

× Precisa de ajuda?