Branch data Line data Source code
1 : : /** @file multixorpostlist.cc
2 : : * @brief N-way XOR postlist
3 : : */
4 : : /* Copyright (C) 2007,2009,2010 Olly Betts
5 : : * Copyright (C) 2009 Lemur Consulting Ltd
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 "multixorpostlist.h"
25 : :
26 : : #include "debuglog.h"
27 : : #include "multimatch.h"
28 : : #include "omassert.h"
29 : :
30 : : using namespace std;
31 : :
32 : 134 : MultiXorPostList::~MultiXorPostList()
33 : : {
34 [ + - ][ # # ]: 134 : if (plist) {
[ # # ]
35 [ - + ][ # # ]: 134 : for (size_t i = 0; i < n_kids; ++i) {
[ # # ]
36 [ # # ][ # # ]: 0 : delete plist[i];
[ # # ]
37 : : }
38 [ + - ][ # # ]: 134 : delete [] plist;
[ # # ]
39 : : }
40 [ + - ][ # # ]: 134 : }
[ # # ]
41 : :
42 : : Xapian::doccount
43 : 134 : MultiXorPostList::get_termfreq_min() const
44 : : {
45 : : // The number of matching documents is minimised when we have the maximum
46 : : // even overlap between the sub-postlists, but that's rather tricky to
47 : : // calculate in general, so just return 0 for now.
48 : : //
49 : : // FIXME: we can certainly work out a better bound in at least some cases
50 : : // (e.g. when tf_min(X) > sum(i!=X){ tf_max(i) } for some sub-pl X).
51 : 134 : return 0;
52 : : }
53 : :
54 : : Xapian::doccount
55 : 134 : MultiXorPostList::get_termfreq_max() const
56 : : {
57 : : // Maximum is if all sub-postlists are disjoint.
58 : 134 : Xapian::doccount result = plist[0]->get_termfreq_max();
59 : 134 : bool all_exact = (result == plist[0]->get_termfreq_min());
60 : 134 : bool overflow = false;
61 [ + + ]: 300 : for (size_t i = 1; i < n_kids; ++i) {
62 : 166 : Xapian::doccount tf_max = plist[i]->get_termfreq_max();
63 : 166 : Xapian::doccount old_result = result;
64 : 166 : result += tf_max;
65 : : // Catch overflowing the type too.
66 [ - + ]: 166 : if (result < old_result)
67 : 0 : overflow = true;
68 [ + + ]: 166 : if (all_exact)
69 : 127 : all_exact = (tf_max == plist[i]->get_termfreq_min());
70 [ + + ][ + - ]: 166 : if (!all_exact && (overflow || result >= db_size))
[ - + ]
71 : 0 : return db_size;
72 : : }
73 [ + + ][ + - ]: 134 : if (all_exact && (overflow || result > db_size)) {
[ + + ]
74 : : // If the sub-postlist tfs are all exact, then if the sum of them has
75 : : // a different odd/even-ness to db_size then max tf of the XOR can't
76 : : // achieve db_size.
77 : 32 : return db_size - ((result & 1) == (db_size & 1));
78 : : }
79 : 134 : return result;
80 : : }
81 : :
82 : : Xapian::doccount
83 : 182 : MultiXorPostList::get_termfreq_est() const
84 : : {
85 : : // We calculate the estimate assuming independence. The simplest
86 : : // way to calculate this seems to be a series of (n_kids - 1) pairwise
87 : : // calculations, which gives the same answer regardless of the order.
88 : 182 : double scale = 1.0 / db_size;
89 : 182 : double P_est = plist[0]->get_termfreq_est() * scale;
90 [ + + ]: 396 : for (size_t i = 1; i < n_kids; ++i) {
91 : 214 : double P_i = plist[i]->get_termfreq_est() * scale;
92 : 214 : P_est += P_i - 2.0 * P_est * P_i;
93 : : }
94 : 182 : return static_cast<Xapian::doccount>(P_est * db_size + 0.5);
95 : : }
96 : :
97 : : TermFreqs
98 : 32 : MultiXorPostList::get_termfreq_est_using_stats(
99 : : const Xapian::Weight::Internal & stats) const
100 : : {
101 : : LOGCALL(MATCH, TermFreqs, "MultiXorPostList::get_termfreq_est_using_stats", stats);
102 : : // We calculate the estimate assuming independence. The simplest
103 : : // way to calculate this seems to be a series of (n_kids - 1) pairwise
104 : : // calculations, which gives the same answer regardless of the order.
105 : 32 : TermFreqs freqs(plist[0]->get_termfreq_est_using_stats(stats));
106 : :
107 : : // Our caller should have ensured this.
108 : : Assert(stats.collection_size);
109 : 32 : double scale = 1.0 / stats.collection_size;
110 : 32 : double P_est = freqs.termfreq * scale;
111 : 32 : double Pr_est = freqs.reltermfreq * scale;
112 : :
113 [ + + ]: 64 : for (size_t i = 1; i < n_kids; ++i) {
114 : 32 : double P_i = freqs.termfreq * scale;
115 : 32 : P_est += P_i - 2.0 * P_est * P_i;
116 : : // If the rset is empty, Pr_est should be 0 already, so leave
117 : : // it alone.
118 [ - + ]: 32 : if (stats.rset_size != 0) {
119 : 0 : double Pr_i = freqs.reltermfreq / stats.rset_size;
120 : 0 : Pr_est += Pr_i - 2.0 * Pr_est * Pr_i;
121 : : }
122 : : }
123 : 32 : RETURN(TermFreqs(Xapian::doccount(P_est * stats.collection_size + 0.5),
124 : : Xapian::doccount(Pr_est * stats.rset_size + 0.5)));
125 : : }
126 : :
127 : : Xapian::weight
128 : 6 : MultiXorPostList::get_maxweight() const
129 : : {
130 : : LOGCALL(MATCH, Xapian::weight, "MultiXorPostList::get_maxweight", NO_ARGS);
131 : 6 : RETURN(max_total);
132 : : }
133 : :
134 : : Xapian::docid
135 : 2213 : MultiXorPostList::get_docid() const
136 : : {
137 : 2213 : return did;
138 : : }
139 : :
140 : : Xapian::termcount
141 : 624 : MultiXorPostList::get_doclength() const
142 : : {
143 : : Assert(did);
144 : 624 : Xapian::termcount doclength = 0;
145 : 624 : bool doclength_set = false;
146 [ + + ]: 1872 : for (size_t i = 0; i < n_kids; ++i) {
147 [ + + ]: 1248 : if (plist[i]->get_docid() == did) {
148 [ + - ]: 624 : if (doclength_set) {
149 : : AssertEq(doclength, plist[i]->get_doclength());
150 : : } else {
151 : 624 : doclength = plist[i]->get_doclength();
152 : 624 : doclength_set = true;
153 : : }
154 : : }
155 : : }
156 : : Assert(doclength_set);
157 : 624 : return doclength;
158 : : }
159 : :
160 : : Xapian::weight
161 : 1649 : MultiXorPostList::get_weight() const
162 : : {
163 : : Assert(did);
164 : 1649 : Xapian::weight result = 0;
165 [ + + ]: 4993 : for (size_t i = 0; i < n_kids; ++i) {
166 [ + + ]: 3344 : if (plist[i]->get_docid() == did)
167 : 1701 : result += plist[i]->get_weight();
168 : : }
169 : 1649 : return result;
170 : : }
171 : :
172 : : bool
173 : 2273 : MultiXorPostList::at_end() const
174 : : {
175 : 2273 : return (did == 0);
176 : : }
177 : :
178 : : Xapian::weight
179 : 134 : MultiXorPostList::recalc_maxweight()
180 : : {
181 : : LOGCALL(MATCH, Xapian::weight, "MultiXorPostList::recalc_maxweight", NO_ARGS);
182 : 134 : max_total = plist[0]->recalc_maxweight();
183 : 134 : double min_max = max_total;
184 [ + + ]: 300 : for (size_t i = 1; i < n_kids; ++i) {
185 : 166 : Xapian::weight new_max = plist[i]->recalc_maxweight();
186 [ + + ]: 166 : if (new_max < min_max)
187 : 54 : min_max = new_max;
188 : 166 : max_total += new_max;
189 : : }
190 [ + + ]: 134 : if ((n_kids & 1) == 0) {
191 : : // If n_kids is even, we omit the child with the smallest maxweight.
192 : 102 : max_total -= min_max;
193 : : }
194 : 134 : RETURN(max_total);
195 : : }
196 : :
197 : : PostList *
198 : 2574 : MultiXorPostList::next(Xapian::weight w_min)
199 : : {
200 : : LOGCALL(MATCH, PostList *, "MultiXorPostList::next", w_min);
201 : 2574 : Xapian::docid old_did = did;
202 : 2574 : did = 0;
203 : 2574 : size_t matching_count = 0;
204 [ + + ]: 7820 : for (size_t i = 0; i < n_kids; ++i) {
205 [ + + ][ + + ]: 5246 : if (old_did == 0 || plist[i]->get_docid() <= old_did) {
[ + + ]
206 : : // FIXME: calculate the min weight required here...
207 : 2959 : PostList * res = plist[i]->next(0);
208 [ + + ]: 2959 : if (res) {
209 [ + - ]: 16 : delete plist[i];
210 : 16 : plist[i] = res;
211 : 16 : matcher->recalc_maxweight();
212 : : }
213 : :
214 [ + + ]: 2959 : if (plist[i]->at_end()) {
215 : 166 : erase_sublist(i--);
216 : 166 : continue;
217 : : }
218 : : }
219 : :
220 : 5080 : Xapian::docid new_did = plist[i]->get_docid();
221 [ + + + + ]: 5080 : if (did == 0 || new_did < did) {
222 : 4356 : did = new_did;
223 : 4356 : matching_count = 1;
224 [ + + ]: 724 : } else if (new_did == did) {
225 : 219 : ++matching_count;
226 : : }
227 : : }
228 : :
229 [ + + ]: 2574 : if (n_kids == 1) {
230 : 134 : n_kids = 0;
231 : 134 : RETURN(plist[0]);
232 : : }
233 : :
234 : : // We've reached the end of all posting lists.
235 [ - + ]: 2440 : if (did == 0)
236 : 0 : RETURN(NULL);
237 : :
238 : : // An odd number of sub-postlists match this docid, so the XOR matches.
239 [ + + ]: 2440 : if (matching_count & 1)
240 : 2273 : RETURN(NULL);
241 : :
242 : : // An even number of sub-postlists match this docid, so advance again.
243 : 2574 : RETURN(next(w_min));
244 : : }
245 : :
246 : : PostList *
247 : 0 : MultiXorPostList::skip_to(Xapian::docid did_min, Xapian::weight w_min)
248 : : {
249 : : LOGCALL(MATCH, PostList *, "MultiXorPostList::skip_to", did_min | w_min);
250 : 0 : Xapian::docid old_did = did;
251 : 0 : did = 0;
252 : 0 : size_t matching_count = 0;
253 [ # # ]: 0 : for (size_t i = 0; i < n_kids; ++i) {
254 [ # # ][ # # ]: 0 : if (old_did == 0 || plist[i]->get_docid() < did_min) {
[ # # ]
255 : : // FIXME: calculate the min weight required here...
256 : 0 : PostList * res = plist[i]->skip_to(did_min, 0);
257 [ # # ]: 0 : if (res) {
258 [ # # ]: 0 : delete plist[i];
259 : 0 : plist[i] = res;
260 : 0 : matcher->recalc_maxweight();
261 : : }
262 : :
263 [ # # ]: 0 : if (plist[i]->at_end()) {
264 : 0 : erase_sublist(i--);
265 : 0 : continue;
266 : : }
267 : : }
268 : :
269 : 0 : Xapian::docid new_did = plist[i]->get_docid();
270 [ # # # # ]: 0 : if (did == 0 || new_did < did) {
271 : 0 : did = new_did;
272 : 0 : matching_count = 1;
273 [ # # ]: 0 : } else if (new_did == did) {
274 : 0 : ++matching_count;
275 : : }
276 : : }
277 : :
278 [ # # ]: 0 : if (n_kids == 1) {
279 : : AssertEq(matching_count, 1);
280 : 0 : n_kids = 0;
281 : 0 : RETURN(plist[0]);
282 : : }
283 : :
284 : : // We've reached the end of all posting lists.
285 [ # # ]: 0 : if (did == 0)
286 : 0 : RETURN(NULL);
287 : :
288 : : // An odd number of sub-postlists match this docid, so the XOR matches.
289 [ # # ]: 0 : if (matching_count & 1)
290 : 0 : RETURN(NULL);
291 : :
292 : : // An even number of sub-postlists match this docid, so call next.
293 : 0 : RETURN(next(w_min));
294 : : }
295 : :
296 : : string
297 : 0 : MultiXorPostList::get_description() const
298 : : {
299 : 0 : string desc("(");
300 : 0 : desc += plist[0]->get_description();
301 [ # # ]: 0 : for (size_t i = 1; i < n_kids; ++i) {
302 : 0 : desc += " XOR ";
303 : 0 : desc += plist[i]->get_description();
304 : : }
305 : 0 : desc += ')';
306 : 0 : return desc;
307 : : }
308 : :
309 : : Xapian::termcount
310 : 624 : MultiXorPostList::get_wdf() const
311 : : {
312 : 624 : Xapian::termcount totwdf = 0;
313 [ + + ]: 1872 : for (size_t i = 0; i < n_kids; ++i) {
314 [ + + ]: 1248 : if (plist[i]->get_docid() == did)
315 : 624 : totwdf += plist[i]->get_wdf();
316 : : }
317 : 624 : return totwdf;
318 : : }
319 : :
320 : : Xapian::termcount
321 : 168 : MultiXorPostList::count_matching_subqs() const
322 : : {
323 : 168 : Xapian::termcount total = 0;
324 [ + + ]: 527 : for (size_t i = 0; i < n_kids; ++i) {
325 [ + + ]: 359 : if (plist[i]->get_docid() == did)
326 : 194 : total += plist[i]->count_matching_subqs();
327 : : }
328 : 168 : return total;
329 : : }
|
