xapian-core/weight/dphweight.cc

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