xapian-core  1.4.20
bm25plusweight.cc
Go to the documentation of this file.
1 
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
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 
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 }
The Xapian namespace contains public interfaces for the Xapian library.
Definition: compactor.cc:80
#define RETURN(A)
Definition: debuglog.h:482
#define AssertRel(A, REL, B)
Definition: omassert.h:123
STL namespace.
#define rare(COND)
Definition: config.h:562
Hierarchy of classes which Xapian can throw as exceptions.
unsigned XAPIAN_TERMCOUNT_BASE_TYPE termcount
A counts of terms.
Definition: types.h:72
functions to serialise and unserialise a double
double unserialise_double(const char **p, const char *end)
Unserialise a double serialised by serialise_double.
Indicates an error in the std::string serialisation of an object.
Definition: error.h:929
#define LOGVALUE(a, b)
Definition: debuglog.h:484
double doclength
A normalised document length.
Definition: types.h:59
Weighting scheme API.
std::string serialise_double(double v)
Serialise a double to a string.
char name[9]
Definition: dbcheck.cc:55
unsigned XAPIAN_DOCID_BASE_TYPE doccount
A count of documents.
Definition: types.h:38
Various assertion macros.
Xapian::Weight subclass implementing the BM25+ probabilistic formula.
Definition: weight.h:639
Debug logging macros.
#define LOGCALL(CATEGORY, TYPE, FUNC, PARAMS)
Definition: debuglog.h:476