xapian-core/weight/bm25plusweight.cc

   1 /** @file
   2  * @brief Xapian::BM25PlusWeight class - the BM25+ probabilistic formula
   3  */
   4 /* Copyright (C) 2009,2010,2011,2012,2014,2015,2016 Olly Betts
   5  * Copyright (C) 2016  Vivek Pal
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License as
   9  * published by the Free Software Foundation; either version 2 of the
  10  * License, or (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 #include <config.h>
  23
  24 #include "xapian/weight.h"
  25
  26 #include "debuglog.h"
  27 #include "omassert.h"
  28 #include "serialise-double.h"
  29
  30 #include "xapian/error.h"
  31
  32 #include <algorithm>
  33 #include <cmath>
  34
  35 using namespace std;
  36
  37 namespace Xapian {
  38
  39 BM25PlusWeight *
  40 BM25PlusWeight::clone() const
  41 {
  42     return new BM25PlusWeight(param_k1, param_k2, param_k3, param_b,
  43                               param_min_normlen, param_delta);
  44 }
  45
  46 void
  47 BM25PlusWeight::init(double factor)
  48 {
  49     Xapian::doccount tf = get_termfreq();
  50
  51     if (rare(tf == 0)) {
  52         termweight = 0;
  53     } else {
  54         // BM25+ formula uses IDF = log((total_no_of_docs + 1) / tf)
  55         termweight = log(double(get_collection_size() + 1) / tf);
  56         termweight *= factor;
  57         if (param_k3 != 0) {
  58             double wqf_double = get_wqf();
  59             termweight *= (param_k3 + 1) * wqf_double / (param_k3 + wqf_double);
  60         }
  61     }
  62
  63     LOGVALUE(WTCALC, termweight);
  64
  65     if (param_k2 == 0 && (param_b == 0 || param_k1 == 0)) {
  66         // If k2 is 0, and either param_b or param_k1 is 0 then the document
  67         // length doesn't affect the weight.
  68         len_factor = 0;
  69     } else {
  70         len_factor = get_average_length();
  71         // len_factor can be zero if all documents are empty (or the database
  72         // is empty!)
  73         if (len_factor != 0) len_factor = 1 / len_factor;
  74     }
  75
  76     LOGVALUE(WTCALC, len_factor);
  77 }
  78
  79 string
  80 BM25PlusWeight::name() const
  81 {
  82     return "Xapian::BM25PlusWeight";
  83 }
  84
  85 string
  86 BM25PlusWeight::serialise() const
  87 {
  88     string result = serialise_double(param_k1);
  89     result += serialise_double(param_k2);
  90     result += serialise_double(param_k3);
  91     result += serialise_double(param_b);
  92     result += serialise_double(param_min_normlen);
  93     result += serialise_double(param_delta);
  94     return result;
  95 }
  96
  97 BM25PlusWeight *
  98 BM25PlusWeight::unserialise(const string & s) const
  99 {
 100     const char *ptr = s.data();
 101     const char *end = ptr + s.size();
 102     double k1 = unserialise_double(&ptr, end);
 103     double k2 = unserialise_double(&ptr, end);
 104     double k3 = unserialise_double(&ptr, end);
 105     double b = unserialise_double(&ptr, end);
 106     double min_normlen = unserialise_double(&ptr, end);
 107     double delta = unserialise_double(&ptr, end);
 108     if (rare(ptr != end))
 109         throw Xapian::SerialisationError("Extra data in BM25PlusWeight::unserialise()");
 110     return new BM25PlusWeight(k1, k2, k3, b, min_normlen, delta);
 111 }
 112
 113 double
 114 BM25PlusWeight::get_sumpart(Xapian::termcount wdf, Xapian::termcount len,
 115                             Xapian::termcount) const
 116 {
 117     LOGCALL(WTCALC, double, "BM25PlusWeight::get_sumpart", wdf | len);
 118     Xapian::doclength normlen = max(len * len_factor, param_min_normlen);
 119
 120     double wdf_double = wdf;
 121     double denom = param_k1 * (normlen * param_b + (1 - param_b)) + wdf_double;
 122     AssertRel(denom,>,0);
 123     // Parameter delta (δ) is a pseudo tf value to control the scale of the
 124     // tf lower bound. δ can be tuned for e.g from 0.0 to 1.5 but BM25+ can
 125     // still work effectively across collections with a fixed δ = 1.0
 126     RETURN(termweight * ((param_k1 + 1) * wdf_double / denom + param_delta));
 127 }
 128
 129 double
 130 BM25PlusWeight::get_maxpart() const
 131 {
 132     LOGCALL(WTCALC, double, "BM25PlusWeight::get_maxpart", NO_ARGS);
 133     double denom = param_k1;
 134     Xapian::termcount wdf_max = get_wdf_upper_bound();
 135     if (param_k1 != 0.0) {
 136         if (param_b != 0.0) {
 137             // "Upper-bound Approximations for Dynamic Pruning" Craig
 138             // Macdonald, Nicola Tonellotto and Iadh Ounis. ACM Transactions on
 139             // Information Systems. 29(4), 2011 shows that evaluating at
 140             // doclen=wdf_max is a good bound.
 141             //
 142             // However, we can do better if doclen_min > wdf_max since then a
 143             // better bound can be found by simply evaluating at
 144             // doclen=doclen_min and wdf=wdf_max.
 145             Xapian::doclength normlen_lb =
 146                  max(max(wdf_max, get_doclength_lower_bound()) * len_factor,
 147                      param_min_normlen);
 148             denom *= (normlen_lb * param_b + (1 - param_b));
 149         }
 150     }
 151     denom += wdf_max;
 152     AssertRel(denom,>,0);
 153     RETURN(termweight * ((param_k1 + 1) * wdf_max / denom + param_delta));
 154 }
 155
 156 /* The paper which describes BM25+ ignores BM25's document-independent
 157  * component (so implicitly k2=0), but we support non-zero k2 too.
 158  *
 159  * The BM25 formula gives:
 160  *
 161  * param_k2 * query_length * (1 - normlen) / (1 + normlen)
 162  *
 163  * To avoid negative sumextra we add the constant (param_k2 * query_length)
 164  * to give:
 165  *
 166  * 2 * param_k2 * query_length / (1 + normlen)
 167  */
 168 double
 169 BM25PlusWeight::get_sumextra(Xapian::termcount len, Xapian::termcount) const
 170 {
 171     LOGCALL(WTCALC, double, "BM25PlusWeight::get_sumextra", len);
 172     double num = (2.0 * param_k2 * get_query_length());
 173     RETURN(num / (1.0 + max(len * len_factor, param_min_normlen)));
 174 }
 175
 176 double
 177 BM25PlusWeight::get_maxextra() const
 178 {
 179     LOGCALL(WTCALC, double, "BM25PlusWeight::get_maxextra", NO_ARGS);
 180     if (param_k2 == 0.0)
 181         RETURN(0.0);
 182     double num = (2.0 * param_k2 * get_query_length());
 183     RETURN(num / (1.0 + max(get_doclength_lower_bound() * len_factor,
 184                             param_min_normlen)));
 185 }
 186
 187 }