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