Similarity defines the components of Lucene scoring. - * Overriding computation of these components is a convenient - * way to alter Lucene scoring. - * - *
Suggested reading: - * - * Introduction To Information Retrieval, Chapter 6. - * - *
The following describes how Lucene scoring evolves from - * underlying information retrieval models to (efficient) implementation. - * We first brief on VSM Score, - * then derive from it Lucene's Conceptual Scoring Formula, - * from which, finally, evolves Lucene's Practical Scoring Function - * (the latter is connected directly with Lucene classes and methods). - * - *
Lucene combines - * - * Boolean model (BM) of Information Retrieval - * with - * - * Vector Space Model (VSM) of Information Retrieval - - * documents "approved" by BM are scored by VSM. - * - *
In VSM, documents and queries are represented as - * weighted vectors in a multi-dimensional space, - * where each distinct index term is a dimension, - * and weights are - * Tf-idf values. - * - *
VSM does not require weights to be Tf-idf values, - * but Tf-idf values are believed to produce search results of high quality, - * and so Lucene is using Tf-idf. - * Tf and Idf are described in more detail below, - * but for now, for completion, let's just say that - * for given term t and document (or query) x, - * Tf(t,x) varies with the number of occurrences of term t in x - * (when one increases so does the other) and - * idf(t) similarly varies with the inverse of the - * number of index documents containing term t. - * - *
VSM score of document d for query q is the
- *
- * Cosine Similarity
- * of the weighted query vectors V(q) and V(d):
- *
- *
- *
- *
| ||||||
|
- * |
Note: the above equation can be viewed as the dot product of - * the normalized weighted vectors, in the sense that dividing - * V(q) by its euclidean norm is normalizing it to a unit vector. - * - *
Lucene refines VSM score for both search quality and usability: - *
Under the simplifying assumption of a single field in the index,
- * we get Lucene's Conceptual scoring formula:
- *
- *
- *
- *
| |||||||
|
- * |
The conceptual formula is a simplification in the sense that (1) terms and documents - * are fielded and (2) boosts are usually per query term rather than per query. - * - *
We now describe how Lucene implements this conceptual scoring formula, and - * derive from it Lucene's Practical Scoring Function. - * - *
For efficient score computation some scoring components - * are computed and aggregated in advance: - * - *
Lucene's Practical Scoring Function is derived from the above. - * The color codes demonstrate how it relates - * to those of the conceptual formula: - * - *
- *
- *
| |||||||
|
- * |
where - *
| - * {@link org.apache.lucene.search.DefaultSimilarity#tf(float) tf(t in d)} = - * | - *- * frequency½ - * | - *
| - * {@link org.apache.lucene.search.DefaultSimilarity#idf(int, int) idf(t)} = - * | - *- * 1 + log ( - * | - *
- *
|
- * - * ) - * | - *
| - * queryNorm(q) = - * {@link org.apache.lucene.search.DefaultSimilarity#queryNorm(float) queryNorm(sumOfSquaredWeights)} - * = - * | - *
- *
|
- *
| - * {@link org.apache.lucene.search.Weight#sumOfSquaredWeights() sumOfSquaredWeights} = - * {@link org.apache.lucene.search.Query#getBoost() q.getBoost()} 2 - * · - * | - *- * ∑ - * | - *- * ( - * idf(t) · - * t.getBoost() - * ) 2 - * | - *
| - * | t in q | - *- * |
- * When a document is added to the index, all the above factors are multiplied.
- * If the document has multiple fields with the same name, all their boosts are multiplied together:
- *
- *
- *
| - * norm(t,d) = - * {@link org.apache.lucene.document.Document#getBoost() doc.getBoost()} - * · - * lengthNorm - * · - * | - *- * ∏ - * | - *- * {@link org.apache.lucene.document.Fieldable#getBoost() f.getBoost}() - * | - *
| - * | field f in d named as t | - *- * |
This is initially an instance of {@link DefaultSimilarity}. - * - * @see Searcher#setSimilarity(Similarity) - * @see org.apache.lucene.index.IndexWriter#setSimilarity(Similarity) - */ - public static Similarity getDefault() { - return Similarity.defaultImpl; - } - - /** Cache of decoded bytes. */ - private static final float[] NORM_TABLE = new float[256]; - - static { - for (int i = 0; i < 256; i++) - NORM_TABLE[i] = SmallFloat.byte315ToFloat((byte)i); - } - - /** - * Decodes a normalization factor stored in an index. - * @see #decodeNormValue(byte) - * @deprecated Use {@link #decodeNormValue} instead. - */ - @Deprecated - public static float decodeNorm(byte b) { - return NORM_TABLE[b & 0xFF]; // & 0xFF maps negative bytes to positive above 127 - } - - /** Decodes a normalization factor stored in an index. - *
- * WARNING: If you override this method, you should change the default - * Similarity to your implementation with {@link Similarity#setDefault(Similarity)}. - * Otherwise, your method may not always be called, especially if you omit norms - * for some fields. - * @see #encodeNormValue(float) - */ - public float decodeNormValue(byte b) { - return NORM_TABLE[b & 0xFF]; // & 0xFF maps negative bytes to positive above 127 - } - - /** Returns a table for decoding normalization bytes. - * @see #encodeNormValue(float) - * @see #decodeNormValue(byte) - * - * @deprecated Use instance methods for encoding/decoding norm values to enable customization. - */ - @Deprecated - public static float[] getNormDecoder() { - return NORM_TABLE; - } - - /** - * Computes the normalization value for a field, given the accumulated - * state of term processing for this field (see {@link FieldInvertState}). - * - *
Implementations should calculate a float value based on the field - * state and then return that value. - * - *
Matches in longer fields are less precise, so implementations of this
- * method usually return smaller values when state.getLength() is large,
- * and larger values when state.getLength() is small.
- *
- *
Note that the return values are computed under - * {@link org.apache.lucene.index.IndexWriter#addDocument(org.apache.lucene.document.Document)} - * and then stored using - * {@link #encodeNormValue(float)}. - * Thus they have limited precision, and documents - * must be re-indexed if this method is altered. - * - *
For backward compatibility this method by default calls - * {@link #lengthNorm(String, int)} passing - * {@link FieldInvertState#getLength()} as the second argument, and - * then multiplies this value by {@link FieldInvertState#getBoost()}.
- * - * @lucene.experimental - * - * @param field field name - * @param state current processing state for this field - * @return the calculated float norm - */ - public abstract float computeNorm(String field, FieldInvertState state); - - /** Computes the normalization value for a field given the total number of - * terms contained in a field. These values, together with field boosts, are - * stored in an index and multipled into scores for hits on each field by the - * search code. - * - *Matches in longer fields are less precise, so implementations of this
- * method usually return smaller values when numTokens is large,
- * and larger values when numTokens is small.
- *
- *
Note that the return values are computed under - * {@link org.apache.lucene.index.IndexWriter#addDocument(org.apache.lucene.document.Document)} - * and then stored using - * {@link #encodeNormValue(float)}. - * Thus they have limited precision, and documents - * must be re-indexed if this method is altered. - * - * @param fieldName the name of the field - * @param numTokens the total number of tokens contained in fields named - * fieldName of doc. - * @return a normalization factor for hits on this field of this document - * - * @see org.apache.lucene.document.Field#setBoost(float) - * - * @deprecated Please override computeNorm instead - */ - @Deprecated - public final float lengthNorm(String fieldName, int numTokens) { - throw new UnsupportedOperationException("please use computeNorm instead"); - } - - /** Computes the normalization value for a query given the sum of the squared - * weights of each of the query terms. This value is multiplied into the - * weight of each query term. While the classic query normalization factor is - * computed as 1/sqrt(sumOfSquaredWeights), other implementations might - * completely ignore sumOfSquaredWeights (ie return 1). - * - *
This does not affect ranking, but the default implementation does make scores - * from different queries more comparable than they would be by eliminating the - * magnitude of the Query vector as a factor in the score. - * - * @param sumOfSquaredWeights the sum of the squares of query term weights - * @return a normalization factor for query weights - */ - public abstract float queryNorm(float sumOfSquaredWeights); - - /** Encodes a normalization factor for storage in an index. - * - *
The encoding uses a three-bit mantissa, a five-bit exponent, and - * the zero-exponent point at 15, thus - * representing values from around 7x10^9 to 2x10^-9 with about one - * significant decimal digit of accuracy. Zero is also represented. - * Negative numbers are rounded up to zero. Values too large to represent - * are rounded down to the largest representable value. Positive values too - * small to represent are rounded up to the smallest positive representable - * value. - *
- * WARNING: If you override this method, you should change the default - * Similarity to your implementation with {@link Similarity#setDefault(Similarity)}. - * Otherwise, your method may not always be called, especially if you omit norms - * for some fields. - * @see org.apache.lucene.document.Field#setBoost(float) - * @see org.apache.lucene.util.SmallFloat - */ - public byte encodeNormValue(float f) { - return SmallFloat.floatToByte315(f); - } - - /** - * Static accessor kept for backwards compability reason, use encodeNormValue instead. - * @param f norm-value to encode - * @return byte representing the given float - * @deprecated Use {@link #encodeNormValue} instead. - * - * @see #encodeNormValue(float) - */ - @Deprecated - public static byte encodeNorm(float f) { - return SmallFloat.floatToByte315(f); - } - - - /** Computes a score factor based on a term or phrase's frequency in a - * document. This value is multiplied by the {@link #idf(int, int)} - * factor for each term in the query and these products are then summed to - * form the initial score for a document. - * - *
Terms and phrases repeated in a document indicate the topic of the
- * document, so implementations of this method usually return larger values
- * when freq is large, and smaller values when freq
- * is small.
- *
- *
The default implementation calls {@link #tf(float)}. - * - * @param freq the frequency of a term within a document - * @return a score factor based on a term's within-document frequency - */ - public float tf(int freq) { - return tf((float)freq); - } - - /** Computes the amount of a sloppy phrase match, based on an edit distance. - * This value is summed for each sloppy phrase match in a document to form - * the frequency that is passed to {@link #tf(float)}. - * - *
A phrase match with a small edit distance to a document passage more - * closely matches the document, so implementations of this method usually - * return larger values when the edit distance is small and smaller values - * when it is large. - * - * @see PhraseQuery#setSlop(int) - * @param distance the edit distance of this sloppy phrase match - * @return the frequency increment for this match - */ - public abstract float sloppyFreq(int distance); - - /** Computes a score factor based on a term or phrase's frequency in a - * document. This value is multiplied by the {@link #idf(int, int)} - * factor for each term in the query and these products are then summed to - * form the initial score for a document. - * - *
Terms and phrases repeated in a document indicate the topic of the
- * document, so implementations of this method usually return larger values
- * when freq is large, and smaller values when freq
- * is small.
- *
- * @param freq the frequency of a term within a document
- * @return a score factor based on a term's within-document frequency
- */
- public abstract float tf(float freq);
-
-
- /**
- * Computes a score factor for a simple term and returns an explanation
- * for that score factor.
- *
- *
- * The default implementation uses: - * - *
- * idf(searcher.docFreq(term), searcher.maxDoc()); - *- * - * Note that {@link Searcher#maxDoc()} is used instead of - * {@link org.apache.lucene.index.IndexReader#numDocs() IndexReader#numDocs()} because also - * {@link Searcher#docFreq(Term)} is used, and when the latter - * is inaccurate, so is {@link Searcher#maxDoc()}, and in the same direction. - * In addition, {@link Searcher#maxDoc()} is more efficient to compute - * - * @param term the term in question - * @param searcher the document collection being searched - * @return an IDFExplain object that includes both an idf score factor - and an explanation for the term. - * @throws IOException - */ - public IDFExplanation idfExplain(final Term term, final Searcher searcher, int docFreq) throws IOException { - - if (!hasIDFExplainWithDocFreqAPI) { - // Fallback to slow impl - return idfExplain(term, searcher); - } - final int df = docFreq; - final int max = searcher.maxDoc(); - final float idf = idf(df, max); - return new IDFExplanation() { - @Override - public String explain() { - return "idf(docFreq=" + df + - ", maxDocs=" + max + ")"; - } - @Override - public float getIdf() { - return idf; - }}; - } - - /** - * This method forwards to {@link - * #idfExplain(Term,Searcher,int)} by passing - *
searcher.docFreq(term) as the docFreq.
- *
- * WARNING: if you subclass Similariary and override this
- * method then you may hit a peformance hit for certain
- * queries. Better to override {@link
- * #idfExplain(Term,Searcher,int)} instead.
- */
- public IDFExplanation idfExplain(final Term term, final Searcher searcher) throws IOException {
- return idfExplain(term, searcher, searcher.docFreq(term));
- }
-
- /**
- * Computes a score factor for a phrase.
- *
- *
- * The default implementation sums the idf factor for
- * each term in the phrase.
- *
- * @param terms the terms in the phrase
- * @param searcher the document collection being searched
- * @return an IDFExplain object that includes both an idf
- * score factor for the phrase and an explanation
- * for each term.
- * @throws IOException
- */
- public IDFExplanation idfExplain(Collection Terms that occur in fewer documents are better indicators of topic, so
- * implementations of this method usually return larger values for rare terms,
- * and smaller values for common terms.
- *
- * @param docFreq the number of documents which contain the term
- * @param numDocs the total number of documents in the collection
- * @return a score factor based on the term's document frequency
- */
- public abstract float idf(int docFreq, int numDocs);
-
- /** Computes a score factor based on the fraction of all query terms that a
- * document contains. This value is multiplied into scores.
- *
- * The presence of a large portion of the query terms indicates a better
- * match with the query, so implementations of this method usually return
- * larger values when the ratio between these parameters is large and smaller
- * values when the ratio between them is small.
- *
- * @param overlap the number of query terms matched in the document
- * @param maxOverlap the total number of terms in the query
- * @return a score factor based on term overlap with the query
- */
- public abstract float coord(int overlap, int maxOverlap);
-
- /**
- * Calculate a scoring factor based on the data in the payload. Overriding implementations
- * are responsible for interpreting what is in the payload. Lucene makes no assumptions about
- * what is in the byte array.
- *
- * The default implementation returns 1.
- *
- * @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
- * @param fieldName The fieldName of the term this payload belongs to
- * @param start The start position of the payload
- * @param end The end position of the payload
- * @param payload The payload byte array to be scored
- * @param offset The offset into the payload array
- * @param length The length in the array
- * @return An implementation dependent float to be used as a scoring factor
- *
- */
- public float scorePayload(int docId, String fieldName, int start, int end, byte [] payload, int offset, int length)
- {
- return 1;
- }
-
-}