ranking_function_atire_bm25.h

Go to the documentation of this file.

/*
    RANKING_FUNCTION_ATIRE_BM25.H
    -----------------------------
    Copyright (c) 2018 Andrew Trotman
    Released under the 2-clause BSD license (See:https://en.wikipedia.org/wiki/BSD_licenses)
*/
#pragma once

#include <math.h>
#include <stdio.h>
#include <stdint.h>

#include <vector>

#include "forceinline.h"
#include "compress_integer.h"
#include "index_postings_impact.h"


namespace JASS
    {
    /*
        CLASS RANKING_FUNCTION_ATIRE_BM25
        ---------------------------------
    */
    class ranking_function_atire_bm25
        {
        private:
            double idf;                                             
            double top_row;                                         
            double k1_plus_1;                                       
            double mean_document_length;                            
            std::vector<float> length_correction;                   

        public:
            /*
                RANKING_FUNCTION_ATIRE_BM25::RANKING_FUNCTION_ATIRE_BM25()
                ----------------------------------------------------------
            */
            ranking_function_atire_bm25(double k1, double b, std::vector<compress_integer::integer> &document_lengths):
                idf(0),
                top_row(0),
                k1_plus_1(k1 + 1.0),
                mean_document_length(0),
                length_correction(document_lengths.size())
                {
                double one_minus_b = 1.0 - b;

                uint64_t sum = 0;
                for (auto length : document_lengths)
                    sum += length;

                mean_document_length = static_cast<double>(sum) / static_cast<double>(document_lengths.size() - 1);         // -1 because ID 0 is not used (and should be 0)

                auto correction = &length_correction[0];            // recall that we count from 1, not from 0
                for (auto length : document_lengths)
                    *correction++ =  k1 * (one_minus_b + b * static_cast<double>(length) / mean_document_length);
                }

            /*
                RANKING_FUNCTION_ATIRE_BM25::~RANKING_FUNCTION_ATIRE_BM25()
                ----------------------------------------------------------
            */
            ~ranking_function_atire_bm25()
                {
                /* Nothing */
                }

            /*
                RANKING_FUNCTION_ATIRE_BM25::COMPUTE_IDF_COMPONENT()
                ----------------------------------------------------
            */
            forceinline void compute_idf_component(compress_integer::integer document_frequency, compress_integer::integer documents_in_collection)
                {
                /*
                                 N
                    IDF = log -
                                 n

                    This variant of IDF is better than log((N - n + 0.5) / (n + 0.5)) on the 70 INEX 2008 Wikipedia topics.  Also, it is always positive.
                */
                idf = log((double)documents_in_collection / (double)document_frequency);
                }

            /*
                RANKING_FUNCTION_ATIRE_BM25::COMPUTE_TF_COMPONENT()
                ---------------------------------------------------
            */
            forceinline void compute_tf_component(index_postings_impact::impact_type term_frequency)
                {
                top_row = term_frequency * k1_plus_1;
                }

            /*
                RANKING_FUNCTION_ATIRE_BM25::COMPUTE_SCORE()
                --------------------------------------------
            */
            forceinline double compute_score(compress_integer::integer document_id, index_postings_impact::impact_type term_frequency)
                {
                /*
                                        tf(td) * (k1 + 1)
                    rsv = ----------------------------------- * IDF
                                                                 len(d)
                            tf(td) + k1 * (1 - b + b * --------)
                                                                av_len_d

                    In this implementation we ignore k3 and the number of times the term occurs in the query.
                */
                double tf = term_frequency;
                return idf * (top_row / (tf + length_correction[document_id]));
                }

            /*
                RANKING_FUNCTION_ATIRE_BM25::UNITTEST()
                ---------------------------------------
            */
            static void unittest(void)
                {
                double rsv;
                std::vector<compress_integer::integer> lengths{30, 40, 50, 60, 70};         // the lengths of the documents in this pseudo-index
                ranking_function_atire_bm25 ranker(0.9, 0.4, lengths);  // k1=0.9, b=0.4

                ranker.compute_idf_component(2, static_cast<uint32_t>(lengths.size()));         // this term occurs in 2 of 5 documents
                ranker.compute_tf_component(12);                                    // it occurs in this document 12 times
                rsv = ranker.compute_score(1, 12);                              // it occurs in document 1 a total of 12 times;

                JASS_assert(static_cast<uint32_t>(rsv * 1000) == 1635);
                puts("ranking_function_atire_bm25::PASSED");
                }
        };
    }