Initial import into git.

[galago.git] / cpp / galago / include / ArrayAccumulators.hpp

//
// ArrayAccumulators
//
// 5 January 2007 -- tds
//  

#include "LongArrayAccumulators.hpp"
#include "indri/indri-platform.h"
#include "lemur/RVLCompress.hpp"
#include "Logging.hpp"
#include "Accumulators.hpp"
#include "Bits.hpp"
#include <vector>
#include <string> 
#include <queue>                   

#ifndef GALAGO_ARRAYACCUMULATORS_HPP
#define GALAGO_ARRAYACCUMULATORS_HPP

template<class _AccumulatorType>
class ArrayAccumulators : public Accumulators {
public:
    typedef typename AccumulatorTypes<_AccumulatorType>::term_type   term_type;
    typedef typename AccumulatorTypes<_AccumulatorType>::update_type update_type;

private:
    std::vector<_AccumulatorType> _first;
    std::vector<_AccumulatorType> _second;
    std::vector<_AccumulatorType>& _accumulators;
    std::vector<_AccumulatorType>& _newAccumulators;
    
    std::vector<UINT32> _maxUnseen;
    std::vector<UINT32> _fullUnseen;
    std::vector<UINT32> _scoreCounts;
    
    int _termCount;
    int _threshold;
    bool _needsTrim;
    bool _canIgnorePostings;

    static inline void _moveNextOrAccumulator( const std::vector<_AccumulatorType>& accumulators,
                                               UINT32& nextAccumulator,
                                               int& index ) {
        index++;
        
        if( index == accumulators.size() ) {
            nextAccumulator = MAX_UINT32;
        } else {
            nextAccumulator = accumulators[index].document();
        }
    }

    static inline void _moveNextAndAccumulator( const std::vector<_AccumulatorType>& accumulators,
                                                term_type termBit,
                                                UINT32& nextAccumulator,
                                                int& index ) {
        while (true) {
            index++;
            
            if( index == accumulators.size() ) {
                nextAccumulator = MAX_UINT32;
                break;
            } else {
                const _AccumulatorType& accumulator = accumulators[index];
                
                if( accumulator.containsTerm( termBit ) ) {
                    continue;
                } else {
                    nextAccumulator = accumulator.document();
                    break;
                }
            }
        }
    }

    //
    // move_to_document
    //
    // Move forward in the inverted list to the next general location where we may be able to
    // update an accumulator.  We do this efficiently by incorporating skip data in the inverted
    // list.
    //
    // Skip data comes in compressed and delta-encoded (document, distance) pairs.  A 
    // (document, distance) tuple implies that the posting for document is immediately before
    // binStart + distance.  So, if we are looking for nextDocument, and nextDocument > document,
    // we can safely skip to binStart + distance.
    //
    // Our strategy is to decode the skip information slightly ahead of nextDocument, so generally
    // skipDocument is set to something greater than nextDocument upon return.  This helps reduce
    // the overhead of skip processing in the event that there are lots of accumulators.
    // Notice that the function begins with a quick check to see if the skip data will be useful,
    // and it returns if it won't be useful.
    //

    static inline const char* _moveToDocument( const UINT32 nextDocument, UINT32& currentDocument,
                                               const char* binStart, const char* binData,
                                               UINT32& skipDocument, size_t& skipDistance,
                                               const char*& skipData, const char* skipEnd ) {
        // if the next skip location isn't available, or if it is further
        // than we need to go, quit now.
        if( nextDocument <= skipDocument )
            return binData;

    #ifndef GALAGO_NO_SKIPS        
        if( skipData == skipEnd )
    #endif
        {
            skipDocument = MAX_UINT32;
            return binData;
        }
        
        // we know there is more skip information, so we'll decode it
        while ( skipData < skipEnd ) {
            int docDelta;
            int distDelta;
            
            // decode a (document, distance) pair
            skipData = lemur::utility::RVLCompress::decompress_int( skipData, docDelta );
            skipData = lemur::utility::RVLCompress::decompress_int( skipData, distDelta );
            skipDocument += docDelta;
            skipDistance += distDelta;
            
            // if this latest skip information is more than we need, quit, 
            // while storing the next skip point in (skipDocument, skipDistance).
            if( nextDocument <= skipDocument ) {
                const char* lastSkip = binStart + skipDistance - distDelta;
                
                if( lastSkip < binData ) {
                    return binData;
                } else {
                    currentDocument = skipDocument - docDelta;
                    return lastSkip;
                }
            }
        }

        // we're all done with skip data, so go to the point indicated by the last skip
        if( binData > binStart + skipDistance ) {
            skipDocument = MAX_UINT32;
            return binData;
        }
        
        currentDocument = skipDocument;
        skipDocument = MAX_UINT32;
        return binStart + skipDistance;
    }
    
    //
    // _newScore
    //

    void _newScore( UINT32 score ) {
        if( _scoreCounts.size() < score+1 ) {
            _scoreCounts.resize( score+1, 0 );
        }
        
        _scoreCounts[score]++;
    }

    //
    // _updateScore
    //

    void _updateScore( UINT32 oldScore, UINT32 newScore ) {
        if( _scoreCounts.size() < newScore+1 ) {
            _scoreCounts.resize( newScore+1, 0 );
        }
        
        _scoreCounts[oldScore]--;
        _scoreCounts[newScore]++;
    }
    
    //
    // _swapAccumulators
    //
    
    void _swapAccumulators() {
        if( &_accumulators == &_first ) {
            _accumulators = _second;
            _newAccumulators = _first;
        } else {
            _accumulators = _first;
            _newAccumulators = _second;
        }
        
        _newAccumulators.clear();
    }
    
public:
    ArrayAccumulators( int termCount ) :
        _accumulators(_first),
        _newAccumulators(_second)
    {
        int actual = std::min( termCount, _AccumulatorType::maxTerms() );
        _threshold = -1;
        _canIgnorePostings = false;
        _maxUnseen.resize( actual, _AccumulatorType::maxScore() );
        _termCount = actual;
        _needsTrim = false;
    }
    
    //
    // setThresholdScore
    //
    
    void setThresholdScore( int threshold ) {
        _threshold = std::max( threshold, _threshold );
    }
    
    //
    // threshold
    //
    
    int threshold() const {
        return _threshold;
    }

    //
    // useAndMode
    //

    bool useAndMode() {
        return totalUnseen() < _threshold;
    } 

    //
    // processBin
    //

    void processBin( int score, BinOrderedBinnedIterator* iterator ) {
        processBinOr( score, -1, iterator );
    }

    //
    // processBin
    //

    void processBin( int score, int termIndex, BinOrderedBinnedIterator* iterator ) {
        if( useAndMode() ) {
            processBinAnd( score, termIndex, iterator );
        } else {
            processBinOr( score, termIndex, iterator );
        }
    }

    //
    // processBinOr
    //

    void processBinOr( int score, int termIndex, BinOrderedBinnedIterator* iterator ) {
        galago_logging log;
        galago_log_bin_start( log, GALAGO_MODE_OR, score, termIndex, iterator->postingsDataLength(), iterator->skipDataLength(), _accumulators.size(), _threshold );
        
        assert( termIndex >= 0 );
        int accIndex=-1;
        update_type updateValue = _AccumulatorType::buildUpdate( termIndex, score );
        UINT32 nextAccumulator = 0;
        
        _moveNextOrAccumulator( _accumulators, nextAccumulator, accIndex );
        _newAccumulators.reserve(_accumulators.size() + iterator->binDataLength() / 2 );
        
        const char* binData = iterator->binData();
        const char* binEnd = iterator->binData() + iterator->binDataLength();
        int document = 0;
        
        while( binData < binEnd ) {
            // decompress the next posting
            int delta = 0;
            binData = lemur::utility::RVLCompress::decompress_int( binData, delta );
            document += delta;

            galago_log_posting( log );
            
            // copy all accumulators that come before the current document
            while( nextAccumulator < document ) {
                _newAccumulators.push_back( _accumulators[accIndex] );
                _moveNextOrAccumulator( _accumulators, nextAccumulator, accIndex );
            }
            
            // if this document already appears in the accumulators, update it
            if( nextAccumulator == document ) {
                _AccumulatorType& accumulator = _accumulators[accIndex];
                UINT32 oldScore = accumulator.score();
                _updateScore( oldScore, oldScore + score ); 
            
                accumulator.update( updateValue );
                _newAccumulators.push_back( accumulator );
                _moveNextOrAccumulator( _accumulators, nextAccumulator, accIndex );
                
                galago_log_accumulator( log, document, oldScore + score );                        
            } else {                                                 
                // otherwise, build a new accumulator for the new document
                _AccumulatorType newAccumulator( document, updateValue );
                _newAccumulators.push_back( newAccumulator );
                _newScore( score );
                
                galago_log_accumulator( log, document, score );
            }
        }   
        
        // some old accumulators may be left; copy those too
        std::copy( _accumulators.begin() + accIndex, _accumulators.end(), std::back_inserter(_newAccumulators) );
        // copy the table back into place
        _swapAccumulators();
        
        galago_log_bin_end( log, _accumulators.size() );
    }    

    //
    // processBinAnd
    //

    void processBinAnd( int score, int termIndex, BinOrderedBinnedIterator* iterator ) {
        galago_logging log;
        galago_log_bin_start( log, GALAGO_MODE_AND, score, termIndex, iterator->postingsDataLength(), iterator->skipDataLength(), _accumulators.size(), _threshold );
        
        int accIndex=0;
        
        if( _accumulators.size() == 0 )
            return;
        
        assert( termIndex <= _AccumulatorType::maxTerms() );
        term_type termBit = _AccumulatorType::buildTerm( termIndex );
        update_type updateValue = _AccumulatorType::buildUpdate( termIndex, score );
        UINT32 nextDocument = _accumulators[0].document();
        size_t skipDistance = 0;
        
        const char* binDataStart = iterator->binData();
        const char* binData = iterator->binData();
        const char* binEnd = iterator->binData() + iterator->binDataLength();
        
        const char* skipData = iterator->skipData();
        const char* skipEnd = skipData + iterator->skipDataLength();
        UINT32 skipDocument = 0;

        // turn off skipping entirely if we have lots of accumulators
        if( iterator->skipDataLength()/4 <= _accumulators.size() ) {
            skipDocument = MAX_UINT32;
            skipData = skipEnd;
        }
            
        UINT32 document = 0;
        binData = _moveToDocument( nextDocument, document, binDataStart, binData, skipDocument, skipDistance, skipData, skipEnd );
        
        while( binData < binEnd ) {
            // decompress the next posting
            int delta = 0;
            binData = lemur::utility::RVLCompress::decompress_int( binData, delta );
            document += delta;
            
            galago_log_posting( log );
                       
            // if this current document is smaller than the next accumulator, we go to the next one
            // just ignore it and move on (very common case)
            if( document < nextDocument )
                continue;
            
            // if the current document is after the next accumulator, we
            // need to move forward to see if current matches a later accumulator
            while( document > nextDocument )
                _moveNextAndAccumulator( _accumulators, termBit, nextDocument, accIndex );
                
            if( nextDocument == MAX_UINT32 )
                break;
            
            // update the accumulator, if this is a hit
            if( document == nextDocument ) {
                _AccumulatorType& accumulator = _accumulators[accIndex];
                UINT32 oldScore = accumulator.score();        
                
                accumulator.update( updateValue );
                _updateScore( oldScore, oldScore + score );
                galago_log_accumulator( log, document, score );

                _moveNextAndAccumulator( _accumulators, termBit, nextDocument, accIndex );
            }

            // try to move the data pointer forward to the next accumulator
            binData = _moveToDocument( nextDocument, document, binDataStart, binData, skipDocument, skipDistance, skipData, skipEnd );
        }
        
        galago_log_bin_end( log, _accumulators.size() );
    }

    //
    // setMaxUnseen
    //

    void setMaxUnseen( int termIndex, int score ) {   
        assert( termIndex < _termCount );
        assert( score <= _AccumulatorType::maxScore() );
        
        _maxUnseen[termIndex] = score;
    } 

    //
    // calculateThresholdScore
    // 
    // The threshold is the n^th largest score in the accumulator table (where n = requested). 
    // Any score in the final ranked list will need to be above this computed threshold value.
    //          

    void calculateThresholdScore( int requested ) {
        int countsSeen = 0;
        int i;
        
        for( i = _scoreCounts.size()-1; i >= 0; i-- ) {
            countsSeen += _scoreCounts[i];
            
            if( countsSeen >= requested )
                break;
        }

    #ifndef GALAGO_NO_AND_MODE
        if( i > 0 ) 
            _needsTrim = true;
        
        setThresholdScore( i );
    #else
        _threshold = -1;
    #endif
    }  

    //
    // trim
    //

    void trim() {
        if( _threshold < 0 || _needsTrim == false )
            return;
            
    #ifdef GALAGO_NO_TRIM
        return;
    #endif                 

        _AccumulatorType::computeUnseenScoreArray( _fullUnseen, _maxUnseen );
        
    #ifdef GALAGO_TRIM_ONCE
        for( int i=0; i<_accumulators.size(); i++ ) {
            const _AccumulatorType& accumulator = _accumulators[i];
            UINT32 score = accumulator.score();
            
            if( score >= _threshold )
                continue;
            
            UINT32 seenTerms = accumulator.terms();
            UINT32 maxValue = score + accumulator.unseen( _fullUnseen );
                       
            // can't trim until no low scoring document would make it in the topk
            if ( maxValue >= _threshold )
                return;
        }
    #endif
        _newAccumulators.reserve( _accumulators.size() );
        
        // for each accumulator, we compute the max possible value and trim if it can't be achieved
        for( int i=0; i<_accumulators.size(); i++ ) {
            const _AccumulatorType& accumulator = _accumulators[i];
            UINT32 maxValue = accumulator.score() + accumulator.unseen( _fullUnseen );
            
            if ( maxValue >= _threshold ) {
                _newAccumulators.push_back( _accumulators[i] );
            }
        }
        
        _swapAccumulators();
        _needsTrim = false;
    }         

    //
    // size
    //

    int size() {
        return _accumulators.size();
    }

    //
    // totalUnseen
    //

    int totalUnseen() {
        int totalUnseen = 0;
        
        for( int i=0; i < _maxUnseen.size(); i++ ) {
            totalUnseen += _maxUnseen[i];
        }
        
        return totalUnseen;
    } 

    //
    // canIgnoreFuturePostings
    //
    // Checks to see if additional postings could possibly change the
    // top ranks; returns true if no additional postings are needed.
    //

    bool canIgnoreFuturePostings( int requested ) {
    #ifdef GALAGO_NO_IGNORE
        return false;
    #endif
        
        // if we're not in AND mode yet, any new posting could change
        // the top of the ranked list
        if( useAndMode() == false )
            return false;

        // if we haven't trimmed the accumulators down very much,
        // it's probably not time to try this yet.
        if( _accumulators.size() > 3*requested )
            return false;
        
        // if we already determined that we can, there's no use
        // checking again
        if( _canIgnorePostings )
            return true;
            
        // decode accumulators 
        std::vector<_AccumulatorType> partials;
        _AccumulatorType::computeUnseenScoreArray( _fullUnseen, _maxUnseen );
        
        for( int i=0; i < _accumulators.size(); i++ ) {
            const _AccumulatorType& accumulator = _accumulators[i];
            UINT32 maxValue = accumulator.score() + accumulator.unseen( _fullUnseen );
            
            if ( maxValue < _threshold )
                continue;

            partials.push_back( accumulator );
        }
        
        if( partials.size() == 0 )
            return false;
        
        std::sort( partials.begin(), partials.end() );
        
        for( int i=0; i<partials.size()-1; i++ ) {
            const _AccumulatorType& one = partials[i];
            const _AccumulatorType& two = partials[i+1];
            
            UINT32 oneLimit = one.score() + one.unseen( _fullUnseen );
            
            // we already know that one.score < two.score, so
            // if oneLimit > two.score, one might surpass two
            // with additional postings
            if ( oneLimit > two.score() )
                return false;
            
            // if the two scores are different, but additional
            // information might make them the same, we need to
            // get additional information
            if ( one.score() < two.score() && oneLimit >= two.score() )
                return false;
        }
        
        _canIgnorePostings = true;
        return true;
    }                 

    //
    // topResults
    //

    std::vector<indri::api::ScoredExtentResult> topResults( int requested ) {
        // find the top accumulators in the list
        std::priority_queue<indri::api::ScoredExtentResult, std::vector<indri::api::ScoredExtentResult>, indri::api::ScoredExtentResult::score_greater> scores;
        int i;
        
        for( i = 0; i < std::min<size_t>( requested, _accumulators.size() ); i++ ) {
            int document = _accumulators[i].document();
            int score = _accumulators[i].score();
            
            scores.push( indri::api::ScoredExtentResult( score, document, 0, 0 ) );
        }       
        
        UINT32 lowScore = (UINT32) scores.top().score;
        
        for( ; i < _accumulators.size(); i++ ) {
            int document = _accumulators[i].document();
            int score = _accumulators[i].score();
            
            if( lowScore < score ) {
                scores.push( indri::api::ScoredExtentResult( score, document, 0, 0 ) );
                scores.pop();
                lowScore = (UINT32) scores.top().score;
            }
        }                               
        
        std::vector<indri::api::ScoredExtentResult> results;
        results.resize( scores.size() );
        
        for( i=scores.size()-1; i>=0; i-- ) {
            results[i] = scores.top();
            scores.pop();
        }
        
        return results;
    }  
    
    //
    // maxTerms
    //
    
    int maxTerms() const {
        return _AccumulatorType::maxTerms();
    }
};

#endif // GALAGO_ARRAYACCUMULATORS_HPP