lucene-java-3.4.0/lucene/src/java/org/apache/lucene/search/Similarity.java

   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 import org.apache.lucene.util.VirtualMethod;
  26
  27 import java.io.IOException;
  28 import java.io.Serializable;
  29 import java.util.Collection;
  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>&nbsp;<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) &nbsp; = &nbsp;
  89  *          </td>
  90  *          <td valign="middle" align="center">
  91  *            <table>
  92  *               <tr><td align="center"><small>V(q)&nbsp;&middot;&nbsp;V(d)</small></td></tr>
  93  *               <tr><td align="center">&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;</td></tr>
  94  *               <tr><td align="center"><small>|V(q)|&nbsp;|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>&nbsp;<br>
 107  *
 108  *
 109  * Where <i>V(q)</i> &middot; <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>&nbsp;<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) &nbsp; = &nbsp;
 174  *            <font color="#FF9933">coord-factor(q,d)</font> &middot; &nbsp;
 175  *            <font color="#CCCC00">query-boost(q)</font> &middot; &nbsp;
 176  *          </td>
 177  *          <td valign="middle" align="center">
 178  *            <table>
 179  *               <tr><td align="center"><small><font color="#993399">V(q)&nbsp;&middot;&nbsp;V(d)</font></small></td></tr>
 180  *               <tr><td align="center">&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;</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  *            &nbsp; &middot; &nbsp; <font color="#3399FF">doc-len-norm(d)</font>
 186  *            &nbsp; &middot; &nbsp; <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>&nbsp;<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) &nbsp; = &nbsp;
 266  *       <A HREF="#formula_coord"><font color="#FF9933">coord(q,d)</font></A> &nbsp;&middot;&nbsp;
 267  *       <A HREF="#formula_queryNorm"><font color="#FF33CC">queryNorm(q)</font></A> &nbsp;&middot;&nbsp;
 268  *     </td>
 269  *     <td valign="bottom" align="center" rowspan="1">
 270  *       <big><big><big>&sum;</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> &nbsp;&middot;&nbsp;
 275  *       <A HREF="#formula_idf"><font color="#993399">idf(t)</font></A><sup>2</sup> &nbsp;&middot;&nbsp;
 276  *       <A HREF="#formula_termBoost"><font color="#CCCC00">t.getBoost()</font></A>&nbsp;&middot;&nbsp;
 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>&nbsp;<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)} &nbsp; = &nbsp;
 315  *          </td>
 316  *          <td valign="top" align="center" rowspan="1">
 317  *               frequency<sup><big>&frac12;</big></sup>
 318  *          </td>
 319  *        </tr>
 320  *      </table>
 321  *      <br>&nbsp;<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>&nbsp;<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)}&nbsp; = &nbsp;
 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">&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;</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>&nbsp;<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>&nbsp;<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>&nbsp;<br>
 384  *      <table cellpadding="1" cellspacing="0" border="0" align="center">
 385  *        <tr>
 386  *          <td valign="middle" align="right" rowspan="1">
 387  *            queryNorm(q)  &nbsp; = &nbsp;
 388  *            {@link org.apache.lucene.search.DefaultSimilarity#queryNorm(float) queryNorm(sumOfSquaredWeights)}
 389  *            &nbsp; = &nbsp;
 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  *                  &ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;
 396  *               </big></td></tr>
 397  *               <tr><td align="center">sumOfSquaredWeights<sup><big>&frac12;</big></sup></td></tr>
 398  *            </table>
 399  *          </td>
 400  *        </tr>
 401  *      </table>
 402  *      <br>&nbsp;<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}
 407  *      computes this value as:
 408  *
 409  *      <br>&nbsp;<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} &nbsp; = &nbsp;
 414  *            {@link org.apache.lucene.search.Query#getBoost() q.getBoost()} <sup><big>2</big></sup>
 415  *            &nbsp;&middot;&nbsp;
 416  *          </td>
 417  *          <td valign="bottom" align="center" rowspan="1">
 418  *            <big><big><big>&sum;</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> &nbsp;&middot;&nbsp;
 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>&nbsp;<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>&nbsp;<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><b>lengthNorm</b> - 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  *      The {@link #computeNorm} method is responsible for
 473  *      combining all of these factors into a single float.
 474  *
 475  *      <p>
 476  *      When a document is added to the index, all the above factors are multiplied.
 477  *      If the document has multiple fields with the same name, all their boosts are multiplied together:
 478  *
 479  *      <br>&nbsp;<br>
 480  *      <table cellpadding="1" cellspacing="0" border="0"n align="center">
 481  *        <tr>
 482  *          <td valign="middle" align="right" rowspan="1">
 483  *            norm(t,d) &nbsp; = &nbsp;
 484  *            {@link org.apache.lucene.document.Document#getBoost() doc.getBoost()}
 485  *            &nbsp;&middot;&nbsp;
 486  *            lengthNorm
 487  *            &nbsp;&middot;&nbsp;
 488  *          </td>
 489  *          <td valign="bottom" align="center" rowspan="1">
 490  *            <big><big><big>&prod;</big></big></big>
 491  *          </td>
 492  *          <td valign="middle" align="right" rowspan="1">
 493  *            {@link org.apache.lucene.document.Fieldable#getBoost() f.getBoost}()
 494  *          </td>
 495  *        </tr>
 496  *        <tr valigh="top">
 497  *          <td></td>
 498  *          <td align="center"><small>field <i><b>f</b></i> in <i>d</i> named as <i><b>t</b></i></small></td>
 499  *          <td></td>
 500  *        </tr>
 501  *      </table>
 502  *      <br>&nbsp;<br>
 503  *      However the resulted <i>norm</i> value is {@link #encodeNormValue(float) encoded} as a single byte
 504  *      before being stored.
 505  *      At search time, the norm byte value is read from the index
 506  *      {@link org.apache.lucene.store.Directory directory} and
 507  *      {@link #decodeNormValue(byte) decoded} back to a float <i>norm</i> value.
 508  *      This encoding/decoding, while reducing index size, comes with the price of
 509  *      precision loss - it is not guaranteed that <i>decode(encode(x)) = x</i>.
 510  *      For instance, <i>decode(encode(0.89)) = 0.75</i>.
 511  *      <br>&nbsp;<br>
 512  *      Compression of norm values to a single byte saves memory at search time,
 513  *      because once a field is referenced at search time, its norms - for
 514  *      all documents - are maintained in memory.
 515  *      <br>&nbsp;<br>
 516  *      The rationale supporting such lossy compression of norm values is that
 517  *      given the difficulty (and inaccuracy) of users to express their true information
 518  *      need by a query, only big differences matter.
 519  *      <br>&nbsp;<br>
 520  *      Last, note that search time is too late to modify this <i>norm</i> part of scoring, e.g. by
 521  *      using a different {@link Similarity} for search.
 522  *      <br>&nbsp;<br>
 523  *    </li>
 524  * </ol>
 525  *
 526  * @see #setDefault(Similarity)
 527  * @see org.apache.lucene.index.IndexWriter#setSimilarity(Similarity)
 528  * @see Searcher#setSimilarity(Similarity)
 529  */
 530 public abstract class Similarity implements Serializable {
 531
 532   // NOTE: this static code must precede setting the static defaultImpl:
 533   private static final VirtualMethod<Similarity> withoutDocFreqMethod =
 534     new VirtualMethod<Similarity>(Similarity.class, "idfExplain", Term.class, Searcher.class);
 535   private static final VirtualMethod<Similarity> withDocFreqMethod =
 536     new VirtualMethod<Similarity>(Similarity.class, "idfExplain", Term.class, Searcher.class, int.class);
 537
 538   private final boolean hasIDFExplainWithDocFreqAPI =
 539     VirtualMethod.compareImplementationDistance(getClass(),
 540         withDocFreqMethod, withoutDocFreqMethod) >= 0; // its ok for both to be overridden
 541   /**
 542    * The Similarity implementation used by default.
 543    **/
 544   private static Similarity defaultImpl = new DefaultSimilarity();
 545
 546   public static final int NO_DOC_ID_PROVIDED = -1;
 547
 548   /** Set the default Similarity implementation used by indexing and search
 549    * code.
 550    *
 551    * @see Searcher#setSimilarity(Similarity)
 552    * @see org.apache.lucene.index.IndexWriter#setSimilarity(Similarity)
 553    */
 554   public static void setDefault(Similarity similarity) {
 555     Similarity.defaultImpl = similarity;
 556   }
 557
 558   /** Return the default Similarity implementation used by indexing and search
 559    * code.
 560    *
 561    * <p>This is initially an instance of {@link DefaultSimilarity}.
 562    *
 563    * @see Searcher#setSimilarity(Similarity)
 564    * @see org.apache.lucene.index.IndexWriter#setSimilarity(Similarity)
 565    */
 566   public static Similarity getDefault() {
 567     return Similarity.defaultImpl;
 568   }
 569
 570   /** Cache of decoded bytes. */
 571   private static final float[] NORM_TABLE = new float[256];
 572
 573   static {
 574     for (int i = 0; i < 256; i++)
 575       NORM_TABLE[i] = SmallFloat.byte315ToFloat((byte)i);
 576   }
 577
 578   /**
 579    * Decodes a normalization factor stored in an index.
 580    * @see #decodeNormValue(byte)
 581    * @deprecated Use {@link #decodeNormValue} instead.
 582    */
 583   @Deprecated
 584   public static float decodeNorm(byte b) {
 585     return NORM_TABLE[b & 0xFF];  // & 0xFF maps negative bytes to positive above 127
 586   }
 587
 588   /** Decodes a normalization factor stored in an index.
 589    * <p>
 590    * <b>WARNING: If you override this method, you should change the default
 591    *    Similarity to your implementation with {@link Similarity#setDefault(Similarity)}.
 592    *    Otherwise, your method may not always be called, especially if you omit norms
 593    *    for some fields.</b>
 594    * @see #encodeNormValue(float)
 595    */
 596   public float decodeNormValue(byte b) {
 597     return NORM_TABLE[b & 0xFF];  // & 0xFF maps negative bytes to positive above 127
 598   }
 599
 600   /** Returns a table for decoding normalization bytes.
 601    * @see #encodeNormValue(float)
 602    * @see #decodeNormValue(byte)
 603    *
 604    * @deprecated Use instance methods for encoding/decoding norm values to enable customization.
 605    */
 606   @Deprecated
 607   public static float[] getNormDecoder() {
 608     return NORM_TABLE;
 609   }
 610
 611   /**
 612    * Computes the normalization value for a field, given the accumulated
 613    * state of term processing for this field (see {@link FieldInvertState}).
 614    *
 615    * <p>Implementations should calculate a float value based on the field
 616    * state and then return that value.
 617    *
 618    * <p>Matches in longer fields are less precise, so implementations of this
 619    * method usually return smaller values when <code>state.getLength()</code> is large,
 620    * and larger values when <code>state.getLength()</code> is small.
 621    *
 622    * <p>Note that the return values are computed under
 623    * {@link org.apache.lucene.index.IndexWriter#addDocument(org.apache.lucene.document.Document)}
 624    * and then stored using
 625    * {@link #encodeNormValue(float)}.
 626    * Thus they have limited precision, and documents
 627    * must be re-indexed if this method is altered.
 628    *
 629    * <p>For backward compatibility this method by default calls
 630    * {@link #lengthNorm(String, int)} passing
 631    * {@link FieldInvertState#getLength()} as the second argument, and
 632    * then multiplies this value by {@link FieldInvertState#getBoost()}.</p>
 633    *
 634    * @lucene.experimental
 635    *
 636    * @param field field name
 637    * @param state current processing state for this field
 638    * @return the calculated float norm
 639    */
 640   public abstract float computeNorm(String field, FieldInvertState state);
 641
 642   /** Computes the normalization value for a field given the total number of
 643    * terms contained in a field.  These values, together with field boosts, are
 644    * stored in an index and multipled into scores for hits on each field by the
 645    * search code.
 646    *
 647    * <p>Matches in longer fields are less precise, so implementations of this
 648    * method usually return smaller values when <code>numTokens</code> is large,
 649    * and larger values when <code>numTokens</code> is small.
 650    *
 651    * <p>Note that the return values are computed under
 652    * {@link org.apache.lucene.index.IndexWriter#addDocument(org.apache.lucene.document.Document)}
 653    * and then stored using
 654    * {@link #encodeNormValue(float)}.
 655    * Thus they have limited precision, and documents
 656    * must be re-indexed if this method is altered.
 657    *
 658    * @param fieldName the name of the field
 659    * @param numTokens the total number of tokens contained in fields named
 660    * <i>fieldName</i> of <i>doc</i>.
 661    * @return a normalization factor for hits on this field of this document
 662    *
 663    * @see org.apache.lucene.document.Field#setBoost(float)
 664    *
 665    * @deprecated Please override computeNorm instead
 666    */
 667   @Deprecated
 668   public final float lengthNorm(String fieldName, int numTokens) {
 669     throw new UnsupportedOperationException("please use computeNorm instead");
 670   }
 671
 672   /** Computes the normalization value for a query given the sum of the squared
 673    * weights of each of the query terms.  This value is multiplied into the
 674    * weight of each query term. While the classic query normalization factor is
 675    * computed as 1/sqrt(sumOfSquaredWeights), other implementations might
 676    * completely ignore sumOfSquaredWeights (ie return 1).
 677    *
 678    * <p>This does not affect ranking, but the default implementation does make scores
 679    * from different queries more comparable than they would be by eliminating the
 680    * magnitude of the Query vector as a factor in the score.
 681    *
 682    * @param sumOfSquaredWeights the sum of the squares of query term weights
 683    * @return a normalization factor for query weights
 684    */
 685   public abstract float queryNorm(float sumOfSquaredWeights);
 686
 687   /** Encodes a normalization factor for storage in an index.
 688    *
 689    * <p>The encoding uses a three-bit mantissa, a five-bit exponent, and
 690    * the zero-exponent point at 15, thus
 691    * representing values from around 7x10^9 to 2x10^-9 with about one
 692    * significant decimal digit of accuracy.  Zero is also represented.
 693    * Negative numbers are rounded up to zero.  Values too large to represent
 694    * are rounded down to the largest representable value.  Positive values too
 695    * small to represent are rounded up to the smallest positive representable
 696    * value.
 697    * <p>
 698    * <b>WARNING: If you override this method, you should change the default
 699    * Similarity to your implementation with {@link Similarity#setDefault(Similarity)}.
 700    * Otherwise, your method may not always be called, especially if you omit norms
 701    * for some fields.</b>
 702    * @see org.apache.lucene.document.Field#setBoost(float)
 703    * @see org.apache.lucene.util.SmallFloat
 704    */
 705   public byte encodeNormValue(float f) {
 706     return SmallFloat.floatToByte315(f);
 707   }
 708
 709   /**
 710    * Static accessor kept for backwards compability reason, use encodeNormValue instead.
 711    * @param f norm-value to encode
 712    * @return byte representing the given float
 713    * @deprecated Use {@link #encodeNormValue} instead.
 714    *
 715    * @see #encodeNormValue(float)
 716    */
 717   @Deprecated
 718   public static byte encodeNorm(float f) {
 719     return SmallFloat.floatToByte315(f);
 720   }
 721
 722
 723   /** Computes a score factor based on a term or phrase's frequency in a
 724    * document.  This value is multiplied by the {@link #idf(int, int)}
 725    * factor for each term in the query and these products are then summed to
 726    * form the initial score for a document.
 727    *
 728    * <p>Terms and phrases repeated in a document indicate the topic of the
 729    * document, so implementations of this method usually return larger values
 730    * when <code>freq</code> is large, and smaller values when <code>freq</code>
 731    * is small.
 732    *
 733    * <p>The default implementation calls {@link #tf(float)}.
 734    *
 735    * @param freq the frequency of a term within a document
 736    * @return a score factor based on a term's within-document frequency
 737    */
 738   public float tf(int freq) {
 739     return tf((float)freq);
 740   }
 741
 742   /** Computes the amount of a sloppy phrase match, based on an edit distance.
 743    * This value is summed for each sloppy phrase match in a document to form
 744    * the frequency that is passed to {@link #tf(float)}.
 745    *
 746    * <p>A phrase match with a small edit distance to a document passage more
 747    * closely matches the document, so implementations of this method usually
 748    * return larger values when the edit distance is small and smaller values
 749    * when it is large.
 750    *
 751    * @see PhraseQuery#setSlop(int)
 752    * @param distance the edit distance of this sloppy phrase match
 753    * @return the frequency increment for this match
 754    */
 755   public abstract float sloppyFreq(int distance);
 756
 757   /** Computes a score factor based on a term or phrase's frequency in a
 758    * document.  This value is multiplied by the {@link #idf(int, int)}
 759    * factor for each term in the query and these products are then summed to
 760    * form the initial score for a document.
 761    *
 762    * <p>Terms and phrases repeated in a document indicate the topic of the
 763    * document, so implementations of this method usually return larger values
 764    * when <code>freq</code> is large, and smaller values when <code>freq</code>
 765    * is small.
 766    *
 767    * @param freq the frequency of a term within a document
 768    * @return a score factor based on a term's within-document frequency
 769    */
 770   public abstract float tf(float freq);
 771
 772
 773   /**
 774    * Computes a score factor for a simple term and returns an explanation
 775    * for that score factor.
 776    *
 777    * <p>
 778    * The default implementation uses:
 779    *
 780    * <pre>
 781    * idf(searcher.docFreq(term), searcher.maxDoc());
 782    * </pre>
 783    *
 784    * Note that {@link Searcher#maxDoc()} is used instead of
 785    * {@link org.apache.lucene.index.IndexReader#numDocs() IndexReader#numDocs()} because also
 786    * {@link Searcher#docFreq(Term)} is used, and when the latter
 787    * is inaccurate, so is {@link Searcher#maxDoc()}, and in the same direction.
 788    * In addition, {@link Searcher#maxDoc()} is more efficient to compute
 789    *
 790    * @param term the term in question
 791    * @param searcher the document collection being searched
 792    * @return an IDFExplain object that includes both an idf score factor
 793              and an explanation for the term.
 794    * @throws IOException
 795    */
 796   public IDFExplanation idfExplain(final Term term, final Searcher searcher, int docFreq) throws IOException {
 797
 798     if (!hasIDFExplainWithDocFreqAPI) {
 799       // Fallback to slow impl
 800       return idfExplain(term, searcher);
 801     }
 802     final int df = docFreq;
 803     final int max = searcher.maxDoc();
 804     final float idf = idf(df, max);
 805     return new IDFExplanation() {
 806         @Override
 807         public String explain() {
 808           return "idf(docFreq=" + df +
 809           ", maxDocs=" + max + ")";
 810         }
 811         @Override
 812         public float getIdf() {
 813           return idf;
 814         }};
 815   }
 816
 817   /**
 818    * This method forwards to {@link
 819    * #idfExplain(Term,Searcher,int)} by passing
 820    * <code>searcher.docFreq(term)</code> as the docFreq.
 821    *
 822    * WARNING: if you subclass Similariary and override this
 823    * method then you may hit a peformance hit for certain
 824    * queries.  Better to override {@link
 825    * #idfExplain(Term,Searcher,int)} instead.
 826    */
 827   public IDFExplanation idfExplain(final Term term, final Searcher searcher) throws IOException {
 828     return idfExplain(term, searcher, searcher.docFreq(term));
 829   }
 830
 831   /**
 832    * Computes a score factor for a phrase.
 833    *
 834    * <p>
 835    * The default implementation sums the idf factor for
 836    * each term in the phrase.
 837    *
 838    * @param terms the terms in the phrase
 839    * @param searcher the document collection being searched
 840    * @return an IDFExplain object that includes both an idf
 841    *         score factor for the phrase and an explanation
 842    *         for each term.
 843    * @throws IOException
 844    */
 845   public IDFExplanation idfExplain(Collection<Term> terms, Searcher searcher) throws IOException {
 846     final int max = searcher.maxDoc();
 847     float idf = 0.0f;
 848     final StringBuilder exp = new StringBuilder();
 849     for (final Term term : terms ) {
 850       final int df = searcher.docFreq(term);
 851       idf += idf(df, max);
 852       exp.append(" ");
 853       exp.append(term.text());
 854       exp.append("=");
 855       exp.append(df);
 856     }
 857     final float fIdf = idf;
 858     return new IDFExplanation() {
 859       @Override
 860       public float getIdf() {
 861         return fIdf;
 862       }
 863       @Override
 864       public String explain() {
 865         return exp.toString();
 866       }
 867     };
 868   }
 869
 870   /** Computes a score factor based on a term's document frequency (the number
 871    * of documents which contain the term).  This value is multiplied by the
 872    * {@link #tf(int)} factor for each term in the query and these products are
 873    * then summed to form the initial score for a document.
 874    *
 875    * <p>Terms that occur in fewer documents are better indicators of topic, so
 876    * implementations of this method usually return larger values for rare terms,
 877    * and smaller values for common terms.
 878    *
 879    * @param docFreq the number of documents which contain the term
 880    * @param numDocs the total number of documents in the collection
 881    * @return a score factor based on the term's document frequency
 882    */
 883   public abstract float idf(int docFreq, int numDocs);
 884
 885   /** Computes a score factor based on the fraction of all query terms that a
 886    * document contains.  This value is multiplied into scores.
 887    *
 888    * <p>The presence of a large portion of the query terms indicates a better
 889    * match with the query, so implementations of this method usually return
 890    * larger values when the ratio between these parameters is large and smaller
 891    * values when the ratio between them is small.
 892    *
 893    * @param overlap the number of query terms matched in the document
 894    * @param maxOverlap the total number of terms in the query
 895    * @return a score factor based on term overlap with the query
 896    */
 897   public abstract float coord(int overlap, int maxOverlap);
 898
 899   /**
 900    * Calculate a scoring factor based on the data in the payload.  Overriding implementations
 901    * are responsible for interpreting what is in the payload.  Lucene makes no assumptions about
 902    * what is in the byte array.
 903    * <p>
 904    * The default implementation returns 1.
 905    *
 906    * @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
 907    * @param fieldName The fieldName of the term this payload belongs to
 908    * @param start The start position of the payload
 909    * @param end The end position of the payload
 910    * @param payload The payload byte array to be scored
 911    * @param offset The offset into the payload array
 912    * @param length The length in the array
 913    * @return An implementation dependent float to be used as a scoring factor
 914    *
 915    */
 916   public float scorePayload(int docId, String fieldName, int start, int end, byte [] payload, int offset, int length)
 917   {
 918     return 1;
 919   }
 920
 921 }