xapian-core/weight/dphweight.cc

   1 /** @file
   2  * @brief Xapian::DPHWeight class - The DPH weighting scheme of the DFR framework.
   3  */
   4 /* Copyright (C) 2013, 2014 Aarsh Shah
   5  * Copyright (C) 2016,2017 Olly Betts
   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 "xapian/error.h"
  27 #include "common/log2.h"
  28 #include <algorithm>
  29 #include <cmath>
  30
  31 using namespace std;
  32
  33 namespace Xapian {
  34
  35 DPHWeight *
  36 DPHWeight::clone() const
  37 {
  38     return new DPHWeight();
  39 }
  40
  41 void
  42 DPHWeight::init(double factor)
  43 {
  44     // Avoid warnings about unused private member.
  45     (void)lower_bound;
  46
  47     if (factor == 0.0) {
  48         // This object is for the term-independent contribution, and that's
  49         // always zero for this scheme.
  50         return;
  51     }
  52
  53     double F = get_collection_freq();
  54     double wdf_lower = 1.0;
  55     double wdf_upper = get_wdf_upper_bound();
  56
  57     double len_upper = get_doclength_upper_bound();
  58
  59     if (wdf_upper == 0) {
  60         upper_bound = 0.0;
  61         return;
  62     }
  63
  64     double min_wdf_to_len = wdf_lower / len_upper;
  65
  66     /* Calculate constant value to be used in get_sumpart(). */
  67     log_constant = get_total_length() / F;
  68     wqf_product_factor = get_wqf() * factor;
  69
  70     // Calculate the upper bound on the weight.
  71
  72     /* Calculations to decide the values to be used for calculating upper bound. */
  73     /* The upper bound of the term appearing in the second log is obtained
  74        by taking the minimum and maximum wdf value in the formula as shown. */
  75     double max_product_1 = wdf_upper * (1.0 - min_wdf_to_len);
  76     /* A second upper bound of the term can be obtained by plugging in the
  77        upper bound of the length and differentiating the term w.r.t wdf
  78        to find the value of wdf at which function attains maximum value. */
  79     double wdf_var = min(wdf_upper, len_upper / 2.0);
  80     double max_product_2 = wdf_var * (1.0 - wdf_var / len_upper);
  81     /* Take the minimum of the two upper bounds. */
  82     double max_product = min(max_product_1, max_product_2);
  83
  84     // Maximization of the product of wdf and normalized wdf.
  85     /* The expression is (wdf * (1.0 - wdf / len) * (1.0 - wdf / len)) /
  86                          (wdf + 1.0). */
  87     /* Now, assuming len to be len_upper for the purpose of maximization,
  88        (d)/(dx) (x * (1 - x / c) * (1 - x / c)) / (x+1) =
  89        ((c - x) * (c - x * (2 * x + 3))) / (c² * (x + 1)²)
  90        Thus, if (c - x * (2 * x + 3)) is positive, the differentiation
  91        value will be positive and hence the function will be an
  92        increasing function. By finding the positive root of the equation
  93        2 * x² + 3 * x - c = 0, we get the value of x(wdf)
  94        at which the differentiation value turns to negative from positive,
  95        and hence, the function will have maximum value for that value of wdf. */
  96     double wdf_root = 0.25 * (sqrt(8.0 * len_upper + 9.0) - 3.0);
  97
  98     // If wdf_root outside valid range, use nearest value in range.
  99     if (wdf_root > wdf_upper) {
 100         wdf_root = wdf_upper;
 101     } else if (wdf_root < wdf_lower) {
 102         wdf_root = wdf_lower;
 103     }
 104
 105     double max_wdf_product_normalization = wdf_root / (wdf_root + 1) *
 106         pow((1 - wdf_root / len_upper), 2.0);
 107
 108     double max_weight = max_wdf_product_normalization *
 109         (log2(log_constant) + (0.5 * log2(2 * M_PI * max_product)));
 110
 111     upper_bound = wqf_product_factor * max_weight;
 112     if (rare(upper_bound < 0.0)) upper_bound = 0.0;
 113 }
 114
 115 string
 116 DPHWeight::name() const
 117 {
 118     return "Xapian::DPHWeight";
 119 }
 120
 121 string
 122 DPHWeight::serialise() const
 123 {
 124     return string();
 125 }
 126
 127 DPHWeight *
 128 DPHWeight::unserialise(const string& s) const
 129 {
 130     if (rare(!s.empty()))
 131         throw Xapian::SerialisationError("Extra data in DPHWeight::unserialise()");
 132     return new DPHWeight();
 133 }
 134
 135 double
 136 DPHWeight::get_sumpart(Xapian::termcount wdf, Xapian::termcount len,
 137                        Xapian::termcount) const
 138 {
 139     if (wdf == 0 || wdf == len) return 0.0;
 140
 141     double wdf_to_len = double(wdf) / len;
 142
 143     double normalization = pow((1 - wdf_to_len), 2) / (wdf + 1);
 144
 145     double wt = normalization *
 146         (wdf * log2(wdf_to_len * log_constant) +
 147          (0.5 * log2(2 * M_PI * wdf * (1 - wdf_to_len))));
 148     if (rare(wt <= 0.0)) return 0.0;
 149
 150     return wqf_product_factor * wt;
 151 }
 152
 153 double
 154 DPHWeight::get_maxpart() const
 155 {
 156     return upper_bound;
 157 }
 158
 159 double
 160 DPHWeight::get_sumextra(Xapian::termcount, Xapian::termcount) const
 161 {
 162     return 0;
 163 }
 164
 165 double
 166 DPHWeight::get_maxextra() const
 167 {
 168     return 0;
 169 }
 170
 171 }