1 package org.apache.lucene.search;
2
3 /**
4 * Licensed to the Apache Software Foundation (ASF) under one or more
5 * contributor license agreements. See the NOTICE file distributed with
6 * this work for additional information regarding copyright ownership.
7 * The ASF licenses this file to You under the Apache License, Version 2.0
8 * (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20
21 import org.apache.lucene.index.FieldInvertState;
22 import org.apache.lucene.index.Term;
23 import org.apache.lucene.search.Explanation.IDFExplanation;
24 import org.apache.lucene.util.SmallFloat;
25
26 import java.io.IOException;
27 import java.io.Serializable;
28 import java.util.Collection;
29 import java.util.IdentityHashMap;
30
31
32 /**
33 * Expert: Scoring API.
34 *
35 * <p>Similarity defines the components of Lucene scoring.
36 * Overriding computation of these components is a convenient
37 * way to alter Lucene scoring.
38 *
39 * <p>Suggested reading:
40 * <a href="http://nlp.stanford.edu/IR-book/html/htmledition/queries-as-vectors-1.html">
41 * Introduction To Information Retrieval, Chapter 6</a>.
42 *
43 * <p>The following describes how Lucene scoring evolves from
44 * underlying information retrieval models to (efficient) implementation.
45 * We first brief on <i>VSM Score</i>,
46 * then derive from it <i>Lucene's Conceptual Scoring Formula</i>,
47 * from which, finally, evolves <i>Lucene's Practical Scoring Function</i>
48 * (the latter is connected directly with Lucene classes and methods).
49 *
50 * <p>Lucene combines
51 * <a href="http://en.wikipedia.org/wiki/Standard_Boolean_model">
52 * Boolean model (BM) of Information Retrieval</a>
53 * with
54 * <a href="http://en.wikipedia.org/wiki/Vector_Space_Model">
55 * Vector Space Model (VSM) of Information Retrieval</a> -
56 * documents "approved" by BM are scored by VSM.
57 *
58 * <p>In VSM, documents and queries are represented as
59 * weighted vectors in a multi-dimensional space,
60 * where each distinct index term is a dimension,
61 * and weights are
62 * <a href="http://en.wikipedia.org/wiki/Tfidf">Tf-idf</a> values.
63 *
64 * <p>VSM does not require weights to be <i>Tf-idf</i> values,
65 * but <i>Tf-idf</i> values are believed to produce search results of high quality,
66 * and so Lucene is using <i>Tf-idf</i>.
67 * <i>Tf</i> and <i>Idf</i> are described in more detail below,
68 * but for now, for completion, let's just say that
69 * for given term <i>t</i> and document (or query) <i>x</i>,
70 * <i>Tf(t,x)</i> varies with the number of occurrences of term <i>t</i> in <i>x</i>
71 * (when one increases so does the other) and
72 * <i>idf(t)</i> similarly varies with the inverse of the
73 * number of index documents containing term <i>t</i>.
74 *
75 * <p><i>VSM score</i> of document <i>d</i> for query <i>q</i> is the
76 * <a href="http://en.wikipedia.org/wiki/Cosine_similarity">
77 * Cosine Similarity</a>
78 * of the weighted query vectors <i>V(q)</i> and <i>V(d)</i>:
79 *
80 * <br> <br>
81 * <table cellpadding="2" cellspacing="2" border="0" align="center">
82 * <tr><td>
83 * <table cellpadding="1" cellspacing="0" border="1" align="center">
84 * <tr><td>
85 * <table cellpadding="2" cellspacing="2" border="0" align="center">
86 * <tr>
87 * <td valign="middle" align="right" rowspan="1">
88 * cosine-similarity(q,d) =
89 * </td>
90 * <td valign="middle" align="center">
91 * <table>
92 * <tr><td align="center"><small>V(q) · V(d)</small></td></tr>
93 * <tr><td align="center">–––––––––</td></tr>
94 * <tr><td align="center"><small>|V(q)| |V(d)|</small></td></tr>
95 * </table>
96 * </td>
97 * </tr>
98 * </table>
99 * </td></tr>
100 * </table>
101 * </td></tr>
102 * <tr><td>
103 * <center><font=-1><u>VSM Score</u></font></center>
104 * </td></tr>
105 * </table>
106 * <br> <br>
107 *
108 *
109 * Where <i>V(q)</i> · <i>V(d)</i> is the
110 * <a href="http://en.wikipedia.org/wiki/Dot_product">dot product</a>
111 * of the weighted vectors,
112 * and <i>|V(q)|</i> and <i>|V(d)|</i> are their
113 * <a href="http://en.wikipedia.org/wiki/Euclidean_norm#Euclidean_norm">Euclidean norms</a>.
114 *
115 * <p>Note: the above equation can be viewed as the dot product of
116 * the normalized weighted vectors, in the sense that dividing
117 * <i>V(q)</i> by its euclidean norm is normalizing it to a unit vector.
118 *
119 * <p>Lucene refines <i>VSM score</i> for both search quality and usability:
120 * <ul>
121 * <li>Normalizing <i>V(d)</i> to the unit vector is known to be problematic in that
122 * it removes all document length information.
123 * For some documents removing this info is probably ok,
124 * e.g. a document made by duplicating a certain paragraph <i>10</i> times,
125 * especially if that paragraph is made of distinct terms.
126 * But for a document which contains no duplicated paragraphs,
127 * this might be wrong.
128 * To avoid this problem, a different document length normalization
129 * factor is used, which normalizes to a vector equal to or larger
130 * than the unit vector: <i>doc-len-norm(d)</i>.
131 * </li>
132 *
133 * <li>At indexing, users can specify that certain documents are more
134 * important than others, by assigning a document boost.
135 * For this, the score of each document is also multiplied by its boost value
136 * <i>doc-boost(d)</i>.
137 * </li>
138 *
139 * <li>Lucene is field based, hence each query term applies to a single
140 * field, document length normalization is by the length of the certain field,
141 * and in addition to document boost there are also document fields boosts.
142 * </li>
143 *
144 * <li>The same field can be added to a document during indexing several times,
145 * and so the boost of that field is the multiplication of the boosts of
146 * the separate additions (or parts) of that field within the document.
147 * </li>
148 *
149 * <li>At search time users can specify boosts to each query, sub-query, and
150 * each query term, hence the contribution of a query term to the score of
151 * a document is multiplied by the boost of that query term <i>query-boost(q)</i>.
152 * </li>
153 *
154 * <li>A document may match a multi term query without containing all
155 * the terms of that query (this is correct for some of the queries),
156 * and users can further reward documents matching more query terms
157 * through a coordination factor, which is usually larger when
158 * more terms are matched: <i>coord-factor(q,d)</i>.
159 * </li>
160 * </ul>
161 *
162 * <p>Under the simplifying assumption of a single field in the index,
163 * we get <i>Lucene's Conceptual scoring formula</i>:
164 *
165 * <br> <br>
166 * <table cellpadding="2" cellspacing="2" border="0" align="center">
167 * <tr><td>
168 * <table cellpadding="1" cellspacing="0" border="1" align="center">
169 * <tr><td>
170 * <table cellpadding="2" cellspacing="2" border="0" align="center">
171 * <tr>
172 * <td valign="middle" align="right" rowspan="1">
173 * score(q,d) =
174 * <font color="#FF9933">coord-factor(q,d)</font> ·
175 * <font color="#CCCC00">query-boost(q)</font> ·
176 * </td>
177 * <td valign="middle" align="center">
178 * <table>
179 * <tr><td align="center"><small><font color="#993399">V(q) · V(d)</font></small></td></tr>
180 * <tr><td align="center">–––––––––</td></tr>
181 * <tr><td align="center"><small><font color="#FF33CC">|V(q)|</font></small></td></tr>
182 * </table>
183 * </td>
184 * <td valign="middle" align="right" rowspan="1">
185 * · <font color="#3399FF">doc-len-norm(d)</font>
186 * · <font color="#3399FF">doc-boost(d)</font>
187 * </td>
188 * </tr>
189 * </table>
190 * </td></tr>
191 * </table>
192 * </td></tr>
193 * <tr><td>
194 * <center><font=-1><u>Lucene Conceptual Scoring Formula</u></font></center>
195 * </td></tr>
196 * </table>
197 * <br> <br>
198 *
199 * <p>The conceptual formula is a simplification in the sense that (1) terms and documents
200 * are fielded and (2) boosts are usually per query term rather than per query.
201 *
202 * <p>We now describe how Lucene implements this conceptual scoring formula, and
203 * derive from it <i>Lucene's Practical Scoring Function</i>.
204 *
205 * <p>For efficient score computation some scoring components
206 * are computed and aggregated in advance:
207 *
208 * <ul>
209 * <li><i>Query-boost</i> for the query (actually for each query term)
210 * is known when search starts.
211 * </li>
212 *
213 * <li>Query Euclidean norm <i>|V(q)|</i> can be computed when search starts,
214 * as it is independent of the document being scored.
215 * From search optimization perspective, it is a valid question
216 * why bother to normalize the query at all, because all
217 * scored documents will be multiplied by the same <i>|V(q)|</i>,
218 * and hence documents ranks (their order by score) will not
219 * be affected by this normalization.
220 * There are two good reasons to keep this normalization:
221 * <ul>
222 * <li>Recall that
223 * <a href="http://en.wikipedia.org/wiki/Cosine_similarity">
224 * Cosine Similarity</a> can be used find how similar
225 * two documents are. One can use Lucene for e.g.
226 * clustering, and use a document as a query to compute
227 * its similarity to other documents.
228 * In this use case it is important that the score of document <i>d3</i>
229 * for query <i>d1</i> is comparable to the score of document <i>d3</i>
230 * for query <i>d2</i>. In other words, scores of a document for two
231 * distinct queries should be comparable.
232 * There are other applications that may require this.
233 * And this is exactly what normalizing the query vector <i>V(q)</i>
234 * provides: comparability (to a certain extent) of two or more queries.
235 * </li>
236 *
237 * <li>Applying query normalization on the scores helps to keep the
238 * scores around the unit vector, hence preventing loss of score data
239 * because of floating point precision limitations.
240 * </li>
241 * </ul>
242 * </li>
243 *
244 * <li>Document length norm <i>doc-len-norm(d)</i> and document
245 * boost <i>doc-boost(d)</i> are known at indexing time.
246 * They are computed in advance and their multiplication
247 * is saved as a single value in the index: <i>norm(d)</i>.
248 * (In the equations below, <i>norm(t in d)</i> means <i>norm(field(t) in doc d)</i>
249 * where <i>field(t)</i> is the field associated with term <i>t</i>.)
250 * </li>
251 * </ul>
252 *
253 * <p><i>Lucene's Practical Scoring Function</i> is derived from the above.
254 * The color codes demonstrate how it relates
255 * to those of the <i>conceptual</i> formula:
256 *
257 * <P>
258 * <table cellpadding="2" cellspacing="2" border="0" align="center">
259 * <tr><td>
260 * <table cellpadding="" cellspacing="2" border="2" align="center">
261 * <tr><td>
262 * <table cellpadding="2" cellspacing="2" border="0" align="center">
263 * <tr>
264 * <td valign="middle" align="right" rowspan="1">
265 * score(q,d) =
266 * <A HREF="#formula_coord"><font color="#FF9933">coord(q,d)</font></A> ·
267 * <A HREF="#formula_queryNorm"><font color="#FF33CC">queryNorm(q)</font></A> ·
268 * </td>
269 * <td valign="bottom" align="center" rowspan="1">
270 * <big><big><big>∑</big></big></big>
271 * </td>
272 * <td valign="middle" align="right" rowspan="1">
273 * <big><big>(</big></big>
274 * <A HREF="#formula_tf"><font color="#993399">tf(t in d)</font></A> ·
275 * <A HREF="#formula_idf"><font color="#993399">idf(t)</font></A><sup>2</sup> ·
276 * <A HREF="#formula_termBoost"><font color="#CCCC00">t.getBoost()</font></A> ·
277 * <A HREF="#formula_norm"><font color="#3399FF">norm(t,d)</font></A>
278 * <big><big>)</big></big>
279 * </td>
280 * </tr>
281 * <tr valigh="top">
282 * <td></td>
283 * <td align="center"><small>t in q</small></td>
284 * <td></td>
285 * </tr>
286 * </table>
287 * </td></tr>
288 * </table>
289 * </td></tr>
290 * <tr><td>
291 * <center><font=-1><u>Lucene Practical Scoring Function</u></font></center>
292 * </td></tr>
293 * </table>
294 *
295 * <p> where
296 * <ol>
297 * <li>
298 * <A NAME="formula_tf"></A>
299 * <b><i>tf(t in d)</i></b>
300 * correlates to the term's <i>frequency</i>,
301 * defined as the number of times term <i>t</i> appears in the currently scored document <i>d</i>.
302 * Documents that have more occurrences of a given term receive a higher score.
303 * Note that <i>tf(t in q)</i> is assumed to be <i>1</i> and therefore it does not appear in this equation,
304 * However if a query contains twice the same term, there will be
305 * two term-queries with that same term and hence the computation would still be correct (although
306 * not very efficient).
307 * The default computation for <i>tf(t in d)</i> in
308 * {@link org.apache.lucene.search.DefaultSimilarity#tf(float) DefaultSimilarity} is:
309 *
310 * <br> <br>
311 * <table cellpadding="2" cellspacing="2" border="0" align="center">
312 * <tr>
313 * <td valign="middle" align="right" rowspan="1">
314 * {@link org.apache.lucene.search.DefaultSimilarity#tf(float) tf(t in d)} =
315 * </td>
316 * <td valign="top" align="center" rowspan="1">
317 * frequency<sup><big>½</big></sup>
318 * </td>
319 * </tr>
320 * </table>
321 * <br> <br>
322 * </li>
323 *
324 * <li>
325 * <A NAME="formula_idf"></A>
326 * <b><i>idf(t)</i></b> stands for Inverse Document Frequency. This value
327 * correlates to the inverse of <i>docFreq</i>
328 * (the number of documents in which the term <i>t</i> appears).
329 * This means rarer terms give higher contribution to the total score.
330 * <i>idf(t)</i> appears for <i>t</i> in both the query and the document,
331 * hence it is squared in the equation.
332 * The default computation for <i>idf(t)</i> in
333 * {@link org.apache.lucene.search.DefaultSimilarity#idf(int, int) DefaultSimilarity} is:
334 *
335 * <br> <br>
336 * <table cellpadding="2" cellspacing="2" border="0" align="center">
337 * <tr>
338 * <td valign="middle" align="right">
339 * {@link org.apache.lucene.search.DefaultSimilarity#idf(int, int) idf(t)} =
340 * </td>
341 * <td valign="middle" align="center">
342 * 1 + log <big>(</big>
343 * </td>
344 * <td valign="middle" align="center">
345 * <table>
346 * <tr><td align="center"><small>numDocs</small></td></tr>
347 * <tr><td align="center">–––––––––</td></tr>
348 * <tr><td align="center"><small>docFreq+1</small></td></tr>
349 * </table>
350 * </td>
351 * <td valign="middle" align="center">
352 * <big>)</big>
353 * </td>
354 * </tr>
355 * </table>
356 * <br> <br>
357 * </li>
358 *
359 * <li>
360 * <A NAME="formula_coord"></A>
361 * <b><i>coord(q,d)</i></b>
362 * is a score factor based on how many of the query terms are found in the specified document.
363 * Typically, a document that contains more of the query's terms will receive a higher score
364 * than another document with fewer query terms.
365 * This is a search time factor computed in
366 * {@link #coord(int, int) coord(q,d)}
367 * by the Similarity in effect at search time.
368 * <br> <br>
369 * </li>
370 *
371 * <li><b>
372 * <A NAME="formula_queryNorm"></A>
373 * <i>queryNorm(q)</i>
374 * </b>
375 * is a normalizing factor used to make scores between queries comparable.
376 * This factor does not affect document ranking (since all ranked documents are multiplied by the same factor),
377 * but rather just attempts to make scores from different queries (or even different indexes) comparable.
378 * This is a search time factor computed by the Similarity in effect at search time.
379 *
380 * The default computation in
381 * {@link org.apache.lucene.search.DefaultSimilarity#queryNorm(float) DefaultSimilarity}
382 * produces a <a href="http://en.wikipedia.org/wiki/Euclidean_norm#Euclidean_norm">Euclidean norm</a>:
383 * <br> <br>
384 * <table cellpadding="1" cellspacing="0" border="0" align="center">
385 * <tr>
386 * <td valign="middle" align="right" rowspan="1">
387 * queryNorm(q) =
388 * {@link org.apache.lucene.search.DefaultSimilarity#queryNorm(float) queryNorm(sumOfSquaredWeights)}
389 * =
390 * </td>
391 * <td valign="middle" align="center" rowspan="1">
392 * <table>
393 * <tr><td align="center"><big>1</big></td></tr>
394 * <tr><td align="center"><big>
395 * ––––––––––––––
396 * </big></td></tr>
397 * <tr><td align="center">sumOfSquaredWeights<sup><big>½</big></sup></td></tr>
398 * </table>
399 * </td>
400 * </tr>
401 * </table>
402 * <br> <br>
403 *
404 * The sum of squared weights (of the query terms) is
405 * computed by the query {@link org.apache.lucene.search.Weight} object.
406 * For example, a {@link org.apache.lucene.search.BooleanQuery boolean query}
407 * computes this value as:
408 *
409 * <br> <br>
410 * <table cellpadding="1" cellspacing="0" border="0"n align="center">
411 * <tr>
412 * <td valign="middle" align="right" rowspan="1">
413 * {@link org.apache.lucene.search.Weight#sumOfSquaredWeights() sumOfSquaredWeights} =
414 * {@link org.apache.lucene.search.Query#getBoost() q.getBoost()} <sup><big>2</big></sup>
415 * ·
416 * </td>
417 * <td valign="bottom" align="center" rowspan="1">
418 * <big><big><big>∑</big></big></big>
419 * </td>
420 * <td valign="middle" align="right" rowspan="1">
421 * <big><big>(</big></big>
422 * <A HREF="#formula_idf">idf(t)</A> ·
423 * <A HREF="#formula_termBoost">t.getBoost()</A>
424 * <big><big>) <sup>2</sup> </big></big>
425 * </td>
426 * </tr>
427 * <tr valigh="top">
428 * <td></td>
429 * <td align="center"><small>t in q</small></td>
430 * <td></td>
431 * </tr>
432 * </table>
433 * <br> <br>
434 *
435 * </li>
436 *
437 * <li>
438 * <A NAME="formula_termBoost"></A>
439 * <b><i>t.getBoost()</i></b>
440 * is a search time boost of term <i>t</i> in the query <i>q</i> as
441 * specified in the query text
442 * (see <A HREF="../../../../../../queryparsersyntax.html#Boosting a Term">query syntax</A>),
443 * or as set by application calls to
444 * {@link org.apache.lucene.search.Query#setBoost(float) setBoost()}.
445 * Notice that there is really no direct API for accessing a boost of one term in a multi term query,
446 * but rather multi terms are represented in a query as multi
447 * {@link org.apache.lucene.search.TermQuery TermQuery} objects,
448 * and so the boost of a term in the query is accessible by calling the sub-query
449 * {@link org.apache.lucene.search.Query#getBoost() getBoost()}.
450 * <br> <br>
451 * </li>
452 *
453 * <li>
454 * <A NAME="formula_norm"></A>
455 * <b><i>norm(t,d)</i></b> encapsulates a few (indexing time) boost and length factors:
456 *
457 * <ul>
458 * <li><b>Document boost</b> - set by calling
459 * {@link org.apache.lucene.document.Document#setBoost(float) doc.setBoost()}
460 * before adding the document to the index.
461 * </li>
462 * <li><b>Field boost</b> - set by calling
463 * {@link org.apache.lucene.document.Fieldable#setBoost(float) field.setBoost()}
464 * before adding the field to a document.
465 * </li>
466 * <li>{@link #lengthNorm(String, int) <b>lengthNorm</b>(field)} - computed
467 * when the document is added to the index in accordance with the number of tokens
468 * of this field in the document, so that shorter fields contribute more to the score.
469 * LengthNorm is computed by the Similarity class in effect at indexing.
470 * </li>
471 * </ul>
472 *
473 * <p>
474 * When a document is added to the index, all the above factors are multiplied.
475 * If the document has multiple fields with the same name, all their boosts are multiplied together:
476 *
477 * <br> <br>
478 * <table cellpadding="1" cellspacing="0" border="0"n align="center">
479 * <tr>
480 * <td valign="middle" align="right" rowspan="1">
481 * norm(t,d) =
482 * {@link org.apache.lucene.document.Document#getBoost() doc.getBoost()}
483 * ·
484 * {@link #lengthNorm(String, int) lengthNorm(field)}
485 * ·
486 * </td>
487 * <td valign="bottom" align="center" rowspan="1">
488 * <big><big><big>∏</big></big></big>
489 * </td>
490 * <td valign="middle" align="right" rowspan="1">
491 * {@link org.apache.lucene.document.Fieldable#getBoost() f.getBoost}()
492 * </td>
493 * </tr>
494 * <tr valigh="top">
495 * <td></td>
496 * <td align="center"><small>field <i><b>f</b></i> in <i>d</i> named as <i><b>t</b></i></small></td>
497 * <td></td>
498 * </tr>
499 * </table>
500 * <br> <br>
501 * However the resulted <i>norm</i> value is {@link #encodeNorm(float) encoded} as a single byte
502 * before being stored.
503 * At search time, the norm byte value is read from the index
504 * {@link org.apache.lucene.store.Directory directory} and
505 * {@link #decodeNorm(byte) decoded} back to a float <i>norm</i> value.
506 * This encoding/decoding, while reducing index size, comes with the price of
507 * precision loss - it is not guaranteed that <i>decode(encode(x)) = x</i>.
508 * For instance, <i>decode(encode(0.89)) = 0.75</i>.
509 * <br> <br>
510 * Compression of norm values to a single byte saves memory at search time,
511 * because once a field is referenced at search time, its norms - for
512 * all documents - are maintained in memory.
513 * <br> <br>
514 * The rationale supporting such lossy compression of norm values is that
515 * given the difficulty (and inaccuracy) of users to express their true information
516 * need by a query, only big differences matter.
517 * <br> <br>
518 * Last, note that search time is too late to modify this <i>norm</i> part of scoring, e.g. by
519 * using a different {@link Similarity} for search.
520 * <br> <br>
521 * </li>
522 * </ol>
523 *
524 * @see #setDefault(Similarity)
525 * @see org.apache.lucene.index.IndexWriter#setSimilarity(Similarity)
526 * @see Searcher#setSimilarity(Similarity)
527 */
528 public abstract class Similarity implements Serializable {
529
530 /**
531 * The Similarity implementation used by default.
532 **/
533 private static Similarity defaultImpl = new DefaultSimilarity();
534 public static final int NO_DOC_ID_PROVIDED = -1;
535
536 /** Set the default Similarity implementation used by indexing and search
537 * code.
538 *
539 * @see Searcher#setSimilarity(Similarity)
540 * @see org.apache.lucene.index.IndexWriter#setSimilarity(Similarity)
541 */
542 public static void setDefault(Similarity similarity) {
543 Similarity.defaultImpl = similarity;
544 }
545
546 /** Return the default Similarity implementation used by indexing and search
547 * code.
548 *
549 * <p>This is initially an instance of {@link DefaultSimilarity}.
550 *
551 * @see Searcher#setSimilarity(Similarity)
552 * @see org.apache.lucene.index.IndexWriter#setSimilarity(Similarity)
553 */
554 public static Similarity getDefault() {
555 return Similarity.defaultImpl;
556 }
557
558 /** Cache of decoded bytes. */
559 private static final float[] NORM_TABLE = new float[256];
560
561 static {
562 for (int i = 0; i < 256; i++)
563 NORM_TABLE[i] = SmallFloat.byte315ToFloat((byte)i);
564 }
565
566 /** Decodes a normalization factor stored in an index.
567 * @see #encodeNorm(float)
568 */
569 public static float decodeNorm(byte b) {
570 return NORM_TABLE[b & 0xFF]; // & 0xFF maps negative bytes to positive above 127
571 }
572
573 /** Returns a table for decoding normalization bytes.
574 * @see #encodeNorm(float)
575 */
576 public static float[] getNormDecoder() {
577 return NORM_TABLE;
578 }
579
580 /**
581 * Compute the normalization value for a field, given the accumulated
582 * state of term processing for this field (see {@link FieldInvertState}).
583 *
584 * <p>Implementations should calculate a float value based on the field
585 * state and then return that value.
586 *
587 * <p>For backward compatibility this method by default calls
588 * {@link #lengthNorm(String, int)} passing
589 * {@link FieldInvertState#getLength()} as the second argument, and
590 * then multiplies this value by {@link FieldInvertState#getBoost()}.</p>
591 *
592 * <p><b>WARNING</b>: This API is new and experimental and may
593 * suddenly change.</p>
594 *
595 * @param field field name
596 * @param state current processing state for this field
597 * @return the calculated float norm
598 */
599 public float computeNorm(String field, FieldInvertState state) {
600 return (float) (state.getBoost() * lengthNorm(field, state.getLength()));
601 }
602
603 /** Computes the normalization value for a field given the total number of
604 * terms contained in a field. These values, together with field boosts, are
605 * stored in an index and multipled into scores for hits on each field by the
606 * search code.
607 *
608 * <p>Matches in longer fields are less precise, so implementations of this
609 * method usually return smaller values when <code>numTokens</code> is large,
610 * and larger values when <code>numTokens</code> is small.
611 *
612 * <p>Note that the return values are computed under
613 * {@link org.apache.lucene.index.IndexWriter#addDocument(org.apache.lucene.document.Document)}
614 * and then stored using
615 * {@link #encodeNorm(float)}.
616 * Thus they have limited precision, and documents
617 * must be re-indexed if this method is altered.
618 *
619 * @param fieldName the name of the field
620 * @param numTokens the total number of tokens contained in fields named
621 * <i>fieldName</i> of <i>doc</i>.
622 * @return a normalization factor for hits on this field of this document
623 *
624 * @see org.apache.lucene.document.Field#setBoost(float)
625 */
626 public abstract float lengthNorm(String fieldName, int numTokens);
627
628 /** Computes the normalization value for a query given the sum of the squared
629 * weights of each of the query terms. This value is multiplied into the
630 * weight of each query term. While the classic query normalization factor is
631 * computed as 1/sqrt(sumOfSquaredWeights), other implementations might
632 * completely ignore sumOfSquaredWeights (ie return 1).
633 *
634 * <p>This does not affect ranking, but the default implementation does make scores
635 * from different queries more comparable than they would be by eliminating the
636 * magnitude of the Query vector as a factor in the score.
637 *
638 * @param sumOfSquaredWeights the sum of the squares of query term weights
639 * @return a normalization factor for query weights
640 */
641 public abstract float queryNorm(float sumOfSquaredWeights);
642
643 /** Encodes a normalization factor for storage in an index.
644 *
645 * <p>The encoding uses a three-bit mantissa, a five-bit exponent, and
646 * the zero-exponent point at 15, thus
647 * representing values from around 7x10^9 to 2x10^-9 with about one
648 * significant decimal digit of accuracy. Zero is also represented.
649 * Negative numbers are rounded up to zero. Values too large to represent
650 * are rounded down to the largest representable value. Positive values too
651 * small to represent are rounded up to the smallest positive representable
652 * value.
653 *
654 * @see org.apache.lucene.document.Field#setBoost(float)
655 * @see org.apache.lucene.util.SmallFloat
656 */
657 public static byte encodeNorm(float f) {
658 return SmallFloat.floatToByte315(f);
659 }
660
661
662 /** Computes a score factor based on a term or phrase's frequency in a
663 * document. This value is multiplied by the {@link #idf(int, int)}
664 * factor for each term in the query and these products are then summed to
665 * form the initial score for a document.
666 *
667 * <p>Terms and phrases repeated in a document indicate the topic of the
668 * document, so implementations of this method usually return larger values
669 * when <code>freq</code> is large, and smaller values when <code>freq</code>
670 * is small.
671 *
672 * <p>The default implementation calls {@link #tf(float)}.
673 *
674 * @param freq the frequency of a term within a document
675 * @return a score factor based on a term's within-document frequency
676 */
677 public float tf(int freq) {
678 return tf((float)freq);
679 }
680
681 /** Computes the amount of a sloppy phrase match, based on an edit distance.
682 * This value is summed for each sloppy phrase match in a document to form
683 * the frequency that is passed to {@link #tf(float)}.
684 *
685 * <p>A phrase match with a small edit distance to a document passage more
686 * closely matches the document, so implementations of this method usually
687 * return larger values when the edit distance is small and smaller values
688 * when it is large.
689 *
690 * @see PhraseQuery#setSlop(int)
691 * @param distance the edit distance of this sloppy phrase match
692 * @return the frequency increment for this match
693 */
694 public abstract float sloppyFreq(int distance);
695
696 /** Computes a score factor based on a term or phrase's frequency in a
697 * document. This value is multiplied by the {@link #idf(int, int)}
698 * factor for each term in the query and these products are then summed to
699 * form the initial score for a document.
700 *
701 * <p>Terms and phrases repeated in a document indicate the topic of the
702 * document, so implementations of this method usually return larger values
703 * when <code>freq</code> is large, and smaller values when <code>freq</code>
704 * is small.
705 *
706 * @param freq the frequency of a term within a document
707 * @return a score factor based on a term's within-document frequency
708 */
709 public abstract float tf(float freq);
710
711 /**
712 * Computes a score factor for a simple term and returns an explanation
713 * for that score factor.
714 *
715 * <p>
716 * The default implementation uses:
717 *
718 * <pre>
719 * idf(searcher.docFreq(term), searcher.maxDoc());
720 * </pre>
721 *
722 * Note that {@link Searcher#maxDoc()} is used instead of
723 * {@link org.apache.lucene.index.IndexReader#numDocs() IndexReader#numDocs()} because also
724 * {@link Searcher#docFreq(Term)} is used, and when the latter
725 * is inaccurate, so is {@link Searcher#maxDoc()}, and in the same direction.
726 * In addition, {@link Searcher#maxDoc()} is more efficient to compute
727 *
728 * @param term the term in question
729 * @param searcher the document collection being searched
730 * @return an IDFExplain object that includes both an idf score factor
731 and an explanation for the term.
732 * @throws IOException
733 */
734 public IDFExplanation idfExplain(final Term term, final Searcher searcher) throws IOException {
735 final int df = searcher.docFreq(term);
736 final int max = searcher.maxDoc();
737 final float idf = idf(df, max);
738 return new IDFExplanation() {
739 @Override
740 public String explain() {
741 return "idf(docFreq=" + df +
742 ", maxDocs=" + max + ")";
743 }
744 @Override
745 public float getIdf() {
746 return idf;
747 }};
748 }
749
750 /**
751 * Computes a score factor for a phrase.
752 *
753 * <p>
754 * The default implementation sums the idf factor for
755 * each term in the phrase.
756 *
757 * @param terms the terms in the phrase
758 * @param searcher the document collection being searched
759 * @return an IDFExplain object that includes both an idf
760 * score factor for the phrase and an explanation
761 * for each term.
762 * @throws IOException
763 */
764 public IDFExplanation idfExplain(Collection<Term> terms, Searcher searcher) throws IOException {
765 final int max = searcher.maxDoc();
766 float idf = 0.0f;
767 final StringBuilder exp = new StringBuilder();
768 for (final Term term : terms ) {
769 final int df = searcher.docFreq(term);
770 idf += idf(df, max);
771 exp.append(" ");
772 exp.append(term.text());
773 exp.append("=");
774 exp.append(df);
775 }
776 final float fIdf = idf;
777 return new IDFExplanation() {
778 @Override
779 public float getIdf() {
780 return fIdf;
781 }
782 @Override
783 public String explain() {
784 return exp.toString();
785 }
786 };
787 }
788
789 /** Computes a score factor based on a term's document frequency (the number
790 * of documents which contain the term). This value is multiplied by the
791 * {@link #tf(int)} factor for each term in the query and these products are
792 * then summed to form the initial score for a document.
793 *
794 * <p>Terms that occur in fewer documents are better indicators of topic, so
795 * implementations of this method usually return larger values for rare terms,
796 * and smaller values for common terms.
797 *
798 * @param docFreq the number of documents which contain the term
799 * @param numDocs the total number of documents in the collection
800 * @return a score factor based on the term's document frequency
801 */
802 public abstract float idf(int docFreq, int numDocs);
803
804 /** Computes a score factor based on the fraction of all query terms that a
805 * document contains. This value is multiplied into scores.
806 *
807 * <p>The presence of a large portion of the query terms indicates a better
808 * match with the query, so implementations of this method usually return
809 * larger values when the ratio between these parameters is large and smaller
810 * values when the ratio between them is small.
811 *
812 * @param overlap the number of query terms matched in the document
813 * @param maxOverlap the total number of terms in the query
814 * @return a score factor based on term overlap with the query
815 */
816 public abstract float coord(int overlap, int maxOverlap);
817
818 /**
819 * Calculate a scoring factor based on the data in the payload. Overriding implementations
820 * are responsible for interpreting what is in the payload. Lucene makes no assumptions about
821 * what is in the byte array.
822 * <p>
823 * The default implementation returns 1.
824 *
825 * @param docId The docId currently being scored. If this value is {@link #NO_DOC_ID_PROVIDED}, then it should be assumed that the PayloadQuery implementation does not provide document information
826 * @param fieldName The fieldName of the term this payload belongs to
827 * @param start The start position of the payload
828 * @param end The end position of the payload
829 * @param payload The payload byte array to be scored
830 * @param offset The offset into the payload array
831 * @param length The length in the array
832 * @return An implementation dependent float to be used as a scoring factor
833 *
834 */
835 public float scorePayload(int docId, String fieldName, int start, int end, byte [] payload, int offset, int length)
836 {
837 return 1;
838 }
839
840 }
Save This Page