quantize.h

Go to the documentation of this file.

/*
    QUANTIZE.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 <iostream>

#include "index_manager.h"
#include "index_manager_sequential.h"
#include "ranking_function_atire_bm25.h"

namespace JASS
    {
    /*
        CLASS QUANTIZE
        --------------
    */
    template <typename RANKER>
    class quantize : public index_manager::delegate, public index_manager::quantizing_delegate
        {
        private:
            double largest_rsv;                                             
            double smallest_rsv;                                                
            std::shared_ptr<RANKER> ranker;                             
            compress_integer::integer documents_in_collection;      
            static constexpr double impact_range = index_postings_impact::largest_impact - index_postings_impact::smallest_impact; 

        public:
            /*
                QUANTIZE::QUANTIZE()
                --------------------
            */
            quantize(size_t documents, std::shared_ptr<RANKER> ranker) :
                index_manager::delegate(documents),
                largest_rsv((std::numeric_limits<decltype(largest_rsv)>::min)()),
                smallest_rsv((std::numeric_limits<decltype(smallest_rsv)>::max)()),
                ranker(ranker),
                documents_in_collection(static_cast<compress_integer::integer>(documents))
                {
                /* Nothing. */
                }

            /*
                QUANTIZE::~QUANTIZE()
                ---------------------
            */
            virtual ~quantize()
                {
//              std::cout << "RSVmin:" << smallest_rsv << '\n';
//              std::cout << "RSVmax:" << largest_rsv << '\n';
                }

            /*
                QUANTIZE::FINISH()
                ------------------
            */
            virtual void finish(void)
                {
                /* Nothing */
                }

            /*
                QUANTIZE::OPERATOR()()
                ----------------------
            */
            virtual void operator()(const slice &term, const index_postings &postings, compress_integer::integer document_frequency, compress_integer::integer *document_ids, index_postings_impact::impact_type *term_frequencies)
                {
                /*
                    Compute the IDF component
                */
                ranker->compute_idf_component(document_frequency, documents_in_collection);

                /*
                    Compute the document / term score and keep a tally of the smallest and largest (for quantization)
                */
                auto end = document_ids + document_frequency;
                auto current_tf = term_frequencies;
                for (compress_integer::integer *current_id = document_ids; current_id < end; current_id++, current_tf++)
                    {
                    /*
                        Compute the term / document score
                    */
                    ranker->compute_tf_component(*current_tf);
                    auto score = ranker->compute_score(*current_id, *current_tf);

                    /*
                        Keep a running tally of the largest and smallest rsv we've seen so far
                    */
                    if (score < smallest_rsv)
                        smallest_rsv = score;
                    if (score > largest_rsv)
                        largest_rsv = score;
                    }
                }

            /*
                QUANTIZE::OPERATOR()()
                ----------------------
            */
            virtual void operator()(size_t document_id, const slice &primary_key)
                {
                /* Nothing. */
                }

            /*
                QUANTIZE::OPERATOR()()
                ----------------------
            */
            virtual void operator()(index_manager::delegate &writer, const slice &term, const index_postings &postings, compress_integer::integer document_frequency, compress_integer::integer *document_ids, index_postings_impact::impact_type *term_frequencies)
                {
                /*
                    Compute the IDF component
                */
                ranker->compute_idf_component(document_frequency, documents_in_collection);

                /*
                    Compute the document / term score and quantize it.
                */
                auto end = document_ids + document_frequency;
                auto current_tf = term_frequencies;
                for (compress_integer::integer *current_id = document_ids; current_id < end; current_id++, current_tf++)
                    {
                    /*
                        Compute the term / document score
                    */
                    ranker->compute_tf_component(*current_tf);
                    double score = ranker->compute_score(*current_id, *current_tf);

                    /*
                        Quantize using uniform quantization, and write back as the new term frequency (which is now an impact score).
                        This uses Uniform Quantiization as defined by Anh et al. in:
                        Vo Ngoc Anh, Owen de Kretser, and Alistair Moffat. 2001. Vector-space ranking with effective early termination. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval (SIGIR '01). ACM, New York, NY, USA, 35-42. DOI: https://doi.org/10.1145/383952.383957
                    */
                    index_postings_impact::impact_type impact = static_cast<index_postings_impact::impact_type>(((score - smallest_rsv) / (largest_rsv - smallest_rsv)) * impact_range) + index_postings_impact::smallest_impact;
                    *current_tf = impact;
                    }

                /*
                    Pass the quantized list to the writer.
                */
                writer(term, postings, document_frequency, document_ids, term_frequencies);
                }

            /*
                QUANTIZE::OPERATOR()()
                ----------------------
            */
            virtual void operator()(index_manager::delegate &writer, size_t document_id, const slice &primary_key)
                {
                writer(document_id, primary_key);
                }

            /*
                QUANTIZE::GET_BOUNDS()
                ----------------------
            */
            void get_bounds(double &smallest, double &largest)
                {
                smallest = smallest_rsv;
                largest = largest_rsv;
                }

            /*
                QUANTIZE::SERIALISE_INDEX()
                ---------------------------
            */
            void serialise_index(index_manager &index, std::vector<std::unique_ptr<index_manager::delegate>> &serialisers)
                {
                for (auto &outputter : serialisers)
                    {
                    index.iterate(*this, *outputter);
                    outputter->finish();
                    }
                }

            /*
                QUANTIZE::UNITTEST()
                --------------------
            */
            static void unittest(void)
                {
                /*
                    Build an index.
                */
                index_manager_sequential index;
                index_manager_sequential::unittest_build_index(index, unittest_data::ten_documents);

                /*
                    Quantize the index.
                */
                std::shared_ptr<ranking_function_atire_bm25> ranker(new ranking_function_atire_bm25(0.9, 0.4, index.get_document_length_vector()));
                quantize<ranking_function_atire_bm25> quantizer(index.get_highest_document_id(), ranker);
                index.iterate(quantizer);

                double smallest;
                double largest;
                quantizer.get_bounds(smallest, largest);

                JASS_assert(static_cast<int>(smallest) == 0);
                JASS_assert(static_cast<int>(largest) == 2);

                puts("quantize::PASSED");
                }
        };
    }