nearpostlist.cc

Go to the documentation of this file.

 
/* Copyright (C) 2006,2007,2009,2010,2011,2014,2015,2017,2018 Olly Betts
 * Copyright (C) 2007 Lemur Consulting Ltd
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see
 * <https://www.gnu.org/licenses/>.
 */
 
#include <config.h>
 
#include "nearpostlist.h"
 
#include "debuglog.h"
#include "backends/positionlist.h"
#include "heap.h"
#include "omassert.h"
#include "str.h"
 
#include <algorithm>
#include <vector>
 
using namespace std;
 
NearPostList::NearPostList(PostList *source_,
                           EstimateOp* estimate_op_,
                           Xapian::termpos window_,
                           const vector<PostList*>::const_iterator &terms_begin,
                           const vector<PostList*>::const_iterator &terms_end,
                           PostListTree* pltree_)
    : SelectPostList(source_, estimate_op_, pltree_),
      window(window_),
      terms(terms_begin, terms_end)
{
    size_t n = terms.size();
    Assert(n > 1);
    poslists = new PositionList*[n];
 
    // It's hard to estimate how many times the postlist will match as it
    // depends a lot on the terms and window, but usually it will occur
    // significantly less often than the individual terms.
    termfreq = pl->get_termfreq() / 2;
}
 
NearPostList::~NearPostList()
{
    delete [] poslists;
}
 
struct TermCmp {
    bool operator()(const PostList * a, const PostList * b) const {
        return a->get_wdf() < b->get_wdf();
    }
};
 
struct Cmp {
    bool operator()(const PositionList * a, const PositionList * b) const {
        return a->get_position() > b->get_position();
    }
};
 
bool
NearPostList::test_doc()
{
    LOGCALL(MATCH, bool, "NearPostList::test_doc", NO_ARGS);
 
    // Sort to put least frequent terms first, to try to minimise the number of
    // position lists we need to read if there are no matches.
    //
    // We use wdf as a proxy for the length of the position lists, since we'd
    // need to read each position list to find its length and we're trying to
    // avoid having to read them all if we can.
    sort(terms.begin(), terms.end(), TermCmp());
 
    poslists[0] = terms[0]->read_position_list();
    if (!poslists[0]->next()) {
        ++rejected;
        RETURN(false);
    }
 
    Xapian::termpos last = poslists[0]->get_position();
    PositionList ** end = poslists + 1;
 
    while (true) {
        if (last - poslists[0]->get_position() < window) {
            if (size_t(end - poslists) != terms.size()) {
                // We haven't started all the position lists yet, so start the
                // next one.
                PositionList * posl =
                    terms[end - poslists]->read_position_list();
                if (last < window) {
                    if (!posl->next())
                        goto reject;
                } else {
                    if (!posl->skip_to(last - window + 1))
                        goto reject;
                }
                Xapian::termpos pos = posl->get_position();
                if (pos > last) last = pos;
                *end++ = posl;
                Heap::push(poslists, end, Cmp());
                continue;
            }
 
            // We have all the terms within the specified window, but some may
            // be at the same position (in particular if the same term is
            // listed twice).  So we work through the terms in ascending
            // position order, and each time we find one with a duplicate
            // position, we advance it - if that pushes us out of the window,
            // we return to the outer loop, otherwise we reinsert it into the
            // heap at its new position and continue to look for duplicates
            // we need to adjust.
            Xapian::termpos pos = poslists[0]->get_position();
            Heap::pop(poslists, end, Cmp());
            PositionList ** i = end - 1;
            while (true) {
                if (poslists[0]->get_position() == pos) {
                    if (!poslists[0]->next())
                        goto reject;
                    Xapian::termpos newpos = poslists[0]->get_position();
                    if (newpos - end[-1]->get_position() >= window) {
                        // No longer fits in the window.
                        last = newpos;
                        break;
                    }
                    Heap::replace(poslists, i, Cmp());
                    continue;
                }
                pos = poslists[0]->get_position();
                Heap::pop(poslists, i, Cmp());
                if (--i == poslists) {
                    Assert(pos - end[-1]->get_position() < window);
                    ++accepted;
                    RETURN(true);
                }
            }
 
            Heap::make(poslists, end, Cmp());
            continue;
        }
        if (!poslists[0]->skip_to(last - window + 1))
            break;
        last = max(last, poslists[0]->get_position());
        Heap::replace(poslists, end, Cmp());
    }
reject:
    ++rejected;
    RETURN(false);
}
 
Xapian::termcount
NearPostList::get_wdf() const
{
    // Calculate an estimate for the wdf of a near postlist.
    //
    // The natural definition of the wdf for a near postlist is the number of
    // times the terms occur in a group within the windowsize in the document -
    // in other words, the number of times a routine like do_test() could find
    // a match, if it kept going after finding the first one.  However,
    // calculating this would be expensive (in CPU time at least - the position
    // lists are probably already read from disk), and the benefit is dubious
    // (given that the estimate here is probably only going to be used for
    // calculating the weight for synonym postlists, and it's not clear that
    // the above definition is exactly appropriate in this situation, anyway).
    //
    // Instead, we could do an estimate of this value, based on the lengths
    // of the position lists.  Rather than having to open the position lists,
    // we could use the wdfs, which will be the same value unless the wdfs have
    // been artificially inflated - in which case we probably want to use the
    // inflated value anyway (it will have been inflated to represent the fact
    // that this term is more important than others, so we should make use of
    // this hint).
    //
    // A reasonable way to calculate an estimate would be to consider the
    // document to be split into W (overlapping) windows, each 1 term apart,
    // and of the same length as the windowsize used for the phrase.  Then,
    // calculate the probability that each term is found in this window (as
    // Prob = wdf / doclen), multiply these probabilities to get the
    // probability that they're all found in the window, and then multiply by
    // the windowsize again to get an estimate.
    //
    // However, this requires the doclen, which won't always be available (ie,
    // if the weighting scheme doesn't use it, we won't have read it from
    // disk).
    //
    // Rather than force an access to disk to get the doclen, we use an even
    // rougher estimate: the minimum wdf in the sub-lists.  This is actually
    // the upper bound for the wdf (since the phrase can only occur the same
    // number of times as the least frequent of its constituent terms).
    //
    // If this estimate proves to give bad results, we can revisit this and try
    // a better approximation.
    vector<PostList *>::const_iterator i = terms.begin();
    Xapian::termcount wdf = (*i)->get_wdf();
    while (++i != terms.end()) {
        wdf = min(wdf, (*i)->get_wdf());
    }
    return wdf;
}
 
string
NearPostList::get_description() const
{
    string m = "(Near ";
    m += str(window);
    m += ' ';
    m += pl->get_description();
    m += ")";
    return m;
}